Source-linked AI summary
Optimality Conditions and Finite Convergence of Lasserre's Hierarchy
Jiawang Nie
TL;DR
The paper studies why Lasserre’s hierarchy often has finite convergence despite only asymptotic guarantees in general. It relates finite convergence to constraint qualification, strict complementarity, and second order sufficiency, using Marshall’s boundary hessian theorem and elimination theory. The hierarchy has finite convergence under these conditions at every global minimizer, and the conditions hold generically on a Zariski open set of input polynomials.
Problem
The paper addresses the discrepancy between theoretically guaranteed asymptotic convergence and frequently observed finite convergence of Lasserre’s hierarchy.
Method
The paper connects optimality conditions to Marshall’s boundary hessian condition and uses elimination theory to establish genericity through coefficient polynomials.
Results
Under the archimedean condition, finite convergence follows when constraint qualification, strict complementarity, and second order sufficiency hold at every global minimizer.
Takeaways & Limitations
These optimality conditions hold at every local minimizer on a Zariski open set of input polynomials, implying generic finite convergence.
Takeaways & Limitations
Finite convergence can fail for specially constructed problems, including minimizing the Motzkin polynomial over the unit ball and problems with feasible-set dimension at least three.
Abstract
from arXiv · showhide
Lasserre's hierarchy is a sequence of semidefinite relaxations for solving polynomial optimization problems globally. This paper studies the relationship between optimality conditions in nonlinear programming theory and finite convergence of Lasserre's hierarchy. Our main results are: i) Lasserre's hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean assumption; the proof uses a result of Marshall on boundary hessian conditions. ii) these optimality conditions are all satisfied at every local minimizer if a finite set of polynomials, which are in the coefficients of input polynomials, do not vanish at the input data (i.e., they hold in a Zariski open set). This implies that Lasserre's hierarchy has finite convergence generically.
1. Introduction
The paper connects nonlinear-programming optimality conditions with finite convergence of Lasserre’s hierarchy, explaining why finite convergence is often observed despite only asymptotic theoretical guarantees. Under archimedeanness, finite convergence follows from conditions at global minimizers, and these conditions hold generically.
- Lasserre’s hierarchy: Lasserre’s hierarchy uses SOS relaxations equivalent to semidefinite programs to globally solve polynomial optimization problems.At relaxation order k, it maximizes γ subject to f − γ belonging to a truncated ideal plus truncated quadratic module.
- Lasserre’s hierarchy: Under the archimedean condition, the relaxation values increase toward the global minimum, but finite convergence is not guaranteed in general.The hierarchy has finite convergence when some relaxation value fk equals fmin; otherwise convergence may remain asymptotic.
- Main results: Theorem 1.1 proves finite convergence when constraint qualification, strict complementarity, and second order sufficiency hold at every global minimizer.The result assumes the archimedean condition on the equality and inequality constraint tuples.
- Main results: Theorem 1.2 establishes that these three optimality conditions hold at every local minimizer when specified coefficient polynomials do not vanish.The nonvanishing condition defines a Zariski open set of input polynomials with prescribed degrees.
- Proof strategy: The proofs combine Marshall’s boundary hessian result with elimination theory from computational algebra.Optimality conditions imply the boundary hessian condition, while elimination theory establishes their generic validity.
2. Preliminary
The preliminary section defines the algebraic objects underlying Lasserre’s hierarchy and states Putinar’s representation theorem. It also introduces Marshall’s local and boundary hessian conditions and the resultant-discriminant tools used for genericity arguments.
- Polynomial optimization framework: The ideal generated by equality constraints and the quadratic module generated by inequalities provide the algebraic framework for SOS certificates.Their truncated versions form the finite-order objects used in Lasserre’s hierarchy.
- Polynomial optimization framework: The archimedean condition requires R − ∥x∥2 to belong to the ideal-plus-quadratic-module representation for some R > 0.Under this condition, Putinar’s Positivstellensatz represents every polynomial positive on the feasible set within that representation.
- Boundary hessian conditions: Marshall’s local parameterization condition requires a nonsingular equality variety with local parameters whose initial coordinates describe the active inequalities.The boundary hessian condition then imposes positive linear coefficients on active directions and a positive definite quadratic form on the remaining directions.
- Boundary hessian conditions: If the boundary hessian condition holds at every global minimizer under archimedeanness, Marshall’s theorem yields f − fmin ∈ I(V) + Q(g).When the equality ideal is real, I(V) equals the equality ideal, giving membership in ⟨h⟩ + Q(g).
- Elimination tools: Resultants and discriminants encode whether polynomial systems have nonzero complex common zeros or singular solutions.They are polynomial expressions in input coefficients and extend to nonhomogeneous systems through homogenization.
3. Optimality conditions and Finite Convergence
The paper links standard nonlinear-programming optimality conditions to finite convergence of Lasserre’s hierarchy, proving sufficiency and exhibiting counterexamples when conditions or attainment assumptions fail.
- Sufficiency: Constraint qualification, strict complementarity, and second order sufficiency at a local minimizer imply the boundary hessian condition.The proof uses local coordinates, positive linear terms from strict complementarity, and a positive-definite quadratic form from second order sufficiency.
- Sufficiency: Under these conditions at every global minimizer, Marshall’s result yields a finite-order SOS certificate and finite convergence of Lasserre’s hierarchy.The construction shows some k0 satisfies fk = fmin for all k ≥ k0.
- Practical implication: Optimality conditions are easier to check than the boundary hessian condition because they require elementary linear algebra rather than a local parametrization of the feasible set.This is presented as the practical advantage of the optimality-condition approach.
- Example: The Robinson-form example satisfies all three conditions at its global minimizers, and numerical computation verifies f5 = fmin = 0 modulo round-off errors.The sphere constraint is smooth, strict complementarity is automatic because there are no inequality constraints, and second order sufficiency holds.
- Counterexamples: Each condition is necessary for the stated sufficiency theorem: failures of constraint qualification, strict complementarity, or second order sufficiency can coincide with non-finite convergence.The paper gives separate counterexamples for each failed condition.
- Necessary condition: If the SOS relaxation attains its optimum, failure of the first order optimality condition at a global minimizer rules out finite convergence.Differentiating a finite SOS certificate at the minimizer would force the first order condition to hold.
4. Zariski Openness of Optimality Conditions
The paper establishes generic optimality conditions by encoding critical-point degeneracies as polynomial nonvanishing conditions in the input coefficients. These conditions imply constraint qualification, strict complementarity, and second order sufficiency at every local minimizer.
- Generic critical-point properties: For generic polynomials, the critical-point variety is finite and generically avoids the zero set of an additional polynomial.The construction uses homogenization and polynomial equations for rank conditions to express these exclusions algebraically.
- Generic critical-point properties: A nonzero polynomial D in the input coefficients certifies that the KKT system is nonsingular.If D does not vanish, the homogenized degeneracy system has no nonzero complex solution, so the KKT system is nonsingular.
- Generic critical-point properties: A direct discriminant construction can fail identically because homogenized constraint equations may always admit solutions at infinity.For example, when n > k = 1 and deg(p1) − deg(p0) ≥ 0, the discriminant system has a nonzero solution arising from a complex zero of the homogenized constraint.
- Zariski openness of optimality conditions: Condition 4.3 implies that constraint qualification, strict complementarity, and second order sufficiency hold at every local minimizer.Its components bound active inequalities, ensure constraint qualification, make multipliers nonzero, and imply nonsingularity of H; together these yield the stated optimality conditions.
5. Some discussions
The paper connects nonlinear-programming optimality conditions with finite convergence, while clarifying genericity and several boundaries of the result. It also explains how flat truncation diagnoses convergence and why infinitely many minimizers can obstruct it.
- Main conclusions: Under the archimedean condition, constraint qualification, strict complementarity, and second order sufficiency at every global minimizer imply finite convergence.This establishes the paper’s main connection between classical nonlinear programming conditions and Lasserre’s hierarchy.
- Main conclusions: These optimality conditions hold at every local minimizer when the input coefficients lie in a Zariski open set.The result yields generic finite convergence for polynomial optimization problems satisfying the stated framework.
- Examples and boundaries: A uniform relaxation-order bound for generic finite convergence typically does not exist, and the archimedean condition cannot be removed.For the three-dimensional unit ball, no such uniform bound exists; without archimedeanity, an unconstrained example does not converge.
- Examples and boundaries: The archimedean condition is not itself generically satisfied, since both it and its complement can have nonempty interior among quadratic constraints.The paper illustrates this using perturbations of 1 − x^T x and x^T x − 1.
- Flat truncation: Flat truncation is a rank condition on dual optimizers that suffices to certify finite convergence and is generically necessary.With finitely many global minimizers and the archimedean condition, flat truncation is always satisfied asymptotically.
- Examples and boundaries: When infinitely many global minimizers occur, flat truncation is typically not satisfied; a shifted Motzkin example has fmin = 0 and no finite convergence.Numerically, convergence was not observed for relaxation orders k = 3, 4, ..., 12 in the cited example.
Appendix A. Non-identically Vanishing of R and D
The appendix proves that the polynomial conditions R and D used in the genericity argument are not identically zero. It does so by constructing polynomial systems without nonzero complex solutions and by analyzing nonsingularity of associated Hessian structures.
- Non-identical vanishing of R: The appendix reduces non-identical vanishing of R to showing that a homogeneous polynomial system has no nonzero complex solution for generic input polynomials.The proof separates the cases x0 ≠ 0 and x0 = 0.
- Non-identical vanishing of R: When x0 ≠ 0, scaling x0 = 1 reduces the system, and genericity makes the associated variety finite so a generic q eliminates solutions.This establishes the required example for the first case of the R argument.
- Non-identical vanishing of R: For the x0 = 0 case, generic leading homogeneous parts have nonzero resultant, constraining any putative solution through gradient relations and Euler’s formula.The argument derives a further polynomial system whose generic nonzero solutions are excluded.
- Non-identical vanishing of D: The appendix concludes that suitable polynomial choices make D nonzero, supporting the generic optimality-condition results used in the main paper.The conclusion follows by combining the two cases of the construction.
- Non-identical vanishing of D: For x0 ≠ 0, carefully chosen polynomials yield linearly independent gradients and an invertible diagonal block, reducing nonsingularity to a Hessian condition.The constructed Hessian is nonsingular for generic f0, and continuity extends this property to nearby generic coefficients.