Optimization Online


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

Hayato Waki(waki***at***cs.uec.ac.jp)

Abstract: 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".

Keywords: Semidefinite programming, weakly infeasible, semidefinite programming relaxation

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: To appear in Optimization Letters

Download: [PDF]

Entry Submitted: 07/03/2011
Entry Accepted: 07/05/2011
Entry Last Modified: 07/03/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society