Maximum block improvement and polynomial optimization

Bilian Chen, Simai He, Zhening Li, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

98 Scopus citations

Abstract

In this paper we propose an efficient method for solving the spherically constrained homogeneous polynomial optimization problem. The new approach has the following three main ingredients. First, we establish a block coordinate descent type search method for nonlinear optimization, with the novelty being that we accept only a block update that achieves the maximum improvement, hence the name of our new search method: maximum block improvement (MBI). Convergence of the sequence produced by the MBI method to a stationary point is proved. Second, we establish that maximizing a homogeneous polynomial over a sphere is equivalent to its tensor relaxation problem; thus we can maximize a homogeneous polynomial function over a sphere by its tensor relaxation via the MBI approach. Third, we propose a scheme to reach a KKT point of the polynomial optimization, provided that a stationary solution for the relaxed tensor problem is available. Numerical experiments have shown that our new method works very efficiently: for a majority of the test instances that we have experimented with, the method finds the global optimal solution at a low computational cost.

Original languageEnglish (US)
Pages (from-to)87-107
Number of pages21
JournalSIAM Journal on Optimization
Volume22
Issue number1
DOIs
StatePublished - Jun 4 2012

Keywords

  • Block coordinate descent
  • Polynomial optimization problem
  • Tensor form

Fingerprint Dive into the research topics of 'Maximum block improvement and polynomial optimization'. Together they form a unique fingerprint.

Cite this