Методы Оптимизации Систем Автоматизированного Проектирования

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

Стратегия поиска. Стратегия решения задачи состоит в построении последовательности точек , k=0, 1, 2, ... таких, что , k=0, 1, 2, .... Точки последовательности вычисляются по правилу:

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

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной миними-зации по t функции .

В случае функции двух переменных данный метод имеет следующую геометрическую интерпретацию: направление движения из точкикасается линии уровня в точке. Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг выбирается путем минимизации по t функции:

Необходимое условие минимума функции.Отсюда получим условие ортогональности векторов направлений спуска в соседних точках:

Алгоритм метода.
Начальный этап
Задать ,.
Найти градиент функции в произвольной точке

Положить k=0.
Основной этап
Шаг 1. Вычислить

Стр.: ..., 2, 3