Optimization Online


An LPCC Approach to Nonconvex Quadratic Programs

Jing Hu(huj***at***rpi.edu)
John E. Mitchell(mitchj***at***rpi.edu)
Jong-Shi Pang(jspang***at***uiuc.edu)

Abstract: Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known a priori to be bounded or unbounded below, can be accomplished in finite time by solving a linear program with linear complementarity constraints, i.e., an LPCC. Alternatively, this task can be divided into two LPCCs: the first one confirms whether or not the QP is bounded below on the feasible set and computes a feasible ray on which the QP is unbounded if such a ray exists; the second LPCC computes a globally optimal solution if it exists, by identifying a stationary point that yields the best quadratic objective value. In turn, the global resolution of these LPCCs can be accomplished by a parameter-free, mixed integer-programming based, finitely terminating algorithm developed recently by the authors, which can be enhanced in this context by a new kind of valid cuts derived from the second-order conditions of the QP and by exploiting the special structure of the LPCCs. Throughout, our treatment makes no boundedness assumption of the QP; this is a significant departure from much of the existing literature which consistently employs the boundedness of the feasible set as a blanket assumption. The general theory is illustrated by 3 classes of indefinite problems: QPs with simple upper and lower bounds (existence of optimal solutions is guaranteed); same QPs with an additional inequality constraint (extending the case of simple bound constraints); and nonnegatively constrained copositive QPs (no guarantee of the existence of an optimal solution).

Keywords: Quadratic programming, Benders decomposition, linear programs with complementarity constraints, LPECs.

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Complementarity and Variational Inequalities

Citation: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180. May 29. 2008. http://www.rpi.edu/~mitchj/papers/QP_unbdd.html

Download: [PDF]

Entry Submitted: 05/29/2008
Entry Accepted: 05/29/2008
Entry Last Modified: 05/29/2008

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 Programming Society