Optimization Online


A Family of Subgradient-Based Methods for Convex Optimization Problems in a Unifying Framework

Masaru Ito (ito1***at***is.titech.ac.jp)
Mituhiro Fukuda (mituhiro***at***is.titech.ac.jp)

Abstract: 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 analyze 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 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 mirror-descent method removes the compactness assumption of the feasible region and the fixation of the total number of iterations which is required by the original mirror-descent method in order to attain the optimal complexity.

Keywords: non-smooth/smooth convex optimization, structured convex optimization, subgradient/gradient-based proximal method, mirror-descent method, dual-averaging method, complexity bounds

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Research Report B-477, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 02/28/2014
Entry Accepted: 02/28/2014
Entry Last Modified: 12/29/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society