Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 11.3. ТЕОРЕМЫ СХОДИМОСТИСледующая теорема сходимости относится к алгоритмам, которые сходятся в том смысле, что удовлетворяют приведенному определению сходимости. Однако прежде чем мы сможем доказать ее, необходимо ввести некоторые понятия. Сначала определим функцию
Очевидно, Лемма 11.1. Пусть Доказательство. Сначала будет доказано утверждение (а). Пусть
Для любого
Поскольку
откуда
Итак,
Аналогично
и согласно (11.3) и (11.4)
Воспользовавшись (11.1), приходим к выводу, что для данного
Поэтому для
Другими словами,
что подтверждает Теперь рассмотрим Функция Как показывает следующая лемма, при этих условиях Лемма 11.2. Пусть последовательность содержится в компактом множестве. Предположим, что для любого К, если Определим
Тогда
Доказательство. Для любой заданной подпоследовательности Учитывая, что непрерывность
Отсюда, так как любая подпоследовательность Улучшаемость функции
Требование, которое мы наложим, по существу заключается в следующем. Допустим, алгоритм вырабатывает
Здесь число после В качестве примера примем
Но для всех
Интуитивно требование улучшаемости сводится к тому, чтобы последовательность имела общую тенденцию к возрастанию. Это требование слабее, чем требование монотонного и строгого возрастания последовательности, имеющееся в теореме сходимости А. Следующая лемма также способствует разъяснению требования улучшаемости. Она обобщает лемму 4.1 и доказывается аналогично. Лемма 11.3. Пусть
Кроме того, допустим также, что для некоторой подпоследовательности
При этих предположениях
Доказательство. Для упрощения обозначения положим
Из непрерывности
Тогда для заданного
Выберем некоторое
Теперь для любых заданных
Отсюда, принимая во внимание (11.12) имеем
Но если мы перейдем к пределу в (11.15) при
Итак, согласно (11.16) для любого заданного
А это есть не что иное, как определение сходимости. Лемма доказана. Замкнутости алгоритмического отображения не требуется. Приведенное обсуждение показывает, как в теореме сходимости С будет обобщено условие 2а теоремы сходимости А—требование улучшаемости. Остается только рассмотреть, как можно было бы исключить требование замкнутости отображения — условие 3 теоремы сходимости А. Новое условие, налагаемое теоремой сходимости С, в основном сводится к следующему. Предположим, что
где Тогда должна существовать другая подпоследовательность
Каким образом это условие исключает требование замкнутости отображения? Допустим, что выполняются предположения теоремы сходимости А. Затем предположим, что
Но тогда условие 2а влечет
Ясно, что (11.17) и (11.19) совпадают. Значит, теорема сходимости А приводит к такому же результату, что и теорема сходимости С. Короче говоря, теорема сходимости С оставляет в силе сущность требования замкнутости отображения, в частности, соотношение (11.19), не требуя самой замкнутости отображения. Общая теорема сходимости С. Пусть для данной задачи НЛП имеется алгоритм, который вырабатывает точки Рассмотрим следующие условия 1 и 2: Условие 1. а. Если для некоторых б. Допустим, что алгоритм вырабатывает бесконечную последовательность точек, ни одна из которых не является подходящей. Тогда, если Условие 2. Пусть алгоритм вырабатывает бесконечную последовательность точек, ни одна из которых не является подходящей, и все точки а) для любого заданного
б) для любой сходящейся подпоследовательности 1) существует такое 2) существует сходящаяся подпоследовательность
Любой алгоритм,, который удовлетворяет условиям 1 и 2, удовлетворяет определению сходимости. При этом, если Доказательство. Достаточность. Пусть алгоритм удовлетворяет условиям 1 и 2 теоремы. Мы должны доказать, что он сходится в смысле определения сходимости. Очевидно, чтоусловие 1а и часть определения сходимости (а) совпадают. Нам следует установить, что справедлива часть определения сходимости Если все точки входят в компактное множество, то остается лишь доказать, что предел любой сходящейся подпоследовательности должен быть подходящей точкой. Пусть Допустим, что Из леммы 11.3 и условия 2а следует:
Воспользовавшись условием 26, часть (2), находим, что имеется такое К, что справедливо выражение (11.20). Тогда на основе компактности можем найти такое
Но согласно лемме
Но из условия 2б, часть (2), и (11.22) имеем
Так как выражения (11.23) и (11.24) противоречат друг другу, то Необходимость. Напомним, что по предположению множество Из части (а) определения сходимости вытекает условие 1а. Допустим, что выработана бесконечная последовательность точек, ни одна из которых не является подходящей. Согласно части (б) определения сходимости при Остается доказать выполнение условия 2. Пусть все точки
где
так как Рассмотрим последовательность
б) все в) из Учитывая пункты
Теперь анализируем условие 2а. Так как по предположению условия
Но согласно (11.27) существует
Справедливость условия 2а установлена. Очевидно, что условие 26 обязательно выполняется, так как предел любой сходящейся подпоследовательности должен быть подходящей точкой. Теорема доказана. Замечания. Любой алгоритм, который удовлетворяет условиям 1 и 2 теоремы сходимости С, сходится в том смысле, что он удовлетворяет определению сходимости. Наоборот, любой алгоритм, который сходится в смысле определения сходимости, удовлетворяет условиям 1 и 2 теоремы. Условие 1а нужно для следующих двух ситуаций. Во-первых, если алгоритм завершает поиск в точке Условие 16 относится к случаю, когда вырабатывается бесконечная последовательность точек, ни одна из которых не является подходящей (в противном случае могло бы быть применено условие 1а). По существу, условие 16 требует, чтобы все точки входили в компактное множество, если Условие 2 предполагает, что все точки входят в некоторое компактное множество. Следовательно, когда нужно доказать, что алгоритм удовлетворяет условию 2, мы можем предположить, что алгоритм вырабатывает точки, входящие в некоторое компактное множество. Можно надеяться, что это предположение упростит задачу, когда необходимо доказать, что алгоритм удовлетворяет этому условию. Чтобы установить выполнение условия 2, мы должны найти для алгоритма соответствующую функцию Условие 2а представляет собой требование улучшаемости, которое обсуждалось выше. Отметим, что алгоритму необходимо удовлетворять условию 2б лишь в том случае, когда он вырабатывает бесконечную последовательность точек, ни одна из которых не является подходящей. При этом алгоритм должен удовлетворять условию 2б только в случае, если Часть (2), как отмечалось выше, представляет собой условие, которое заменяет предположение о замкнутости отображения. Часть Сформулируем еще одну заключительную теорему сходимости, имеющую цель избежать предположения относительно компактности. Теорема сходимости Предположим, что выполняются следующие условия: Условие 1. Если Условие 2. Существует непрерывная функция а. Для любой заданной точки Если существует сходящаяся подпоследовательность 1) имеется такое 2) существует сходящаяся подпоследовательность При этих условиях, если алгоритм завершает поиск в точке точкой. (Обратите внимание на то, что в части (2) К не обязательно должна входить в Доказательство. Доказательство оставляется в качестве упражнения 1. Замечание. Обратите внимание на то, что алгоритм, который удовлетворяет предположениям теоремы сходимости В упражнениях даны другие теоремы сходимости. В частности, см. упр. 3 для конечной сходимости. Упражнения(см. скан) (см. скан) Примечания и ссылкиЭта глава представляет собой отражение положений статьи Зингвила (1966g) Упражнение 11.4 взято из статьи Полака -и Депариса, в которой теория сходимости применена к интересному алгоритму оптимального управления.
|
1 |
Оглавление
|