"Combinatorial certificates in SDP duality: how elementary row operations help"Pataki, GaborSemidefinite programs (SDPs) are some of the most useful and versatile optimization problems of the last three decades. They generalizes linear programs, and appear in combinatorial optimization, polynomial optimization, and many other areas. To solve SDPs, we rely on a natural dual problem. However, SDP duality is often messy: feasible SDPs may not attain their optimal value and/or their optimal value may differ from that of their dual. Infeasible SDPs may lack a Farkas lemma certificate. Such odd SDPs are often difficult, or impossible to solve or to verify their infeasibility. I will show that many of these pathologies can be understood using some basic convex analysis, and tools from elementary linear algebra. In particular, we can transform SDPs to normal forms that make the odd behaviors easy to recognize; the transformations mostly use elementary row operations inherited from Gaussian elimination. The normal forms provide combinatorial certificates of the odd behaviors, allow us to generate any SDP with prescribed behavior, and have computational uses; for example, in several cases they help us recognize infeasibility. I will review some of my work and work of others, e.g. Ramana's dual, which 30 years after its discovery still gives the best complexity result on SDP feasibility. Some of this work is joint with students Minghui Liu, Alex Touzov, and Yuzixuan Zhu, and colleague Quoc Tran-Dinh. |
« back