Semidefinite Representation of Convex Sets

J. William Helton; Jiawang Nie

Source-linked AI summary

Semidefinite Representation of Convex Sets

J. William Helton, Jiawang Nie

arXiv:0705.4068v5May 28, 2007math.OCmath.AG

TL;DR

The paper addresses the open problem of determining when convex semialgebraic sets admit semidefinite representations. It validates moment/SOS-based lifted-LMI constructions under PDLH, sos-concavity, strict quasi-concavity, and curvature-related conditions, concluding SDP representability under these hypotheses. The scope assumes compact convex sets with nonempty interior and relies on defining-polynomial and boundary regularity conditions.

Problem
The paper asks which convex semialgebraic sets are projections of LMI-representable sets, addressing a question described as largely open.
Method
It analyzes moment and SOS lifted-LMI constructions and proves exactness using PDLH, concavity, quasi-concavity, SOS, and curvature-based conditions.
Results
The paper proves SDP representability when defining polynomials satisfy PDLH with concavity, are sos-concave or strictly quasi-concave, or induce sos-convex, poscurv-convex, or extendable poscurv-convex component sets.
Takeaways & Limitations
These sufficient conditions provide criteria for validating finite lifted-LMI representations of convex semialgebraic sets.
Takeaways & Limitations
The results assume S is compact, convex, and has nonempty interior, with additional concavity, curvature, or nonsingularity conditions depending on the theorem.

Abstract

from arXiv · show

Let $S =\{x\in \re^n: g_1(x)\geq 0, ..., g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n: g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper discusses whether $S$ can be represented as the projection of some LMI representable set. Such $S$ is called semidefinite representable or SDP representable. The contributions of this paper: {\bf (i)} Assume $g_i(x)$ are all concave on $S$. If the positive definite Lagrange Hessian (PDLH) condition holds, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function $\ell^Tx$ on $S$ is positive definite at the minimizer, then $S$ is SDP representable. {\bf (ii)} If each $g_i(x)$ is either sos-concave ($-\nabla^2g_i(x)=W(x)^TW(x)$ for some possibly nonsquare matrix polynomial $W(x)$) or strictly quasi-concave on $S$, then $S$ is SDP representable. {\bf (iii)} If each $S_i$ is either sos-convex or poscurv-convex ($S_i$ is compact convex, whose boundary has positive curvature and is nonsingular, i.e. $\nabla g_i(x) \not = 0$ on $\bdS_i \cap S$), then $S$ is SDP representable. This also holds for $S_i$ for which $\bdS_i \cap S$ extends smoothly to the boundary of a poscurv-convex set containing $S$. {\bf (iv)} We give the complexity of Schmüdgen and Putinar's matrix Positivstellensatz, which are critical to the proofs of (i)-(iii).

1. Introduction

The paper asks which convex semialgebraic sets admit LMI lifts and provides sufficient conditions guaranteeing SDP representability. It develops moment/SOS-based constructions and geometric criteria involving curvature, concavity, and nonsingularity.

Motivation: The central question is which convex sets are projections of sets having an LMI representation, equivalently which convex sets are SDP representable.SDP representability requires representing S as the projection onto x-space of an LMI-representable lifted set.
Existing constructions: Infinite-dimensional measure representations are unsuitable as SDP formulations, while moment and SOS truncations yield finite LMIs whose exactness remains to be established.For each degree N, the constructed lifted set projects to a superset of S; the open issue is whether some finite N gives equality.
Main results: The paper gives sufficient conditions under which convex compact semialgebraic sets with nonempty interior are SDP representable, organized through Theorems 1–4.The results progressively weaken their hypotheses, beginning with the PDLH condition and extending to geometric boundary conditions.
Theorem 1: When the defining polynomials are concave on S and satisfy the PDLH condition, S is SDP representable; the PDLH condition is generic under concavity.The PDLH condition requires positive definiteness of the Lagrange Hessian at minimizers of nonzero linear objectives.
Theorem 2: If every defining polynomial is sos-concave or strictly quasi-concave on S, then S is SDP representable.For strictly quasi-concave polynomials, a uniform constant can be chosen in the relevant construction.
Theorems 3–4: If each component set S_i is sos-convex or poscurv-convex, or is extendable poscurv-convex with respect to S, then S is SDP representable.The follow-up result further connects extendable poscurv-convexity with positive curvature and nonsingularity on boundary intersections.

2. The SDP representations when gi(x) are concave on S

The section constructs lifted LMI representations for sets with concave defining polynomials and reduces exactness to bounded-degree SOS representations. Under concavity with SOS or boundary strict-curvature conditions, finite relaxation orders recover S exactly.

Lifted LMI constructions: The lifted moment construction uses finitely many moments and localizing moment matrices indexed by products of the defining polynomials.For N at least the maximum product degree, feasible moments induce a lifted set whose projection contains S and shrinks as N increases.
Lifted LMI constructions: Exactness asks whether a finite relaxation order N satisfies ρN(ŜN) = S, rather than merely containing S.The projection always contains S because moments generated by any x in S are feasible.
Schmüdgen certificates: Schmüdgen’s bounded-degree representation reformulates exactness as uniform SOS certificates for affine polynomials positive on S.The stronger nonnegative representation allows affine polynomials nonnegative on S and implies the bounded-degree representation needed for exactness.
Schmüdgen certificates: Under concavity, if each −∇^2gi is SOS or positive definite on ∂Si ∩ ∂S, S satisfies S-BDNR and equals ρN(ŜN) for sufficiently large N.This is the section’s finite-order exactness theorem for the first lifted construction.
Putinar-Prestel certificates: The Putinar-Prestel construction uses individual defining polynomials and requires the archimedean condition for its bounded-degree certificates.The archimedean condition implies compactness, though compactness alone need not imply it.
Putinar-Prestel certificates: If each −∇^2gi is SOS or positive definite on ∂Si ∩ ∂S, then PP-BDNR holds and the second lifted projection equals S for sufficiently large N.The theorem assumes concavity on S, nonempty interior, and the archimedean condition.

3. The SDP representation when gi(x) are sos-concave

This section gives an explicit lifted LMI for sos-concave defining polynomials and proves its exactness using separating hyperplanes and SOS certificates derived from Hessians. The resulting projection equals S without requiring compactness.

Construction and exactness: The section studies Lasserre- and Parrilo-type lifted LMIs and asks when their projection onto x-space equals S.The construction assumes the defining polynomials are concave, while the main sufficient condition strengthens this to sos-concavity.
Construction and exactness: Exactness can be certified by showing that every supporting polynomial fℓ is SOS; otherwise the lifted LMI may strictly contain S.Checking SOS is tractable for a fixed polynomial through an SDP feasibility problem, but not directly for uncountably many ℓ.
SOS integration lemma: A double integral of an SOS matrix polynomial’s Hessian remains SOS, providing the key mechanism for converting Hessian information into polynomial SOS certificates.The scalar case yields the corresponding result for polynomial Hessians.
SOS integration lemma: If p(u) = 0, ∇p(u) = 0, and ∇^2p is SOS, then p itself is SOS.The proof integrates the Hessian twice along the segment from u to x.
Main theorem: If every gi is sos-concave, the explicit LMI (3.1) is a lifted LMI representation for S.The proof uses a separating linear functional, Lagrange multipliers, and the SOS Hessian lemma to contradict any projected point outside S.
Main theorem: The sos-concavity condition can be checked numerically by testing whether −∇^2gi(x) is an SOS matrix polynomial through SDP feasibility software.The paper notes that compactness is unnecessary under the sos-concavity assumption.

4. Concave defining functions for poscurv-convex sets

The section constructs new defining polynomials with negative definite Hessians from strictly quasi-concave functions and positively curved boundaries. These constructions support the paper’s semidefinite-representation results.

4.2. Convex sets with boundary having positive curvature: Positive curvature is stronger than strict convexity because it requires a strictly positive second fundamental form.The section distinguishes these geometric conditions and notes that strictly convex boundaries may have zero curvature at isolated points.
4.1. Convex sets defined by quasi-concave functions: Strict quasi-concavity can be converted into a defining polynomial with a negative definite Hessian on S.For each gi, a positive polynomial hi yields pi=gi hi, which is concave with negative definite Hessian on S.
4.1. Convex sets defined by quasi-concave functions: The modified Hessian becomes positive definite after adding a sufficiently large gradient outer-product term.Strict quasi-concavity gives positivity on tangent spaces, while a large coefficient controls the remaining direction.
4.1. Convex sets defined by quasi-concave functions: Strict convexity alone does not suffice for the modified-Hessian construction.A strictly convex counterexample remains unable to produce a positive semidefinite modified Hessian near the origin, regardless of M.
4.2. Convex sets with boundary having positive curvature: A poscurv-convex set admits a smooth defining function with negative definite Hessian and nonvanishing boundary gradient.The construction uses the Minkowski function, a concave smooth surrogate, polynomial approximation, and a small quadratic perturbation to enforce strict concavity.
4.2. Convex sets with boundary having positive curvature: For extendable poscurv-convex Si, multiplying gi by a positive polynomial produces a polynomial defining function with negative definite Hessian on S.The same conclusion holds directly for a poscurv-convex set, yielding a strictly concave polynomial positive inside and zero on the boundary.

5. Proofs

The proofs establish exact lifted LMI representations by obtaining uniform-degree Schmüdgen or Putinar representations for separating affine polynomials. Hessian conditions yield the required positivity and degree bounds, which then imply bounded-degree representation properties and exactness.

Proof strategy: Separating hyperplanes reduce exactness of the lifted LMIs to uniform-degree Positivstellensatz representations of affine polynomials nonnegative on S.The separation theorem supplies a linear functional separating any projected point outside S.
Proof strategy: Under concavity and Slater’s condition, minimizers and nonnegative Lagrange multipliers exist for every unit linear objective.The minimizer lies on the boundary, and active constraints have zero values with nonnegative multipliers.
Hessian conditions: SOS Hessians or positive-definite boundary Hessians make the auxiliary matrix polynomials SOS or uniformly positive definite on S.Compactness provides constants M > δ > 0 independent of the objective direction.
Degree bounds: Theorem 20 supplies a finite degree N uniformly over all unit objective vectors, yielding Schmüdgen representations with bounded SOS degrees.The degree is selected using the Positivstellensatz degree bound and constants controlling the auxiliary matrices.
Exactness: The resulting S-BDR or PP-BDR properties certify that the corresponding lifted LMI projection equals S for sufficiently large N.The proof substitutes moment variables into the SOS identities and derives contradictions for projected points outside S.

6. Appendix: The complexity of the matrix Positivstellensatz

The appendix develops degree-bounded matrix Positivstellensatz results for positive definite matrix polynomials on compact basic semialgebraic sets. These bounds support the finite-degree SOS certificates used in the SDP representation proofs.

Objective: The appendix seeks degree bounds for Schmüdgen and Putinar representations of positive definite matrix polynomials in the defining polynomials of S.The matrix versions use symmetric SOS matrix-polynomial multipliers.
Normalization: The constructions assume compactness and normalize the defining polynomials through coordinate scaling and auxiliary constraints.The appendix embeds S within a box and introduces scaled polynomials for the degree analysis.
Representations: Schmüdgen’s matrix Positivstellensatz represents F(x) using SOS matrix polynomials multiplied by products of the defining polynomials.Putinar’s form uses an additive representation under the archimedean condition.

Define new polynomials

The appendix constructs auxiliary homogeneous and matrix polynomials to transfer positivity on S into a form suitable for quantitative Positivstellensatz bounds. These constructions produce finite-degree SOS matrix certificates under compactness or archimedeanness.

Schmüdgen bounds: Theorem 27 gives a degree bound for representing matrix polynomials satisfying F(x) ⪰ δI on compact S, with constants depending on the defining polynomials.The proof combines homogeneous positivity arguments with Schmüdgen-type certificates for auxiliary constraints.
Auxiliary construction: A homomorphism maps auxiliary variables back to the original x-coordinates, with its kernel described by finitely many polynomial generators.The zero set of these generators identifies the embedded copy of S.
Putinar bounds: Under the archimedean condition, Theorem 29 represents F(x) as G0(x) + g1(x)G1(x) + ··· + gm(x)Gm(x), with SOS matrix polynomials and bounded degrees.This is the matrix Putinar representation used in the paper’s lifted-LMI arguments.

7. Conclusions

The paper supplies sufficient conditions for SDP representability of compact convex basic semialgebraic sets, approaching geometric necessity through SOS and positive-curvature hypotheses. Its proofs rely on uniform-degree Positivstellensatz certificates, while those bounds remain dependent on the objective in related approaches.

Main conclusions: For convex, compact S with nonempty interior, SDP representability follows under PDLH with concave defining polynomials or under sos-convex or extendable poscurv-convex constraints.The paper identifies these as additional sufficient conditions beyond convexity and semialgebraicity.
Proof mechanism: The proof strategy controls Schmüdgen or Putinar representations of affine separating polynomials using Hessians and degree bounds independent of the objective direction.This uniformity is what validates finite lifted LMIs.
Open direction: Representations obtained through Marshall and Scheiderer may have degrees depending on ℓ, so they do not provide the uniform degree bound used here.The authors identify objective-independent degree control as an open direction for future work.
Geometric scope: The geometric hypotheses are close to necessary boundary behavior because convex boundaries have nonnegative curvature, while the paper requires positive curvature or SOS structure.The follow-up result cited by the authors weakens extendability to positive curvature and nonsingularity on the relevant boundary.