10.2. АЛГОРИТМ ЛАГРАНЖА

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

Предположения о седловой точке. Как было показано в теореме 2.18, если функция Лагранжа обладает седловой точкой , то х решает задачу (10.1). Метод Лагранжа предполагает, что такая

седловая точка существует. В явной форме это означает существование точки , удовлетворяющей условиям

Кроме того, предполагается, что существует единственная точка которая решает задачу (10.6). Тогда

(Простое условие, гарантирующее выполнение этого предположения, приведено в упр. 8.)

Если определим множество — седловая точка для то будет множеством всех , для которых является седловой точкой. По предположению не пусто, однако, кроме того, предполагаем, что компактно. Несмотря на то, что обычно компактно, в следующей лемме даны условия, обеспечивающие выполнение этого требования.

Лемма 10.1. Пусть существует точка для которой тогда компактно.

Доказательство. По определению седловой точки для любой

Из того, что следует, что

Но так как

т. е. все компоненты ограничены.

Теперь мы замкнутость множества Пусть где Должо быть установлено, что По определению седловой точки для любых

Переходя к пределу в (10.8), получаем

Поэтому замкнуто и ограничено. Лемма доказана.

Алгоритмическое отображение. Теперь определим алгоритмическое отображение. Пусть

является градиентом по х, а

— градиентом по X. Тогда по данному алгоритмическое отображение дает с помощью уравнений

где — параметр, указывающий длину шага, представляет собой фиксированную скалярную величину, которая будет определена далее. Операция в (10.12) является покомпонентной операцией, т. е. согласно (10.12)

Обратите внимание на то, что для определения алгоритмического отображения требуется как х, так и Я. Следовательно, и алгоритмическое отображение представляет собой функцию

Функция Мы определяем функцию следующим образом:

Иначе говоря, определяется как расстояние между и ближайшей седловой точкой . Заметим, что из теоремы 7.1 и компактности следует, что минимум достигается, а согласно теореме 7.2 функция непрерывна (см. упр. 6). Так как значения функции представляет собой расстояние, то множества

компактны для любых положительных у и (см. упр. 7),

Подходящая точка. Точка называется подходящей, если для данного

Таким образом, является подходящей точкой, если расстояние между точкой х и оптимальной точкой х не превышает .

Если точка окажется подходящей, то алгоритм завершает поиск.

Выбор в алгоритмическом отображении. После того как определены понятия подходящей точки и функции можно дать определение параметра в алгоритмическом отображении.

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

Согласно (10.14) множества, по которым выполняется минимизация, являются компактными, при этом полезно заметить, что требование обеспечивает неравенство

На основе непрерывной дифференцируемости функций функция в (10.16) является непрерывной. Как показывает следующая лемма, она также положительна во всех точках. Тогда из следствия 2.1.1 получаем, что

Лемма 10.2. Пусть и вогнуты и непрерывно дифференцируемы. Тогда

Доказательство. Согласно вогнутости по х

Из а по определений функцйй Лагранжа

Но тогда комбинация соотношений (10.19) и (10.20) дает

По определению седловой точки и по (10.7), если то

Наконец, из (10.21) и (10.22) получаем

Доказательство сходимости. Теперь установим сходимость процедуры Лагранжа, используя теорему сходимости А. Для полноты мы вкратце приведем все предположения, которые требуются для сходимости. Функции и вогнуты и непрерывно дифференцируемы. Существует седловая точка единственно. Кроме того, компактно. Теперь будет доказана сходимость.

Условие 3. Условие 3 следует непосредственно, так как алгоритмическое отображение является непрерывной функцией.

Условие 2. Для того чтобы доказать выполнение условия 2, требуются некоторые предварительные рассмотрения.

Обозначим

Возводя в квадрат (10.12), получаем

Кроме того, из (10.12), учитывая, что имеем

Далее, используя (10.23) и (10.24), после небольших преобразований приходим к

Точно так же, как (10.25) было получено из (10.12), из (10.11) мы можем получить соотношение

Складывая (10.25) и (10.26), получаем

Теперь уже мы можем установить выполнение условия 2. Заметим, что в данном случае необходимо убедиться в справедливости неравенства Пусть не является подходящей точкой. Анализируя (10.27) и определение видим, что для того, чтобы доказать неравенство необходимо лишь установить

Учитывая (10.17) и то, что точка не является подходящей, получаем

Теперь с помощью определения видим, что левая часть (10.28) больше, чем

где последнее неравенство следует из леммы 10.2. Таким образом, установлена справедливость (10.28), а значит, и выполнение условия 2а (см. упр. 12),

Выполнение условия 26 следует сразу же, так как, если является подходящей точкой, то алгоритм завершает поиск.

Итак, выполнение условия 2 установлено

Условие 1. Заметим, что условие 2 дает Тогда согласно (10.14) все входят в компактное множество и, следовательно, условие I также выполняется. Итак, алгоритм сходится.

Замечания. Необходимо отметить, что из того, как определено — длина шага, возникает следующий вопрос. Параметр определяется через решение, с другой стороны, цель алгоритма заключается в определении этого решения. Здесь можно привести следующее обоснование. Если дано то существует для которого алгоритм сходится. Вычисление точного значения невозможно. При выполнении расчетов по этому алгоритму варьируется для того, чтобы достигнуть «хорошего» значения. Выяснение того, когда является подходящей точкой, также может оказаться нелегкой задачей.

В большинстве предшествовавших алгоритмов трудной частью было доказательство условия замкнутости, условия 3. Обычно выполнение условия 2 вытекало непосредственно. Для алгоритма Лагранжа имеет место противоположная ситуация. Справедливость условия 3 была установлена быстро, тогда как проверка условия

2 потребовала скрупулезного рассмотрения. Одной из причин этого отличия является то, что в методе Лагранжа ищется седловая точка; таким образом, мы решаем задачу на . С другой стороны, большинство рассмотренных алгоритмов решает чистую задачу на максимум и целевая функция, так как она всегда возрастает, может быть использована как функция . В методе Лагранжа функцией, которую следовало бы рассматривать в качестве функции является сама функция Лагранжа. Но вследствие особенностей операции функция Лагранжа как возрастает, так и убывает и не может быть использована в качестве функции Вместо нее приходится использовать сложную функцию основанную на расстоянии до седловой точки. Поэтому проверка выполнения условия 2, которая требует, чтобы мы все ближе и ближе подходили к седловой точке, была сравнительно трудной.

Можно также отметить, что для этого алгоритма мы доказали выполнение условия 1, условия компактности.

В большинстве предшествовавших алгоритмов выполнение условия 1 не доказывалось, а предполагалось. Это объясняется тем, что в предыдущих алгоритмах постулирование условия 1 является геометрически обоснованным. Достаточно беглого рассмотрения, чтобы видеть, что такие алгоритмы, за исключением необычных ситуаций, должны вырабатывать точки, входящие в компактное множество. К сожалению, для метода Лагранжа нелегко получить такое геометрическое представление. Поэтому мы привели математическое доказательство справедливости условия 1. Ситуации, когда компактность не имеет места, рассмотрены в гл. 11.