Back to Search
Start Over
MAXIMUM BLOCK IMPROVEMENT AND POLYNOMIAL OPTIMIZATION.
- Source :
- SIAM Journal on Optimization; 2012, Vol. 22 Issue 1, p87-107, 21p
- Publication Year :
- 2012
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- POLYNOMIALS
MATHEMATICAL optimization
ALGEBRA
ALGORITHMS
MATHEMATICAL inequalities
Subjects
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 22
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 76599885
- Full Text :
- https://doi.org/10.1137/110834524