Tutte seminar - Hayato Waki

SemiDefinite Programming Relaxation for Polynomial Optimization Problems

Abstract:

Polynomial Optimization Problem (POP) is the problem of minimizing a polynomial objective function over a set defined by finite many polynomial equalities and/or inequalities. Lasserre proposed an approach via SemiDefinite Programming (SDP) to find a tighter lower bound or the exact optimal value of a given POP. However, it is known that the resulting SDP problems by Lasserre's approach often become large-scale and/or highly degenerate. As a result, we need to overcome these difficulties to find a lower bound or the exact optimal value of a given POP. 

This talk consists of two parts. In part I, we deal with POPs with a sparse structure. For such POPs, we propose a sparse SDP relaxation. We present some numerical results and observe that the resulting SDP relaxation problems become small enough to be solved effectively. In part II, we show that for simple POPs, the 'optimal' values of SDP relaxation problems reported by the standard SDP solvers converge to the optimal values of those POPs, while the true optimal values of SDP relaxation problems are strictly and significantly less than those values. One of this reason is that the SDP relaxation problems are highly degenerate. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly. 
This is joint work with Masakazu Kojima, Sunyoung Kim, Masakazu Muramatsu and Maho Nakata.