Схема методов спуска
1. Задать начальное приближение .
Для выполнить действия:
2. В точке выбрать направление спуска
.
3. Произвести выбор шага спуска .
4. Найти -ое приближение по формуле
. (5.4.2)
Релаксационные процессы.Процесс построения последовательности точек , назовем релаксационным, если
. (5.4.3)
В настоящем параграфе вопросы сходимости последовательности к минимуму функции исследуются в предположении релаксационности процесса спуска.
Выбор направления. В релаксационных методах спуска направление спуска выбирается таким образом, чтобы обеспечить возможность выполнения неравенства (5.4.3), по крайней мере, для малых значений
. Для дифференцируемой функции в некоторой окрестности точки
справедливо представление:
. (5.4.4)
Отсюда, при малых в (5.4.2), убывание функции на итерации
обеспечивается выбором направления
из условия:
. (5.4.5)
В большинстве эффективных методов спуска выбор направления связан с вычислением градиента минимизируемой функции в точке . На практике, при отсутствии процедур вычисления градиента, приходится пользоваться конечно-разностной аппроксимацией градиента по значениям функции.
Обозначим через величину косинуса угла между направлением антиградиента
, то есть направлением наискорейшего убывания функции
в точке
, и направлением спуска
в точке
.
. (5.4.6)
Условие , т.е. условие (3.2.5), является непременным условием выбора направления. При организации алгоритмов спуска на направление спуска накладывается более жесткое ограничение
, (5.4.7)
которое, в случае сильновыпуклых функций, гарантирует сходимость со скоростью геометрической прогрессии последовательности к минимуму. Если условие (5.4.7) не выполняется, то направление спуска соответствующим образом корректируется, с тем чтобы удовлетворить (5.4.7).
Выбор длины шага . С точки зрения оценок скорости сходимости методов спуска, как это мы увидим ниже, наилучшим является выбор
из условия минимума функции вдоль направления
. На практике применяют методы одномерной минимизации, гарантирующие лишь некоторую степень убывания функции
, (5.4.8)
где , при условии
, (5.4.9)
так как точное решение может оказаться неоправданно дорогим по затратам машинного времени.
В некоторых задачах минимизации условие точного одномерного спуска может ухудшить характеристики скорости сходимости процесса минимизации. Поэтому на практике проводится настройка параметров процедур одномерной минимизации на определенный класс практических задач.