An LPCC Approach to Nonconvex Quadratic Programs
Download the paper,
in pdf.
Authors:
Jing Hu
huj at rpi.edu
Department of
Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
John E. Mitchell
mitchj at rpi.edu
Department of
Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Jong-Shi
Pang
jspang at uiuc.edu
Industrial and Enterprise Systems
Engineering,
University of Illinois at Urbana-Champaign,
117 Transportation Bldg., 104 S. Mathews Ave., Urbana, IL 61801.
May 29, 2008.
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.
Download the paper,
in pdf.
Return to my list of papers.