New Results on Quadratic Minimization

Yinyu Ye (yinyu-yeuiowa.edu)
Shuzhong Zhang (zhangse.cuhk.edu.hk)

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 where the constraints are two quadratic inequalities. This formulation is known as {\em the extended trust region subproblem}\/ and the computational complexity of this problem is still unknown. We consider several interesting cases related to this problem and show that for those cases the corresponding SDP 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 which will lead to an optimal solution. Combining 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.

Keywords: Quadratic minimization, SDP relaxation, parameterization.

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report Series Number SEEM2001-03 Department of Systems Engineering & Engineering Management The Chinese University of Hong Kong

Download: [Postscript]

Entry Submitted: 05/30/2001
Entry Accepted: 05/30/2001
Entry Last Modified: 05/31/2001

Modify/Update this entry