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

该合作研究奖为开发新的和更强大的技术提供资金，用于解决具有全局最优性互补约束的优化问题。互补性问题在商业、工程和经济学中普遍存在，因为互补性条件出现在非线性规划的最优性条件和均衡模型中。直到最近，互补性问题的算法主要是通过采用局部优化技术来解决可行性问题。这个项目的重点是这些问题的凸松弛的发展，目标是将它们纳入全局优化的分支定界算法。研究的目的是推导出(i)利用互补约束的组合和析取结构的程序，（ii）关注具有可证明的强度保证的松弛，以及（iii）一些约束（除了互补）是非线性的目标问题。将研究相对于成熟的全局优化算法实现的松弛技术的好处。如果成功，本研究开发的新松弛，以及因子分解和分离技术，将推动互补规划全局优化的发展，使许多实际相关问题在可处理的范围内。由于互补性约束出现在供需均衡分析、战略互动实体之间的对抗关系、交通平衡和多阶段优化问题的分析中，因此本研究可以提高经济各个部门的效率。此外，由于双层计划在国防规划中有许多应用，包括关键基础设施的拦截和保护，因此该研究可能对国防的各个领域产生积极影响。从教育角度来看，相关材料将被纳入本科和研究生教育，博士生将接受整数规划和全局优化等相关技术的培训。此外，还将设计一个网站来传播原型实施和问题数据集。

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.