Умови Вольфе

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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 \alpha _{k}}$ лежати близько до критичної точки $\varphi$.

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

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

$\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 \nabla f(\mathbf {x} _{k})\rightarrow 0}$.

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