Further Development in the Global Resolution of Convex Programs with Complementarity Constraints
ILLINOIS UNIV AT URBANA-CHAMPAIGN
Pagination or Media Count:
Project Summary This collaborative project aims at the study of the global resolution of convex programs with complementarity constraints CPCCs, which form a large subclass of the class of mathematical programs with complementarity constraints MPCCs. Despite the large literature on the local properties of an MPCC, there is a lack of systematic investigation on the computation of a globally optimal solution of these constrained optimization problems, or in the case where such a solution does not exist, on the generation of a certificate demonstrating the solution non-existence. While this is by no means an easy task, the pervasiveness of the CPCC in applications provides an important motivation for the undertaking of this project. Extending our previous study on the subclass of linear programs with linear complementarity constraints LPCCs, which is essentially a linear program with additional complementarity constraints on certain pairs of variables, we have investigated the class of convex quadratic programs with complementarity constraints QPCCs and begun to explore the global resolution of the class of l0 optimization problems. Our work has provided a solid foundation for the design of efficient algorithms for obtaining a solution with provable quality of the class of highly challenging complementarity constrained optimization problems.
- Operations Research