5.4. АЛГОРИТМЫ ДЛЯ ЗАДАЧ БЕЗ ОГРАНИЧЕНИЙ
В последующих алгоритмах мы полагаем, что все вырабатываемые точки находятся в компактном множестве X. Это имеет место почти неизменно, и такое предположение автоматически обеспечивает выполнение условия 1 теоремы сходимости А. Ситуации, когда это предположение не выполняется, рассмотрены позже.
По существу требуется проверить лишь два условия. Во-первых, направление
должно быть направлением возрастания
если мы не находимся в подходящей точке. Во-вторых, отображение
должно быть замкнутым. Тогда вследствие замкнутости
соблюдаются все предположения теоремы сходимости А. В приводимом ниже алгоритме проверка этих двух условий осуществляется сразу.
5.4.1. Алгоритм скорейшего спуска Коши
В теореме 2.1 было показано, что если
то, выбирая
как направление для продвижения, можно добиться увеличения целевой функции. Процедура Коши построена на этой идее. В точке
определяем градиент и находим точку
максимизируя
в направлении градиента, исходящем из точки
Алгоритмическое отображение для процедуры Коши имеет вид
где
представляет собой функцию
а интервал
Часто мы выбираем величину а достаточно большой, чтобы обеспечить достижение максимума
при некотором
хотя это и не обязательно (см. упр. 13).
Теперь установим выполнение условия 2. Определим
и назовем точку х подходящей, если
Для проверки условия 2а обратите внимание на то, что если
то по теореме 2.1
и, следовательно,
Условие 26 следует непосредственно.
Теперь рассмотрим условие 3. Если предположить, что
имеет непрерывные производные, то
-непрерывная функция. Так как интервал
ограничен, из леммы 5.1 следует, что
— замкнутое отображение. Тогда согласно результатам гл. 4 А - замкнутое отображение и доказано выполнение условия 3 теоремы сходимости А.
Если предположить, что условие 1 выполняется, то сходимость установлена, так как процедура Коши удовлетворяет условиям теоремы сходимости А.