Адаптивный координатный спуск

Адаптивный координатный спуск ­— улучшенный вариант алгоритма координатного спуска для неразделимой оптимизации, использующий технику адаптивного кодирования. Адаптивный координатный спуск последовательно строит преобразования координатной системы так, что новые координаты максимально декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск конкурентен с передовыми эволюционными алгоритмами и обладает следующими свойствами инвариантности:

• инвариантность относительно монотонного изменения функции (масштабирование)
• инвариантность относительно ортогональных преобразований пространства поиска (вращения).

CMA-подобное адаптивное кодирование (b), в основном базирующееся на методе главных компонент (a), используется для расширения метода координатного спуска (c) для решения неразделимых задач оптимизации (d).

Адаптация приемлемой координатной системы позволяет методу адаптивного координатного спуска превзойти координатный спуск на неразделимых функциях. Следующий рисунок показывает сходимость обоих алгоритмов для двумерной функции Розенброка до целевого значения функции $10^{-10}$ начиная с точки $x_{0}=(-3,-4)$.

Адаптивный координатный спуск достигает целевого значения всего за 325 вычислений функции (примерно в 70 раз быстрее координатного спуска), что сравнимо с методами, основанными на градиентах. Алгоритм имеет линейную сложность по времени, если обновлять систему координат каждые D итераций, и пригоден для нелинейных задач оптимизации большого размера (D>>100).

Связанные подходы

Первые подходы к оптимизации с использованием адаптации системы координат были предложены уже в 1960-е годы (например, методы Розенброка). Алгоритм PRincipal Axis (PRAXIS), известный также как алгоритм Брента — алгоритм без вычисления производной, в котором предполагается квадратичная форма оптимизируемой функции и периодически обновляется набор направлений поиска. Алгоритм, однако, не инвариантен относительно масштабирования целевой функции и может привести к неудаче при некоторых сохраняющих ранг преобразованиях (например, может привести целевую функцию к неквадратичной форме).

Описан пример применения адаптивного координатного спуска с адаптацией шага и локальным вращением координат для планирования пути робота-манипулятора в трёхмерном пространстве со статическими многоугольными препятствиями.

Литература

• Loshchilov I., Schoenauer M., Sebag M. Adaptive Coordinate Descent // Genetic and Evolutionary Computation Conference (GECCO). — ACM Press, 2011. — P. 885–892.
• Nikolaus Hansen. Adaptive Encoding: How to Render Search Coordinate System Invariant // Parallel Problem Solving from Nature – PPSN X / G. Rudolph, T. Jansen, S. Lucas, C. Poloni, N. Beume (Eds.). — Dortmund, Germany, 2008. — Т. 5199. — (LNCS).
• Brent R.P. Algorithms for minimization without derivatives. — Prentice-Hall, 1972.
• Ali U., Kickmeier-Rust M.D. Implementation and Applications of a Three-Round User Strategy for Improved Principal Axis Minimization // Journal of Applied Quantitative Methods. — 2008.
• Pavlov D. Manipulator path planning in 3-dimensional space // Computer Science--Theory and Applications. — Springer, 2006.

Ссылки

• Source code ACD ACD is a MATLAB source code for Adaptive Coordinate Descent