Крок 4

Крок 3.

Крок 2.

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

,

або, у координатній формі:

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

або, у координатній формі:

.

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

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

Рис. 1.

Схема алгоритму градієнтного методу з постійним кроком

1.2.3. Градієнтний метод із дробленням кроку

У методі градієнтного спуску із дробленням кроку величина кроку a_k вибирається так, щоб була виконана нерівність:

,

де 0< d <1 — довільно обрана постійна (та сама для всіх ітерацій). Це вимога на вибір кроку a_k більше твердого, чим умова убування, але має той же зміст: функція повинна убувати від ітерації до ітерації. Однак при виконанні нерівності функція буде зменшуватися на гарантовану величину, обумовлену правою частиною нерівності.

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

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

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