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

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

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.