Adaptive coordinate descent

Adaptive coordinate descent is an improvement of the coordinate descent algorithm to non-separable optimization by the use of adaptive encoding.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Adaptive coordinate descent is an improvement of the coordinate descent algorithm to non-separable optimization by the use of adaptive encoding. The adaptive coordinate descent approach gradually builds a transformation of the coordinate system such that the new coordinates are as decorrelated as possible with respect to the objective function.

The adaptive coordinate descent was shown to be competitive to the state-of-the-art evolutionary algorithms and has the following invariance properties: Invariance with respect to monotonous transformations of the function (scaling) Invariance with respect to orthogonal transformations of the search space (rotation). CMA-like Adaptive Encoding Update (b) mostly based on principal component analysis (a) is used to extend the coordinate descent method (c) to the optimization of non-separable problems (d). The adaptation of an appropriate coordinate system allows adaptive coordinate descent to outperform coordinate descent on non-separable functions.

The following figure illustrates the convergence of both algorithms on 2-dimensional Rosenbrock function up to a target function value 10^{-10} , starting from the initial point x_0=(-3,-4) . The adaptive coordinate descent method reaches the target value after only 325 function evaluations (about 70 times faster than coordinate descent), that is comparable to gradient-based methods.

The algorithm has linear time complexity if update coordinate system every D iterations, it is also suitable for large-scale (D>>100) non-linear optimization.

Relevant approaches

First approaches to optimization using adaptive coordinate system were proposed already in the 1960s (see, e.g., Rosenbrock's method). PRincipal Axis (PRAXIS) algorithm, also referred to as Brent's algorithm, is a derivative-free algorithm which assumes quadratic form of the optimized function and repeatedly updates a set of conjugate search directions.

The algorithm, however, is not invariant to scaling of the objective function and may fail under its certain rank-preserving transformations (e.g., will lead to a non-quadratic shape of the objective function). A recent analysis of PRAXIS can be found in.

For practical applications see, where an adaptive coordinate descent approach with step-size adaptation and local coordinate system rotation was proposed for robot-manipulator path planning in 3D space with static polygonal obstacles.

See also

Coordinate descent CMA-ES Rosenbrock methods Mathematical optimization

Text derived from https://en.wikipedia.org/w/index.php?oldid=1249472970 under CC BY-SA 4.0; modifications have been made.

Words in each sectionRelevant approachesRelevant approachesRelevant approaches: 126 words126See alsoSee alsoSee also: 28 words28
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001249472970 · captured 2024-10-05 · ledger · version history

Cite this page as: encyclopegia.org, “Adaptive coordinate descent”, snapshot enwiki-001249472970. https://encyclopegia.org/a/adaptive-coordinate-descent

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.