An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone
From MaRDI portal
Publication:6380985
DOI10.1007/S10208-022-09552-0arXiv2110.11437OpenAlexW3211099158MaRDI QIDQ6380985FDOQ6380985
Authors: Gábor Pataki 
Publication date: 21 October 2021
Abstract: A weakly infeasible semidefinite program (SDP) has no feasible solution, but it has approximate solutions whose constraint violation is arbitrarily small. 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: (i) it is obtained by elementary row operations and congruence transformations, (ii) it makes weak infeasibility evident, and (iii) it permits us to construct any weakly infeasible SDP or bad linear projection by an elementary combinatorial algorithm. Based on our echelon form we generate a challenging library of weakly infeasible SDPs. Finally, we show 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.
Full work available at URL: https://doi.org/10.1007/s10208-022-09552-0
Semidefinite programming (90C22) Canonical forms, reductions, classification (15A21) Duality theory (optimization) (49N15) Linear operators and ill-posed problems, regularization (47A52)
Cited In (1)
This page was built for publication: An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380985)
