11.3. ТЕОРЕМЫ СХОДИМОСТИ

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

Очевидно, определяет расстояние от точки до ближайшей точки множества подходящих точек . В следующей лемме даны два важных свойства функции

Лемма 11.1. Пусть Тогда непрерывна и б) если — замкнутое множество, то тогда и только тогда, когда

Доказательство. Сначала будет доказано утверждение (а). Пусть

Для любого

Поскольку —произвольная точка,

откуда

Итак,

Аналогично

и согласно (11.3) и (11.4)

Воспользовавшись (11.1), приходим к выводу, что для данного существует такое Р, что при

Поэтому для

Другими словами,

что подтверждает

Теперь рассмотрим Ясно, что если то Допустим По определению существует последовательность которая сходится к точке Тогда благодаря замкнутости так как для всех к, то Лемма доказана.

Функция играет важную роль в доказательстве необходимости. Рассмотрим последовательность точек в свете одного аспекта этого доказательства. Последовательность должна обладать тем свойством, что предел любой сходящейся подпоследовательности является подходящей точкой.

Как показывает следующая лемма, при этих условиях Иначе говоря, с увеличением к точка становится все ближе и ближе к множеству

Лемма 11.2. Пусть последовательность

содержится в компактом множестве. Предположим, что для любого К, если то

Определим

Тогда

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

Учитывая, что непрерывность была установлена леммой 11.1, получаем

Отсюда, так как любая подпоследовательность обладает подпоследовательностью, которая сходится к нулю, то вся последовательность должна сходиться к нулю. Этим завершается доказательство леммы.

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

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

Здесь число может зависеть от и Если выразить это положение словами, то в любой итерации, следующей после итераций за итерацией, функция должна быть по крайней мере так же велика, как и на итерации. Таким образом, после итерации в течение итераций допускается убывание функции но

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

В качестве примера примем Пусть для всех тогда требование возрастания функции удовлетворяется. Обратите внимание на то, что но Таким образом, для

Но для всех

Интуитивно требование улучшаемости сводится к тому, чтобы последовательность имела общую тенденцию к возрастанию. Это требование слабее, чем требование монотонного и строгого возрастания последовательности, имеющееся в теореме сходимости А.

Следующая лемма также способствует разъяснению требования улучшаемости. Она обобщает лемму 4.1 и доказывается аналогично.

Лемма 11.3. Пусть — непрерывная функция Предположим, что для любого существует такое положительное целое число что если то

Кроме того, допустим также, что для некоторой подпоследовательности

При этих предположениях

Доказательство. Для упрощения обозначения положим

Из непрерывности имеем

Тогда для заданного существует такое целое число Р, что если для для то

Выберем некоторое такое, что где и определим На основе (11.7) для любого

Теперь для любых заданных опять же по (11.7)

Отсюда, принимая во внимание (11.12) имеем

Но если мы перейдем к пределу в (11.15) при то из (11.11) получим

Итак, согласно (11.16) для любого заданного при имеем

А это есть не что иное, как определение сходимости. Лемма доказана.

Замкнутости алгоритмического отображения не требуется. Приведенное обсуждение показывает, как в теореме сходимости С будет обобщено условие 2а теоремы сходимости А—требование улучшаемости. Остается только рассмотреть, как можно было бы исключить требование замкнутости отображения — условие 3 теоремы сходимости А. Новое условие, налагаемое теоремой сходимости С, в основном сводится к следующему. Предположим, что

где не является подходящей точкой.

Тогда должна существовать другая подпоследовательность такая, что

Каким образом это условие исключает требование замкнутости отображения? Допустим, что выполняются предположения теоремы сходимости А. Затем предположим, что где не является подходящей точкой. Тогда согласно теореме сходимости А должна существовать другая подпоследовательность, а именно

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

Но тогда условие 2а влечет

Ясно, что (11.17) и (11.19) совпадают. Значит, теорема сходимости А приводит к такому же результату, что и теорема сходимости С. Короче говоря, теорема сходимости С оставляет в силе сущность требования замкнутости отображения, в частности, соотношение (11.19), не требуя самой замкнутости отображения.

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

Рассмотрим следующие условия 1 и 2:

Условие 1.

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

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

Условие 2. Пусть алгоритм вырабатывает бесконечную последовательность точек, ни одна из которых не является подходящей, и все точки входят в компактное множество для всех Тогда существует непрерывная функция удовлетворяющая требованиям:

а) для любого заданного существует такое что для всех

б) для любой сходящейся подпоследовательности если не является подходящей точкой, то или

1) существует такое что или

2) существует сходящаяся подпоследовательность такая, что

Любой алгоритм,, который удовлетворяет условиям 1 и 2, удовлетворяет определению сходимости. При этом, если замкнуто, то любой алгоритм, который сходится в соответствии с определением сходимости, удовлетворяет условиям 1 и 2.

Доказательство.

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

Очевидно, чтоусловие 1а и часть определения сходимости (а) совпадают.

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

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

Допустим, что не является подходящей точкой и покажем, что это допущение приводит к противоречию. Доказательство будет проведено лишь для части (2) условия 26, так как доказательство для части (1) аналогично.

Из леммы 11.3 и условия 2а следует:

Воспользовавшись условием 26, часть (2), находим, что имеется такое К, что справедливо выражение (11.20). Тогда на основе компактности можем найти такое что где вследствие непрерывности

Но согласно лемме Следовательно, из выражения (11.21) получаем

Но из условия 2б, часть (2), и (11.22) имеем

Так как выражения (11.23) и (11.24) противоречат друг другу, то должна быть подходящей точкой.

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

Из части (а) определения сходимости вытекает условие 1а.

Допустим, что выработана бесконечная последовательность точек, ни одна из которых не является подходящей. Согласно части (б) определения сходимости при все точки входят в некоторое компактное множество Условие 16 выполнено.

Остается доказать выполнение условия 2. Пусть все точки входят в некоторое компактное множество, но ни одна из них не является подходящей. Определим функцию

где определяется леммой 11.1. Из этой леммы следует, что — непрерывная функция и что

так как замкнуто.

Рассмотрим последовательность Заметим, что

б) все входят в некоторое компактное множество,

в) из по определению сходимости вытекает, что и значит на основе выражения

Учитывая пункты и леммы 11.2, мы убеждаемся в том, что

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

Но согласно (11.27) существует такое, что при

Справедливость условия 2а установлена.

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

Замечания. Любой алгоритм, который удовлетворяет условиям 1 и 2 теоремы сходимости С, сходится в том смысле, что он удовлетворяет определению сходимости. Наоборот, любой алгоритм, который сходится в смысле определения сходимости, удовлетворяет условиям 1 и 2 теоремы.

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

Условие 16 относится к случаю, когда вырабатывается бесконечная последовательность точек, ни одна из которых не является подходящей (в противном случае могло бы быть применено условие 1а). По существу, условие 16 требует, чтобы все точки входили в компактное множество, если

Условие 2 предполагает, что все точки входят в некоторое компактное множество. Следовательно, когда нужно доказать, что алгоритм удовлетворяет условию 2, мы можем предположить, что алгоритм вырабатывает точки, входящие в некоторое компактное множество. Можно надеяться, что это предположение упростит задачу, когда необходимо доказать, что алгоритм удовлетворяет этому условию.

Чтобы установить выполнение условия 2, мы должны найти для алгоритма соответствующую функцию непрерывна и удовлетворяет условиям 2а и 2б.

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

Отметим, что алгоритму необходимо удовлетворять условию 2б лишь в том случае, когда он вырабатывает бесконечную последовательность точек, ни одна из которых не является подходящей. При этом алгоритм должен удовлетворять условию 2б только в случае, если не является подходящей точкой. Если уже подходящая точка, то условие 2б снимается автоматически. Более того, алгоритм должен удовлетворять лишь одной из двух частей условия 2б: (1) или (2).

Часть (2), как отмечалось выше, представляет собой условие, которое заменяет предположение о замкнутости отображения. Часть -аналогичное условие, которое также отражает необходимость в требовании замкнутости отображения.

Сформулируем еще одну заключительную теорему сходимости, имеющую цель избежать предположения относительно компактности.

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

Предположим, что выполняются следующие условия:

Условие 1. Если то либо — подходящая точка, либо

Условие 2. Существует непрерывная функция удовлетворяющая требованиям:

а. Для любой заданной точки существует такое что для всех если существует то она удовлетворяет условию

Если существует сходящаяся подпоследовательность такая, что не является подходящей точкой, то либо

1) имеется такое что либо

2) существует сходящаяся подпоследовательность такая, что

При этих условиях, если алгоритм завершает поиск в точке то либо является подходящей, либо Кроме того, если будет выработано бесконечное число точек, то в случае существования сходящейся подпоследовательности является подходящей

точкой. (Обратите внимание на то, что в части (2) К не обязательно должна входить в

Доказательство. Доказательство оставляется в качестве упражнения 1.

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

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

Упражнения

(см. скан)

(см. скан)

Примечания и ссылки

Эта глава представляет собой отражение положений статьи Зингвила (1966g)

Упражнение 11.4 взято из статьи Полака -и Депариса, в которой теория сходимости применена к интересному алгоритму оптимального управления.