Collaborative Research: Reformulation-Linearization Technique for Discrete and Continuous Nonconvex Optimization with Applications

该项目的研究目标是开发理论和计算工具来解决困难的，大规模的，离散和连续的非凸优化问题。这项工作将集中在扩展和完善的重构线性化/凸化技术（RLT）。RLT是一种方法论概念，通过在提升的高维空间中构建改进的（收紧的）数学模型来增强问题的可解决性。本研究的目的是解决几个理论和算法的发展，以及计算实现相关的RLT问题，并确定和利用数学结构，从应用它。具体来说，工作包括（1）通过使用拉格朗日插值多项式来表征离散集的凸船体的结构，解决整数规划的能力;（2）一个统一的RLT方法与半定规划结构沿着与过滤和基减少技术，可以用来设计有效的算法，解决离散以及连续的非凸优化问题;以及（3）发展量身定制的方法，用于解决在特定应用中出现的具有某些特殊结构的离散和非线性问题。本研究的结果预期将导致更有效的工具来解决各种具有挑战性的非凸优化程序，包括离散和连续的。离散程序出现在集群、密码学、设施布局、逻辑推理和调度等不同领域，而连续非凸程序则应用于工程设计、网络设计、风险管理和国土安全。研究还将展示如何利用拉格朗日插值多项式的代数性质来分析和生成混合整数和连续非线性规划问题的切割。从概念上讲，这项研究将统一离散和连续优化领域，并提高对这些领域的理解。

The research objective of this project is to develop theoretical and computational tools for solving difficult, large-scale, discrete and continuous nonconvex optimization problems. The work will focus on extending and refining a reformulation-linearization/convexification technique (RLT). The RLT is a methodological concept for enhancing problem solvability by constructing improved (tightened) mathematical models in lifted, higher-dimensional spaces. The intent of this study is to address several theoretical and algorithmic developments as well as computational implementation issues related to the RLT, and to identify and exploit mathematical structures that arise from applying it. Specifically, the work will include (1) an extension of the underlying RLT theory through the use of Lagrange interpolating polynomials to characterize structures of the convex hull of discrete sets by way of enhancing the ability to solve integer programs; (2) a unified RLT approach with semidefinite programming constructs along with filtering and basis-reduction techniques that can be used to design effective algorithms for solving discrete as well as continuous nonconvex optimization problems; and (3) the development of tailored methods for solving both discrete and nonlinear problems having certain special structures that arise in particular applications.The results of this study are expected to lead to more efficient tools for solving a variety of challenging nonconvex optimization programs, both discrete and continuous. The discrete programs arise in such diverse areas as clustering, cryptography, facility layout, logical inference, and scheduling, while the continuous nonconvex programs have applications in engineering design, network design, risk management, and Homeland Security. The research will also demonstrate how the algebraic properties of Lagrange interpolating polynomials can be exploited to analyze and generate cuts for mixed-integer and continuous nonlinear programming problems. Conceptually, the research will unify the realms of discrete and continuous optimization, and improve understanding of these domains.