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


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

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

Как мы видели, в случае, когда функция φ(х) выпукла и принадлежит классу С1,1(En), удается получить оценки скорости сходимости для большинства рассмотренных выше методов минимизации. Ставится вопрос, при каких условиях на не выпуклую функцию φ(x) методы спуска остаются сходящимися. При этом речь идет не об оценках скорости сходимости, а лишь о факте сходимости.

Будем предполагать, что функция φ(x) непрерывна и что не пусто замкнутое множество Х* = {х*: φ(x*)= min φ (х)}. Обозначим через р=р(х) проекцию точки х на множество X*:


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


Пусть последовательность {xk} такова, что

φ (xk+1)≤φ(xk) (k = 0, 1, ...).

Теорема 9.12.Если для всякого ε>0 найдется такое число η = η (ε) > 0 и такая последовательность {xk} ⊆ {xk}, для членов которой, не принадлежащих Uε, выполняется неравенство


то найдется такой номер k0 = k0(η), что xki∈Uξ (ki≥k0+1) и, следовательно,


Доказательство. Так как последовательность {φ(хk)} сходящаяся (ввиду ее монотонности и ограниченности снизу числом φ(x*)), то найдется такой номер k0=k0(η), что для всех ki≥k0+1 будет


и, следовательно, xki∈Uε (ki≥k0+1).

Рассмотрим общую процедуру методов спуска:

xk+1=xkksk (k = 0, 1,....)

где х0-любая точка из Еn, a sk-направление в точке хk, способами выбора которого различаются методы. Число βk будем определять из соотношений


Предположим, что функция φ(x) удовлетворяет условиям:

1) φ(x)∈С1,1(En);

2) для любого ε > 0 найдется такое δ = α (ε) > 0, что ||φ'(х)||≥δ для всех х∉Uε.

Эти условия означают, что у гладкой (в смысле С1,1) функции φ(x), достигающей минимума в пространстве Еn (условие не пустоты множества X*), отсутствуют точки локальных минимумов (условие 2). Более того, условие 2 накладывает определенные ограничения даже на класс выпуклых функций.

Из соотношений, определяющих величину βk, и из условия 1, ввиду леммы 9.3, получаем (см. 9.10) оценку


Теорема 9.13.Если направление sk выбирается таким образом, что α2k≥α2>0 (k = 0, 1, ...), то


и


Доказательство. Из условия 2 и предыдущей оценки следует, что для любого ε>0 и всех xk∉Uε будет


где


а значит, по предыдущей теореме


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


где x̃∈[хk, р(хk)]. Отсюда, учитывая условие 1 и то, что φ' (р(хk)) = 0, приходим к неравенству

(9.33)

Поэтому


Применим эту теорему для установления сходимости некоторых методов минимизации, предполагая, что φ(x) удовлетворяет условиям 1 и 2.

Метод градиентног отпуска. Здесь sk = φ'(xk) (см. п. 9.5). Сходимость метода очевидна, ввиду того, что αk=1, (k = 0, 1, ...).

Метод случайного спуска (см. п. 9.10). Здесь в качестве sk выбирается случайная точка на единичной сфере, подчиняющаяся на ней равномерному распределению.

Если для любого ε>0 найдется такая подпоследовательность {xki}, что xki∈Uε, то


значит, согласно (9.33)


Отсюда, ввиду сходимости последовательности


получаем


Предположим, что такой последовательности нет. Тогда существует такое ε>0, что, начиная с некоторого номера k0 = k0(ε), будет


Пусть номер k1 = k1 (η) ≥ k0 таков, что для всех k > k1 будет

φ(xk) - φ(xk+1) < η, где η = λδ/2Ln

Так как x̃k∈Uε, то по условию ||φ'(xk)||≥δ и, ввиду (9.32), справедливо неравенство

φ(xk)-φ(xk+1)≥1/2L λδα2k (k = k0+1, k0+2,...)

Но, согласно закону "нуля или единицы" вероятность появления такого случайного номера k≥k0+1 что α2k≥α>0 (для достаточно малого α∈(0, 1/n)), равна единице (см. теорему 9.10), и поэтому с вероятностью, равной единице, наступит событие

φ(xk)-φ(xk+1)≥η

противоречащее предположению. Таким образом,


вследствие чего


и


Циклический покоординатный спуск. Для обоснования сходимости требование ||φ'(x)||≥δ при x∉Uε усилим следующим. Предположим, что для всякого ε>0 в последовательности {xk}, где xk+1=xkkej(k) (см. п. 9.8), найдется такая Подпоследовательность {хk}, для членов которой, не принадлежащих Uε, выполняется неравенство


Так же как и в п. 9.7, из леммы 9.3 и определения величины δ получаем для xki∉Uε неравенство


из которого на основании теоремы 9.12 получаем


а значит, согласно (9.33)


Замечание об условиях существования оценок скорости сходимости. В случае, когда для выпуклой функции φ(x) выполняются условия 1 и 2, справедливы оценки скорости сходимости методов спуска, в том числе градиентного спуска и метода сопряженных направлений, а так же методов случайного покоординатного спуска и метода случайного спуска, аналогичные тем, которые приводились в пп. 9.4,9.5,9.9,9.10. При этом константы в этих оценках будут иными, но порядок скорости сходимости остается прежним. Подчеркнем, что ранее всегда требовалась ограниченность множества


здесь же это требование заменится условием 2.

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





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


Диски от INNOBI.RU




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