Coordinate-wise descent method

From Encyclopedia of Mathematics
Jump to: navigation, search

One of the methods for minimizing a function of several variables based only on the values of the function to be minimized. The method is used when the function is not differentiable or if a calculation of the derivatives involves a large amount of computation. Below the use of the coordinate-wise descent method for minimizing a function on a set

where and are given numbers, , is described and the cases where all or some of the or are not excluded. Let be the coordinate vector in which the -th coordinate is equal to 1 and the other coordinates are equal to zero. One specifies an initial approximation , . Assume that the -th approximation is known and that , for some . Take , where and is the integer part of . Then

i.e. one performs a cyclic selection of the coordinate vectors . First one checks if the conditions


are fulfilled. If (1) is fulfilled, one sets , . If on the other hand (1) is not fulfilled, one checks the condition


If (2) is fulfilled, one sets , . If conditions (1) and (2) are both not fulfilled, one sets ,


where is the parameter of the method, . Condition (3) means that if at least one of the conditions (1) and (2) is fulfilled in a single cycle of iterations involving a selection of all coordinate vectors with step , then the length of the step is not reduced and is retained at least during the following cycle of iterations; if on the other hand neither (1) nor (2) is ever fulfilled in the subsequent iterations, the step is reduced.

Let be convex and continuously differentiable on , let the set be bounded and let be a positive number. Then the methods (1)–(3) converge, i.e.

and the sequence converges to the set of minima for in . If is not differentiable on , the method need not converge [1], [2].


[1] F.P. Vasil'ev, "Numerical methods for solving extremum problems" , Moscow (1980) (In Russian)
[2] V.G. Karmanov, "Mathematical programming" , Moscow (1975) (In Russian)



[a1] W.I. Zangwill, "Nonlinear programming: a unified approach" , Prentice-Hall (1969)
How to Cite This Entry:
Coordinate-wise descent method. F.P. Vasil'ev (originator), Encyclopedia of Mathematics. URL:
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098