Адаптивный координатный спуск
Адаптивный координатный спуск[1] — улучшенный вариант алгоритма координатного спуска для неразделимой оптимизации, использующий технику адаптивного кодирования[2]. Адаптивный координатный спуск последовательно строит преобразования координатной системы так, что новые координаты максимально декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск конкурентен с передовыми эволюционными алгоритмами и имеют следующие свойства инвариантности:
- инвариантность относительно монотонного изменения функции (масштабирование)
- инвариантность относительно ортогональных преобразований пространства поиска (вращения).
CMA-подобное адаптивное кодирование (b), в основном базирующееся на методе главных компонент (a), используется для расширения метода координатного спуска (c) для решения неразделимых задач оптимизации (d).
![](../I/Adaptive_Coordinate_Descent_illustration.png.webp)
Адаптация приемлемой координатной системы позволяет методу адаптивного координатного спуска превзойти координатный спуск на неразделимых функциях. Следующий рисунок показывает сходимость обоих алгоритмов для двумерной функции Розенброка до целевого значения функции начиная с точки .
![](../I/Rosenbrock2D.png.webp)
Адаптивный координатный спуск достигает целевого значения всего за 325 вычислений функции (примерно в 70 раз быстрее координатного спуска), что сравнимо с методами, основанными на градиентах. Алгоритм имеет линейную сложность по времени, если обновлять систему координат каждые D итераций, и пригоден для нелинейных задач оптимизации большого размера (D>>100).
Связанные подходы
Первые подходы к оптимизации с использованием адаптации системы координат были предложены уже в 1960-е годы (например, методы Розенброка). Алгоритм PRincipal Axis (PRAXIS), известный также как алгоритм Брента — алгоритм без вычисления производной, в котором предполагается квадратичная форма оптимизируемой функции и периодически обновляется набор направлений поиска[3]. Алгоритм, однако, не инвариантен относительно масштабирования целевой функции и может привести к неудаче при некоторых сохраняющих ранг преобразованиях (например, может привести целевую функцию к неквадратичной форме)[4].
Описан пример применения адаптивного координатного спуска с адаптацией шага и локальным вращением координат для планирования пути робота-манипулятора в трёхмерном пространстве со статическими многоугольными препятствиями[5].
Примечания
- Loshchilov, Schoenauer, Sebag, 2011, с. 885–892.
- Hansen, 2008, с. 205—214.
- Brent, 1972.
- Ali, Kickmeier-Rust, 2008, с. 505–513.
- Pavlov, 2006, с. 505–513.
Литература
- 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.