Coordinate descent

Coordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, then exactly or inexactly minimizes over the corresponding coordinate hyperplane while fixing all other coordinates or coordinate blocks. A line search along the coordinate direction can be performed at the current iterate to determine the appropriate step size. Coordinate descent is applicable in both differentiable and derivative-free contexts. Coordinate descent is based on the idea that the minimization of a multivariable function can be achieved by minimizing it along one direction at a time, i.e., solving univariate (or at least much simpler) optimization problems in a loop. In the simplest case of cyclic coordinate descent, one cyclically iterates through the directions, one at a time, minimizing the objective function with respect to each coordinate direction at a time. That is, starting with initial variable values round defines from by iteratively solving the single variable optimization problems for each variable of , for from 1 to . Thus, one begins with an initial guess for a local minimum of , and gets a sequence iteratively. By doing line search in each iteration, one automatically has It can be shown that this sequence has similar convergence properties as steepest descent. No improvement after one cycle of line search along coordinate directions implies a stationary point is reached. This process is illustrated below. In the case of a continuously differentiable function F, a coordinate descent algorithm can be sketched as: Choose an initial parameter vector x. Until convergence is reached, or for some fixed number of iterations: Choose an index i from 1 to n. Choose a step size α. Update xi to xi − α∂F/∂xi(x). The step size can be chosen in various ways, e.g., by solving for the exact minimizer of f(xi) = F(x) (i.e.