Умови Вольфе

У необмеженій проблемі мінімізації умови Вулфа - це сукупність нерівностей для здійснення приблизного пошуку ліній, особливо у квазі-Ньютонових методах, вперше опублікованих Філіпом Вулфом у 1969 році.

У цих методах головна ідея - це знайти

${\displaystyle \min _{x}f({\mathbf {x} })}$

Для певної гладкої функції ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} .}$ Кожен крок часто включає наближене вирішення підпроблеми

${\displaystyle \min _{\alpha }f({\mathbf {x} }_{k}+\alpha {\mathbf {p} }_{k})}$

де ${\displaystyle {\displaystyle \mathbf {x} _{k}}}$ - це найкраща поточна апроксимація, ${\displaystyle {\displaystyle \mathbf {p} _{k}\in \mathbb {R} ^{n}}}$ няпрямок пошуку і ${\displaystyle {\displaystyle \alpha \in \mathbb {R} }}$ довжина кроку.

Приблизний лінійний пошук забезпечує ефективний спосіб обчислення прийнятної довжини кроку ${\displaystyle {\alpha }}$, що знижує цільову функцію "достатньо", а не мінімізує ЇЇ на ${\displaystyle {\displaystyle \alpha \in \mathbb {R} ^{+}}}$. Алгоритм лінійного пошуку може використовувати умови Вулфа як вимогу для будь-якої апроксимації ${\displaystyle {\alpha }}$, перш ніж знайти новий напрямок пошуку ${\displaystyle {\displaystyle \mathbf {p} _{k}}}$.

Правило Армійо і кривизна

Довжина кроку ${\displaystyle {a_{k}}}$ відповідає умовам Вулфа, обмеженим напрямком ${\displaystyle {\displaystyle \mathbf {p} _{k}}}$, якщо мають місце дві нерівності:

${\displaystyle {\displaystyle {\begin{aligned}{\textbf {i)}}&\quad f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq f(\mathbf {x} _{k})+c_{1}\alpha _{k}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),\\[6pt]{\textbf {ii)}}&\quad {-\mathbf {p} }_{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq -c_{2}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),\end{aligned}}}}$

із ${\displaystyle {\displaystyle 0<c_{1}<c_{2}<1}}$ (В умові (ii), завуважте, щоб ${\displaystyle \mathbf {p} _{k}}$ був напрямком спуску, ми маємо ${\displaystyle {\displaystyle \mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})<0}}$, як у випадку спуску градієнта, де ${\displaystyle {\displaystyle \mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}}$, або Ньютон – Рафсон, де ${\displaystyle {\displaystyle \mathbf {p} _{k}=-\mathbf {H} ^{-1}\nabla f(\mathbf {x} _{k})}}$ де ${\displaystyle {\displaystyle \mathbf {H} }}$ позитивно визначена.)

${\displaystyle c_{1}}$зазвичай обирається зовсім невеликим, тоді як ${\displaystyle c_{2}}$ значно більший; Nocedal і Wright дають приклади значень ${\displaystyle {\displaystyle c_{1}=10^{-4}}}$ і ${\displaystyle {\displaystyle c_{2}=0.9}}$ для методів Ньютона або квазі-Ньютона і ${\displaystyle {\displaystyle c_{2}=0.1}}$ для нелінійного методу градієнта спряжених. Нерівність i) відома як правило Армійо та ii) як умова кривизни; i) гарантує, що довжина кроку ${\displaystyle {\alpha _{k}}}$ зменшує ${\displaystyle f}$ 'достатньо', і ii) забезпечує зменшення нахилу в достатній мірі. Умови i) та ii) можуть бути інтерпретовані відповідно до надання верхньої та нижньої меж допустимих значень довжини кроку.

Сильний умови Вулфа на кривизні

Позначимо одновимірну функцію ${\displaystyle {\displaystyle \varphi }}$ обмеженою в напрямку ${\displaystyle {\displaystyle \mathbf {p} _{k}}}$ як ${\displaystyle {\displaystyle \varphi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}}$. Умови Вулфа можуть призвести до значення довжини кроку, не близького до мінімізатора ${\displaystyle \varphi }$. Якщо ми змінимо умову кривизни на наступне,

${\displaystyle {\displaystyle {\textbf {iii)}}\quad {\big |}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}){\big |}\leq c_{2}{\big |}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}){\big |}}}$

то i) та iii) разом утворюють так звані сильні умови Вулфа і змушують ${\displaystyle {\displaystyle \alpha _{k}}}$ лежати близько до критичної точки ${\displaystyle \varphi }$.

Обґрунтування

Основна причина накладення умов Вульфа в алгоритмі оптимізації, де ${\displaystyle {\mathbf {x} }_{k+1}={\mathbf {x} }_{k}+\alpha {\mathbf {p} }_{k}}$ забезпечить збіжність градієнта до нуля. Зокрема, якщо косинус кута між ${\displaystyle {\displaystyle \mathbf {p} _{k}}}$ та градієнтом,

${\displaystyle \cos \theta _{k}={\frac {\nabla f({\mathbf {x} }_{k})^{\mathrm {T} }{\mathbf {p} }_{k}}{\|\nabla f({\mathbf {x} }_{k})\|\|{\mathbf {p} }_{k}\|}}}$

обмежений від нуля, а умови i) та ii) виконуються, тоді ${\displaystyle {\displaystyle \nabla f(\mathbf {x} _{k})\rightarrow 0}}$.

Додатковою мотивацією у випадку квазі-Ньютонського методу є те, що якщо ${\displaystyle {\displaystyle \mathbf {p} _{k}=-B_{k}^{-1}\nabla f(\mathbf {x} _{k})}}$, де матриця ${\displaystyle B_{k}}$ оновлюється формулою BFGS або DFP, тоді якщо ${\displaystyle B_{k}}$ є позитивно визначеною ii) означає ${\displaystyle B_{k+1}}$ також є позитивно визначеню.

Посилання

1. Nocedal, Jorge Wright, Stephen J., 1960- (1999). Numerical optimization. Springer. ISBN . OCLC 896912768.
2. Armijo, Larry (1966). Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, A Non-profit Corporation. OCLC 670687888.