LP/SDP Hierarchies and Sum of Squares Proofs 1

on YouTube ↗01h 01m

" summary

Explains that nonnegativity checks reduce to semidefinite programming by writing a polynomial as a quadratic form over a chosen monomial basis and searching for a positive semidefinite Gram matrix, shows geometric examples (a convex region bounded by an elliptic curve) and a nuclear‑norm SDP lifting, gives the explicit non‑SOS Motzkin sextic as a witness, recalls Hilbert’s 17th problem is resolved affirmatively for rationals, and frames polynomial minimization and parameterized relaxations as tractable SOS→SDP procedures with practical numerical caveats.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 2:44What Is the Geometry of a Semi Definite Problem
3. 4:57Properties
4. 10:42Singular Value Decomposition
5. 10:55Sum of a Singular Value
6. 13:09Extended Formulations
7. 32:07The Cauchy Riemann Identity
8. 44:47So that Causes the Effect of these Dynamic Relationships That Exist between these Monomials Is that There's Not a Unique Matrix in Here That Realizes Is Polynomial but that's Actually a Whole Affine Subspace and Why There's a Whole Defined Surface like I Said before this if You Expand this Expression Let's Actually Do this Whatever You Want To Get and Get X to the Fourth Times Q Zero this Is Not the Interesting Example Y to the Fourth Is Not Interesting either Times Q3 but When You Look at for Instance X Square Y Square What Happens in Here Is I Get One Coefficient That Comes from this Term

" related talks

• 42mTight Semidefinite Programming Relaxations for Polynomial OptimizationJiawang Nie · Hyperbolic Polynomials and Hyperbolic Programming
• 44mCombinatorial Characterizations in Semidefinite Programming Duality: ...Gabor Pataki · Hyperbolic Polynomials and Hyperbolic Programming
• 27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to LearningGeorgina Hall · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 01h 04mFrom Proofs to Algorithms for Machine Learning ProblemsDavid Steurer · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 31mA Positivity-First Approach to Sum-of-Squares Over the HypercubeTim Kunisky · Computational Phase Transitions (Simons Institute, 2020)
• 59mCertificates of Polynomial Non-Negativity via Hyperbolic OptimizationJames Saunderson · Hyperbolic Polynomials and Hyperbolic Programming
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower BoundsAaron Potechin · Rigorous Evidence for Information-Computation Trade-offs