An LPCC Approach to Nonconvex Quadratic Programs
Mathematical
Programming, 133(1-2), pages 243-277, 2012.
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.
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 two
linear programs with linear complementarity constraints, i.e.,
LPCCs. Specifically, this task can be divided into two LPCCs: the
first confirms whether the QP is bounded below on the feasible set
and, if not, computes a feasible ray on which the QP is unbounded;
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 cut 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). We also present
numerical results to support the special cuts obtained due to the
QP connection.
Keywords:
Quadratic programming, logical Benders decomposition,
linear programs with complementarity constraints, LPECs.
Download the paper,
in pdf.
Return to my list of papers.