Sparsity in Polynomial Optimization
Presenter
January 20, 2007
Keywords:
- Sums of squares
MSC:
- 11E25
Abstract
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.