An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone

A weakly infeasible semidefinite program (SDP) has no feasible solution, but it has nearly feasible solutions that approximate the constraint set to arbitrary precision. These SDPs are ill-posed and numerically often unsolvable. They are also closely related to ``bad" linear projections that map the cone of positive semidefinite matrices to a nonclosed set. We describe a simple echelon form of weakly infeasible SDPs with the following properties: it is obtained by elementary row operations and congruence transformations; it makes weak infeasibility evident; and using it we can construct any weakly infeasible SDP or bad linear projection by an elementary combinatorial algorithm. We also prove that some SDPs in the literature are in our echelon form, for example, the SDP from the sum-of-squares relaxation of minimizing the famous Motzkin polynomial.

Article

Download

View An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone