Two decomposition algorithms for nonconvex optimization problems with global variables
Two decomposition algorithms for nonconvex optimization problems with global variables
复制标题
全局变量非凸优化问题的两种分解算法
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Angel
中科院分区：
文献类型：
--
作者：
W. Murray;Angel
许多优化问题的一个共同特征是组件系统之间的弱连通性。分解算法通过将问题分解为一组较小的独立问题来利用这一特性。一种类型的连通性发生在只有少数变量（称为全局变量）与所有系统相关，而其余变量与单个组件相关时。我们称这些问题为全局变量优化问题。例子出现在复杂系统的设计，如飞机或汽车，并在随机问题的解决方案，如投资组合管理。
协同优化（CO）是一种很有前途的分解算法，它将一个全局变量优化问题转化为一个等价的主问题和一组子问题。不幸的是，CO主问题和子问题都是退化的。非退化性是大多数优化算法在证明收敛性时的一个常见假设。毫不奇怪，CO无法解决一些简单的测试问题。
我们提出了两种新的分解算法，规避了与CO的一些困难。第一种算法，名为不精确的惩罚分解（IPD），使用不精确的惩罚函数。第二种算法，称为精确罚分解（EPD），采用精确罚函数和障碍函数。主要的优点是，这些新的方法在非退化问题的结果。因此，存在快速局部收敛的主问题和子问题的算法。
为了测试新的算法，我们提出了一个新的二次规划测试问题集。用户可以选择问题的规模、凸性、退化性和耦合度。所有的测试问题最小化器都是先验已知的。IPD和EPD都成功地解决了各种情况下的测试集。
A feature common to many optimization problems is a weak connectivity between component systems. Decomposition algorithms exploit this feature by breaking the problem into a set of smaller independent problems. One type of connectivity occurs when only a few of the variables, known as global variables, are relevant to all systems, while the remainder are local to a single component. We term these problems Optimization Problems with Global Variables. Examples arise in the design of complex systems such as an aircraft or automobile and in the solution of stochastic problems such as portfolio management.
Collaborative Optimization (CO) is a promising decomposition algorithm that transforms an Optimization Problem with Global Variables into an equivalent master problem and a set of subproblems. Unfortunately, both the CO master problem and the subproblems are degenerate. Nondegeneracy is a common assumption when proving convergence for most optimization algorithms. Not surprisingly, CO fails to solve some simple test problems.
We propose two novel decomposition algorithms that circumvent some of the difficulties associated with CO. The first algorithm, named Inexact Penalty Decomposition (IPD), uses an inexact penalty function. The second algorithm, termed Exact Penalty Decomposition (EPD), employs an exact penalty function and a barrier function. The main advantage is that these new approaches result in nondegenerate problems. Consequently, there exist algorithms that are fast locally convergent for both the master problem and the subproblems.
To test the new algorithms we present a new quadratic programming test-problem set. The user can choose problem size, convexity, degeneracy, and degree of coupling. All test-problem minimizers are known a priori. Both IPD and EPD successfully solve the test set for a wide variety of circumstances.