Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 75
Текст из файла (страница 75)
Теорема 6 доказана. П Для сильно выпуклых функций несложно получить оценку скорости метода (45), Теорема 7. Пусть функция 7(ж) е С'С(Е") и сильно выпукла на Е", а функция а(с), чс >О, [ а(С)де=+со. Тогда для траектории х(С) системы(45) с любым начальным о условием х(0) = хо справедлива оценка: с ]х(с) — х]< ]зо — х]ехр(-р ] а(т)дт) Чс >О, о где постоянная р > 0 взлта иа теоремы 4.3.3. Доказательство. Пресссде всего заметим, что по теореме 43.1 точка минимума х, функции ?(х) на Е" существует и единственна, а по теореме 4.2.3 У'(зь) = О. Полохсим 1'(с) = 1 [х(с) — ж„!2, с > О. Тогда с учетом (45) и теоремы 4.3.3 имеем: Р(С) = (х(С) — х„, х(С)) = — а(СЯ (х(с)) — 7 (ж ), х(С) — х ) < < -ра(С)!ж(С) — х 12 = -2ра(С)У(С), соз > 0; У(0) = !зс — х !~/2. Отсюда следует; — ('г'(с) ехр(2р [ а(т)дт) ) < 0 сс'с > О.
Интегрируя это неравенство, полу- чим дэ о с с 0 < У(С) < У(0) ехр( — 2р 1 а(т)дт) = !жо — х!2 ехр( — 2р ] а(т)дт) /2, о о что авносильно оценке (47). Теорема 7 доказана. |3 ользуясь терминологией, принятой в теории устойчивости обыкновенных дифференциаль. ных уравнений [328; 376; 588; 694], можно сказать, что в теореме 7 доказана асимптотическая устойчивость системы (45) относительно точки равновесия х, этой системы.
Для доказательст- ва этого факта использован второй метод Ляпунова, в качестве функции Ляпунова была взята функция (48). В связи с этим полезно заметить, что при исследовании многих методов миними- зации явно или неявно используется второй метод Ляпунова или его дискретный аналог; в каче- стве функции ляпунова наряду с (48) часто используются также функции У(с) = ?(х(с)) — ?„ и(с) = !7"'(х(с))]~ и др.
систематическое исследование сходимости методов минимизации с помощью метода Ляпунова проведена в [77]. Существуют и другие дифференциальные уравнения, траектории которых являются мини- мизирующими. Например, так называемый метод тяхселого шарики [74] заключается в рассмо- трении системы дифференциальных уравнений вида: ж(с)+ х(с) + а(с)7~(х(с)) = О, с > О, а(с) > О. (49) Оказывается, траектории системы (49) при довольно широких предполоскениях сходятся к точке минимума функции У(х) на и", причем скорость сходимости, вообще говоря, выше, чем у т аекторий системы (45).
ледует заметить, что непрерывные методы минимизации привлекательны тем, что для приближенного решения возникающих здесь задач Коши могут быть использованы не толька метод ломаных Эйлера, ио и другие известные методы [59;?4; 89; 481], которые, возможно, будут сходиться быстрее н лучше приспособлены для минимизации овражных функций, приводящих к так называемым жестким системам дифференциальных уравнений. На этом пути можно получить различные классы дискретных методов минимизации, которые подчас трудно обнаружить, оставаясь в рамках привычных представлений, навязанных итеративными схемами. Перечисленные обстоятельства стимулируют развитие непрерывных методов решения экстремальных задач (см., например,[25; 26; 28-30; 732)).
Непрерывные аналоги некоторых методов изложены ниже в 66 2, 6, 11. 7. В заключение отметим, что градиентный метод, вообще говоря, хорошо работает лишь на первых этапах поиска минимума, когда точки жь из (3) не слишком близки к точке минимума х, а вблизи точки х, расстояние ]з. — з,! часто перестает уменьшаться, сходимость метода 'ь ухудшается. Это связано с тем, что в окрестности точки минимума градиент Г (хь) близок к нулю, главная линейная часть приращения У(жь) — 7(х„), на базе которой выбирается направление спуска в методе (3), становится малой, усиливается влияние квадратичной части приращения, метод (3) становится слишком чувствительным и неизбежным погрешностям вычислений.
Поэтому вблизи точки минимума при необходимости пользуются более точными и, вообще говоря, более трудоемкими методами, лучше учитывающими не только линейные, но и квадратичные части приращения. Упражнении 1. Описать различные варианты градиентного метода длв задачи из примера 2.2.2. 2.
Установить сходимость, метода скорейшего спуска для функции (5); описать другие варианты градиентного метода для этой функции. 3. Рассмотреть метод скорейшего спуска и другие варианты градиентного метода для задачи минимизации функции ?(ж) = !Ах — Ь], ж е Е", где А — матрица порядка т х п, Ь е Е "1 исследовать их сходимость. 4. Рассмотреть метод скорейшего спуска для минимизации функций у(и) = ж + ау, и = 2 2 =(з, у) е и, и 7(и)= х +у +аг, и=(з, у, з) е Ез, при различном начальном приближении ио, считая коэффициент а намного больше единицы. 5. Доказать теоремы 1, 2 для метода (3), (7).
9 2. Метод проекции градиента 1. Будем рассматривать задачу У(х)- !и[; х Е Х С лэ", (1) где множество Х необязательно совпадает со всем пространством Е", а функция 7"(х) е с'(х). непосредственное применение описанного выше градиентного метода в случае Х ф Я" может привести к затруднениям, так как точка х„, из (1.3) при каком-то )с может не принадлежать Х. Однако эту трудность можно преодолеть, если полученную с помощью формулы (1.3) точку х„— а 7"'(хь) при каждом )с проектировать иа множество Х (см. определенйе 4А.[).
В результате мы придем к так называемому методу проекции градиента. А именно, пусть х е Х вЂ” некоторое начальное приближение. Далее будем строить последовательность (хь) по правилу хс„, ='Рх(хь — ссьу'(хь)), й = О, 1,..., (2) 251 250 Гл. 3. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 4 2. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 41 :д где а„— положительная величина. Если Х вЂ” выпуклое замкнутое множество и способ выбора (со„) в (2) задан, то в силу теоремы 4.4.1 последовательность (х,) будет однозначно определяться условием (2). В частности, при Х = Е метод (2) превратится в градиентный метод. Если в (2) на некоторой итерации оказалось х, э, = х„(например, зто случится при /'(х„) = 0), то процесс (2) прекращают.
В этом случае точка х„ удовлетворяет йеобходимому условию оптимальности х„=Рз(хо — ао/'(х„)) (см. теорему (4.4.3), и для выяснения того, является ли в действительности х„решением задачи (1) или нет, при необходимости нужно провести дополнйтельное исследование поведения функции /(х) в окрестности точки х,, В частности, если /(х) — выпуклая функция, то такая точка х„ является решением задачи (1). В зависимости от способа выбора а, в (2) можно получить различные варианты метода проекции градиента.
Укажем несколько наиболее употребительных на практике способов выбора а, 1) Введем функцию одной переменной д (со) = /(Рх(х„ — а/'(х,)), а > О, и определим а„ из условий дь(соь) = >п1 дь(а) =д „а„> О. (3) оо Очевидно, при Х = .Е" метод (2), (3) превратится в метод скорейшего спуска. Поскольку величину а, из условий (3) удается найти точно лишь в редких случаях (возможно также, что нижняя грань в (3) не всегда достигается), то со, на практике определя>от приближенно из условий типа (1.6) или (1.7). 2) Иногда приходится довольствоваться нахождением какого-либо а, > О, обеспечивающего условие монотонности: /(хь+,) < /(хь).
Для этого обычно выбирают какую-либо постоянную а > 0 и в методе (2) на каждой итерации берут со. = а, а затем проверяют условие монотонности и при необходимости дробят величину ао = а, добиваясь выполнения условия монотонности. 3) Если функция /(х) принадлежит С' '(Х) и константа Липшица Ь для градиента /'(х) известна, то в (2) в качестве а, можно взять любое число, удовлетворяющее условиям О< го< а„<2/(Ь+2г), (4) где г, г — положительные числа, являющиеся параметрами метода. 4) Возможен выбор со„из условия /(хо) /(Рх(хо соо/'(хь))) > г[хь Рх(хо сои/'(х ))~о, (5) где г > 0 — параметр метода. Для определения такого а„можно взять какое- либо число а„= а (например, а = 1) и затем дробить его до тех пор, пока не выполнится условие (5). Если /(х) Е С' '(Х), то нетрудно показатач что выполнения условия (5) молоко добиться за конечное число дроблений.
5) Возможно априорное задание величин а„из условий аь>0, й=0,1,...; ~, 'а„=со, ~ со,'<со, (6) ь=о о-о например, а„=(й+ 1) ', й =О, 1,... Сходимость метода (2), (6) будет исследована в 9 3. Заметим, что описанные здесь варианты метода (2) при Х = Е" переходят в соответствующие варианты градиентного метода.
На практике для ускорения сходимости вместо (2) часто пользуются более общим вариантом метода проекции градиента х„„, = х„+ До(Р (хо — со~ 7'(х„)) — хо) = =/3 Р,(х, — а,/'(х )) +(1 — Во)хоо О < 17о > 1, а > О, (2) где параметры со„, д могут выбираться различными способами. Заметим, что в методах (2) или (2') на каждой итерации, кроме выбора параметров а„, д„, нужно еще проектировать точку на множество Х или, иначе говоря, решить задачу минимизации Фь(х) = [х — (хь — а./'(х ))[о — ~ 1п1, х Е Х; (7) здесь возможно использование функции Ф (х)=[х — х,['+2а (/'(хл), х — хь), отличающейся от предыдущей функции постоянным слагаемым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
