Умови Вольфе

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Для певної гладкої функції Кожен крок часто включає наближене вирішення підпроблеми

де - це найкраща поточна апроксимація, няпрямок пошуку і довжина кроку.

Приблизний лінійний пошук забезпечує ефективний спосіб обчислення прийнятної довжини кроку , що знижує цільову функцію "достатньо", а не мінімізує ЇЇ на . Алгоритм лінійного пошуку може використовувати умови Вулфа як вимогу для будь-якої апроксимації , перш ніж знайти новий напрямок пошуку .

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

[ред. | ред. код]

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

із (В умові (ii), завуважте, щоб був напрямком спуску, ми маємо , як у випадку спуску градієнта, де , або Ньютон – Рафсон, де де позитивно визначена.)

зазвичай обирається зовсім невеликим, тоді як значно більший; Nocedal і Wright[1] дають приклади значень і для методів Ньютона або квазі-Ньютона і для нелінійного методу градієнта спряжених. Нерівність i) відома як правило Армійо[2] та ii) як умова кривизни; i) гарантує, що довжина кроку зменшує 'достатньо', і ii) забезпечує зменшення нахилу в достатній мірі. Умови i) та ii) можуть бути інтерпретовані відповідно до надання верхньої та нижньої меж допустимих значень довжини кроку.

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

[ред. | ред. код]

Позначимо одновимірну функцію обмеженою в напрямку як . Умови Вулфа можуть призвести до значення довжини кроку, не близького до мінімізатора . Якщо ми змінимо умову кривизни на наступне,

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

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

[ред. | ред. код]

Основна причина накладення умов Вульфа в алгоритмі оптимізації, де забезпечить збіжність градієнта до нуля. Зокрема, якщо косинус кута між та градієнтом,

обмежений від нуля, а умови i) та ii) виконуються, тоді .

Додатковою мотивацією у випадку квазі-Ньютонського методу є те, що якщо , де матриця оновлюється формулою BFGS або DFP, тоді якщо є позитивно визначеною ii) означає також є позитивно визначеню.

Посилання

[ред. | ред. код]
  1. Nocedal, Jorge Wright, Stephen J., 1960- (1999). Numerical optimization. Springer. ISBN 0-387-98793-2. 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.