We propose a new family of subgradient- and gradient-basedmethods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objecti...
详细信息
We propose a new family of subgradient- and gradient-basedmethods 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 gradientmethods and its accelerations generalize Devolder et al.'s, Nesterov's primal/dual gradientmethods, and Tseng's accelerated proximalgradientmethods. 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.
暂无评论