Градиентные методы (методы первого порядка)

1 2 3 4 5

1. Градиентные методы (методы первого порядка).

Как мы знаем, градиент в точке направлен в сторону наибольшего возрастания функции и ортогонален линии уровня в точке .

Вектор - антиградиент, направлен в сторону наибольшего убывания .

Выберем в качестве направления антиградиент в точке и придем к алгоритму:

(5)

в координатной форме

(6)

Методы (5) и (6) называют градиентными методами, и они отличаются друг от друга способами выбора шага . Таких способов существует много, но наиболее распространены 2:

1. Метод с дроблением шага, связан с проверкой на каждой итерации некоторого неравенства.

2. Метод, в котором при переходе от к функция - метод наискорейшего спуска.

Метод с дроблением шага.

Рассмотрим процесс (5). Как выбрать шаг ? Малый шаг обеспечит убывание функции

Но приводит к большому числу операций. Но большой шаг может вызвать неожиданно большой рост функции, либо приводит к колебаниям(цикл).

Рассмотрим пример:

При - процесс сходится

При - процесс расходится

При , то , , - процесс зацикливается.

В методах с дроблением шага выбирается так, чтобы выполнялось неравенство

, (7)

где , т.е. функция должна убывать на каждом шаге.

Делают так: выбирают и на k-й итерации проверяют выполнение (7). Если оно выполняется, то . Если нет, то шаг дробят до тех пор пока оно не выполнится.