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

Polynomial optimization problems (POP) is the problem of minimizing a polynomial objective function over the set defined by polynomial equalities and/or inequalities. It is well-known that finding the global value of POP is NP-hard. Lasserre and Parrilo independently proposed SDP approaches to find a tighter lower bound of the global value of POP. However, the resulting SDP relaxation problems often become degenerate so that it is difficult to solve it correctly. In this talk, we give such two examples. In the first example, 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 the SDP solvers are given. In the second example, all the resulting SDP relaxation problems for a two-dimensional POP with compact and full-dimensional feasible region are infeasible. However, we observe that SDP solvers return the optimal value of the POP and do not detect the infeasibility. These results give a warning to users of the SDP relaxation method for POPs to be careful in believing the results of the SDP solvers.