Duality 1

on YouTube ↗01h 01m

" summary

Develops conic duality and Slater regularity for cone programs, shows the PSD and second‑order cones are self‑dual, and derives complementary slackness that forces the product of primal and dual PSD matrices to be the zero matrix. Builds a rank‑one PSD encoding of independent sets and formulates Lovász’s theta as an SDP that upper bounds alpha(G); proves Lovász theta equals alpha on perfect graphs and notes the ellipsoid method yields polynomial‑time computation. Theta body sits strictly between stab(G) and clique‑cover relaxations unless G is perfect.

AI-written summary · about

" chapters (13)

1. 0:00Introduction to duality
2. 2:55Discrete vs continuous problems
3. 5:18The concept of relaxation
4. 7:40Properties of relaxations
5. 12:50Basics of duality
6. 14:30Conic optimization
7. 19:35Dual cones and SDP
8. 25:55Weak and strong duality
9. 28:50Strong duality proof
10. 37:38Complementary slackness
11. 43:14Lovasz theta function
12. 49:42Perfect graphs
13. 55:10Sandwich theorem and concluding

" related talks

• 54mPrimal-Dual Algorithms for Hyperbolic Programming ProblemsLevent Tuncel · Hyperbolic Polynomials and Hyperbolic Programming
• 44mCombinatorial Characterizations in Semidefinite Programming Duality: ...Gabor Pataki · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 11m(Hidden) Symmetries of Computational Problems (continued)Michael Walter, Avi Wigderson · Geometric Methods in Optimization and Sampling Boot Camp
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 01h 12mGeodesic Convexity and OptimizationSuvrit Sra · Geometric Methods in Optimization and Sampling Boot Camp
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 44mStructured Sparsity-Inducing Norms Through Submodular FunctionsFrancis Bach · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 40mExponential Lower Bounds on Spectrahedral Representations of Hyperbolicity ConesNick Ryder · Hyperbolic Polynomials and Hyperbolic Programming