Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Градієнтний спуск



План:


Введення

Градієнтний спуск - метод знаходження локального мінімуму ( максимуму) функції за допомогою руху уздовж градієнта. Для мінімізації функції в напрямку градієнта використовуються методи одновимірної оптимізації, наприклад, метод золотого перерізу. Також можна шукати не найкращу точку в напрямку градієнта, а яку-небудь краще поточної.

Збіжність методу градієнтного спуску залежить від ставлення максимального і мінімального власних чисел матриці Гессе в околиці мінімуму (максимуму). Чим більше це відношення, тим гірше збіжність методу.


1. Опис

Ілюстрація послідовних наближень до точки екстремуму в напрямі найшвидшого спуску (червоне) в разі дробового кроку. Синім позначені лінії рівня.

Нехай цільова функція має вигляд:

F (\ vec {x}): \; \ mathbb {X} \ to \ mathbb {R} .

І завдання оптимізації задана наступним чином:

F (\ vec {x}) \ to \ min_ {\ vec {x} \ in \ mathbb {X}} \!

Основна ідея методу полягає в тому, щоб йти в напрямку найшвидшого спуску, а цей напрямок задається анти градієнтом - \ Nabla F :

\ Overrightarrow {x} ^ {[j +1]} = \ overrightarrow {x} ^ {[j]} - \ lambda ^ {[j]} \ nabla F (\ overrightarrow {x} ^ {[j]}) \!

де λ [j] вибирається

  • постійною, в цьому випадку метод може розходитися;
  • дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
  • порад задля спуском: \ Lambda ^ {[j]} = \ mathrm {argmin} _ {\ lambda} \, F (\ vec {x} ^ {[j]} - \ lambda ^ {[j]} \ nabla F (\ vec { x} ^ {[j]})) \!

1.1. Алгоритм

  1. Задають початкове наближення і точність розрахунку \ Vec {x} ^ 0, \ quad \ varepsilon
  2. Розраховують \ Overrightarrow {x} ^ {[j +1]} = \ overrightarrow {x} ^ {[j]} - \ lambda ^ {[j]} \ nabla F (\ overrightarrow {x} ^ {[j]}) \! , Де \ Lambda ^ {[j]} = \ mathrm {argmin} _ {\ lambda} \, F (\ vec {x} ^ {[j]} - \ lambda ^ {[j]} \ nabla F (\ vec { x} ^ {[j]})) \!
  3. Перевіряють умова зупинки:
    • Якщо | \ Vec {x} ^ {[j +1]} - \ vec {x} ^ {[j]} |> \ varepsilon \! або | F (\ vec {x} ^ {[j +1]})-F (\ vec {x} ^ {[j ]})|> \ varepsilon \! (Вибирають одну з умов), то j = j + 1 і перехід до кроку 2.
    • Інакше \ Vec {x} = \ vec {x} ^ {[j +1]} \! і зупинка.

1.2. Приклад

Застосуємо градієнтний метод до функції F (x, y) = \ sin \ left (\ frac {1} {2} x ^ 2 - \ frac {1} {4} y ^ 2 + 3 \ right) \ cos (2 x +1- e ^ y) . Тоді послідовні наближення будуть виглядати так:

Градієнтний метод у дії. Ілюстрація для ліній однакового рівня. Градієнтний метод у дії. Ілюстрація для поверхні.


1.3. Удосконалення

Метод градієнтного спуску виявляється дуже повільним при русі вздовж яру (див. яружний функції). Прикладом такої функції є функції Розенброка. Більш ефективним вважається метод спряжених градієнтів.


Цей текст може містити помилки.

Схожі роботи | скачати
© Усі права захищені
написати до нас
Рейтинг@Mail.ru