Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 8
Текст из файла (страница 8)
П доказательстве необходимых условий экстремума в гладкой ри докатя задаче с равенствами и неравенствами нам понадобится следующая теорема о субдифференциале максимума. Дубовицкого — Милютина. [Глава 6, Введение] Пусть Л и уз — непрерывные выпуклые функции на Х, у1(Х) = Я ). д тахЦЬ ~з)(й) = соич(ду~(Ю) и 01~(й)). Сформулируем также теорему Дубовицкого — Милютина для субли- нейных функций. Теорема.
Пусть рн рз — непрерывные сублингйные фу ц ф ик ии. Тогда д тах(рн Р~ИО) = сооч(др,(О) г1 др~(0)). 45 в 4. Выпуклые задачи Глава 1. Экстремальные задачи 4.2. Теоремы отделимости При выводе необходимых условий экстремума (принципа Лагранжа) в выпуклых задачах и в задачах с равенствами и неравенствами мы будем использовать свойство отделимости непересекающихся выпуклых м ножеста.
Определение 1. Множества А и В из пространства Х называются отделимыми, если существует линейный непрерывный функционал Л Е Х', Л ~ О, для которого гп!п(Л,а) > так (Л, Ь) агЛ ' ЫВ Из определения следует, что множества являются отделимыми, если можно провести гиперплоскость Н = (х Е Х ! (Л,х) = с), с б К, так что одно из множеств лежит в одном замкнутом полупространстве Н» = (х Е Х ! (Л, х) > су, а другое — в другом замкнутом полупространстве Н = (х Е Х ! (Л,х) < с). Определение 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а! .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
