LP/SDP Hierarchies and Sum of Squares Proofs 2

on YouTube ↗01h 04m

" summary

Real infeasibility certificates appear as an f + g = -1 certificate with f in the ideal of equations and g in the cone generated by inequalities; bounding the syntactic degree turns the search into a degree-bounded SDP that is solvable in practice. Pathologies include rational p that require irrational q or huge bit-complexity dependence, so one works with epsilon-approximations. Over the hypercube a delta-function SOS gives a trivial certificate; practical reductions use symmetry reduction and sparsity or quotient rings to keep the SDP tractable.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 11:05Inequality
3. 14:50Possible constraints
4. 18:20The real notional sense
5. 21:40Infeasible equations
6. 27:25polynomial equations
7. 32:50non polynomial equations
8. 38:00algebraically compact
9. 41:28why is this even true
10. 45:05why do I do this
11. 50:00what matters
12. 51:25semidefinite problems
13. 52:50Explicit equations

" related talks

• 44mCombinatorial Characterizations in Semidefinite Programming Duality: ...Gabor Pataki · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 04mFrom Proofs to Algorithms for Machine Learning ProblemsDavid Steurer · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 39mOptimization over the Hypercube via Sums of Nonnegative Circuit PolynomialsMareike Dressler · Hyperbolic Polynomials and Hyperbolic Programming
• 59mCertificates of Polynomial Non-Negativity via Hyperbolic OptimizationJames Saunderson · Hyperbolic Polynomials and Hyperbolic Programming
• 42mTight Semidefinite Programming Relaxations for Polynomial OptimizationJiawang Nie · Hyperbolic Polynomials and Hyperbolic Programming
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 46mFaster SDP Hierarchy Solvers for Local Rounding AlgorithmsAli Sinop · Semidefinite Optimization, Approximation and Applications 2014
• 31mA Positivity-First Approach to Sum-of-Squares Over the HypercubeTim Kunisky · Computational Phase Transitions (Simons Institute, 2020)