Coordinate-wise descent method

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

(1)

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

(2)

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

(3)

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].

References

[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)

References

[a1]	W.I. Zangwill, "Nonlinear programming: a unified approach" , Prentice-Hall (1969)