Spring 2019

Combinatorial Characterizations in Semidefinite Programming Duality: How Elementary Row Operations Help

Wednesday, May 1, 2019 11:45 am12:30 pm PDT

Add to Calendar


Gabor Pataki (University of North Carolina at Chapel Hill)

Semidefinite programs (SDPs) are some of the most useful and versatile optimization problems to emerge in the last few decades. However, their duality theory is not as clearcut as that of linear programming: they may not attain their optimal value, and their optimal value may differ from that of their dual. Such SDPs are often difficult, or impossible to solve.

I will show that many of these pathologies can be understood using a surprisingly simple tool: we can transform SDPs to normal forms that makes the pathology trivial to recognize. The transformations mostly use elementary row operations coming from Gaussian elimination. The normal forms have computational uses, for example, in several cases they help us recognize infeasibility. The talk relies only on basic  linear algebra, and some elementary convex analysis. Some parts of this work are joint with Minghui Liu and some others with Yuzixuan Zhu and Quoc Tran-Dinh.