Optimization Online


Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization

Hayato Waki(hayato.waki***at***jsb.cs.uec.ac.jp)
Maho Nakata(maho***at***riken.jp)
Masakazu Muramatsu(muramatu***at***cs.uec.ac.jp)

Abstract: We observe that in a simple one-dimensional polynomial optimization problem (POP), the `optimal' values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial evidences for the strange behaviours of SDP solvers are given. This result gives a warning to users of SDP relaxation method for POP to be careful in believing the results of the SDP solvers. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly.

Keywords: Polynomial Optimization, Semidefinite Programming, Numerical Stability

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

Category 2: Optimization Software and Modeling Systems (Other )

Citation: Technical report CS-08-02, Department of Computer Science, The University of Electro-Communications

Download: [PDF]

Entry Submitted: 08/11/2008
Entry Accepted: 08/12/2008
Entry Last Modified: 08/11/2008

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 Programming Society