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

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

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

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

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

Положить k=0.
Основной этап
Шаг 1. Вычислить
Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3.
Шаг 3. Задать величину шага
Шаг 4. Вычислить
Шаг 5. Проверить выполнение условия
а) если условие выполнено, то положить k= k +1 и перейти к шагу 1.
б) если условие не выполнено, то положить и перейти к шагу 4.

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