В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров, Сборник задач по оптимизации (теория, примеры, задачи) (1155771), страница 11
Текст из файла (страница 11)
1бА = гА. 2. /)зА = блА. де1 <) (1рА) (х*) =- зп р ((х'з, х) — 1п1 (а ~ а ) О, х/сс ~з А)) = х <О, х* н=- пА, =- зпр зпр ((х*,х) — сс) = — ~ и х=аА +со,х фпА, ~> 3 . О з- :А =~- гА = илА. < Ое- =А ='» зА(х'з) ~: О. Если гА(х*) =О, то весь луч ах* принадлежит поляре и, значит, ряА(х*) = О. Пусть гА(х*) >-О. Тогда Уя>О=~гА(х*/сс) = а 'гА(х*), т.
е. гА (хз) = 1п1(сс ! (хз/сс, х) 1 Чх я=- лА) = )зяА (х*) ~>, 4. 1р = бдр. ее~ <) 1р= зпр((х х) р(х)) = х О, (хз, х) «( р (х), Ух, — б др (>. + оо, в остальных случаях 5. оК= — пК. вг! 6. зК= боК. 7, бпК= гК, Пусть А, и А, — множества в Х. Тогда из определений легко выводятся равенства: 8 6(А1+Ае) =ЬЛ1®ЬАг.
9. 6(А~ П Аа) = 6А~ ~Г ЬАг = ЬА1 + ЬАе. 10. 6(Л, сопч Б А,) = ЬА, сопч /~ ЬА,. Запишем теперь символически результаты теорем пп. 3.2.1 и 3.2.4, касающиеся оператора 1: Р1= Л (1) 1(Л+Ь) = — Ч ~~Ь, (2) ЩЕУ,) =1У,+гУ„ (3) гц,чу 'ч К ц, (4) ПЛсо Ла=гЬМг~,. (5) В (2) — (4) мы также пишем =, если равенство име- ет место без дополнительных допущений, и ж, если нуж- но наложить некоторые требования относительно непре- рывности функций ~, и ~,. (Утверждение (1) доказано в ЛТФ, с. 227; см.
также (131, с. 186. Утверждения (2)— (5) доказаны в (13), с. 188 — 194.) А теперь выведем иэ выписанных соотношений неко- торые из сформулированных теорем, предоставив читате- лю доказать остальные, Теорема п. 3.2.1. 4 Пункт а) есть теорема Фенхеля — Моро (1).
Необхо- димость пп. б) и в) очевидна. Докажем достаточность. б) Пусть Л выпукло, замкнуто и содержит нуль. Тогда 8А рЬЛ ЬА ~ Аоо Л (0) в) Пусть К вЂ” выпуклый и замкнутый конус. Тогда е. (е) а'К вЂ” '( — л) ( — я) К = ЯРК = К ~> Теорема 1 и. 3.2.3. Докажем пункт а) теоремы для выпуклых однородных функций. е. 4. сз> 6(др,+др)='Ьдр,®Ьдр ='1р ® 1р =— (з) 4. =-1(р, + р,) = Ьд (р, + р,), (> Для неоднородных функций результат теоремы п.
3,2.3 следует из того обстоятельства, что для выпуклых функций д~(х) =др, где р(х) =~'(х, х) =1пп (~(х+ ах)— а40 — У(х))я ' (подробности см. в (131, с. 207, 208), Я Докажем теперь несколько формул из таблицы. Л) Пусть р, и р, — две конечные и непрерывные на Х выпуклые однородные функчии. Тогда д(р, Ъ' рв) = др сопч Л дрв. 4. (4) 4. <3 6д (р, ~ р,) — ' Е (р, ~/ р,) — Ер, сопч /~ Ер,= = 6др, сопч Д 6дре =' 6(др, соп т Ц дрв). (:» Б) Пусть А, и А, выпуклы и 1пФА, П А, чь 8. Тогда г(А, ПА,) =гА, + гА,.
сД г(А, Д А,) =' Е6 (А, П А,) = Е (6А, + 6А,) й =Е6А, ~ Е6А,='гА,®гА, С> В) Пусть К, и К, — выпуклые конусы и 1п(К, П К,ч~ ~ И. Тогда (К1 Д Кв)* = К1 + Кв, 6л(К1 П Кв) г(К1 П Кг)ли~ гК1Р гКв = 6лК, щ 6лК, — 6 (лК, + лК,), ~> Остальные формулы доказываются аналогично. Упражнения. 1. Доказать, что конус К является выпуклым тогда в только тогда, когда из условия х„х,<иК следует, что х, +х,~К. 2, Доказать,' что для выпуклости собственной функции Е необходимо и достаточно, чтобы неравенство Иенсена е(сех, + (1 — сех,)) ~ а/(х,) + (1 — сс)е(х,) выполнялось ч'х„хг ~ Х, Усе г— : [О, 1).
3, Доказать, что функция р является выпуклой однородной на пространстве Х тогда и только тогда, когда р (сех) = ар (х) Усе ) О, Чх я= Х и р (х + х ) ~ р (х,) + + р(хв) Ух„херов = Х, 4. Доказать, что не существует выпуклой ограниченной функции, определенной на всей прямой и отличной от константы. 5. Доказать, что любая выпуклая функция, конечная на всей прямой, непрерывна. 6. Доказать, что сопряженная функция является выпуклой и замкнутой.
7. Доказать, что функция, сопряженная к собственной функции, также является собственной. 8. Доказать, что поляра множества А с=В" является выпуклым и замкнутым множеством в В", Ь В. и. Алексеев и лр. 65 9. Доказать, что субдифференциал выпуклой однородной функции является выпуклым и замкнутым множеством в К". 10. Доказать, что индикаторная функция выпуклого множества является выпуклой. 11. Доказать, что функция Минковского выпуклого множества является выпуклой однородной. 12. Доказать, что опорная функция множества является выпуклой. 13. Показать, что условие выпуклости в п. а) теоремы п. 3.2.4 является существенным. Задачи.
3 1. Выяснить, при каких значениях параметров дан- ные функции являются выпуклыми: а) ~(х) ах'+ Ьх+ с; б) /(х) ае'*+ Ье*+ с; в) /(хо ха) ~~а (!х~! + [хр!')'", р ) 0; г) ~ (х1 хг) а11х1~ + 2а12х1х~ + а х~а 3.2. Являются ли выпуклыми следующие функции: а) /(х) х[пх+(1 — х) 1п(1 — х), хаа (О, 1); б) ~ (х) = 1п1 [х', + х' ,! х, + х, ~ х1~ 3.3. Найти сопряженные функции от следующих функ- ций одно~о переменного: а) е"; б) ах'+Ьх+с; в) !хР/р, р)0; г) б(0) — индикаторная функция множества А ° (0); ( — 1пх, х.: О, д) б[а, Ь1; е) /(х) = '[+, .:-.О. 3.4.
Найти сопряженные функции от следующих функций многих переменных: а) а,х,+агх,+Ь; 2 а. а1х1+а а ха б) а„х, + 2а„х„х, + аа,х,; в) в г) бВ, где В -"((х„х,) ей'!!х,/а,!'+ !х,/аа!" (1), р) 1' и) /(х„..., х.) ° шах(х„..., х„). З.Ь. Найти вторые сопряженные функции от следую- щих функций: а) УТх!; б) (х'-1)'", в) е1пх; г) 1/х', д) !х[+ [х — а[; е) ! !х! — 1!. 3.6.
Найти сопряженную функцию от функции С([0, 1)) — В, /(х( )) = тпах х(~). ~я[о,11 3.7. Найти поляры следующих множеств на плоскости! а) А = И-1, — 1), (-1, 1), (1, -1), (1, 1)); б) А = !(т„х,)1х,' + х~ < Ц) в) треугольник с вершинами в точках (1,0), ( — 1/2, =ь УЗ/2); г) Б„=((х„х2)! !х,!" + !х,!" < 1), р) 1; д) А = ((хд, хо)1хг~/аг + х~/а~~(1), 3.8. Вычислить субдифференциалы следующих вы- пуклых однородных функций одной переменной: а) !х!; б) шах(х, 0); в) шах( — х, О). 3.9. Вычислить субдифференциалы следующих выпук- лых однородных функций многих переменных: и г12 а) !х! — ~х', ! б) шах !х,!; 1=1 ~=1...,и в) шах х,; г) шах(О, (а,х)), а~ В", 3.10. Вычислить субдифференциал следующей выпуклой однородной функции в пространстве 0([0, 1) ): /(х( )) = шаххИ). ы(о ~д 3.11. Найти субдифференциал нормы (как выпуклой однородной функции) в нормированном пространстве.
ЗЛ2. Найти субдпфференцпал д/(т) следующих выпуклых функций: а) Х В, /(х) = шах (е", 1 — х), т = 0; б) Х= С((0, 1)), ~(х(.)) = тах !хИ)!, Ъ) = в)пЗл1. гя(о, 0 ЗЛЗ. Найти функцию Минковского для треугольника с вершинами в точках (1, О), ( — 1/2, ~УЗ/2). ЗЛ4. Найти сопряженную функцию от функции Минковского. 3,15. Привести пример выпуклой замкнутой функции / и точки х таких, что !/Й)! (, д)(х) = О. ЗЛ6. (Р) Доказать, что если /; В' - В и при етом ~~(х) УЬ), то У(х) =!х!'/2.
ЗЛ7. (Р) Доказать, что если поляра множества в евклидовом пространстве совпадает с самим множеством, то зто множество является единичным шаром. 3.18. Привести пример выпуклой, но не замкнутой функции. ЗЛ9. Показать на примере, что суперпозиция двух выпуклых функций не всегда выпукла. 3.20. Показать на примере, что сумма двух выпуклых замкнутых функций не всегда является выпуклой замкнутой функцией. $4. ВЫПУКЛЫЕ ЗАДАЧИ 4Л.
Принцип Лагранжа в выпуклом программировании. 4ЛЛ. Постановка задачи. Задачей выпуклого программирования (или выпуклой задачей) называется следующая экстремальная задача: ~,(х) - 1п1; ~~(х) ~ О, 1 1. . ., т, х «в А. (з) Здесь )',: Х- В, 1=0, 1, ..., т,— выпуклые функпип (функционалы), отображаюшие некоторое линейное (не обязательно нормированное) пространство Х в расширенную прямую, А — выпуклое подмножество в Х.
Поскольку из выпуклости функции ~ не следует, вообще говоря, выпуклость функции — 1, то существенно, что (з) — задача не максимизации, а минимизации. Точка х называется допустимой в (з), если х я А н ~~(х)~0,1 1, ..., т. Л е м м а. Пусть Х вЂ” нормированное пространство. В выпуклой задаче локальный минимум является и глобальным. 4 Пусть хвв1осш1пз. Это означает, что существует окрестность Я точки х такая, что — ( ~,(х) < ~,(х) для любой допустимой точки х«з Я.
Возьмем произвольную допустимую точку х. Тогда при достаточно малом а- С ° ~ вектор х = (1 — а)х+ ах еа Ф и является допустимым. ° ' Следовательно, по неравенству Иенссена 1,(х) ~ ~,(х) ~ ~ (1 — а)~,(х) + а~(х), откуда Дх) «й ~,(х). Поэтому в дальнейшем в выпуклых задачах мы, говоря «минимум», имеем в виду абсолютный минимум. 4.1.2. Правило решения. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
