Videos

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.