Mirror descent and nonlinear projected subgradient methods for convex optimization
Mirror descent and nonlinear projected subgradient methods for convex optimization
复制标题
DOI：
10.1016/s0167-6377(02)00231-6
复制
发表时间：
2003-05-01
影响因子：
1.1
通讯作者：
Teboulle, M
中科院分区：
文献类型：
--
作者：
Beck, A;Teboulle, M
镜像下降算法（MDA）由涅米罗夫斯基（Nemirovsky）和尤丁（Yudin）提出，用于解决凸优化问题。该方法所呈现的效率估计在一定程度上取决于决策变量的维度，因此适用于解决大规模的优化问题。我们对该算法进行了新的推导和分析。我们表明，MDA可被视为一种非线性投影次梯度类型的方法，它是通过使用一种类距离的通用函数而非通常的欧几里得平方距离推导而来的。在这种解释下，我们以一种简单的方式推导出了收敛性和效率估计。然后，我们针对单位单纯形上的凸最小化问题提出了一种熵镜像下降算法，并且证明了其全局效率估计在一定程度上取决于问题的维度。2003年爱思唯尔科学出版社（Elsevier Science B.V.）版权所有。
The mirror descent algorithm (MDA) was introduced by Nemirovsky and Yudin for solving convex optimization problems. This method exhibits an efficiency estimate that is mildly dependent in the decision variables dimension, and thus suitable for solving very large scale optimization problems. We present a new derivation and analysis of this algorithm. We show that the MDA can be viewed as a nonlinear projected-subgradient type method. derived from using a general distance-like function instead of the usual Euclidean squared distance. Within this interpretation, we derive in a simple way convergence and efficiency estimates. We then propose an Entropic mirror descent algorithm for convex minimization over the unit simplex, with a global efficiency estimate proven to be mildly dependent in the dimension of the problem, (C) 2003 Elsevier Science B.V. All rights reserved.