Combinatorial Characterizations in Semidefinite Programming Duality: ...
summary
Proves exact, checkable criteria for SDP pathologies: a system is badly behaved iff there exists a Z (max-rank slack) and V certificate with the stated block-range condition, and infeasibility iff the instance reformulates to an epsilon reformulation with K+1 special rows that yield a two-line contradiction. Uses elementary row-operations + similarity transforms to produce normal forms, gives a polynomial-model corollary that feasibility is in NP∩coNP, builds a simple sieve preprocessor and problem library that often detects infeasible or weakly infeasible SDPs, and characterizes positive duality gaps for m=2.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:31A pair of Semidefinite Programs (SDP)
- 1:21SDP duality
- 4:07Pathology # 2: positive duality gap
- 4:48Terminology
- 6:01Motivation
- 9:31What is missing?
- 11:07Reformulations of
- 12:11Theorem: (Psp) is badly behaved it has a reformulation
- 14:38Example before reformulation
- 14:54Example after reformulation
- 15:20Corollaries
- 17:18Semidefinite System (spectrahedron)
- 17:31Farkas' Lemma for SDP
- 18:53Literature: exact certificates of infeasibility
- 20:36Infeasible example, and proof of infeasibility
- 21:36Reformulation (again!)
- 26:56Proof outline
- 28:54Is this just theory?
- 32:25Application 21 recognizing infeasibility in practice
- 35:44Papers
- 36:13Conclusion
related talks
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
01h 02mDuality 2
32mLocal Statistics, Semidefinite Programming, and Community Detection
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
01h 01mDuality 1
35mLocal Statistics, Semidefinite Programming, and Community Detection II
01h 04mFrom Proofs to Algorithms for Machine Learning Problems