Collaborative Research: Binary Constrained Convex Quadratic Programs with Complementarity Constraints and Extensions

Project: Research project

Project Details


Overview. Mathematical programs with complementarity constraints (MPCCs) form a
broad class of constrained optimization problems wherein some of the constraints are de-
scribed by the disjunctive condition of complementary slackness, or simply complementar-
ity. Motivated by an increasing number of applied problems that can be formulated as
MPCCs where some of the decision variables are constrained to be binary, this proposal
takes up an in-depth study of such binary-constrained, complementarity-constrained opti-
mization problems. Built on the recent advances in the global resolution of linear programs
with linear complementarity constraints (LPCCs) and their extensions to problems with
convex quadratic objective functions (QPCCs), both with continuous variables only, this
investigation will initially focus on the binary-constrained (BC-)L/QPCCs, with the goal
of developing e�cient solution methods for the global resolution of this important class of
constrained optimization problems that possess both discrete and continuous characteristics.
Intellectual Merits. It is well known that MPCCs in continuous variables already con-
stitute a highly intellectually challenging class of constrained optimization problems, whose
global resolution has only recently received increasing attention in the optimization litera-
ture. Adding binary restrictions to some of the variables adds signi�cant value to this class
of problems. The intellectual merits of the proposed research extend beyond existing opti-
mization research. In particular, computational advances from diverse areas of optimization
need to be integrated in order to e�ectively handle the discrete and continuous features of
the BC-MPCCs. The integration of such subdomains of optimization and the expected the-
oretical advances in understanding the intrinsic properties of this new class of optimization
problems form the intellectual crux of the proposed project.
Broader Impact. Binary and complementarity constrained optimization problems arise
from many applications in complex engineering and economic systems involving hierarchical
decision making with logical constraints. Advances in our research will have signi�cant
impacts in understanding such problems as optimal plant locations in competitive markets,
discrete-choice portfolio investments under risk, classi�cation problems in medical decision
making, and compressed sensing in signal and image processing. The education and training
of graduate students, the dissemination of publications, and the presentation of results at
conferences and workshops all add to the broader impacts of the project.
Effective start/end date8/15/137/31/17


  • National Science Foundation (CMMI-1334639)


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.