Convexity in semi-algebraic geometry and polynomial optimization

Motivation.

• The paper studies whether the SDP moment approach simplifies or converges better on convex polynomial optimization problems.It presents convexity recognition as a desirable feature because convex problems are, in principle, easier to solve.Source: Motivation · p. 1
• It investigates semidefinite representations of convex basic semi-algebraic sets and certificates of convexity when their defining polynomials are not convex.The paper also considers relatively simple, explicit representations enabled by convexity.Source: Motivation · p. 1
• It asks whether Jensen’s inequality can extend, for a certain class of convex polynomials, to linear functionals beyond probability measures.Source: Motivation · p. 1

Background.

• The SDP moment hierarchy gives a monotone sequence of relaxation values converging to the global optimum.Source: Background · p. 2
• The r-th SDP relaxation typically has O(n2r) variables and semidefinite matrices of O(nr) sizes, motivating a method that recognizes easier convex problems.The passage contrasts this growth with convex optimization problems that can be solved efficiently.Source: Background · p. 2
• Semidefinite representability asks whether a set is a projection of one defined by linear matrix inequalities.Source: Background · p. 2
• For basic semi-algebraic sets, prior sufficient conditions yield semidefinite representations, but a numerical algebraic certificate of convexity was not known to the authors.The certificate sought would imply convexity and be checkable numerically without infinitely many tests.Source: Background · pp. 2–3
• The paper also asks whether Jensen’s inequality for convex functions and probability measures extends to a broader class of linear functionals for certain convex polynomials.Source: Background · p. 3

Contribution

• The paper recalls density of convex SOS in nonnegative convex polynomials and a convex Positivstellensatz before analyzing how convexity improves SDP relaxations.The contribution draws on results of Helton and Nie [6].Source: Contribution · p. 3
• If f and −gj are convex and ∇2f is positive definite on K, the SDP-relaxation hierarchy has finite convergence.The contribution states this result under Slater’s condition for K.Source: Contribution · p. 3
• If f and the polynomials −gj are SOS-convex, polynomial optimization reduces to one SDP at a readily available hierarchy index.Slater’s condition is stated for K in the surrounding contribution; SOS-convexity means the Hessians are SOS matrix polynomials.Source: Contribution · p. 3
• For compact K with nonempty interior and a nondegenerate boundary, a new sufficient condition gives a convexity certificate and an explicit semidefinite representation.The condition is almost necessary in the sense that it holds when relaxed by any ǫ > 0; the certificates are obtained numerically and are valid only up to machine precision.Source: Contribution · p. 3
• For SOS-convex polynomials, Jensen’s inequality extends to linear functionals in the dual cone of SOS polynomials with Ly(1) = 1, not only probability measures.Source: Contribution · p. 4

2. Notation, definitions and preliminary results

• R[X] denotes the ring of real polynomials, and Σ2[X] denotes its subset of sums-of-squares polynomials.Source: §2 · p. 4
• Polynomial coefficients are represented in the usual canonical monomial basis, with f identified by its coefficient vector.Source: §2 · p. 4
• The paper uses the l1-norm of the polynomial’s coefficient vector and denotes by Σ2[X]d the SOS polynomials of degree at most 2d.Source: §2 · p. 4
• Uppercase X denotes a polynomial variable, lowercase x a point in Rn, and Ly denotes a linear functional associated with a sequence y.Source: §2 · p. 4, Moment matrix · p. 4

• The moment matrix Md(y) has rows and columns indexed by the canonical monomial basis (X^α).Source: Moment matrix · p. 4
• The localizing matrix Md(g y) is likewise indexed by the canonical monomial basis (X^α).Source: Moment matrix · p. 4
• Q(g) is the quadratic module generated by the polynomials g_j.Source: Putinar Positivstellensatz · p. 4

Putinar Positivstellensatz.

• Assumption 2.1 holds when all g_j are affine or one constraint’s nonnegative level set is compact, and a redundant ball constraint can ensure it.Source: Putinar Positivstellensatz · pp. 4–5
• Under Assumption 2.1, every polynomial strictly positive on K belongs to the quadratic module Q(g).The assumption requires compact K and M − ||X||^2 ∈ Q(g).Source: Putinar Positivstellensatz · pp. 4–5

2.1. A hierarchy of semidefinite relaxations (SDP-relaxations).

• Under Assumption 2.1, the SDP relaxation values increase to the global optimum as the hierarchy order grows.Source: §2.1 · p. 5

2.2. Convexity and SOS-convexity.

• Convexity on a convex set is characterized by the two-point inequality f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y).Source: §2.2 · p. 5
• For twice-differentiable functions on an open convex set, a positive semidefinite Hessian characterizes convexity, while a positive definite Hessian implies strict convexity.Source: §2.2 · p. 5

SOS-convexity.

• A polynomial is SOS-convex when its Hessian factors as L L^T for a real matrix polynomial L.Source: SOS-convexity · p. 6
• SOS-convexity can be checked numerically by solving a semidefinite program.Source: SOS-convexity · p. 6
• An SOS-convex polynomial f with f(u) = 0 and ∇f(u) = 0 is an SOS polynomial.Source: SOS-convexity · p. 6

2.3. An extension of Jensen’s inequality.

• For SOS-convex f and y with Md(y) ⪰ 0 and y_0 = 1, Ly[f(X)] ≥ f(Ly[X]), even when y is not a probability-measure moment sequence.Source: §2.3 · pp. 6–7
• For convex univariate f and polynomial g, the extension gives Ly[f(g(X))] ≥ f(Ly[g(X)]).Source: §2.3 · p. 7

3.1. A convex Positivstellensatz.

• Under Slater’s condition, Qc(g) ∩ FK is dense in FK, so convex polynomials nonnegative on K can be approximated by certificates from Qc(g).The cited result allows nonnegative polynomials and noncompact K.Source: §3.1 · p. 8
• If f − f* belongs to Qc(g), the simplified SDP relaxation and its dual are exact; with the stated rank condition, the moment solution yields a global minimizer, even when K is noncompact.Source: §3.1 · p. 9

3.2. The SOS-convex case.

• When f and −g_j are SOS-convex and Slater’s condition holds, the simplified SDP and its dual are exact and an optimal solution yields a global minimizer.The theorem assumes the minimum is attained on K.Source: §3.2 · p. 9
• For SOS-convex optimization, the single SDP relaxation (3.3) can solve the problem, and the result does not require compact K.Source: §3.2 · p. 10

3.3. The strictly convex case.

• If f and −g_j are convex and ∇²f is positive definite on K, the full SDP hierarchy has finite convergence, although the simplified relaxation is not guaranteed exact.Source: §3.3 · pp. 10–11
• At some hierarchy order r, the primal and dual SDP values coincide with the global optimum.Source: §3.3 · p. 10

4.1. Algebraic certificate of convexity.

• Equation (4.3) states that ⟨∇gj(y), x − y⟩ ≥ 0 for every x ∈ K and every y ∈ K satisfying gj(y) = 0.Source: §4.1 · p. 13
• Corollary 4.4 encodes these supporting-gradient inequalities as polynomial SOS-preordering identities, providing an algebraic convexity certificate under the boundary nondegeneracy assumption.The identity uses an integer power and polynomials from the preordering generated by the defining inequalities.Source: §4.1 · p. 13
• With Assumption 4.6’s identities at ε = 0, convexity is certified under boundary nondegeneracy, while compact convex sets satisfying the stated assumptions admit corresponding identities for every ε > 0.For fixed degree bounds, checking the identities reduces to a semidefinite program; numerical solutions certify only up to machine precision.Source: §4.1 · p. 14
• Under Assumption 2.1, Slater’s condition, boundary nondegeneracy (∇gj(y) ≠ 0 whenever y ∈ K and gj(y) = 0), and Assumption 4.6, K is convex and Ω in (4.2), with d := max_j d_j, is a semidefinite representation of K.Assumption 4.6 holds if, for every j, −gj is SOS-convex, or −gj is convex on K and −∇²gj ≻ 0 on K ∩ {x : gj(x) = 0}. Theorem 4.8 contains Theorem 4.2 as a special case.Source: §4.1 · pp. 16–17
• For the convex set in Example 2, Assumption 4.6 holds with ρ1 ≈ 10^-11 and max[d1, d2] = 3; Theorem 4.8 gives a semidefinite representation if ρ1 is exactly zero.The defining polynomial g1 is not concave.Source: §4.1 · p. 19
• In practice, minimizing Ly(f) over Ω for a linear polynomial f gives the optimal value f* = min_x∈K f(x) up to ρ1 ≈ -10^-11.The bounds are f* + ρ1 ≤ min{f^T x : (x, y) ∈ Ω} ≤ f*.Source: §4.1 · p. 19

• For SOS-convex or strictly convex polynomial data, basic moment SDP relaxations recognize convexity and achieve finite convergence; K also has an explicit semidefinite representation.Source: §5 · p. 19
• For SOS-convex polynomials, the relaxation’s semidefinite constraint involves only the data-independent Hankel-like moment matrix, and Jensen’s inequality extends to dual-cone linear functionals that need not be probability measures.Source: §5 · p. 19
• A further research question is how large the SOS-convex subclass is within convex polynomials and whether simple sufficient conditions for SOS-convexity can be found.Source: §5 · p. 19