Математика

Численная оптимизация

Алгоритмы поиска минимума и выбор шага, ограничения и инерция.

Как выбрать подходящий материал

Уточните, ищется ли минимум на интервале, без ограничений или в допустимом множестве. Градиентный метод и поиск по интервалу требуют разных исходных данных.
Проверяйте убывание цели, допустимость точки и условие остановки. Стационарная точка не обязательно является минимумом.

10 формул

Формулы темы

Метод золотого сечения: сужение интервала минимума

Золотое сечение находит минимум унимодальной функции без производных. Два внутренних значения позволяют отбросить часть интервала, а удачное отношение длин сохраняет одно вычисление для следующего шага.

$\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$

Тернарный поиск минимума непрерывной унимодальной функции

Тернарный поиск сравнивает функцию в двух точках, делящих интервал на трети. При унимодальности одно сравнение позволяет удалить крайнюю треть и сохранить интервал, содержащий минимум.

$u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$

Параболическая интерполяция для поиска минимума функции

Через три значения функции строят квадратичный интерполянт и используют его вершину как новую пробную точку минимума. В отличие от деления интервала схема учитывает высоты всех трёх точек.

$A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}$

Градиентный спуск с постоянным шагом: условие убывания

Постоянный шаг градиентного спуска смещает точку против градиента. При липшицевом градиенте известная граница шага обеспечивает уменьшение функции и объясняет, почему слишком крупный шаг вызывает расходимость.

$x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$

Правило Армихо: обратный поиск длины шага спуска

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

$f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$

Метод Ньютона для минимума: шаг через матрицу Гессе

Метод Ньютона выбирает шаг по квадратичной модели целевой функции: матрица Гессе учитывает кривизну, а градиент задаёт линейную часть. Решение системы даёт направление, но длину шага иногда приходится уменьшать.

$H_k d_k=-g_k,\qquad x_{k+1}=x_k+\alpha_k d_k$

Покоординатный спуск для выпуклой квадратичной функции

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

$x_i^{+}=x_i-\frac{(Ax-b)_i}{A_{ii}},\quad f(x)=\tfrac12x^TAx-b^Tx$

Проекционный градиент: минимум с ограничениями на переменные

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

$x_{k+1}=\Pi_C(x_k-\alpha\nabla f(x_k))$

Метод Франка — Вульфа: линейный подшаг на симплексе

Метод Франка — Вульфа заменяет проекцию решением линейной задачи на допустимой области. Новая точка лежит на отрезке между старой точкой и решением подзадачи; на симплексе линейный минимум достигается в одной из его вершин.

$s_k\in\arg\min_{s\in C}\nabla f(x_k)^Ts,\quad x_{k+1}=(1-\gamma_k)x_k+\gamma_k s_k$

Метод тяжёлого шарика: инерционный шаг для квадратичной цели

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

$x_{k+1}=x_k-\alpha\nabla f(x_k)+\beta(x_k-x_{k-1})$