Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 8
Текст из файла (страница 8)
Определение 2. Множества А и В называются строго отделимыми, если существует линейный непрерывный функционал Л Е Х', для которого пнп(Л,а) > тах(Л,Ь). «ЕЛ 6СВ Приведем результаты об отделимости в конечномерном случае. Теорема ! (первая теорема отделимости в консчномерном случае). Пусть А и  — нгаустыг выпуклые множества' в К", А П В = й6. Тогда множества А и В отделимы. Теорема 2 (вторая теорема отделимости в конечномерном случае). Пусть А — иепустог выпуклое замкнутое множество в К", Ь к А.
Тогда точку Ь можно строго отделить от множества А. Доказательство теорем 1, 2 см. (ГГ, с. 20). Сформулируем результаты об отделимости в случае нормированных пространств. Теорема 1' (псрвая теорема отделимости в нормированных пространстнах). Пусть А и  — иеиустые выпуклые множества в Х, т1А ~ «З, пи А й В = и. Тогда миожесгива А и В отделимы. Теорема 2' (вторая теорема отделимости в нормированйых простран:твах). Пусть А — иепустог выпуклое замкнутое множество в Х, Ь й А. Тогда тачку Ь мохсиа строго отделить ат миажества А. Доказательство теорем 1', 2' см. (АТФ, с.
124]. 4.3. 3йдйчи без огрйиичеиий Пусть у: Х вЂ” К вЂ” выпуклая функция, отображающая нормированное пространство Х в расширенную прямую. Выпуклой задачей без ограничений называется следующая экстремальная задача: у(х) пни. Теорема !аналог теоремы мы Ферма), Влл ного чтобы тачка х доставляла х Е аЬаттР, в выпуклой задаче бгз ограничений (Р) абсолютный минимум (х Е аЬзт!и ), необходимо и достаточно, чтобы выполнялось саатиошгиие О б дг(х).
доюгэе тельство. у(й) > О = (О, х — Е) 'Ф х Е Х сь О Е ВУ(*). Поскольку из выпуклости функции у не следует, вообще говоря, выпуклость ункции— ф —,Г, то существенно, что рассматривается задача минимизации, а не максимизации. 4.4. Зйдйчи с огрйиичеиием Пусть у Х вЂ” К вЂ” выпукаая функция отображающая нормиро ванное пространство Х в расширенную прямую, Р С Х вЂ” выпукаое множеспю. Выпуклой задачей с ограничением (ил рост и п о выпуклой задачей) называется следующая экстремальная задача: г(х) - ппп; х б Р. Теорема.
та ос Н«ус х Е 1ост!пР— доставляет локальный минимум в выпуклой за че г р ог а да (Р). Т да х б аЬат!пР— доставляет абсолютный минимум в этой задаче. ок отпасть У точки х, такая, что — оо < у(х) < у(х) ч' х Е У й Р. Возьмем произвольную точку х б Р. Тогда окрестность У =,1 — а,э+ ах б У Г6 Р при достаточно малом а > О. Следовательно, по неравенству Иенсена Сь Х < у(х) < у(х) < (1 — а)у(й) + ау(х), откуда ау(х) < аГ(х) сь у( ) ,У(х) ч х Е Р.
Значит, х доставляет абсолютный минимум в задаче (Р). ° Из тео мы следует, что в выпукаой задаче локальныи минимум является и абсолютным (глобальным). Поэтому в дальнейшем в выпуклых задачах, говоря «мин нимум», имеем в виду абсолютный минимум. 46 Глава !. Экстремальные задачн 4.5. Задача выпуклого программпровапия Пусть Ус: Х вЂ” К, о = О, 1,..., по, — выпуклые функции, отображающие нормированное пространство Х в расширенную прямую, А С Х— выпуклое множество.
Задачей выпуклого программирования называется следующая экстремальная задача: Уо(х) — ппп; ус(х) < 0 о — ! щ Точка х называется допустимой в задаче (Р), если х Е А и выполняются все заданные ограничения типа неравенств. Упражнение. Докажите, что задача выпуклого программирования является выпуклой задачей, т. е., что множество допустимых элементов в этой задаче является выпуклым множеством.
Теорема Куна — Танкера. 1. Если й Е аЬзпнп.Р— решение задачи выпуклого программирования, та найдется ненулевой вектор множителей Лагранжа Л = (Ло, Лс,..., Л ) Е ы К~+', такой, что длл функции Лагранжа Л(х) = 2 ', ЛсУс(х) выпсинюатся с=о условия: а) принцип минимума доя функции Лагранжа пппй(х) = й(й); тол Ь) дополняющей нгхгесекагти: ЛсУс(й) = О, с) неотрицатглонасти: 1= 1,...,по; Л >О о=О! пс 2.
Если йи допустимой точки й выполнены условия а) — с) и Ло ф О, та й Е аЬящпР. 3. Если длн допустимой точки й выполнены условии а) — с) и мналсяства допустимых элементов удовлетворяет условию Слейеера, та х Е аЬящп Р. Прн проверке достаточных условий минимума в задаче выпуклого программирования будет использоваться некоторое условие регулярности множества допустимых элементов — условие Слейтера. Множество допустимых элементов в задаче (Р) удовлетворяет условию Слейтвра, если сУществУет точка й Е А, дла котоРой Ус(х) < О, о = 1,, гп. а 4, Выпуклые задачн 47 считаем, что гос г = 'йс = Π— иначе введем новую функцию Уо(х Уо(х) — Уо(й). Положнм В = (Ь = (Ь Ьн, Ь,„) Е К "' ! 3 х Е А: Ус(х) < Ьс, о = О, 1,..., Покажем, что и — непустаг выпуклое множество. Действителыю, неотрнц нцательный октант сс+ Кт+! С В т.е.
любой ектор с нео'рица т В, ибо в определении множетельными компонентами принадлежит, и о в В. став В можно положить х = х. Докажем вы укл п ость мнохсества ь, что Пусть точки и пр Ь Ь' ннадлежат множеству В. Надо доказат, / аЬ+ (1 — а)Ь' Е В 'Ф а Е (О, 1). Поскольку точки Ь, Ь Е В„то по опре- А такие, что Ус(х) < Ь;, делению множества В существуют х,х Е Ус(х') < Ь;, о' = О,,..., гп. ол —,1 .... П ожнм х = ах+(1 — а)х'. Тогда х Е А, ,о'=0 1 ...,по, поскольку А — выпукло, а ввиду выпуклости функций Ус, о' =,,..., по, по неравенству Иенсена У (х ) = Ус(ах+(1 — а)х') < аУс(х) +(1 — а)Ус(х) < аЬ;+(! — а)Ь,, т е точка аЬ+ (1 о)Ь Е В м С = (с = (со 0 ...,0) Е К + ! со < О) — открыты«лу'с в пространстве К +'.
Ясно, что С вЂ” непустае выпуклое множества. то С Г! В = И. Действительно, если бы существовала точка Покажем, что С й = . е В отсюда следовахо с Е С й В, то ввиду определения мнолсестаа бы, что имеется элемент х Е А, для которого выполняются неравенства: Уо(й) < со < О, Ус(х) < О, о = 1,..., пс. Но из этих неравенств следует, что У (В) < У (х) = 0 т е й Е аЬзпип Р Получили противоречие с условием теоремы й Е аЬоппп Р.
Значит С ГС По первой теореме отделимости в конечномерном случае множества В и С можно отделить, т.е. существует вектор для которого щ!и ',У „ЛсЬ, > щах ~~ ' Л;с; = гпах Лого > 0 Таким образом ЛЬ;>О ссЬЕВ. с=о Из неравенства сог улуг ( ) б выведены условия неотрицательностн, дополняющей нехсесткостн н принцип минимума. 49 а 4. Вывуклые задачи Глава 1. Экстремальные задачи 1. Условие неотрицательности. Поскольку, как мы уже говорили, любой вектор с неотрицательными компонентами принадлежит В, то вектор (О,...,0,1,0,...,0) Е В, где единица стоит на 2-ом месте (счет начинаем с нуля). Подставив эту точку в неравенство (ь), получим, что Лг >О.
Зслпвие допаоняющей нелсестности. Нетрудно видеть, что точка (О,...,О,У,(х),0,...,0) Е В. Действительно, в определении множества В возьмем х = х, тогда х Е В и нужные неравенства выполняются. Подставив эту точку в неравенство (ь), имеем Л,З,(х) > О.
Если Л;~,(й) > О, то (так как по уже доказанному условию неотрицательности Л, > 0) Г,(й) > 0 — это противоречит допустимости точки х. Значит, Л,у)(х) = О. Принцип минимума. Возьмем точку х Е А, тогла точка (го(х), ,Г1(х),... у (х)) б В. Отсюда по неравенству (ь) Л(х) = ~ Л;у,( ) > О = 'Я Л,(1(х), )=О 1=0 так как, не ограничивая общности, положили Ях) = 0 и по уже доказанному условию дополняющей нежесткости л)зг(х) = О, 1' = 1,...,пь. Таким образом, принцип минимума для функции Лагранжа доказан. 2. Пусть для допустимой точки х выполнены условия а) — с) и Ло ~ О.
Положим Ло = 1. Тогда для любой лопустимой точки х будет выполняться неравенство )о(й) = Уо(й) + ~', Л;уг(х) 'А' Л(й) < и=1 м а) он с) < л(х) д Уо(х) + х~, л;Лг(х) < Уо(х). Это означает, что х Е аЬзщ!и Р. 3. Пусть для допустимой точки х выполнены условия а)-с) и множество допустимых элементов удовлетворяет условию Слейтера. Прел- положим, что при этом Ло = О, Так как вектор Л Ф О, то в силу условия неотрицательности существует Л . > О, 1 Е (1,..., т), Следовательно, м с) И1 Л(х) = ~~2 Л, У)(х) «Лг уг(х) < 0 = ~ь Л1 Г1(х) = Л(й). г=1 Но это неравенство противоречит с условием а). Значит, наше предположение, что Ло — — 0 неверно.
Поэтому Ло ~ 0 и по доказанному п.2 х Е абзш!пР. Теорема Куна — Таккера полностыр доказана. Пример. (1 1) х1 + хг — 2 > О, д)2(х) = ~ (а,о), (о! < 1, х, + хг — 2 = О, » О е ду(х) е=» (-1, — !), Х1 + хг — 2 < О 2Х, +хг+ 3 = О, х1+2хг+3=0 2х, + хг+ За = О, х)+ 2хг + Зо = О ( 2х1+ х2 — 3 = О, Х1 + 2хг — 3 = 0 при Х1+х2 — 2 > 0; при х, + аг — 2 = О, (1а! . 1); (!!) (ш) при х, +хг — 2 < О. В случае (!) нет критических точек, так как из уравнений системы следует, что Х1+ х, = — 2 — противоречие с условием х, + хг — 2 > О. В случае (гй) также нет критических точек, так как из уравнений системы следует, что х + х = 2 — противоречие с условием х1+ Хг — 2 < О. г= В случае (й) система из трех уравнений с тремя неизвестными и ее ЕДИНСТВЕННОЕ РЕШЕНИЕ Х1 —— Х, —— 1, О = — 1. ТаКИМ О6РаЗОМ, даь = 3.
при х, =х2=1 у(х„х ) = х', + х,х, +*',+ 3)Х1+ хг — 2! — """. Решение. Функция З(Х1, хг) является выпуклой функцией как сумма 2 2 ып кла двух выпуклых функций. Функция о(х„хг) = х, + х,хг+ хг выпукла, так как по критерию Сильвестра матрица вторых производных дй(х) 2 1 не зависит от х и положительно определена. Очевидно, что функция )2(х„хг) = )Х1+ хг — 2), валяющаяся модулем линейной функции также является выпуклой функцией.
Необходимое и достаточное условие экстремума в выпуклой задаче без ограничений: 0 Е дз (х) = дд(х) + Зд)2(х). Для лифференцируемой функции ее субдифференциач совпадает с производной: дд(х) = (2Х1+ хг,х1+ 2хг). найдем д)2(х), по определению субдифференциала а = (а1, аг) б д)2(х) ч=» (х — х, а) < )2(х) — 6(х) о'х Е Вг ч=» а,х, + агхг — а1А — агхг < )Х1 + хг — 2! — )х1 + хг — 2! 4=» а1(х) + хг) + (аг — а1)хг < )Х1 Е хг — 2! — )х1 + хг — 2) + а121 + агхг Отсюда вытекает, что )а,! < 1 и а1 = аг, т.е. а = а,о , о ,о, о < 1.
Поэтом 50 Глава !. Экстремальные задачи 51 4.б. Задачи, упражнений В задачах 4.1-4.4 выяснить, при каких значениях параметра функ- ции являются выпуклыми: 85. Элементы функционального анализа ф 5. Элементы Функционального анализа 5.1. Нормированные и банаховы пространства 4 11. у(х, х„) = 2 ', !х !. »=! 4,12. У(хн...,х„) = »пах !хд!.
» = ! ... л 4 .13. У(х н .. . , х„) = »пах а, . »щ,...м 4.14. у(хн.,.,х„) = гпах (О,(а,х)1 (а Е а ). ,1.15. у. Х й, у(х) = цхц (Х вЂ” нормированное пРостРанство). 4.1б. Доказать, что любая выпуклая функция, конечная на всей прямой, 4.17. 4. 18 4.19 4.20 4. 21 4.1. 4.2. 4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
