Cтраница 2
Формулировку и доказательство теоремы сходимости метода условного градиента, когда величина а в ( 4) выбирается согласно пп. [16]
Теперь может быть сформулирована теорема сходимости для - методов отсечений. Мы рассмотрим лишь случай, когда вырабатывается бесконечная последовательность ( 2ft i, так как случай, когда поиск завершается через конечное число шагов, является тривиальным. [17]
Очевидно, условие 1а теоремы сходимости С выполняется. По предположению все xh входят в компактное множество X, и решение существует, так что условие 16 также выполняется. [18]
Необходимо отметить, что теорема сходимости С дает несколько больше, чем необходимо для доказательства сходимости. Фактически доказательство оптимальности точки х уже устанавливает сходимость. [19]
Установим сходимость с помощью теоремы сходимости для методов возможных направлений. Напомним, что f и gt предполагаются непрерывно дифференцируемыми. Точку х будем называть подходящей, если для нее выполняются условия Куна - Таккера. [20]
Для установления сходимости будет использована теорема сходимости А. [21]
С нашими вспомогательными средствами доказательство теоремы сходимости получается совсем просто. [22]
Проанализируем теперь более подробно предположения теоремы сходимости А. Эта переменная означает точку, от которой зависит алгоритмическое отображение. В более общем случае, однако, переменная задачи и z отличаются. Действительно, как будет показано, одним из основных моментов при доказательстве сходимости является определение соответствующей переменной 2, от которой зависит алгоритмическое отображение. [23]
Прежде чем переходить к доказательству теоремы сходимости, использующей нормы [ ср С) 11п выведем предварительно одну оценку для разности значений вектор-функции, аналогичную теореме о среднем и представляющую также самостоятельный интерес. [24]
Сходимость будет доказана при помощи теоремы сходимости А. Напомним, что выполнение условия 1 этой теоремы предполагается. Установим выполнение условия 2 теоремы сходимости А. Пусть х не является подходящей точкой. [25]
Приведенные в предыдущих разделах книги теоремы сходимости А и В являются действенным инструментом и, как было показано, дают возможность прямо доказывать алгоритмическую сходимость. Несмотря на это, некоторые алгоритмы, такие как представленные в следующих двух главах, сходятся, хотя они не удовлетворяют предположениям этих теорем. Применительно к алгоритмам такого рода в настоящей главе даны более общие теоремы сходимости. Эти новые теоремы являются не только достаточными для сходимости, но И необходимыми. В частности, сформулировано весьма общее определение алгоритмической сходимости и затем Приведена теорема, содержащая условия, которые выполняются тогда и только тогда, когда алгоритм сходится. Приведены также другие теоремы, связанные с рассматриваемыми вопросами. [26]
Сходимость будет установлена при помощи теоремы сходимости С. [27]
Следовательно, установлено выполнение предположений теоремы сходимости С. [28]
В этой главе, применяя теорему сходимости В к задаче без ограничений, мы предположим, что xz, f Z и все вырабатываемые точки находятся в компактном множестве X. Теорема сходимости В просто требует, чтобы для некоторого бесконечного подмножества К. Тогда в пределе для любой сходящейся подпоследовательности zh - - z, k K, значение целевой функции f ( z) будет по крайней мере так же велико, как и значение целевой функции в подходящей точке для основного алгоритмического отображения В. [29]
Теперь сходимость будет установлена с помощью теоремы сходимости для метода отсечений. [30]