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.