6.1. СМЕШАННЫЕ АЛГОРИТМЫ И ИХ ИСПОЛЬЗОВАНИЕ ДЛЯ ПОВЫШЕНИЯ СКОРОСТИ СХОДИМОСТИ

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

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

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

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

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

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

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

Далее предполагается, что

1) все где множество X компактно;

2) если

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

Доказательство. Рассмотрим произвольную сходящуюся подпоследовательность Следует доказать, что — подходящая точка. (Обратите внимание, что нет необходимости в том, чтобы К было связано с К.)

Из соотношения (6.1) и из свойств отображения В следует, что для всех а из леммы 4.1 имеем

Благодаря условию 1 этой теоремы существует такае что Применяя лемму 4.1 повторно, находим, что

Поэтому из (6.2) и (6.3)

Рассуждая так же, как и при доказательстве теоремы сходимости А и учитывая, что при видим

Тогда из условий 2 этой теоремы и соотношения (6.4) вытекает, что Теорема доказана.

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