2014/06/27 by Liu, Minghui, Pataki, Gabor · 1 citation
#49N15 #52A40 (Secondary) #90C46 (Primary) #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1406.7274
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 semidefinite system of the form Ai*X = bi (i=1,...,m) (P) X >= 0 using only elementary row operations, and rotations. When (P) is infeasible, the reformulated system is trivially infeasible. When (P) is feasible, the reformulated system has strong duality with its Lagrange dual for all objective functions. As a corollary, we obtain algorithms to generate the constraints of \em all infeasible SDPs and the constraints of \em all feasible SDPs with a fixed rank maximal solution.