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 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 F ( x ) {displaystyle F(mathbf {x} )} 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 k + 1 {displaystyle k+1} defines x k + 1 {displaystyle mathbf {x} ^{k+1}} from x k {displaystyle mathbf {x} ^{k}} by iteratively solving the single variable optimization problems for each variable x i {displaystyle x_{i}} of x {displaystyle mathbf {x} } , for i {displaystyle i} from 1 to n {displaystyle n} . Thus, one begins with an initial guess x 0 {displaystyle mathbf {x} ^{0}} for a local minimum of F {displaystyle F} , and gets a sequence x 0 , x 1 , x 2 , … {displaystyle mathbf {x} ^{0},mathbf {x} ^{1},mathbf {x} ^{2},dots } 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.