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

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

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

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

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

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

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

$\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(x^k) → 0 при k→ ∞. Якщо при цьому x^* — єдина стаціонарна точка, то x^k → x^*, де f(x^*) = min_xf(x).

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

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

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

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

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

де

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

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

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

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

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