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

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

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

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

${\displaystyle 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})}$[2]

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

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

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

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

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

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

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

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

Алгоритмы координатного спуска популярны ввиду их простоты, но то же свойство побуждает исследователей игнорировать их в пользу более интересных (более сложных) методов[1]. Ранние приложения оптимизации методом координатного спуска были в области компьютерной томографии[7], где метод показал быструю сходимость[8] и был использован для реконструкции изображений многослойной спиральной компьютерной томографии[9]. Алгоритм циклического координатного спуска был применён в предсказании протеиновой структуры[10]. Более того, рос интерес к применению координатного спуска с появлением задач большого размера в обучении машин, где координатный спуск, как было показано, конкуррентен с другими методами, когда применяется к таким задачам, как обучение линейным методом опорных векторов[11] (см. LIBLINEAR) и неотрицательное матричное разложение[12]. Методы привлекательны для задач, когда вычисление градиента невыполнимо, возможно потому, что требуемые данные распределены по компьютерным сетям[13].

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