Collaborative Research: Novel Tighter Relaxations for Complementarity Constraints with Applications to Nonlinear and Bilevel Programming

This collaborative research award provides funding for the development of new and stronger techniques for the solution of optimization problems with complementarity constraints to global optimality. Complementarity problems are pervasive in business, engineering, and economics, since complementarity conditions arise in optimality conditions for nonlinear programs and in models of equilibria. Algorithms for complementarity problems have until recently focused on feasibility problems by employing local optimization techniques. This project focuses on the development of convex relaxations for these problems, with the goal of incorporating them into branch-and-bound algorithms for global optimization. The research is aimed at deriving procedures that (i) exploit the combinatorial and disjunctive structure of complementarity constraints, (ii) focus on relaxations with a provable guarantee of strength, and (iii) target problems in which some of the constraints (besides complementarities) are nonlinear. The benefits of relaxation techniques will be studied relative to mature implementations of global optimization algorithms.

If successful, the new relaxations developed with this research, along with factorable decomposition and separation techniques, will advance the state of the art in the global optimization of complementarity programs, bringing many practically relevant problems within the range of tractability. Because complementarity constraints arise in equilibrium analyses of supply and demand, adversarial relationships between strategically interacting entities, traffic equilibria, and in the analyses of multistage optimization problems, this research could lead to improved efficiencies in various sectors of the economy. Further, since bilevel programs have numerous applications in defense planning, including interdiction and protection of critical infrastructure, this research could impact positively various areas of national defense. From an educational perspective, related material will be incorporated into undergraduate and graduate education and doctoral students will be trained in relevant technologies including integer programming and global optimization. In addition, a website will be designed to disseminate prototype implementations and problem data sets.