View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264601.png" /> on a set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264602.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264603.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264604.png" /> are given numbers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264605.png" />, is described and the cases where all or some of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264606.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264607.png" /> are not excluded. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264608.png" /> be the coordinate vector in which the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c0264609.png" />-th coordinate is equal to 1 and the other coordinates are equal to zero. One specifies an initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646011.png" />. Assume that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646012.png" />-th approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646013.png" /> is known and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646014.png" />, for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646015.png" />. Take <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646016.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646018.png" /> is the integer part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646019.png" />. Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646020.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646021.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646022.png" /></td> </tr></table>

i.e. one performs a cyclic selection of the coordinate vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646023.png" />. First one checks if the conditions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646024.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

are fulfilled. If (1) is fulfilled, one sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646026.png" />. If on the other hand (1) is not fulfilled, one checks the condition

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646027.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

If (2) is fulfilled, one sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646029.png" />. If conditions (1) and (2) are both not fulfilled, one sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646030.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646032.png" /> is the parameter of the method, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646033.png" />. Condition (3) means that if at least one of the conditions (1) and (2) is fulfilled in a single cycle of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646034.png" /> iterations involving a selection of all coordinate vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646035.png" /> with step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646036.png" />, then the length of the step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646037.png" /> is not reduced and is retained at least during the following cycle of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646038.png" /> iterations; if on the other hand neither (1) nor (2) is ever fulfilled in the subsequent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646039.png" /> iterations, the step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646040.png" /> is reduced.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646041.png" /> be convex and continuously differentiable on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646042.png" />, let the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646043.png" /> be bounded and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646044.png" /> be a positive number. Then the methods (1)–(3) converge, i.e.

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646045.png" /></td> </tr></table>

and the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646046.png" /> converges to the set of minima for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646047.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646048.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646049.png" /> is not differentiable on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026460/c02646050.png" />, the method need not converge [[#References|[1]]], [[#References|[2]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F.P. Vasil'ev,   "Numerical methods for solving extremum problems" , Moscow  (1980)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.G. Karmanov,   "Mathematical programming" , Moscow  (1975)  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.I. Zangwill,   "Nonlinear programming: a unified approach" , Prentice-Hall  (1969)</TD></TR></table>