A family of subgradient-based methods for convex optimization problems in a unifying framework
A family of subgradient-based methods for convex optimization problems in a unifying framework
复制标题
DOI：
10.1080/10556788.2016.1182165
复制
发表时间：
2014-03
影响因子：
2.2
通讯作者：
Masaru Ito;Mituhiro Fukuda
中科院分区：
文献类型：
--
作者：
Masaru Ito;Mituhiro Fukuda
对于可行域足够简单的凸优化问题，我们提出了一类新的次梯度方法和基于梯度的方法，它以最优的复杂性收敛。这包括目标函数是非光滑的、光滑的、具有复合/鞍形结构的情况，或者由不精确的先知模型给出的情况。我们统一了构造这些方法每次迭代所需解决的子问题的方式。这使我们能够与以前的结果相比，以统一的方式分析这些方法的收敛情况，因为以前的结果要求每种方法/算法采用不同的方法。我们的贡献依赖于非光滑凸优化中的两种著名方法：Nomerovski-Yudin的镜像下降法(MDM)和Nester ov的对偶平均法。因此，我们的方法家族将它们和许多其他方法作为特殊情况包括在内。例如，提出的经典梯度法族及其加速算法推广了Devold等人的S、Nester ov的原始/对偶梯度法和Tseng的加速近邻梯度法.此外，我们的方法族也可以部分地成为其他通用方法的特例.作为额外的贡献，新的扩展MDM去掉了原MDM所要求的可行域的紧致性假设和总迭代次数的固定，以达到最优的复杂度.
We propose a new family of subgradient- and gradient-based methods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objective function is non-smooth, smooth, have composite/saddle structure, or are given by an inexact oracle model. We unified the way of constructing the subproblems which are necessary to be solved at each iteration of these methods. This permitted us to analyse the convergence of these methods in a unified way compared to previous results which required different approaches for each method/algorithm. Our contribution rely on two well-known methods in non-smooth convex optimization: the mirror-descent method (MDM) by Nemirovski-Yudin and the dual-averaging method by Nesterov. Therefore, our family of methods includes them and many other methods as particular cases. For instance, the proposed family of classical gradient methods and its accelerations generalize Devolder et al.'s, Nesterov's primal/dual gradient methods, and Tseng's accelerated proximal gradient methods. Also our family of methods can partially become special cases of other universal methods, too. As an additional contribution, the novel extended MDM removes the compactness assumption of the feasible region and the fixation of the total number of iterations which is required by the original MDM in order to attain the optimal complexity.