A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization

By Meisam Razaviyayn, Mingyi Hong, Zhi-Quan Tom Luo. 2012

1,321 citations recorded by the source corpus.

The block coordinate descent (BCD) method is widely used for minimizing a continuous function $f$ of several block variables. At each iteration of this method, a single block of variables is optimized, while the remaining variables are held fixed. To ensure the convergence of the BCD method, the subproblem of each block variable needs to be solved to its unique global optimal. Unfortunately, this requirement is often too restrictive for many practical scenarios. In this paper, we study an alternative inexact BCD approach which updates the variable blocks by successively minimizing a sequence of approximations of $f$ which are either locally tight upper bounds of $f$ or strictly convex local approximations of $f$. The main contributions of this work include the characterizations of the convergence conditions for a fairly wide class of such methods, especially for the cases where the objective functions are either nondifferentiable or nonconvex. Our results unify and extend the existing convergence results ...

Subfields: Computational Mathematics, Computational Mechanics, Numerical Analysis, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

  1. Andrzej S. Cichocki
  2. Anh Huy Phan
  3. Julien Mairal
  4. Wotao Yin
  5. Qibin Zhao
  6. Yangyang Xu
  7. Danilo P. Mandic
  8. Zhi-Quan Tom Luo

In Computational Mechanics

  1. Mingyi Hong
  2. Francis R. Bach
  3. Julien Mairal
  4. Jason D. Lee
  5. Wotao Yin
  6. Zhi-Quan Tom Luo
  7. Peter Richtárik
  8. Meisam Razaviyayn

In Numerical Analysis

  1. Julien Mairal
  2. Zhi-Quan Tom Luo
  3. Jong-Shi Pang
  4. Mingyi Hong
  5. D. P. Palomar
  6. Wotao Yin
  7. Francis R. Bach
  8. Gesualdo Scutari

In Mathematical Optimization

  1. Julien Mairal
  2. Zhi-Quan Tom Luo
  3. D. P. Palomar
  4. Jong-Shi Pang
  5. Gesualdo Scutari
  6. Mingyi Hong
  7. Francis R. Bach
  8. Francisco Facchinei

Citations in the corpus