Ф.П. Васильев - Методы оптимизации (1125241), страница 83
Текст из файла (страница 83)
Можно заметить, что описанный в гл. 3 симплекс-метод для решения канонической эа ачн линейного программирования по существу является вариантам метода возможных напразлед ний, Более того, опираясь на идеи метода возможных направлений, можно получить симплек м сетод непосредственно для основной задачи линейного программирования (без ее сведения к канонической задаче). Выше во вспомогательной задаче (2) было принято условие нормировки (е> ! < 1, / = 1,..., п, Возможны н другие условия нормировки, например, (е! < 1 нли !В» г( < 1, где Вй — специально выбираемая матриил, Заметим, что при такой нормировке задача (2) уже не будет задачей 278 Гл. б. МЕТОДЫ МИНИМИЗАЦИИ ФУН!(ЦИЙ МНОГИХ ПЕРЕМЕННЫХ линейного программироаания. Тем не менее удачный выбор Вь может облегчить выбор еозможного напраеления убывания, ускорить сходимость метода. Д других способах нормироеки, о сходимости различных вариантов метода еозможных напраелений и других аспектах етого метода см., например, [319; 326! 374; 7741.
Упражнения 1. Сделать несколько итераций метода возможных направлений для задачи минимизации 7(м) = хьу на мноткьстее х =(и =(х, у); д!(и) = хе — у <О, дз(о) = у — 1 <О) при различном выборе начальной точки оо. 2. Вычислить несколько приближений по методу зозмохгных напраелений для задачи из примера 1 при различном начальном приближении ч„. $6.
Проксимальный метод 1. Этот метод используется для решения выпуклых задач минимизации у(х) — ~ !п(, х е Х, (1) когда Х вЂ” выпуклое замкнутое множество из Е", функция 7'(х) выпукла на Х. В его основе лежит понятие проксимального оператора, который определяется следующим образом. Фиксируются точка хе Е и число сг > > О, определяется функция (2) переменной х е Х, и рассматривается задача минимизации р(я, х, сх) — +!П1, г е Х.
(3) Так как функция (о(х,х,сх) сильно выпукла на Х с постоянной сильной выпуклости х = 1, то согласно теореме 4.3.1 задача (3) имеет, притом единственное решение х, = х„(х,ст). Тем самым определен оператор, который каждой точке х е Е" и числу гх > О ставит в соответствие решение н„ задачи (3). Этот оператор называется проксималоным, его обозначают символом рг. Таким образом, рг(х,сг) = х.
е Х вЂ” решение задачи (3). Изучим некоторые свойства проксимального оператора. Из (3) и неравенства (4.3.3) следует, что й!х — рГ(х,сг)! ~ (Чз(х,х,сг) (о(рг(х,сг),х,ст) ЧхеХ, хеЕ, сг>О. Если функция у'(х) дифференцируема на Х, то 3о„(х, х, о) = х — х+ ст7'(х) и для решения рг(х, гх) задачи (3) по теореме 4.2.3 имеем (рГ (х, гх) — х+ сгГ(рг (х, сг)), х — рг (х, ст)) > О Чх е Х. Отсюда, вспоминая характеристическое свойство проекции точки на мно жество (неравенство (4.4.1)), обнаруживаем следующую связь между прок снмальным оператором и оператором проектирования: рг(х, сг) =Р.
(х — ст,7'(рг(х, сх))) !Ухе Е, Гх >О. (5) б б. ПРОКСИМАЛЬНЫЙ МЕТОД 279 Если функция 7(х) не является дифференцируемой, то эту связь можно выразить с помощью субградиентов. Всюду ниже в этом параграфе мы будем предполагать, что функция 7'(х) определена и выпукла на открытом выпуклом множестве Иг, содержащем множество Х. Тогда при каждом х е Х субдифференциал д7(г) является непустым выпуклым замкнутым ограниченным множеством (теорема 4.6.2). По правилу 7 субдифференцнровання из $4.6 для функции (2) имеем д!р(н, х, сг) = х — х + ездим(г) Чг Е Х.
(6) Согласно теореме 4.6.4 для решения рг(х, сх) задачи (3) найдется субградиент с,(рг(х, ст)) е д~р(рг(х, сг), х, сг), такой, что (с,(рг(х, сг)), х — рг(х, ст)) >О !Гх б Х. Из формулы (6) следует существование с(рг (х, гх)) е дУ(рг (х, сх )), для кото рого с,(рг (х, сг)) = рг(х, сг) — х+ сто(рг(х, ст)), и поэтому предыдущее нера венство можно записать в виде (7) (рг(х, сг) — х+ сгс(рг(х, сх)), х — рг(х, ст)) >О !ун х Х, Отсюда вместо формулы (5) получим рг(х, сг) ='Рх(х — ос(рг(х, сх)) !Ух ~ Е, сг > О, (8) для некоторого субградиента с(рг(х, ст)) ~ ду(рг(х, сг)). С помощью установленной связи (8) между проксимальным оператором и оператором проектирования нетрудно доказать следующий критерий оптимальности для задачи (1). Теорема 1.
Для того, чтобы х, е Х„, необходимо и достаточно, чтобы х„= рг(х., а) !угх >О. Доказательство. Необходимость. Пусть х, е Х„. По теореме 4.6.4 найдется субградиент с(х,) е ду'(х,) такой, что (с(х,), г — х,) > О !Ухе Х. Тогда, как следует из формулы (6) с,(х )=х„— х+сгс(х)=ос(х)е е д!р(х., х„гх). Умножая на ст > О предыдущее варйационное неравенство, получаем: (с,(х.), х — х,) > О !Уг е Х. Согласно теореме 4.6.4 это означает, что х, — решение задачи (3) при х = х„т. е. х„= рг(хтл сг). До с т а т о ч н о с т ь. Пусть х„= рг(х„ст),*Согласно формуле (8) найдется с(рг(х, сг)) = с(х„) Е ду(рг(х„ст)) = ду(х„), что х, = Рх(х, — гхс(х,)).
Отсюда и из замечания 1 к теореме 4.6.4 имеем: х, я Хлы Теорема 1 доказана. П Т е о р е м а 2. Проксимальный оператор рг(х, сг) непрерывен по переменной х равномерно относительно ст > О и, более того, 1рг(х, сх) — рг(у, сх)1<1х — у! ух, у ЕЕ, сг > О. (9) До к аз а тел ьст в о. Из неравенства (4) при х = рг(у, сг) имеем: -1рг (у, сг) — рг (х, сг)1' < р(рг (у, ст), х, сг) — (о(рг (х, сх), х, сг). Меняя здесь х и у ролями, получим -1рг(х, сх) — рг (у, сг)1' < Чз(рг (х, сх), у, сг)— — чз(рг(у, сг), у, сх).
сложим эти два неравенства: !рг(х, сг) — рг(у, сг)!з < < (о(рг (у, сг), х, сг) — 1о(рг (х, сг), х, гх)+(о(рг (х, сг), у, сг ) — ьо(рг (у, гх), у, сх). 280 г . з мптоды минимизАции фунхцин' многих ппппмкнных В правую часть этого неравенства подставим соответствующие значения функции ч>(г, х,а) согласно ее определени>о (2). После простых преобразований получим 1рг (х«а) — рг (у, а)1«<(рг (х«а) — рг (у,а),х — у) Чх, убЕ", а >О, (10) К правой части неравенства (10) применим неравенство Коши — Буняковского: 1рг(х, а) — рг(у, а)1' <»рг(х, а) — рг(у, а)!. »х — у). Отсюда следует не авенство (9). П следующеи теореме приводятся условия, обеспечивающие непрерывность рг (х, а) по совокупности аргументов (х, а) во всех точках х ~ Е", а > О.
Те о рема 3. Пусть в дополнение к сделанным выше предположениям функция »(х) удовлетворяет условию Липшица: »>(х) — 7(у)~ < Е1х— — у~ Чх уЕХ, пусть хьЕЕ, аь>0, 1=1,2,..., (хь) — «х, (аь) — «а>0. Тогда»1ш рг(х„, а„) =рг(х, а). ь ш До к аз а тел ьст в о. По неравенству треугольника имеем: 1рг (х„а ) — рг (х, а)» < 1рг(х, а„) — рг(х, а„)(+ + )рг(х, а,) — рг(х, а)), й = 1, 2,... (11) Первое слагаемое в правой части неравенства (11) в силу (9): 1рг (х„, а,)— — рг (х, а„)! <1х„— х» — «О при й — оо. Докажем, что второе слагаемое также стремится к нулю. Из неравенства (4) при а = а„, г = рг(х, а) следует 2!рг(х«а) — рг(х, а„)1' ( 2!рг(х«а) — х/ — 21рг(х«а„) — х»'+ + аь(у(рг(х, а)) — »(рг(х, аь))), й = 1, 2,...
По условию функция Т" (х) удовлетворяет условию Липшица, поэтому 1>(рг(х, а)) — »(рг(х, а„))» ( Ь1рг(х, а) — рг(х, а„)!. Ото>ода и из предыдущего неравенства для величины а, =1рг(х, а) — рг(х, а,)» > 0 имеем: а'„— 2а„Ьа„— »рг(х, а) — х»' < О, к = 1,2,... Замечая,,что левая часть этого неравенства представляет собой квадратный трехчлен относительно пе еменной а„, получаем оценку для а„: 0 < а„ < а„Ь + + 1рг(х, а) — х1'+ а„'Ь' < 2Ь апр а„+»рг (х, а) — х).
Тогда последователь- «>о ность (рг (х, а,)) также ограничена н согласно теореме Больцано — Вейерштрасса имеет хотя бы одну предельную точку и>. Выбирая при необходимости подпоследовательность, можем считать, что (рг(х, аь)) - х. Тогда мно>кество У, состоящее из точек рг(х,а,), й = 1,2,... и точки ж компактно. В силу компактности субдифференциального отображения (теорема 4.6.5) тогда компактно и множество дТ"(у), которое содержит субградиенты уев с(рг (х, а„)), входящие в неравенства (7) при а = а„, к = 1, 2,.... Поэтому можем считать, что (с(рг(х, а ))) — «с. Из замкнутости субдифференциального отображения (теорема 4.6.5) следует, что с Е ду(ю).
Теперь мы можем совершить предельный переход при й — со в вариационных неравенствах (рг(х, а ) — х+ а с(рг (х, а )), г — рг (х, а )) > 0 Чг е Х, полученных из (7) при а = а,. Будем иметь (ю — х+ ас, г — и«) > 0 Чг е Х. Здесь с е ду(и) и согласно формуле (6) имеем с, = ю — х+ ас е д«р(ю, х, а). Отсюда и из предыдущего неравенства, записанного в виде (сн в — ю) > 0 Чг е Х с помощью 4 6. ПРОксимАлъный метод 281 теоремы 4.6.4 получим, что и> решение задачи (3), т.
е. и = рг(х, а). Это аначит, что последовательность (рг(х, а„)) имеет единственную предельную точку рг(х, а), т, е, !нп рг (х, а„) = рг(х, а). Тем самым мы доказали, что второе слагаемое из правой части неравенства (11) также стремится к нулю. Непрерывность проксимального отображения рг (х, а) по совокупности аргументов (х,а) установлена. П 3 а м е ч а н и е 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
