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

Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3.
Шаг 3. Вычислить величину шагаиз условия

Шаг 4. Вычислить
Шаг 5. Положить k= k +1 и перейти к шагу 1

Сходимость метода.

Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на, а ее градиент удовлетворяет условию Липшица

Тогда при произвольной начальной точке для метода наискорейшего градиентного спуска с постоянным шагом имеем

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

где M и m – оценки наибольшего и наименьшего собственных значений матрицы Гессе H(x) функции f(x).

Пример.

Решение.

Итерация 0.

Итерация 1.

Стр.: 1, ..., 3