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

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.