The block-coordinate descent method for nonconvex optimization

Background

The block-coordinate update (BCU) method solves the problem in the form of

 min_{mathbf{x}_1,ldots,mathbf{x}_s} f(mathbf{x}_1,ldots,mathbf{x}_s),~mathrm{subject~to}~(mathbf{x}_1,ldots,mathbf{x}_s)inmathcal{X}

by updating just one or a few blocks of variables at a time, rather than updating all the blocks together (the batch update). The order of update can be deterministic or stochastic. The deterministic orders can be eithr cyclic or greedy according to a certain rank.

The main advantage is that updating one or just a few blocks of variables are computationally much cheaper than the batch update. On the other hand, convergence requires more stringent conditions and typically takes more iterations.

The update applied to each block can be exact minimization over the block or take different forms of inexact updates such as

There is a tradeoff between the per-update complexity and the progress of overall minimization.

BCU is a generalization to the following classic methods:

Motivation and the Proposed Method

It is challenging to establish the global convergence of BCU for optimization problems that are nonconvex and/or nonsmooth. In general, either nonconvexity or nonsmoothness can cause BCU to stagnate at a non-stationary point.

To establish global convergence, we assume that the non-smooth part of the objective is block-separable, namely, the non-smooth part can be written as sum_{i=1}^s r_i(mathbf{x}_i). A differentiable part of the objective exists to couple all blocks together. Many interesting applications have this structure; see below. We propose a BCU algorithm with three different block-update schemes; the choice for each block is independent of others. Under certain conditions, we show that any limit point satisfies the Nash equilibrium conditions (a generalization to stationarity). Furthermore, global convergence and asymptotic convergence rate are established for problems obeying the Kurdyka-Lojasiewicz inequality.

Applications

Tested problem sets

Matlab codes and demos

Citations