4.5. ТЕОРЕМА СХОДИМОСТИ

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

Лемма 4.1. Пусть — непрерывная функция. Пусть существует последовательность точек из X такая, что

Тогда

Доказательство. Благодаря непрерывности

Согласно (а) последовательность монотонна, так что для любого

Используя выражение (4.6) и определение предела, видим, что для данного существует такое, что для

Для согласно (а)

Тогда из выражений (4.7) — (4.9) следует, что

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

Компактность. Нам необходимо ввести еще одно понятие — компактность. Множество X называется компактным, если любая последовательность

(или подпоследовательность) в X содержит сходящуюся подпоследовательность. В более явной форме, если дана подпоследовательность в X, где X компактно, существует такое, что входит в X

Можно показать, что в эвклидовом пространстве компактные множества соответствуют замкнутым и ограниченным множествам. Компактное множество должно содержать всю свою границу и не может простираться в бесконечность ни в одном направлении. Точки, вырабатываемые большинством алгоритмов, должны находиться в таких множествах.

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

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

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

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

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

Предположим, что

1) все точки принадлежат компактному множеству

2) существует непрерывная функция такая, что

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

б) если — подходящая точка, то либо алгоритм завершает поиск, либо для любого

3) отображение А замкнуто в точке если эта точка не является подходящей.

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

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

Прежде всего следует обратить внимание на то, что согласно должна существовать сходящаяся подпоследовательность

Используя видим? что Но тогда из леммы 4.1 следует, что

Рассмотрим теперь подпоследовательность Согласно существует такое, что а из леммы 4.1 имеем

Условия (4.10) и (4.11) дают

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

Тогда согласно п. 3

По предположению не является подходящей точкой, тогда из следует, что

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

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

Проанализируем теперь более подробно предположения теоремы сходимости А. В первую очередь, следует обратить внимание на то, что вместо переменной х мы пользовались переменной Эта переменная означает точку, от которой зависит алгоритмическое отображение. Часто бывает, что представляет собой переменную х задачи математического программирования, и в этом случае . В более общем случае, однако, переменная задачи и отличаются. Действительно, как будет показано, одним из основных моментов при доказательстве сходимости является определение соответствующей переменной 2, от которой зависит алгоритмическое отображение.

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

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

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

При установлении сходимости доказательство условия 3 обычно является наиболее сложным. Часто при математическом подтверждении условия 3 помогает следующая эвристика. Пусть так что у следует за в последовательности, вырабатываемой алгоритмом. Теперь слегка сместим в точку и пусть Если у близка к у, то, вероятно, А обладает свойством непрерывности (т. е. замкнутости). Другими словами, небольшое изменение вызывает небольшое изменение точки, следующей за Если это утверждение подтверждается интуитивно, то соблюдение условия 3 обычно удается доказать строго математически.

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