Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 54
Текст из файла (страница 54)
Докажем неравенство (2). Поскольйу любой модуль выпуклости б(]) < < р(г), то неравенство (2) достаточно докааать длн р(с). Возьмем любую точку ив щ 7/в. Тогда 0( 1 (аи+ (1 — а) и ) — 1 (и ) (а (1 (и] — 1 (ив)]— — а(1 — а)р(] и — о]) или а(1 — а) р((и — и В(а(1(и) — 1(ив)) (О < а < 1, игн П). Деля на а) 0 и устремляя а-».+О, отсюда получаем неравенство (2). Наконец, пусть функция 1(и) строго равномерно выпукла на П. Тогда она строго выпукла на 1/ и согласно теореме 2Л множество 1]в будет состоять из единственной точки ив. Возьмем произвольную минимизирующую последовательность (иь). Полагая в (2) и = иь и устремляя /г -ь о», получаем б (( иа — ив ]) -ь О.
Это возможно только при !иь — ив ) -ь О, так как 1(и) строго равномерно выпукла. 2. Остановимся на некоторых необходимых, а также достаточных условиях равномерной выпуклости функции. Теорема 2, Пусть 1/ — открытое выпуклое множество ие Е», пусть учункиия 1(и) равномерно выпукла на 7/ о модулем выпуклости б(Г). Тогда необходимо выполняютея неравенства 222 элиз[инты ВынуклОГО АнАлизА [ГЛ. 4 Доказательство. Поскольку равномерно выпуклая функция является и просто выпуклой, то из теоремы 6.1 следует, что д1(и) чь 8 при всех и вн ТУ, Возьмем произвольные и, Р си П, с(Р) я дУ(Р).
Из определения субградиента и из (1) при всех сс (О ( сс < 1) имеем я< с (с), и — Р> + 1(Р) ( 1(аи + (1 — а) Р) ( ( аУ(и) + (1 — Я)1(Р) — а(1 — сс)6()и — Р() мли (1 — а)6()и — Р() + <с(Р), и — Р> (1(и) — 1(с), Отсюда при а- -[-О получим неравенство (9). Поменяя в (9) переменные и и и ролями; будем иметь 1(с) >1(и) +<с(и), Р— и>+6()и — Р(), с(и) шдУ(и). Складывая зто неравенство с (9), приходим к (10). Приведем одно достаточное условие равномерной выпуклости функции.
Теорема 3. Пусть П вЂ” выпуклое множество, 1(и) сиСс(П)с и пусть для некоторой непрерывной неотрицательной функции $(С) (О ( С ( в 6[аж П), 2(С) = 0(С)2 при С вЂ” с-+О, З(С) ~0, выполняется неравенстве <У'(и) — 1'(Р), и — Р> ) $()и — Р() (11) при всех и, Р ~ (У.
Тогда функция 1(сс) равномерно выпукла на ТУ с моду- 1 лвм выпуклости 6(с) = ~ ($ (тс)12) дт. о Доказательство. Из формулы (2.7) и условия (11) имеем сс1 (и) + (1 — а) 1 (Р) — 1 (яи+ (1 — а) Р) = 1 1 =я(1 — я) ) <1' (г ) — У' (21), 2 — 2 > — ~ )а (1 — а) " 6 (~ 2 — 2 [) — = т 1 2 о о 1 = я(1 — я) ) 2 (т) и — Р)) — =- я(1 — а) 6() и — Р(), и, Рви 11, авн[0, 1), йт е что и требовалось Доказанная теорема 3 может быть использована для установления равномерной выпуклости колкретных функций. Те о р е и а 4.
Функция 1(и) = (и)Р строго равномерно выпукло ни Е" при всех р ) 2. Доказательство. Покагкем, что <1' (и) — 1'(Р), и — Р> > 2 ш1п(1; 22 Р)( и — Р(Р, и, Рш Е". (12) Здесь 1'(и) = р(и(Р-2. Тогда <1' (и) — 1' (Р), и — Р> = (р( и)Р 2 и — р(Р(Р 2 Р, и — Р> = — р((и)Р+(Р)Р <и Р>((и(Р 2+(Р(Р 2)1= =р~( )'+) )'- )и) +(')'-('-'( ((.) -'+) ) -')~= 2 = — ((( и (Р 2 — ) Р (Р 2) () и ) — ( Р( ) + ( и — Р) (( и'(Р - + [ Р (Р 2)) ) > у)и — Р)2()и)Р ~+(Р(~ ), и, оси Е". (13) ПРАВИЛО МНОЖИТВЛВН ЛАГРАНЖА 9 8! Покажем, что ]и]и '+ ]и]а ') ]и — и]и 'поп(1; 2с — а), и, ияЕе. (14) Рассмотрпм функцию ф(х) = (х" + 1)с(х+ 1)" при х ) 1, а ) О. Иьсеем ф'(х) = а(х" ' — 1) (х+ 1) " '.
Если а ) 1, то ф'(х) ) О, и ф(х) ) ф(1) = = 2' —" для всех х ) 1. Если 0 < а < 1, то ср'(х) < 0 и ф(х) ) ф(сс) = 1 при всех х ) 1. Следовательно, ф(х) ) А = шш (1; 2'-") (х ) 1), плп А (х+1)" <х" +1, х) 1, а) О. (15) Далее имеем ]и — и]е-с < (/и] + /и])т-'. Без ограничения общности можем считать ]и] ) (и]. Тогда с помощью неравенства (15) получим ]и — и(Р з<]и]и з(]иии]+1)с' з<А с ((]и]с]и])с' з+1))и]" что равкоссгльно (14). Бз (13) и (14) следует неравенство (12).
С помощью теоремы 3 отсюда заключаем, что функция 1(и) = ]и]и при р ) 2 равномерно выпукла на е" с модулем б(с) = се псш (1; 2с-г)12. Более тонкие оценки показывают, что функция 1(и) = ]и]а прн р ) 2 имеет точный модуль выпуклости и(С) = Се]2г-с (С ) 0).
Будет ли функция 1(и) = ]и]т равномерно выпуклой на Е" прп 1 < р < 2? Оказывается, не будет. Чтобы убедиться в этом, достаточно показать, что функция ф(х) = хт одной переменной при 1 < р < 2 не будет равномерно выпуклой на полуоси х ) О, поскольку функция 1(и) = = (и)т вдоль лучей и= Се (]е] =1) ведет себя как функция Си одной переменной. Если бы функция ф(х) = хе (1 < р < 2) была равномерно выпуклой прн х ) 1 с некоторым модулем выпуклости б(с), то согласно теореме 2 необходимо выполнялось бы неравенство (10), В данном случае неравенство (10) имеет внд 25(С) <СР [( + С)т-' — * -'], х)О, С)О, С помощью формулы конечных превращений отсюда имеем 26(С) < Яр(р — 1) (х+ ОС)а ' < Нр(р — 1)хе ', х ) О, С ) О. Зафиксируем адесь произвольное с ) О, а х устремим к сс.
Получим б(с) =— = 0 прп всех С ) О. Таким образом, функция 1(и) = ]и]т прн 1 < р < 2 не является равномерно выпунлой на Е". Маятно, однако, показать, что зта функция строго равномерно выпукла на любом выпуклом ограниченном множестве нз Еп [92] 9 8. Правило множителей Лагранжа 1. Пользуясь теоремами отделимости выпуклых множеств, можно получить условия экстремума для более общих задач па условньш экстремум, чем задачи из 3 2.2. А именно, рассмотрим задачу 1(и) - сп1; и ж ьс, (1) У = (и Я У,: д,(п) < О, с = 1, ..., т; Ег(и) = О, с = т + 1, ..., 8), (2) где П, — заданное множество из Е", функции У(и), дг(и), ..., Е,(и) опРеДелены на ссз и пРинимают конечные значениЯ.
224 злвмкнты Вьшуклого АнллизА [ГЛ. 4 Здесь не исключаются воаможности, когда отсутствуют либо ограничения у,(и)<0 типа неравенств (и< 0), либо ограничения д,(и) = 0 типа равенств (г = и), либо оба вида ограничений (пг =в = О, У= У<). Разумеется, и само множество П, адесь может задаваться ограничениями типа равенств и неравенств. При выделении множества У< в (2) обычно руководствуются тем, чтобы У< имело простую структуру, чтобы легко (без трудоемкой вычислительной работы) можно было проверить включение и<н У„указать какую-либо конкретную точку из П„ чтобы легко было проектировать точку на У< и т. д.
В задачах линейного программирования роль У< обычно играет неотрицательный ортантЕ+. Часто множество У, представляет собой параллелепипед У<=(и=(и', ..., й)<нЕ": а<(и'(~<, 1 1, ..., г), (3) где аь р< — заданные числа, и<( р< (возможно, некоторые а<= — ). Конечно, в (2) не исключается возмоя<ность У, =Е . Здесь мы можем вспомнить теорему 2.21, в которой с помощью функции Лагранжа было сформулировано необходимое условие оптимальности для задачи (1), (2) в частном случае, когда У, =Е, т = О.
При исследовании задачи (1), (2) и общем случае также важную роль играет функция Лагранжа 2'(и, Л)=Л!(и)+Лу,(и)+...+Лу,(и) (4) переменных и=(и', ..., и")ы У„Л=(Л„Л„..., Л,)ыЕ'+<, Теорема 1. Пусть и„он<< — точка локального минимума в задаче (1), (2) функции У(и), у,(и), ..., у„(и) дифференцируемьь е точке ие, функции у„<.,(и), ..., д,(и) непрерывно дифференцируемь< в некоторой окрестности точки ие, с<< — выпуклое ° Ф *'Ф множество.
Тогда существуют числа Лг, Л„..., Л, такие, что Л* = (Лг< ..., Л) ~0< Лг)0, Л<)0, ...< Л )О, (5) (У„(ие, Л'), и — иг))~0 гиен У„ (6) Л;у (ие) = О, < = 1, ..., г; (7) здесь Х„(ие, Ле) = Л У'(и. )+ Л<у,(и,„) + ... + Л,у,(и„) — градиент функции!е'(и, Ле) переменной и<и У, в точке и = ие. ° $ Числа Лг, Л„..., Л, называют множителя и Лагранжа.
Согласно условию (5) Л, и множители, соответствующие ограничениям типа неравенств, неотрица тельны, а множители Л +и ..., Л., соответствующие ограничениям типа равенств, могут иметь любой знак. Ограничение у<(и) ~ О, где 1 «( и<, называют активным (пассивнььи) в точке ие, если у (ие) = 0 [у<(и.„)(0~. Иа условий (7), часто называемых условием дополняющей нежесткости, ПРАВИЛО МНОЖИТЕЛЕЙ ЛАГРАНЖА $8! 225 следует, что множители Лагранжа, соответствующие пассивным ограничениям типа неравенств, равны нулю. Задачу (1), (2) называют регулярной (нееырожденной) в точке иа, если существуют множители Лагранжа Л* с координатой Л,") О; в противном случае задача (1), (2) называется нерегулярной (еырожденной), Простейший класс регулярных задач получается из (1), (2) при т= 8=0, У= У,.
В атом случае ограничения типа равенств и неравенств в (2) отсутствуют и нет необходимости вводить множители Л„..., Л„поэтому 2'(и, Л)= Л,У(и), условия (7) исчезают; кроме того, из (5) следует, что Ле)0, а тогда неравенство (6) превратится в условие (Г(ие), и — ие))~0 (и~У), известное нам из теоремы 2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
