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.