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

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

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

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

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

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

 x^{k+1} = x^k - t(x^k) \cdot \nabla f (x^k) . (1)

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

 \min_t f\left(x^k - t \nabla f (x^k)\right) = f\left(x^k - t(x^k)\nabla f(x^k)\right). (2)

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

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

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

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

H(x) = \left\{ \frac{\partial^2F}{\partial x_i \partial x_j} \right\}^n_{i,j=1},

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

\sum_{i=1}^n (x_i^{k+1} - x_i^*) \leq q \sum_{i=1}^n(x_i^k - x_i^*)^2 при kN,

де

 q = \frac{M(x^*) - m(x^*)}{M(x^*) + m(x^*)} < 1 ,

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

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

 x^{k+1} = x^k - \tau \nabla f (x^k). (3)

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

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

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