Tight Semidefinite Programming Relaxations for Polynomial Optimization
summary
Shows that KKT multipliers admit a polynomial multiplier representation whenever the constraint Jacobian is nonsingular (over the complex variety), and uses that to build SDP moment/SOS relaxations with extra algebraic equations (via a polynomial left inverse of the Jacobian). Claims: these relaxations often drop required relaxation degree, give finite convergence under Archimedean quadratic module assumptions, and speed up extraction of global minimizers; tested on linear/quadratic and cubic examples with improved numerical performance.
AI-written summary · about
chapters (9)
- 0:00Introduction to optimization
- 2:24Moment and SOS hierarchy
- 7:54Convergence and challenges
- 10:04KKT conditions and multipliers
- 15:42Constraint non-singularity
- 22:40Numerical performance analysis
- 30:50Advanced optimization examples
- 33:45Summary and conclusions
- 36:06Q&A session
related talks
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
01h 02mDuality 2
45mSum of Squares SDP Relaxations on Random Tensors
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro Factorization
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
32mLocal Statistics, Semidefinite Programming, and Community Detection
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4