Задача квадратичной оптимизации - 5 - Метод наискорейшего спуска

алгоритм

Это 17-й день моего участия в ноябрьском испытании обновлений.Подробности о событии:Вызов последнего обновления 2021 г.

title: date: 2020-12-16 16:47:46 tags: [Machine_Learning] categories: [Machine_Learning] mathjax: true

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

описание проблемы

Чтобы переформулировать проблему, нам нужно оптимизировать:

f(x)=12xTAx−bTx+c\label1(1)f({\bf{x} }) = \frac{1}{2}{\bf{x^TAx} } - { {\bf{b} }^{\bf{T} } }{\bf{x} } + {\bf{c} } \tag{1} \label{1}
  • матрицаA\bf{A}положительно определенная симметрия
  • Цель состоит в том, чтобы оптимизироватьx\bf{x}, так чтоf(x)f(\bf{x})получить минимальное значение

крутой спуск

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

смысл

  • Наша цель — найти минимальное значение функции, и я уже знаю, что эта функция — всего лишь точка минимума, что эквивалентно нахождению нижней точки поверхности, блок-схема метода наискорейшего спуска:
нет
да
найти минимум функции
Вычислить текущее направление градиента
Рассчитать расстояние
Соответствует ли точность требованиям
выходное текущее местоположение

Процесс расчета

исходное положение:x0\bf{x}_0
Рассчитать градиентg\bf{g}
g=f'(x)=Ax−b(2)\bf{g} = f'(\bf{x}) = A\bf{x}-\bf{b} \tag{2}
  • Так оx0\bf{x}_0Для того, чтобы найти минимальное значение, необходимо двигаться в обратном направлении градиента, но чтобы обеспечить плавный процесс вывода, коэффициент прямого расстояния не имеет значения знака, пусть первыйiiРасстояние, которое должен пройти шаг, равноальфаi{\alpha}_i, то для первогоiiКусокxi\bf{x}_i,имеют:
xi+1=xi+альфаigi\label3(3){\bf{x}_{i + 1} } = {\bf{x}_i} + \alpha_i {\bf{g}_i} \tag{3} \label{3}
коэффициентальфаi{\alpha}_iрешать
метод 1:

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

который:

{% raw %}

giTgi+1=0(4){\bf{g}}_i^T {{\bf{g}}_{i + 1}}=0 \tag{4}

в:

gi=Axi−b(5){ {\bf{g} }_i}{\bf{ = A} }{ {\bf{x} }_i}{\bf{ - b} } \tag{5}
xi+1=xi+альфаigi=xi+альфаi(Axi−b)(6){ {\bf{x} }_{i + 1} } = { {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i} = {\bf{x}_i} + {\alpha _i}({\bf{A} }{ {\bf{x} }_i} - {\bf{b} }) \tag{6}
gi+1=Axi+1−b=A(xi+альфаigi)−b(7)\begin{array}{l} { {\bf{g} }_{i + 1} } &= {\bf{A} }{ {\bf{x} }_{i + 1} } - {\bf{b} }\\ &= {\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - {\bf{b} } \tag{7} \end{array}

Тогда есть:

giTgi+1=giTA(xi+альфаigi)−giTb=0{\bf{g} }_i^T{ {\bf{g} }_{i + 1} } = {\bf{g} }_i^T{\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - {\bf{g} }_i^T{\bf{b} } = 0
giTAxi+альфаigiTAgi−giTb=0{\bf{g} }_i^T{\bf{A} }{ {\bf{x} }_i} + {\alpha _i}{\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} - {\bf{g} }_i^T{\bf{b} } = 0
альфаigiTAgi+giTgi=0{\alpha _i}{\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} + {\bf{g} }_i^T{ {\bf{g} }_i} = 0
альфаi=−giTgigiTAgi(8){\alpha _i} = - \frac{ { {\bf{g} }_i^T{ {\bf{g} }_i} } }{ { {\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} } } \tag{8}

{% endraw %}

Способ 2

Определить направление градиентаg\bf{g}после решенияальфа\alpha, так как метод наискорейшего спуска определяет локальное оптимальное решение в направлении каждого шага, то есть положение, где минимальное значение получается при движении в этом направлении, тоальфа\alphaВозьмем производную так, чтобы производная была равна 0:

  • Зависит от\eqref1\eqref{1}и\eqref3\eqref{3},имеют:
f(x)=12(x+альфаg)TA(x+альфаg)−bT(x+альфаg)+c(9)f({\bf{x} }) = \frac{1}{2}{({\bf{x} } + \alpha {\bf{g} })^T}{\bf{A} }({\bf{x} } + \alpha {\bf{g} }) - { {\bf{b} }^{\bf{T} } }({\bf{x} } + \alpha {\bf{g} }) + {\bf{c} } \tag{9}
  • Для текущего местоположения, которое было определеноxi\bf{x}_i, который в настоящее время можно рассматривать примерно какxi\bf{x}_i,альфаi\alpha_iФункция:
f(xi+1)=f(xi,альфаi)=12(xi+альфаigi)TA(xi+альфаigi)−bT(xi+альфаigi)+c(10)f(\bf{x}_{i+1}) =f(\bf{x}_i,{\alpha _i}) = \frac{1}{2}{({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i})^T}{\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - { {\bf{b} }^{\bf{T} } }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) + {\bf{c} } \tag{10}
  • правильноальфаi\alpha_iНайдите частную производную:

{% raw %}

∂f(xi+1)∂альфаi=∂f(xi+1)∂xi+1∂xi+1∂альфаi=(Axi+1−b)Tgi=(A(xi+альфаigi)−b)Tgi=(Axi−b+альфаiAgi)Tgi=(giT+альфаigiTA)gi=giTgi+альфаigiTAgi=0(11)\begin{array}{l} \frac{ {\partial f({ {\bf{x} }_{i + 1} })} }{ {\partial {\alpha _i} } } &= \frac{ {\partial f({ {\bf{x} }_{i + 1} })} }{ {\partial { {\bf{x} }_{i + 1} } } }\frac{ {\partial { {\bf{x} }_{i + 1} } } }{ {\partial {\alpha _i} } }\\ &= {({\bf{A} }{ {\bf{x} }_{i + 1} } - {\bf{b} })^T}{ {\bf{g} }_i}\\ &= {({\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - {\bf{b} })^T}{ {\bf{g} }_i}\\ &= {({\bf{A} }{ {\bf{x} }_i} - {\bf{b} } + {\alpha _i}{\bf{A} }{ {\bf{g} }_i})^T}{ {\bf{g} }_i}\\ &= ({\bf{g} }_i^T + {\alpha _i}{\bf{g} }_i^T{\bf{A} }){ {\bf{g} }_i}\\ &= {\bf{g} }_i^T{ {\bf{g} }_i} + {\alpha _i}{\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} =0 \end{array} \tag{11}

{% endraw %}

  • получить:
альфаi=−giTgigiTAgi(12){\alpha _i} = - \frac{ { {\bf{g} }_i^T{ {\bf{g} }_i} } }{ { {\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} } } \tag{12}
следующая позиция
  • По формуле\eqref3\eqref{3}, получить следующую выбранную позициюxi+1\bf{x}_{i+1}
  • Определить текущий размер градиента, если градиент меньше определенного порогаε\varepsilonТо есть считается, что достигнуто минимальное значение:
ε≥∥gi+1∥(13)\varepsilon \ge \left\| { { {\bf{g} }_{i+1} } } \right\| \tag{13}
  • В противном случае сделайте следующий шаг вперед

анализировать

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

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

  • Прежде всего следует сказать, что этот метод является сходящимся, т. е. в рамках определяемой нами задачи он может постепенно сходиться к оптимальному решению Доказательство более сложное.Extras (2) - Скучная деривация на самом крутом спуске

  • Есть также некоторые проблемы с этим методом, поскольку моделирование слишком простое, расчетные результаты оптимального значения и реальное минимальное значение по-прежнему пропускают отклонения.

Происхождение метода сопряженных градиентов

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