Exact Duality in Semidefinite Programming Based on Elementary Reformulations

• DOI: 10.1137/140972354
• Publication Date: 2015-07-23T15:03:13Z
• Authors: Minghui Liu; Gábor Pataki
• Keywords: Semidefinite Programming; Semidefinite embedding; Corollary; Duality (order theory); Lemma (botany); Rank (graph theory); Cutting-plane method

In semidefinite programming (SDP), unlike in linear programming, Farkas' lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility SDP by elementary approach: reformulate any equality constrained system using only row operations, and rotations. When a is infeasible, the reformulated trivially infeasible. feasible, has strong duality with its Lagrange dual for all objective functions. As corollary, algorithms generate constraints infeasible SDPs feasible fixed rank maximal solution. Our reformulations can be constructed either direct method, or adapting Waki-Muramatsu facial reduction algorithm. different language, provide standard form spectrahedra, easily verify their emptiness, tight upper bound on solutions.