Structural Properties and Strong Relaxations for Mixed Integer Polynomial Optimization

近年来，混合整数非线性优化的研究在理论、算法和软件层面都有了长足的发展。虽然这些新的算法类别已经在科学、工程和经济学领域产生了显著的影响，但仍有许多重要的应用是这些方法无法解决的。与线性和凸非线性求解器相比，混合整数非线性求解器非常慢，不能处理大规模问题，并且需要高水平的用户专业知识。事实上，许多优化专家认为，对于非凸非线性问题，要么放弃速度，要么放弃解的质量保证。该项目旨在通过发展基础理论来解决这种权衡，为各种经常作为非凸混合整数非线性优化问题的构建块出现的非凸集构建强且易于处理的多面体松弛。该项目的研究目标的成功解决将潜在地改变混合整数非线性优化问题的求解器技术；一个非常强大的框架，包含了许多现实世界的优化问题。该项目通过研究生指导、将研究成果纳入课程作业以及广泛传播研究成果来开展教育和推广活动。可因式规划是一种广泛应用于一般非凸函数定界的技术。特别是，许多非凸问题，包括二次规划、多线性规划和多项式优化问题的可因式重构，包含了一组多线性方程。本研究的主要重点是研究在原变量空间中由多线性方程组定义的集合的凸壳的面结构。通过一个优雅的基于超图的表示方案，我们将研究这些集合的各种结构特性、分解技术和提升操作。将对松弛的强度和复杂性进行严格的研究，并提出新的多项式可解优化问题。

Research in mixed-integer nonlinear optimization has witnessed a significant growth at the theoretical, algorithmic and software levels over the last few years. While these new classes of algorithms have already had a remarkable impact across science, engineering, and economics, there exists a variety of important applications that these methods are unable to address. Compared to linear and convex nonlinear solvers, mixed-integer nonlinear solvers are very slow, cannot handle large-scale problems, and require a high level of user expertise. In fact, many optimization experts believe that in case of nonconvex nonlinear problems, one has to give up on either speed or the guarantee of solution quality. This project aims to address this trade-off, by developing foundational theory to construct strong and tractable polyhedral relaxations for a variety of nonconvex sets that frequently appear as building blocks of nonconvex mixed-integer nonlinear optimization problems. Successful resolution of the research goals of this project will potentially transform solver technology for mixed-integer nonlinear optimization problems; a very powerful framework that subsumes many real-world optimization problems. The project addresses the educational and outreach activities through graduate student mentoring, integration of research results in course work, and broad dissemination of the results of the research.Factorable programming is a widely-used technique for bounding general nonconvex functions. In particular, factorable reformulations of many nonconvex problems, including quadratic programs, multilinear programs, and polynomial optimization problems, contain a collection of multilinear equations. A main focus of this research is to study the facial structure of the convex hull of a set defined by a system of multilinear equations in the space of the original variables. Through an elegant hypergraph-based representation scheme, various structural properties, decomposition techniques, and lifting operations for such sets will be studied. A rigorous study of the strength and complexity of the relaxations will be performed, and new classes of polynomially-solvable optimization problems will be presented.