Метод покоординатного спуску

Алгоритм методу найшвидшого спуску

Крок 1. Задаються

х ₀,

e.

Обчислюється градієнт , напрямок пошуку. Привласнюється k =0.

Крок 2. Визначається точка чергового експерименту:

,

де a_k — мінімум задачі одномірної мінімізації:

Крок 3. Обчислюється значення градієнта в точці х_{к +1}: .

Крок 4. Якщо , то пошук точки мінімуму закінчується й покладається:

Інакше k = k +1 і перехід до кроку 2.

Рис. 3.

Схема алгоритму методу найшвидшого спуску.

Ідея методу покоординатного спуску

Бажання зменшити об'єм обчислювальної роботи, необхідної для здійснення однієї ітерації методу найшвидшого спуска, привело до створення методів покоординатного спуску.

Нехай — початкове наближення. Обчислимо частинну похідну по першій координаті й приймемо:

де е ₁={1, 0, …, 0} ^T — одиничний вектор вісі х ¹. Наступна ітерація складається в обчисленні точки х ₂ по формулі:

де е ₂={0, 1, 0, …, 0} ^T —одиничний вектор осі х ² і т.д.

Таким чином, у методах покоординатного спуску ми спускаємося по ламаній, що складається з відрізків прямих, паралельних координатним осям.

Рис. 4.

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

Спуск по всіх координатах становить одну «зовнішню» ітерацію. Нехай k — номер чергової зовнішньої ітерації, а j -номер тієї координати, по якій відбувається спуск. Тоді формула, що визначає наступне наближення до точки мінімуму, має вигляд:

де k =0, 1, 2, …; j =1, 2, …, n.

У координатній формі формула виглядає так:

Після j = n лічильник числа зовнішніх ітерацій до збільшується на одиницю, а j приймає значення рівне одиниці.

Величина кроку a_k вибирається на кожній ітерації аналогічно тому, як це робиться в градієнтних методах. Наприклад, якщо a_k = a постійно, те маємо покоординатний спуск із постійним кроком.

Алгоритму методу покоординатного спуску зі сталим кроком

Дата добавления: 2015-05-23