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

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

Описание

Координатный спуск основан на идее, что минимизация функции $F(\mathbf {x} )$ многих переменных может быть осуществлена путём минимизации вдоль одного направления в каждый момент времени, например, путём решения оптимизационной задачи от одной переменной (или, по меньшей мере, более простой задачи) в цикле. В простейшем случае циклического координатного спуска алгоритм циклически делает итерации по координатным направлениям по одному за итерацию, минимизируя целевую функцию по каждой координате за раз. То есть, начиная с начальных значений

$\mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0})$,

итерация $k+1$ определяет $\mathbf {x} ^{k+1}$ из $\mathbf {x} ^{k}$ путём итеративного решения задач оптимизации от одной переменной

$x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})$

для каждой переменной $x_{i}$ вектора $\mathbf {x}$ для $i$ от 1 до $n$.

Таким образом, алгоритм начинается с начального приближения $\mathbf {x} ^{0}$ локального минимума функции $F$ и получает последовательность векторов $\mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots$ итеративно.

При осуществлении линейного поиска на каждой итерации получаем

$F(\mathbf {x} ^{0})\geqslant F(\mathbf {x} ^{1})\geqslant F(\mathbf {x} ^{2})\geqslant \dots .$

Можно показать, что эта последовательность имеет свойства сходимости, аналогичные методу наискорейшего спуска. Отсутствие улучшения целевой функции после очередного цикла линейных поисков вдоль координатных направлений говорит о достижении стационарной точки.

Процесс работы алгоритма продемонстрирован ниже.

Дифференцируемый случай

В случае непрерывной дифференцируемости функции F алгоритм координатного спуска можно изложить кратко как:

• Выбираем начальный вектор x.
• Пока не будет достигнут уровень сходимости или не будет сделано фиксированное число итерации:
  • Выбираем индекс i из промежутка от 1 до n.
  • Выбираем размер шага α.
  • Заменяем $x_{i}$ на $x_{i}-\alpha {\tfrac {\partial F}{\partial x_{i}}}(\mathbf {x} )$.

Шаг может быть выбран разными способами, например, путём решения задачи минимизации $f(x_{i})=F(\mathbf {x} )$ (то есть, путём минимизацииF с фиксированными переменными за исключением $x_{i}$), или путём традиционного линейного поиска.

Ограничения

Координатный спуск имеет две проблемы. Одна из них заключается в наличии негладкой функции от нескольких переменных. Рисунок показывает, что итерации координатного спуска могут упереться в нестационарную точку, если кривые уровня функции не гладкие. Предположим, что алгоритм оказался в точке (-2, -2). Тогда имеется два направления, параллельные осям, по которым следовало бы делать очередной шаг. Они показаны красными стрелками. Однако любой шаг в этих двух направлениях приведёт к росту значения функции (предполагается, что решается задача минимизации), так что алгоритм не сделает ни одного шага, хотя два шага вместе привели бы алгоритм ближе к оптимуму. Хотя данный пример показывает, что координатный спуск не обязательно приводит к оптимальному решению, можно показать формальную сходимость при нормальных условиях.

Другая проблема – трудности в распараллеливании. Поскольку природа координатного спуска заключается в цикле по направлениям и минимизации функции по каждому координатному направлению, координатный спуск не является очевидным кандидатом для распараллеливания. Недавние исследования показали, что распараллеливание можно использовать для координатного спуска при некоторых специальных приёмах.

Приложения

Алгоритмы координатного спуска популярны ввиду их простоты, но то же свойство побуждает исследователей игнорировать их в пользу более интересных (более сложных) методов. Ранние приложения оптимизации методом координатного спуска были в области компьютерной томографии, где метод показал быструю сходимость и был использован для реконструкции изображений многослойной спиральной компьютерной томографии. Алгоритм циклического координатного спуска был применён в предсказании протеиновой структуры. Более того, рос интерес к применению координатного спуска с появлением задач большого размера в машинном обучении, где координатный спуск, как было показано, конкуррентен с другими методами, когда применяется к таким задачам, как обучение линейным методом опорных векторов (см. LIBLINEAR) и неотрицательное матричное разложение. Методы привлекательны для задач, когда вычисление градиента невыполнимо, возможно потому, что требуемые данные распределены по компьютерным сетям.

См. также

• Адаптивный координатный спуск
• Метод сопряжённых градиентов
• Градиентный спуск
• Линейный поиск
• Оптимизация (математика)
• Метод Ньютона
• Стохастический градиентный спуск