Optimization Seminar: Gabor Pataki
Proving infeasibility in semidefinite programming: how elementary row operations help
Gabor Pataki, University of North Carolina at Chapel Hill
Semidefinite programs (SDPs) — optimization problems with linear constraints and semidefinite matrix variables — are some of the most useful, versatile, and popular optimization problems of the last three decades.
A fundamental, and difficult issue in SDP is proving infeasibility. SDP has a kind of Farkas’ lemma, i.e., a certain alternative system, but this often fails to prove infeasibility.
I will show that we can always prove infeasibility using a surprisingly simple tool: we can transform SDPs to a normal form that makes the infeasibility trivial to recognize. The transformation is very simple, as it mostly uses elementary row operations coming from Gaussian elimination, and it builds on the idea of facial reduction. Thus our normal form of SDPs is analogous to the row echelon form of a linear system of equations.
The normal form has theoretical uses: for example, it gives a simple proof that SDP feasibility is in co-NP in the real number model of computing. The normal form also has computational uses: in many cases it helps to recognize infeasibility in practice.
The talk relies only on knowledge of elementary linear algebra. Most of this work is joint with Minghui Liu. Some other parts are joint work with Yuzixuan Zhu and Quoc Tran-Dinh.