  


An LPCC Approach to Nonconvex Quadratic Programs
Jing Hu(hujrpi.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 parameterfree, mixed integerprogramming 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 secondorder 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  