Метод найшвидшого спуску

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

Метод найшвидшого спуску (градієнтний метод) — ітераційний метод пошуку локального мінімуму функції багатьох змінних f(x). Метод полягає в кроковому переміщенні в напрямі оберненому до градієнту функції в актуальній точці на відстань пропорційну величині цього градієнта.

Опис методу[ред.ред. код]

Геометричне представлення методу в . Синім кольором показані лінії рівня функції.

Метод полягає в побудові послідовності {xk} за формулою:

. (1)

де ∇ f(xk) — градієнт функції f(x) в точці xk, а t(xk) вибирається виходячи із умови:

. (2)

Вперше метод був запропонований французьким математиком Оґюстеном Коші. Широке застосування цього методу обумовлено тим, що в напряму антиградієнту — ∇ f(x) похідна функції за напрямом досягає найменшого значення.

Якщо градієнт ∇ f(x) неперервний по x а f(x) → ∞ при x → ∞, то при довільному початковому наближенні ∇ f(xk) → 0 при k→ ∞. Якщо при цьому x* — єдина стаціонарна точка, то xkx*, де f(x*) = minxf(x).

Якщо f(x) неопукла і стаціонарних точок декілька, то послідовність {xk} може, взагалі кажучи, не сходитись навіть до локального екстремуму функції f(x).

Нехай існує матриця Гессе

,

додатньо визначена в кожній точці x. Тоді для послідовності (1) xkx*, та, починаючи з деякого номеру N, виконується нерівність

при kN,

де

,

xkii-та координата xk, M(x*) та m(x*) — відповідно найбільше та найменше власні значення матриці H(x*).

Існує модифікація методу, коли t(xk) = τ > 0 — const, тобто

. (3)

Якщо градієнт ∇ f(x) задовольняє умові Ліпшиця, то для послідовності (3) при виконанні перелічених припущень вірні відповідні властивості послідовності (1).

Джерела інформації[ред.ред. код]

Див. також[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.