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

Крок 5.

Крок 4.

Крок 3.

Крок 2.

Крок 1.

Задаються:

х ₀,

e ₃,

d

a — початкове значення кроку.

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

Перевіряється умова: . Якщо виконується, то переходимо до кроку 3, інакше дробимо значення (α = α /2) і повторюємо крок 2.

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

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

Якщо , то пошук закінчується, при цьому:

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

Рис. 2.

Алгоритм градієнтного методу з дробленням кроку

Ідея методу найшвидшого спуску

У градієнтному методі з постійним кроком величина кроку, що забезпечує убування функції f (x) від ітерації до ітерації, виявляється дуже малої, що приводить до необхідності проводити велику кількість ітерації для досягнення точки мінімуму. Тому методи спуска зі змінним кроком є більше ощадливими. Алгоритм, на кожній ітерації якого крок a_k вибирається з умови мінімуму функції f(x) у напрямку руху, тобто:

називається методом найшвидшого спуска. Зрозуміло, цей спосіб вибору a_k складніше раніше розглянутих варіантів.

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

Варто мати на увазі, що одномірну мінімізацію можна робити будь-яким методом одномірної оптимізації, що породжує різні варіанти методу найшвидшого спуска.

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