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
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.
|||F.P. Vasil'ev, "Numerical methods for solving extremum problems" , Moscow (1980) (In Russian)|
|||V.G. Karmanov, "Mathematical programming" , Moscow (1975) (In Russian)|
|[a1]||W.I. Zangwill, "Nonlinear programming: a unified approach" , Prentice-Hall (1969)|
Coordinate-wise descent method. F.P. Vasil'ev (originator), Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Coordinate-wise_descent_method&oldid=18950