Найшвидшого спуску метод

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

Найшвидшого спуску метод — метод мінімізації функції f(x) на всьому просторі Rn.

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

Метод полягає в побудові послідовності {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).

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

[ред.] Дивіться також


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