Global minimization of normal quartic polynomials based on global descent directions

Liqun Qi, Zhong Wan, Yu Fei Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

A normal quartic polynomial is a quartic polynomial whose fourth degree term coefficient tensor is positive definite. Its minimization problem is one of the simplest cases of nonconvex global optimization, and has engineering applications. We call a direction a global descent direction of a function at a point if there is another point with a lower function value along this direction. For a normal quartic polynomial, we present a criterion to find a global descent direction at a noncritical point, a saddle point, or a local maximizer. We give sufficient conditions to judge whether a local minimizer is global and give a method for finding a global descent direction at a local, but not global, minimizer. We also give a formula at a critical point and a method at a noncritical point to find a one-dimensional global minimizer along a global descent direction. Based upon these, we propose a global descent algorithm for finding a global minimizer of a normal quartic polynomial when n = 2. For the case n ≥ 3, we propose an algorithm for finding an ε-global minimizer. At each iteration of a second algorithm, a system of constrained nonlinear equations is solved. Numerical tests show that these two algorithms are promising.
Original languageEnglish
Pages (from-to)275-302
Number of pages28
JournalSIAM Journal on Optimization
Volume15
Issue number1
DOIs
Publication statusPublished - 29 Mar 2005

Keywords

  • Global optimization
  • Normal quartic polynomial
  • Tensor

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software

Cite this