Sparsity in Polynomial Optimization

Saturday, January 20, 2007 - 9:30am - 10:20am
EE/CS 3-180
Masakazu Kojima (Tokyo Institute of Technology)
A polynomial optimization problem (POP) is a problem of minimizing a polynomial
objective function subject to polynomial equalities and inequalities. It is getting
popular to apply the sum of squares (SOS) relaxation to compute global minimum
solutions of a POP. The SOS relaxation problem is reduced to a semidefinite
programming problem (SDP), which we can solve by applying the primal-dual interior-point
method. In this process, exploiting sparsity is essential in solving a large-scale POP. We present
correlative sparsity, a certain structured sparsity of a POP which is characterized
as a sparse Cholesky factorization of an aggregated sparsity pattern matrix of the POP.
With this correlative sparsity, we can apply the sparse SOS relaxation to a large-scale POP, and
we can solve the resulting SDP efficiently by the primal-dual interior-point method.
We also discuss some applications.
MSC Code: