Optimization Online


A Revisit to Quadratic Programming with One Inequality Quadratic Constraint via Matrix Pencil

Hsia Yong(dearyxia***at***gmail.com)
Lin Gang-Xuan(spybeiman***at***gmail.com)
Sheu Ruey-Lin(rsheu***at***mail.ncku.edu.tw)

Abstract: The quadratic programming over one inequality quadratic constraint (QP1QC) is a very special case of quadratically constrained quadratic programming (QCQP) and attracted much attention since early 1990's. It is now understood that, under the primal Slater condition, (QP1QC) has a tight SDP relaxation (PSDP). The optimal solution to (QP1QC), if exists, can be obtained by a matrix rank one decomposition of the optimal matrixX  to (PSDP). In this paper, we pay a revisit to (QP1QC) by analyzing the associated matrix pencil of two symmetric real matrices AandB, the former matrix of which de nes the quadratic term of the objective function whereas the latter for the constraint. We focus on the \undesired" (QP1QC) problems which are often ignored in typical literature: either there exists no Slater point, or (QP1QC) is unbounded below, or (QP1QC) is bounded below but unattainable. Our analysis is conducted with the help of the matrix pencil, not only for checking whether the undesired cases do happen, but also for an alternative way otherwise to compute the optimal solution in comparison with the usual SDP/rank-one-decomposition procedure.

Keywords: Quadratically constrained quadratic program, matrix pencil, hidden convexity, Slater condition, unattainable SDP, simultaneously diagonalizable with congruence

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization (Theory )


Download: [PDF]

Entry Submitted: 12/02/2013
Entry Accepted: 12/02/2013
Entry Last Modified: 12/02/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society