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

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

Описание

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

${𝐱}^0=(x_1^0,\dots ,x_n^0)$,

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

$x_i^{k+1}=\underset{y\in ℝ}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}f(x_1^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^k,\dots ,x_n^k)$Шаблон:R

для каждой переменной $x_i$ вектора $𝐱$ для $i$ от 1 до $n$.

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

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

$F({𝐱}^0)⩾F({𝐱}^1)⩾F({𝐱}^2)⩾\dots .$

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

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

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

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

• Выбираем начальный вектор Шаблон:Math.
• Пока не будет достигнут уровень сходимости или не будет сделано фиксированное число итерации:
  • Выбираем индекс Шаблон:Mvar из промежутка от Шаблон:Math до Шаблон:Mvar.
  • Выбираем размер шага Шаблон:Mvar.
  • Заменяем $x_i$ на $x_i-\alpha \frac{\partial F}{\partial x_i}(𝐱)$.

Шаг может быть выбран разными способами, например, путём решения задачи минимизации $f(x_i)=F(𝐱)$ (то есть, путём минимизацииШаблон:Mvar с фиксированными переменными за исключением $x_i$), или путём традиционного линейного поискаШаблон:Sfn.

Ограничения

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

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

Приложения

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Статья