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

合作研究：离散和连续非凸优化的重构线性化技术及其应用

• 批准号: 0968909
• 负责人: Warren Adams
• 金额: $ 25万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-05-15 至 2013-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0968909&HistoricalAwards=false
• 关键词: Collaborative; Research; Reformulation; Linearization; Technique

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.

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