Theta Bodies for Polynomial Ideals
From MaRDI portal
Publication:3058523
DOI10.1137/090746525zbMath1213.90190arXiv0809.3480OpenAlexW3105023213MaRDI QIDQ3058523
Pablo A. Parrilo, João Gouveia, Rekha R. Thomas
Publication date: 3 December 2010
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0809.3480
Semidefinite programming (90C22) Sums of squares and representations by other particular quadratic forms (11E25) Combinatorial optimization (90C27) Real algebraic sets (14P05) Approximation by convex sets (52A27)
Related Items
Lifting for Simplicity: Concise Descriptions of Convex Sets, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Strong nonnegativity and sums of squares on real varieties, On the local stability of semidefinite relaxations, Sums of squares on the hypercube, Certifying the global optimality of quartic minimization over the sphere, Algebraic boundaries of \(\mathrm{SO}(2)\)-orbitopes, Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes, High-dimensional change-point estimation: combining filtering with convex optimization, Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators, A semidefinite approach to the $K_i$-cover problem, Bounds on the number of 2-level polytopes, cones, and configurations, Polytopes of minimum positive semidefinite rank, The convex geometry of linear inverse problems, Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism, Binary scalar products, Deciding Polyhedrality of Spectrahedra, Two Double Poset Polytopes, Toric rings of perfectly matchable subgraph polytopes, A Sum of Squares Characterization of Perfect Graphs, Perfectly contractile graphs and quadratic toric rings, The geometry of SDP-exactness in quadratic optimization, Torsionfreeness for divisor class groups of toric rings of integral polytopes, Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases, An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials, Semidefinite Representation for Convex Hulls of Real Algebraic Curves, Spectrahedral Shadows, Low degree Nullstellensatz certificates for 3-colorability, Many 2-level polytopes from matroids, Symmetric Tensor Nuclear Norms, On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy, Convex hulls of curves of genus one, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, Spectral bounds for the independence ratio and the chromatic number of an operator, Free semidefinite representation of matrix power functions, An Introduction to Compressed Sensing, Handelman's hierarchy for the maximum stable set problem, A note on convex relaxations for the inverse eigenvalue problem, Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation, Enumeration of 2-level polytopes, Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes, Theta rank, levelness, and matroid minors, Four-dimensional polytopes of minimum positive semidefinite rank, Semidefinite approximations of conical hulls of measured sets, An axiomatic duality framework for the theta body and related convex corners, The tropical analogue of the Helton-Nie conjecture is true, Computational and statistical tradeoffs via convex relaxation, Unnamed Item, Lipschitz polytopes of posets and permutation statistics, Matrix convex hulls of free semialgebraic sets, Two Results on the Size of Spectrahedral Descriptions, Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Convex Hulls of Algebraic Sets, Tensor theta norms and low rank recovery, Linear optimization with cones of moments and nonnegative polynomials, On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems, On Vertices and Facets of Combinatorial 2-Level Polytopes, Two-Level Polytopes with a Prescribed Facet, Semidefinite Representations of Noncompact Convex Sets, Completely positive reformulations for polynomial optimization
