Novel Relaxations for Global Optimization

全局优化的新颖松弛

• 批准号: 1030168
• 负责人: Nikolaos Sahinidis
• 金额: $ 20万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1030168&HistoricalAwards=false
• 关键词: Novel; Relaxations; Global; Optimization

Software implementing general-purpose deterministic global optimization algorithms for nonconvex nonlinear programs (NLPs) and mixed-integer nonlinear programs (MINLPs) became available for the first time over the past two decades. By building upon results from convex analysis, combinatorial optimization, and convex programming, these algorithms and software have already had a transformative impact in operations research, computer science, engineering design, and computational biology. Yet, there exist vast classes of important applications that these tools are unable to address at the moment. The primary goal of this project is to address the problem that lies at the heart of global optimization algorithms, i.e., the construction of sharp relaxations. Current algorithms iteratively decompose nonconvex functions, through the introduction of variables and constraints for intermediate functional expressions, until the intermediate expressions can be outer-approximated by a convex feasible set. While it is easy to automate, this factorable programming technique often leads to weak relaxations. This project pursues and systematically applies an innovative technique for relaxation construction that generates convex and concave envelopes of nonconvex functions while minimizing, or even entirely eliminating, the steps of this factorable decomposition. The technique relies on ideas from convex analysis with a careful exploitation of properties to derive closed-form solutions for convex optimization problems that characterize convex and concave envelopes of nonconvex functions. The project will develop analytical expressions for the envelopes of a variety of functions that appear in diverse application areas. The project will also investigate the computational implications of using these envelopes in branch-and-cut algorithms for NLPs and MINLPs.If successful, the results of this research will lay the foundations of a new generation of algorithms and software for global optimization capable of solving large-scale nonconvex NLPs and MINLPs that are ubiquitous in engineering design, manufacturing, logistics, and the chemical and biological sciences.

实现非凸非线性规划（nlp）和混合整数非线性规划（minlp）的通用确定性全局优化算法的软件在过去二十年中首次出现。通过构建凸分析、组合优化和凸规划的结果，这些算法和软件已经在运筹学、计算机科学、工程设计和计算生物学中产生了变革性的影响。然而，目前有大量重要的应用程序是这些工具无法解决的。这个项目的主要目标是解决全局优化算法的核心问题，即尖锐松弛的构造。目前的算法迭代分解非凸函数，通过引入中间函数表达式的变量和约束，直到中间表达式可以被凸可行集外逼近。虽然易于自动化，但这种可分解编程技术经常导致弱松弛。该项目追求并系统地应用了一种创新的松弛构造技术，该技术可以生成非凸函数的凸和凹包络，同时最小化甚至完全消除这种因子分解的步骤。该技术依赖于凸分析的思想，并仔细利用性质来推导非凸函数的凸包络和凹包络特征的凸优化问题的闭形式解。该项目将为出现在不同应用领域的各种功能的围护结构开发解析表达式。该项目还将研究在nlp和minlp的分支-切割算法中使用这些包络的计算含义。如果成功，这项研究的结果将为新一代算法和软件的全局优化奠定基础，这些算法和软件能够解决在工程设计、制造、物流、化学和生物科学中无处不在的大规模非凸nlp和minlp。