Галеев Э.М. - Оптимизация (теория, примеры, задачи), страница 5

.,=ис-Ат).решениянеравенствконечномернойограничениямисзадачиследует:т1)Составитьфункцию2)а)Выписатьнеобходимоестационарности:Ь)дополняющейА(х)Лагранжаусловие==г0,=I порядка:1,. .,гонеотрицательности:А;^0,г=1,. .]Р А*/<(а;).1=0экстремуманежесткости:А,-/.-(А)с)допустимыхконусЛагранжамаксимумачто{/г€К"|(/ (^),/г)<0,—1.=точка—К/г €К:=где1,. .,множителейгладкойрешениягсовокупность—Vа,0,=условиетого,равенств/г)этойисключениема||/г| 2^константой{//(ж),условияА € 1осгшпТогдак)А)/г,,т.типа§ 3.

Конечномерные3)гладкиеНайтиточкиПрива)Ь)с)а)-с)условиямвзадаче.=1=-1(или(илиа)Влюбой(этиточкислучаиконстанте);константе).положительнойотрицательнойлюбойкритическиеВзадаче.рассмотреть37неравенствами0;=точкиЬ)случаес)случаедоставлятьмогуткритическиекритическиеминимум,иточкимакси-минимуммаксимумдоставлятьмогутточкиидоставлятьмогутзадаче.ПринахожденииЛ,0=критическихА{/;(ж)нежесткости4)0=гдополняющейусловияхвточеккаждогодляне-дварассматриватьнадослучая:А< Ф 0.иИсследоватьлокальныйнакритическиеабсолютныйиеслиили,точкипоследовательностинайденныеэкстремум5пиднайтинет,ихдопустимыхнаточек,5шахикоторыхуказатьиабсолютныеэтидостигаются.экстремумыПриэтомиликаждойкритическойнеобходимыхперейтитипанеравенствбудемисследованиипри3.4.+=+х2а;3—*■т'ш;критическойвточкеХ0(х\2х\+х2—5,^х^+а^х2+х^=+х\+х\)НеобходимыеХгB^1+Х2-локальногоусловия+Жз-5)++А2А2(Ж1+Х2+Х]-минимума:стационарности:АХ1=ГЛ'дополняющей=03.ЛагранжаФункцияРешение.Ь)функцииточках.1.хха)непосредственнуюПримерыПримерЛправило,какиспользоватьдопустимыхограничениямиПоэтому,исследуемойзначениеблизкихввнеобхосзадаченепростая.экстремумасравниваязначениямиеепроверкавзадачапорядкавыполненияэкстремума—про-Iэкстремумачтоусловийипроверку,Отметим,точке.равенствмыусловийисследованиюкдостаточныхилинепосредственнойвоспользоватьсяпытатьсяможнопроверкойсиудовлетворяющиеотдельноследуетэтомА0АоАоВ случаевх,равенствамискритическими).называютсямаксимумзадачи<=><02А0Ж!4=>0,АХ10,ЛЖ2АХ} =0,Г==I2Ал+<^<=>I2ХоХ1+2Хох22А0ж3-+нежесткости:х2+Х]-5)=0;=2А1ХгА!0,+++А2Х2А2===0,0,0;3).38Главас)Экстремальные1.неотрицательности:АоЕсливсеАо0,=тоПоэтомуВыразим=А[—А2,—Г2А!4АХ-\-а)условияАьчерезА2:Х\+х\уравнениявнеможет.Ь)1х\-2А!-А2,А2=0=—-.силувусловияЗначит,А22А2--=Пусть=равенство+х\1—фТогдах2+х^=+Х2х->,+х2—хт,ж21х\3,=сх\х\=0.=5,А1-А2,+х2—5—=хзх\ВейерштрассатеоремыхA,1,1)=ПримерПриведение2.ПустьА5т1поо—*■—.=1=\х\при3,5,==Ь).ПодставляяЗО-А2ж,--А2=-1=^а;1==асуществует,бытьможетрешениемслед-позначитоо,—»задачивсилуона.только3.=квадратичнойдЗА22А2--точка.точки(яу)(.=-А2.-ЗА2=решениеаЬ$тт,€-неотрицательностичтох\+2Хг6\г-нет.а;3=(условиемполучаем,критическойИтак,х2=3,+\5,точеккритических=3,==критическая=единственностиА2А2--противоречие—0.}(х)из+А!А1--единственная—ФункцияследствиюА2А2-0\А!хъ0<—-случаев=А!А!+-9Ахоткудахг=А1чтовыводим,бытьэтогочтополучим,вАоподставивинули,тогдаизХх,Х2,хза)аполагаем\ ф§,Предположим0.^пункта—ф 0,АоА!О,>уравненийизЛагранжамножителихт,задачиформысимметричнаяосям.главнымк(Оуматрицаау,)=иф(а;)=лЕ«Х]ж){Лж,=соответствующая—ейквадратичнаяС}имеетформа.•,.7=1/ь••ВТеорема./п.•в>К"пространствесуществуетквадратичнаякоторомформабазисортонормированныйпредставление1=1В/ь.базисек/ьбазису.

.,Доказательство.любая.-,/„/ь. .,/пвекторовортонормированнаяформыматрицаназываются/п^главнымиприведениемназываетсяЕслифсистема.=0,Направлениядиагональна.формытоА!=..С},формыосямик=главнымА„апереходосям.=0,/ь. ,/„—3.§КонечномерныегладкиеС? ^ О, тогдаДляопределенностиРассмотримПустьзначения.значения.задачиффх)толькозадачукакафункцияжх)Необходимыеа)Ь)с){жх)-Ц/ъ/г}/11,ОбозначимЕслиАсобственный5пш1Аь=С}{х){х0Vх€К"€Ь\,Пусть<Э ^0ТогдаЬ\.наЬ\напринимаетРешениехсечение/2=НеобходимыеЕслиПоэтомуизто0,Фнули,полагаемравенствоДиилизадачу(Р2)существует,\)-таккомпактом.по-прежнемух)фчто0.=Вейерштрасса/2,0=А((/2,/2)а)пункта—Аолюбая—вторую(х, /,)1,\((х,+2ц(х,+/1)./1а^0/2и(задачаначтоА/2Ао=чтонена(А/2,/1)ц}х+0;=максимум!),+что^ДА^АВ0.=(I==00.силувсе—может.Тогда-1.А/2+0;=следует,бытьэтого1)-скалярнополучим,А0-4/2«=>выводим,векторовпоследнеевекторов<АоЛагранжаУмножаяД•,максимума:"независимостимножители•считаем,РассмотримАх0,•положительныеявляетсянежесткости:=/г,теперьтеоремех)Хй(Ах,условияАопоЬ^=а) стационарности:Ь) дополняющейс) неотрицательности:линейной(Р2)плоскостьюЛ0,=А.К".впринимает(х, х)тах;->задачиБЛагранжа2^!назначения.х)А„определенностиположительныешараФункция^Для(Ах,подпространство=—А),=матрицыЬ^.иззначения.(А!А^=значение=Таким1.=АД.—(.А/1,/1)чтоА}\этоно=Ь) {/ь/0А,0,=А}\получим,—..а)из/ь0}=Дчтоусловию=А2тосистемаотрицательные}\)0;=^ 0.матрицысобственное| (х,Х/1+Тогдапоиминимальное—==0>векторА!Ь\=0;=выводим,наскалярноОтсюдаА1.=Х0А^1)—0,а)Аополагаем0.<—^пунктаизравенствоортонормированнаяортогональностьиЬ).Зтш=Л(Р{)задачи«=>/1)А({/ь00,фпоследнееобразом,какфАтоАоК",вкомпактомЛагранжаО=АоПоэтомусуществует,является.неотрицательности:Умножая1}^Ах0,Вейерштрассатеоременежесткости:Аорассма-надоминимума:условию=по| (х,х)Функция1)-дополняющейпротиворечиттозначения,(Ру)К"€условия=(Ру)1.^неотрицательныестационарности:Еслих)(х,непрерывна.({ж,А+задачу—»тт;задачи=(Ах,х)Х0(Ах,1Д1/г=Вшаротрицательныепринимаетмаксимум.наРешениетакотрицательныеилифэкстремальнуюпервую39неравенствамиичтосчитаем,принимаетрассматриватьравенствамиположительныепринимает(Ах,Еслиса) А/2из/1и==учитываяА(/2,/1)А/2+М/1-ортогональ-+м(//)2'40!/==1М-/ОжаяОтсюда(А/2,/г)(/2) /т)А/2(МДалее{хК"=из2^2А),=/г)А„1,=(х,/2)B^0значения.отрицательныечтоЬ)условиюА,матрицыортогональны.Ь2<?(ж)0=V€хпринимаеттоположительныерассматриваем=Ь2,системаортонормированная2/2напоиподпространствоЕслилюбаяфТогдаВновь•/2иУмно-получим,векторВводим0}.—2/2на0>0.=/2,наА/1векторы/з,.

-,/п{/г^/д=собственный—=А/г)скалярнообразом.0,0,=Пусть•/2|/2|=^/гОтсюда0.>подобным| (х,=..■З'тах(/2,==образом,поступаем€АзТаким1-==задачи(АЬ,/!)=А/2Ц/г,/г)-^2/2=рравенствополученноеЭкстремальные1.Главазадачуилинаилиминимуммаксимум:х){Ах,Решая/ззадачу,эту(х, х)еххг;Поступаяаналогично,/\,-. ,/п{х, /2)=/звектортакой,(Р3)0.=-А/зчто=/2-шитогевкпридемсобственныхиз(х, /01,^единичныйполучаем/\ортогональнобазису->ба-ортонормированномуАматрицывекторовсобственны-спА1,.

.,А„.числамимиПриэтомвекторадлях5Г(а;>/>)/>=имеем1=1**Х>>=П)*ПЁ=1=1А,-<аг,/,)/,■и1=1п1=13.5.3.1.)7=11=1Задачих\хгхт,ж^еххг;—>х\+х\+1.^п3.2.3.3.ж]тах—»•7=1е*1""*23.5.а^+3.6.а?!+3.7.х\+х1Ах\3.8.а?!+а;?2а?1•7=13.4.—2а?11^^]^Е^-;7=13.9.х)^3ехгг;а?!-а;2++2а?1++х\х\—»ех!г;—»•а;з-^~хза;^++ехгг;ат^атгехгг;а^-=За;3~3,а;2а;2^0.а;3^12,а?!^0,а;2^0,а;3^0.+атз^12,а?!^0,а;2^0,а;3^0.1,х^0,^+а;з8а?!^х2^0.+еххг;а;2^0,а?!+а;2->Х\^0,1,^ж21,^а?!4а;2+Х2ж^+а?!ехгг;->■ехгг;-»•+а;2-0.-За;2+хгЗа;3^40,+х2-а;3=-.Выпуклые§4.2х\ЗЛО.3.11.За;1За;211а;!-За;2-2ж2+3.13.а;1а;3-2а;2—>3.14.а;!а;2а;3ех!г;3.15.Доказать—»2,->ехгт;—*■ех!г;ХуХу2а;1-а;2-За;3^а;!неравенство+За;3+7^0,1х2+За;3+^0,7 ^0,1,а;2а;^ 4-^^1,а;2За;14-2а;24-а;3+6.=^з8.=степенныхп/Е1а:7|Рч1/р^1т/Е1Ж71*\1/«й[^)\\Iтэкстремальнойрешения)0<Р^оо,,задачи7=17=13.16.40,=1х210,среднихдляппутем-^^1,а;3—Зх3+^ 0.а;3ех1г;Зх2-0.ех!г;—>2,&хг^а;3х3-^а;3—а;3—^а;3—Зх3-За;2—2ж2+5ху4х2+Па^—5х\3.12.2а;!+41задачиДоказатьнеравенствоарифметическимсредниммеждусреднимигеометрическим:^) У7=1§ 4.ВыпуклыеПустьвзадачиXпунктеэтом(определениелинейногопростоты■/=1,.

.,т.^тлинейное—пониманияможноЭлементывыпуклогопространствонормированноесчитать,см.пространстваXнормированногочтоК"=§5),вдляконечномерное—пространство.4.1.Напомнимесливыпуклым,@, 1)I €числаС:=ПустьЭлементV{=1комбинациейС.A+{с1,. .,ст}]Р 2,-с,-,=Ь^элементлюбыхдляXС2,- ^0,г=Множествомножества.выпуклогоопределениеназываетсяСубдифференциаланализа.двух1)а2-—1,. .,€п\точекатАизАилюбогоА.подмножество.конечноенекотороет,и]Р{=12,-=1,называетсявыпуклойСX42ГлаваСовокупностьвсехСмножества(иногдаМожнозаподмножествконечныхСоболочкойвыпуклойлегковсехберуткомбинацийвыпуклыхназываетсязадачисопуСобозначаетсяиС).сопересечениемЭкстремальные1.чтопоказать,оболочки).оболочкаконечногочислассовпадает(иногдаСсодержащихвыпуклойопределениеВыпуклаясошСмножествомножеств,выпуклыхэтоназываетсяточекпересесвойствовыпуклыммногогранником.Пусть(функционал)функциязаданаМножествоеР1/вКпространствеФункция•Xх/{(а,=/:х)КеX\XхК—*надграфикомназываетсявыпуклой,называется{—оо}Ыфункцииесли{+оо}.Ы/(х)}>аК:=/.надграфик/надграфик/выпуклое—множество.Функция•/замкнутой,называетсяеслизамкнутое—множество.Функция•Мы/будембудемтогдавыпуклатолькоиV-оофункции.сразумножествавыпуклогоопределения>хДляЯсно,чтотогда,Попробуйтефункцией.вытекаетследующейизкогда2./(ж)/(х)случаеем,\хГ,р>1.функцияК"-»•переменнойсразуопределениянепрерывнои>тогда,толькоО Vфункций,выпуклойвыпуклыхидваждыКтогда(/"(х)1теоремы—*•выпукла€хК).выпуклостько-функции.а€К.функцийвыпуклойАффинная(/:1?2(К)).К/:онапримеров=ВыпуклостьфункцияТогданеотрицательнаиз=определения3.Пустьнесколькоследуетсразу1.€производнаявтораяПриведемкоторых42.]с.(/ееоднойфункцийвы-являетсявсегданетеоремы.[Р,1.Теоремадифференцируемафункциейявляетсяпривестиклассическихмногих@, 1).* €Vфункцийпример!выпуклыхфункцияИенсена:неравенствофункцийвыпуклыхдвухсуперпозицияВыпуклостьидвухсуммаНо+оо.краткостичтоследует,выполненокогда\/хьх2еХ,выпуклой.выпуклой/ ^ифункции.«выпуклые»простоих/(ж)еслисобственныевыпуклыеизучатьназыватьИзсобственной,называетсяК).из1-2примеровсразуследуетизтеоремыфункции.}{х)=(а, х) +Ъ,а€К",Ь €К,вмногомерном1§ 4.АффиннаяВыпуклостьтакжефункцияфункций[Р,(/ее€(}"{х)(=^К"/:она)^О VС}(х)=(Ах,х),ЭтовытекаетсразуВыпуклымиявляютсянеотрицательнотогда,толькоАсимметричная—Аматрицакогдатогда,(функционалами)переменныхмногихнормы|,.

.,|а:„|},6.функцияИндикаторнаяА& А.хАмножествааГххтт{ааОпорная>чтобыфункцияонважногоопределениефункции,субдифференциалапроизводнойпонятиеСубдифференциаломвыпуклоймножество0/D)гладкомвв={х*сопряженномеХ*\(х-х,.4},€ЕАвчисло,А(х*,тахх€Аа>О,Vа>О,вкотороенадоА.множествомножества=Vиначе.наименьшеепопалнепустого$А(х*)Дадима-1а;0,означаетх,вектор8.|МинковскогоФункцияXСа~1х&А+оо,уменьшитьXСхеа,+оо,выпуклого{О,+оо.=множества/ о,_МинковскогоФункциярвыпуклогоЩх)={7.явля-функции:следующиеФункция2.теоремыизфункциямитакже5.следующеевсюдугдетолькоинепрерывнои).К"€хдваждытогдаопределена.неотрицательнопонятияК[гессиан)тогдаопределять1.—»выпуклапроизводныхвыпуклойявляетсяможнотеоремыфункцияТогдафункцияКвадратичнаяматрица,Пусть1>2(КП)).Иенсена.неравенствупопеременныхобобщениявторыхматрицаопределена4.42.]с.дифференцируемакогдавыпуклойнесколькихмногомерного1.Теорема43задачиявляетсяследующегоизВыпуклыеXСх).анализавыпуклогопонятияобобщающегофункцийвыпуклыхдляпоня-—анализе./функциих*)^/(ж)следу-называетсяхточкевX*:пространстве-/(А)Vх€Х).44ГлаваНапомним,сопряженнымчтолинейныхпространство(К")*определениясразуX*.вфункцииоднойсовокупность\х\=(см.К"=ск,лежатвыпуклое—производной.еед/(х)субдифференциал(х, / (ж)),/(ж)Пример.совпадаетточкучерезXслучаеСубдифференциалзамкнуто.оночтопеременнойкоэффициентовугловыхпроходящиеВсубдифференциалчтодоказать,функцииДляпрост-называетсяX.наК".=вытекает,ЛегкодифференцируемойX*пространствомпространствоИззадачифункционаловнепрерывныхсопряженноемножествоЭкстремальные1.которыхприупрямыефункцииграфикомподэто—кх+Ь,=у/ (х).=рис.6).Рис.6субдифференциалаДлянаафункцийсуммытеоремегачнаяопроизводной[5].ТеоремаМоро—РокафеллараX.точкаСуществуетфункция/2 непрерывнах0,в(/€ПриС(Х(,)).равенствамиотеоремаинепрерывныевыпуклымрконусом+функциивыпуклые—(|/1(а:о)|конечнаЭ/2(Х)V<X.экстремумагладкойвпонадобитсянам[5].вточке/г(х)х,сфункциисублинейной,называетсявершиной=внуле./1Пустьследующаяи/г—выпуклыеТогда/г(^)-сопу@/,(А)=выпуклойпримеромФункция}\условийДубовицкого—МилютинаВажным/гимаксимума.вшах{/1,/2}D)функция.(*)неравенствамисубдифференциалеТеоремафункции,0/1=/1ТогданеобходимыхдоказательствесзадачеПустьфункциякоторой/2)Ианало-теоремаместоимеетфункций.суммыи0Д(А)).являетсяеслиеесублинейнаянадграфикфункявляетсяоо),§ 4.