Cyclic descent

From Glossary

Jump to: navigation, search

An algorithm that seeks to optimize a multivariate function by optimizing each coordinate with a univariate optimization technique (keeping the other coordinates fixed). This is repeated until a fixed point is reached. In general, it is possible for such a fixed point not to be an optimum (even locally) because a simultaneous change in variables could result in an improvement. An example is given by:

LaTeX: f(x, y) = (y - x^2)(y - 2x^2) \; \mbox{ at } \; (x, y) = (0,0).

LaTeX: f(0, y) has a minimum at LaTeX: y=0, and LaTeX: f(x, 0) has a minimum at LaTeX: x=0. However, LaTeX: f decreases with simultaneous change, LaTeX: y=(3/2)x^2. Along this parabola, LaTeX: f(x,y) = -(x^4)/4, which is negative for LaTeX: x nonzero. Thus, LaTeX: 0 is not a local minimum of LaTeX: f. For further discussion about this example, see Myths and Counter Examples.

Personal tools