Optimization: Semidefinite Programming & SOS
Optimization: Semidefinite Programming & SOS
💡 Key Takeaways
- Understand the core idea of semidefinite programming and why it’s a powerful tool in convex optimization.
- Learn how sums of squares (SOS) decompose polynomials to certify nonnegativity and how this connects to SDP.
- See how to build Gram matrix representations and formulate SOS problems as linear matrix inequalities (LMIs).
- Explore typical university-level optimization problems that use SDP and SOS, including basic duality concepts and solution approaches.
❓ Frequently Asked Questions
What is semidefinite programming?
A convex optimization framework where you minimize a linear objective over symmetric matrices constrained to be positive semidefinite, often with linear equality constraints.
What is a sum-of-squares (SOS) decomposition?
A polynomial is SOS if it can be written as a sum of squares of other polynomials; this certifies nonnegativity and can be checked via semidefinite programming using a Gram matrix.
How are SDP and SOS related?
Many SOS questions can be reformulated as semidefinite programs; an SOS decomposition corresponds to a positive semidefinite Gram matrix, allowing SDP solvers to verify it.
How is a typical SDP problem formulated?
Minimize c^T x subject to F0 + sum_i x_i Fi is positive semidefinite, together with any linear equality constraints; F0 and Fi are given symmetric matrices.