When: October 30, 2015, 12:00 PM
Location: 1163 Mechanical Engineering Building
Contact: 608-316-4401, email@example.com
Combinatorial Characterizations in Semidefinite Programming Duality
Semidefinite programs (SDPs) generalize linear programs by replacing the nonnegativity constraint by membership in the set of positive semidefinite matrices. SDPs are remarkably broadly applicable in areas as diverse as engineering and combinatorial optimization.
Duality plays a central role in SDP, just like in linear programming. However, in SDP, unlike in LP, pathological phenomena occur: nonattainment of the optimal value; positive duality gaps between the primal and dual problems; and the failure of Farkas’ lemma to prove infeasibility.
We provide combinatorial characterizations for several fundamental problems in SDP. The first is infeasibility: we give an analogy of the row echelon form of a linear system of equations, and show that a semidefinite system is infeasible exactly if by elementary operations we can bring it to a format which is trivially so. The second is the pathological behavior of feasible systems: we give an “excluded minor” type characterization of such systems, and again use elementary operations to bring them to a form, where the pathological behavior is easily recognizable.
Part of this work is joint with Minghui Liu.
Gabor Pataki received his MS degree from Eotvos Lorand University in Budapest in 1990, and his PhD in Algorithms, Combinatorics and Optimization from Carnegie Mellon University in 1996. He has been at UNC Chapel Hill since 2000. His research area is in convex analysis, convex optimization, mainly in semidefinite programming.