How to generate weakly infeasible semidefinite programs via Lasserre’s relaxations for polynomial optimization

Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre's semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test whether a semidefinite solver can detect weak infeasibility. In addition, in this note, we generate weakly infeasible semidefinite programs from an instance of polynomial optimization with nonempty feasible region and solve them by semidefinite solvers. Although all semidefinite programming relaxation problems are infeasible, we observe that semidefinite solvers do not detect the infeasibility and that values returned by semidefinite solvers are equal to the optimal value of the instance due to numerical round-off errors. The original title was "Note on the weak infeasibility of Lasserre's semidefinite programming relaxation problems for a polynomial optimization problem".

Citation

To appear in Optimization Letters

Article

Download

View How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization