Направление спуска

редактировать

В оптимизации направление спуска - это вектор $p ∈ R n {\ displaystyle \ mathbf {p} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {p} \ in \ mathbb {R} ^ {n}}$ , что в приведенном ниже смысле приближает нас к локальному минимуму $x ∗ {\ displaystyle \ mathbf {x} ^ {*}}$ $\ mathbf {x} ^ *$ нашей целевой функции $f: R n → R {\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R} }$ $f: \ mathbb {R} ^ {n} \ to \ mathbb {R}$ .

Предположим, мы вычисляем $x ∗ {\ displaystyle \ mathbf {x} ^ {*}}$ $\ mathbf {x} ^ *$ итерационным методом, таким как поиск по строке. Мы определяем направление спуска $pk ∈ R n {\ displaystyle \ mathbf {p} _ {k} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {p} _ {k} \ in \ mathbb {R} ^ {n}}$ в точке $k {\ displaystyle k}$ $k$ th итерация должна быть любой $pk {\ displaystyle \ mathbf {p} _ {k}}$ $\ mathbf {p} _ {k}$ такой, что $⟨pk, ∇ f (xk) ⟩ < 0 {\displaystyle \langle \mathbf {p} _{k},\nabla f(\mathbf {x} _{k})\rangle <0}$ ${\ displaystyle \ langle \ mathbf {p} _ {k}, \ nabla f (\ mathbf {x} _ {k}) \ rangle <0}$ , где $⟨,⟩ {\ displaystyle \ langle, \ rangle}$ ${\ displaystyle \ langle, \ rangle}$ обозначает внутренний продукт. Мотивация для такого подхода заключается в том, что небольшие шаги по $pk {\ displaystyle \ mathbf {p} _ {k}}$ $\ mathbf {p} _ {k}$ гарантируют, что $f {\ displaystyle \ displaystyle f}$ $\ displaystyle f$ сокращается по теореме Тейлора.

Используя это определение, отрицательное значение ненулевого градиента всегда является направлением спуска, так как $⟨- f (xk), ∇ f (xk) ⟩ = - ⟨∇ f (xk), ∇ f (xk)⟩ < 0 {\displaystyle \langle -\nabla f(\mathbf {x} _{k}),\nabla f(\mathbf {x} _{k})\rangle =-\langle \nabla f(\mathbf {x} _{k}),\nabla f(\mathbf {x} _{k})\rangle <0}$ ${\ displaystyle \ langle - \ nabla f (\ mathbf {x} _ {k}), \ nabla f (\ mathbf {x} _ {k}) \ rangle = - \ langle \ nabla f (\ mathbf {x} _ {k}), \ nabla f (\ mathbf {x} _ {k}) \ rangle <0}$ .

Существует множество методов вычисления направлений спуска, все с разными достоинствами. Например, можно использовать градиентный спуск или метод сопряженного градиента.

В более общем случае, если $P {\ displaystyle P}$ $P$ является положительным определенная матрица, тогда $pk = - P ∇ f (xk) {\ displaystyle p_ {k} = - P \ nabla f (x_ {k})}$ ${\ displaystyle p_ {k} = - P \ nabla f (x_ {k})}$ - направление спуска в $хк {\ displaystyle x_ {k}}$ $x_ {k}$ . Эта универсальность используется в методах предварительно обусловленного градиентного спуска.

См. Также

Производная по направлению

Ссылки