Semidefinite Representation for Convex Hulls of Real Algebraic Curves

DOI10.1137/17M1115113zbMATH Open1390.14173arXiv1208.3865MaRDI QIDQ4603028FDOQ4603028

Authors: Claus Scheiderer 

Publication date: 14 February 2018

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Abstract: We show that the closed convex hull of any one-dimensional semi-algebraic subset of R^n has a semidefinite representation, meaning that it can be written as a linear projection of the solution set of some linear matrix inequality. This is proved by an application of the moment relaxation method. Given a nonsingular affine real algebraic curve C and a compact semialgebraic subset K of its R-points, the preordering P(K) of all regular functions on C that are nonnegative on K is known to be finitely generated. We prove that P(K) is stable, meaning that uniform degree bounds exist for weighted sum of squares representations of elements of P(K). We also extend this last result to the case where K is only virtually compact. The main technical tool for the proof of stability is the archimedean local-global principle. As a consequence of our results we prove that every convex semialgebraic subset of R^2 has a semidefinite representation.

Full work available at URL: https://arxiv.org/abs/1208.3865

Recommendations

• Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
• LMI representations of the convex hulls of quadratic basic semialgebraic sets
• First order conditions for semidefinite representations of convex sets defined by rational or singular polynomials
• Semidefinite representability
• Convex sets with semidefinite representation
• Convex hulls of quadratically parameterized sets with quadratic constraints
• Semidefinite Approximation of Closed Convex Set
• Semidefinite Representation of Convex Sets and Convex Hulls
• Certificates of convexity for basic semi-algebraic sets
• Optimization of Polynomials on Compact Semialgebraic Sets

zbMATH Keywords

convex hullLMIsemialgebraic setssemidefinite representationmoment relaxationHelton-Nie conjecturespectrahedral shadow

Mathematics Subject Classification ID

Semidefinite programming (90C22) Real algebraic sets (14P05)

Cites Work

• Convex Analysis
• Title not available (Why is that?)
• The \(K\)-moment problem for compact semi-algebraic sets
• Moments, positive polynomials and their applications
• Positivity and sums of squares: a guide to recent results
• Title not available (Why is that?)
• Semidefinite Optimization and Convex Algebraic Geometry
• Sums of squares on real algebraic curves
• Title not available (Why is that?)
• Positive polynomials and sums of squares
• On the convex hull of a space curve
• The convex hull of a variety
• Advances in convex optimization: conic programming
• Generic Spectrahedral Shadows
• Theta bodies for polynomial ideals
• Sums of squares on real algebraic surfaces
• Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
• Sums of squares of regular functions on real algebraic varieties
• Non-existence of degree bounds for weighted sums of squares representations
• The moment problem for non-compact semialgebraic sets
• Convex sets with semidefinite representation
• On semidefinite representations of non-closed sets
• Semidefinite representation of convex hulls of rational varieties
• Convex hulls of curves of genus one
• Weighted sums of squares in local rings and their completions. I
• Spectrahedral shadows

Cited In (32)

• The tropical analogue of the Helton-Nie conjecture is true
• A polyhedral approximation algorithm for recession cones of spectrahedral shadows
• Semi-definite programming and quantum information
• Matrix convex hulls of free semialgebraic sets
• The geometry of discotopes
• Spectrahedral approximations of convex hulls of algebraic sets
• On the exactness of Lasserre relaxations for compact convex basic closed semialgebraic sets
• Spectrahedral representations of plane hyperbolic curves
• Algebraic boundaries of \(\mathrm{SO}(2)\)-orbitopes
• Semidefinite Representation of Convex Sets and Convex Hulls
• On the realization problem of real algebraic plane curves as Hessian curves
• Title not available (Why is that?)
• Linear optimization with cones of moments and nonnegative polynomials
• Positive semidefinite rank
• Kippenhahn's construction revisited
• Sharp degree bounds for sum-of-squares certificates on projective curves
• Constraint satisfaction problems over numeric domains
• Convex Algebraic Geometry of Curvature Operators
• Hyperbolic secant varieties of \(M\)-curves
• LMI representations of convex semialgebraic sets and determinantal representations of algebraic hypersurfaces: past, present, and future
• Degree Bounds for Putinar’s Positivstellensatz on the Hypercube
• Semidefinite representation of convex hulls of rational varieties
• Exact algorithms for linear matrix inequalities
• Second-Order Cone Representation for Convex Sets in the Plane
• Convex hulls of curves of genus one
• The multidimensional truncated moment problem: the moment cone
• Semidefinite representation of convex sets
• Convex hulls of quadratically parameterized sets with quadratic constraints
• Universality and optimality in the information-disturbance tradeoff
• The real spectrum of a noncommutative ring and the Artin-Lang homomorphism theorem
• Semi-definite representations for sets of cubics on the two-dimensional sphere
• Spectrahedral shadows

This page was built for publication: Semidefinite Representation for Convex Hulls of Real Algebraic Curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603028)