Structural Properties and Strong Relaxations for Mixed Integer Polynomial Optimization

混合整数多项式优化的结构性质和强松弛

基本信息

批准号：
1634768
负责人：
Alberto Del Pia
金额：
$ 32.72万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-01-01 至 2020-12-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1634768&HistoricalAwards=false
关键词：
Structural Properties Strong Relaxations Mixed

项目摘要

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.

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