New results on quadratic minimization

Yinyu Ye, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

196 Scopus citations

Abstract

In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case in which the constraints are two quadratic inequalities. This formulation is termed the extended trust region subproblem in this paper, to distinguish it from the ordinary trust region subproblem, in which the constraint is a single ellipsoid. The computational complexity of the extended trust region subproblem in general is still unknown. In this paper we consider several interesting cases related to this problem and show that for those cases the corresponding semidefinite programming relaxation admits no gap with the true optimal value, and consequently we obtain polynomial-time procedures for solving those special cases of quadratic optimization. For the extended trust region subproblem itself, we introduce a parameterized problem and prove the existence of a trajectory that will lead to an optimal solution. Combining this with a result obtained in the first part of the paper, we propose a polynomial-time solution procedure for the extended trust region subproblem arising from solving nonlinear programs with a single equality constraint.

Original languageEnglish (US)
Pages (from-to)245-267
Number of pages23
JournalSIAM Journal on Optimization
Volume14
Issue number1
DOIs
StatePublished - 2004

Keywords

  • Parameterization
  • Quadratic minimization
  • SDP relaxation

Fingerprint

Dive into the research topics of 'New results on quadratic minimization'. Together they form a unique fingerprint.

Cite this