Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

10.7. О сходимости релаксационных методов в задачах с не выпуклой целевой функцией

Рассмотрим функцию φ(х), определенную на выпуклом замкнутом множестве X. Введем обозначения:


p*(х) - проекция точки х на множество X*:


Для ε>0 определим множество


Пусть v=x-υφ'(x), υ>0, p(v)-проекция точки υ на множество X:


Всюду дальше будем предполагать, что выполняются следующие условия:

1) множество X выпукло и замкнуто;

2)

3)Х*≠∅;

4) для всякого ε>0 найдется такое δ = δ (ε) > 0, что


для всех


Заметим, что в любой точке локального минимума (функции φ(x) на множестве X будет


(замечание к теореме 2.16); поэтому условие 4) означает, что всюду вне множества X* не выполняются необходимые условия локального минимума.

Обратимся к анализу сходимости методов проекции градиента и условного градиента в применении к задаче


Метод проекции градиента(ср. схему 1 п. 10.2).







Теорема 10.12. Если выполняются условия 1)-4), то последовательность {хk}, построенная методом проекции градиента, такова, что


Ясли, кроле того,


то


Доказательство. Из леммы 9.3, аналогично тому, как выводилось неравенство (10.33) (см. доказательство теоремы 10.3), получаем


где


Отсюда ввиду условия 4) следует, что для любого ε>0 и всех xk∈X\Uε


Поскольку теорема 9.12 справедлива и для задачи минимизации на выпуклом и замкнутом множестве X, то из последнего неравенства и теоремы 9.12 вытекает


Далее, пользуясь формулой конечных приращений, поручаем


Метод условного градиента (ср. схему 4 п. 10.1).







Теорема 10.13.Если выполняются условия 1)-4) и если существует такое число χ>0, что


то последовательность {хk}, построенная методом условного градиента, такова, что


Если, кроме того,


то


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


то, <φ'(xk), xk-yk>≥σk<φ'(xk), xk-p(vk)> где p(vk)- проекция точки vk=xkkφ'(xk) (0<υk≤υ<∞) на множество X. Но (см. (10.25))


и значит,


Если же


то


Поэтому для всех хk∈Х\uε ввиду условия 4)


Пользуясь леммой 9.3, получаем неравенство


справедливое для всех β∈[0, 1]. Выберем


Если β = 1, то вследствие неравенства


получаем


Если


то


Итак,


и для всех x


справедливо неравенство


где


а значит, по теореме 9.12,


Соотношение


доказывается так же, как и в предыдущей теореме.

Замечание об условиях существования оценок скорости сходимости. В случае, когда для выпуклой функции φ(x) выполняются условия теорем 10.12 и 10.13, справедливы оценки скорости сходимости методов проекции градиента и условного градиента, аналогичные тем, которые приводились в пп. 10.1 и 10.2. Правда, константы в этих оценках будут иными, но порядок скорости сходимости сохраняется прежним.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"