In semidefinite programming (SDP), unlike in linear programming, Farkas' lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP by an elementary approach: we reformulate any equality constrained semidefinite system using only elementary row operations, and rotations. When the system is infeasible, the infeasibility of the reformulated system is trivial to verify by inspection. \\ For feasible systems we obtain a similar reformulation, which trivially has strong duality with its Lagrange dual for all objective functions. As a corollary, we obtain algorithms to systematically generate the data of all infeasible semidefinite programs (SDPs), and the data of all feasible SDPs whose maximum rank feasible solution has a prescribed rank.
Article
View Exact duality in semidefinite programming based on elementary reformulations