A Unifying Polyhedral Approximation Framework for Convex Optimization
A Unifying Polyhedral Approximation Framework for Convex Optimization
复制标题
凸优化的统一多面体逼近框架
DOI：
10.1137/090772204
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Huizhen Yu
中科院分区：
文献类型：
--
作者：
D. Bertsekas;Huizhen Yu
我们提出了一个统一的框架，多面体近似凸优化。它包含经典方法，例如切割平面和单纯分解，但也包括新方法和旧方法的新版本/扩展，例如用于不可微优化的单纯分解方法和用于凸单一商品网络流问题的新分段线性逼近方法。我们的框架是基于一个扩展形式的monotropic规划，一个广泛适用的模型，其中包括作为特殊情况下Fenchel对偶和Rockafellar的monotropic规划，其特征在于一个优雅的和对称的对偶理论。我们的算法灵活地结合了成本函数的外线性化和内线性化。线性化是逐步完善，通过使用原始和对偶微分，和外部和内部线性化的作用是颠倒的数学等价的对偶算法。我们提供了收敛结果的一般情况下，外部和内部线性化相结合，在同一算法。
We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods and new versions/extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization and a new piecewise linear approximation method for convex single commodity network flow problems. Our framework is based on an extended form of monotropic programming, a broadly applicable model, which includes as special cases Fenchel duality and Rockafellar's monotropic programming, and is characterized by an elegant and symmetric duality theory. Our algorithm combines flexibly outer and inner linearization of the cost function. The linearization is progressively refined by using primal and dual differentiation, and the roles of outer and inner linearization are reversed in a mathematically equivalent dual algorithm. We provide convergence results for the general case where outer and inner linearization are combined in the same algorithm.