Умови Вольфе

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

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

$\underset{x}{\min }f(𝐱)$

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

$\underset{\alpha }{\min }f({𝐱}_k+\alpha {𝐩}_k)$

де ${𝐱}_k$ - це найкраща поточна апроксимація, ${𝐩}_k\in {ℝ}^n$ няпрямок пошуку і $\alpha \in ℝ$ довжина кроку.

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

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

Довжина кроку $a_k$ відповідає умовам Вулфа, обмеженим напрямком ${𝐩}_k$, якщо мають місце дві нерівності:

$\begin{array}{cc}\mathbf{\text{i)}}& f({𝐱}_k+{\alpha }_k{𝐩}_k)\le f({𝐱}_k)+c_1{\alpha }_k{𝐩}_k^{\mathrm{T}}\mathrm{\nabla }f({𝐱}_k),\\ \mathbf{\text{ii)}}& {-𝐩}_k^{\mathrm{T}}\mathrm{\nabla }f({𝐱}_k+{\alpha }_k{𝐩}_k)\le -c_2{𝐩}_k^{\mathrm{T}}\mathrm{\nabla }f({𝐱}_k),\end{array}$

із $0<c_1<c_2<1$ (В умові (ii), завуважте, щоб ${𝐩}_k$ був напрямком спуску, ми маємо ${𝐩}_k^{\mathrm{T}}\mathrm{\nabla }f({𝐱}_k)<0$, як у випадку спуску градієнта, де ${𝐩}_k=-\mathrm{\nabla }f({𝐱}_k)$, або Ньютон – Рафсон, де ${𝐩}_k=-{𝐇}^{-1}\mathrm{\nabla }f({𝐱}_k)$ де $𝐇$ позитивно визначена.)

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

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

Позначимо одновимірну функцію $\phi$ обмеженою в напрямку ${𝐩}_k$ як $\phi (\alpha )=f({𝐱}_k+\alpha {𝐩}_k)$. Умови Вулфа можуть призвести до значення довжини кроку, не близького до мінімізатора $\phi$. Якщо ми змінимо умову кривизни на наступне,

$\mathbf{\text{iii)}}|{𝐩}_k^{\mathrm{T}}\mathrm{\nabla }f({𝐱}_k+{\alpha }_k{𝐩}_k)|\le c_2|{𝐩}_k^{\mathrm{T}}\mathrm{\nabla }f({𝐱}_k)|$

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

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

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

$\cos {\theta }_k=\frac{\mathrm{\nabla }f({𝐱}_k{)}^{\mathrm{T}}{𝐩}_k}{\Vert \mathrm{\nabla }f({𝐱}_k)\Vert \Vert {𝐩}_k\Vert }$

обмежений від нуля, а умови i) та ii) виконуються, тоді $\mathrm{\nabla }f({𝐱}_k)\to 0$.

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