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

.=некотором2 ^т:/,2т^(тах)//{2т)(х)0,=/'(А)либото/х.точкеточка—==..точка—Доказательство.(/Bт)(ж)0>0)<A)п.экстремума:условия1остшПустьвыполняетсяеслилокального(максимума)то/.функции1осгшп/.€хопределенностидляA),условиеминимумафор-ПоТейлораформулеНеобходимость1.п>/(')(*)!(х)-==хдостаточномалых/четно—53 —Г1*ТогдапоФерма.Пусть}'(х)либо0,далее==..}(х)-Так—ур~^=/®(х)какФ 0,+п(к)то0^отсюдаприследует,0.>/'(х)Пустьформулек)к.модулю}A)(х)/(п)(ж)==}(х+тоДостаточность.теоремы+г(Н)А"пои=приЛ->о).Значит,1остт/,еизследует../0,!^п.к=1Поскольку1=/'(х)/(;)B)0,=А)пприлибоТогда(^?-0о(А")=чтоэкстремумомдифференцируемаразесли(максимума)Достаточные€Б"€ответлокальнымхлибо0,=точкаэкстремума:минимума}'(х)А/исчерпывающийпочтидатьданнаяфункцияусловиялокального/(п)(х)можнолиПустьпротивоположныйимеютнеравенстваявляетсяНеобходимыезадачисоответственно.случаеТеоремапримаксимума< 0}"(х)иЭкстремальные1.ГлаваТейлора=/<2т-!)(ж)=..=0,/2тB)/0.приЛ-,0.Посколькут.е.х€кклшп/./Bт)(ж)>0,то/(х+к)~/(х)^0придостаточномалыхк,■§1.2.2.Сформулируемконечномерной1.КонечномерныеФункциинесколькихзадаченеобходимоеограничений,без1.ТеоремахусловиедифференцируемаI порядкаэкстремумаявляющееся,хп)(XI,.

.=пв11ограниченийпеременныхЕслифункцииэкстремумабеззадачих,Ферма.точка—}{х\,. .конеч-втеоремы1осех1г/€переменныхточкеаналогом,хп)локального/функцияи€то. .0.ОХ\РассмотримДоказательство./(хь.. ,хг_ихг,Х1+и.. ,хп).то€щ1осех1гу.экстремумаКромеоднойСформулируемпорядканапомним,являетсяатакжедостаточныебезприведемназываетсяIэкстремумаусловиеПредварительноограничений.переменныхнесколькихпроизводныхзнакоопределенностейопределенияАусловиюФерматеоремефункциивторых=1осех1г/,€необходимолгу—производнойматрицаМатрицаматриц.изадачесимметричнаяПопеременнойнеобходимыеконечномернойчтовторойв(хь.. ,хп)=^?(ж,).€<рх<р(хг)переменнойоднойфункциюПосколькутогофункцийдляОХпсимметричных(Аопределеннойнеотрицательно0),^еслипV^ОАМатрицаназываетсяАМатрицаа>УЛЕК",называется0определяютсяОтметим,нетак[АТФ,€0),если>определенной,К".еслиУ/геК".ис.242]).матрицыА.АВэквивалентнобесконечномерныхматрицы.отрицательнаяусловиепространствематрицы(см.>а\\Н\ 2конечномерномсимметричнойопределенностистрогойположительностиэтов,кп)й/0.неположительнаячто(Аположительнострого(Нь..чтотакое,{АН,Н)Аналогично=определеннойположительно(Ак,Н)>0существуетНположительнойусловиюпространствахстро-12Глава2.ТеоремаПустьЭкстремальные1.функция/задачи(х)Т>€Х=(хи..

,Хп).Необходимыеэкстремума:условиялокальногоДостаточные/'D)/.функцииЛ)(тах)1осгшп€./Л)+Докажем/D)=теоремубезограничений}(хАЛ)+Л)|(/"D)А,+/(х)>0V/точка—Vл€К",ек".ЛЛ/0,(максимума)г(А),+СлучайА€1остт/,Iпорядкафунк-аналогичен.пово-первых,не-конечномерной/'(х)ФермаА.о(\Н\2).=максимумавмалыхдостаточног(А)то,теоремыприо)0)<Л)минимума.аналогу—-<минимумаэкстремумаусловиюл)(тах)ТейлораПосколькунеобходимомуЛ)локальногослучаядляНеобходимость.(</"D)А,формуле(/'D),+1осгшпточкееслиточкаПо€вто(</"D)а,о>0>—Доказательство./D/,экстремума:</"D)А,0,=хтол)условия^функции</"D)а,о,=дифференцируемаеогм(максимума)минимума}'{х)дваждызадаче0,=Поэтомувво-вторых,формулысилуТейлора/D+АА)Амальгхпри/D)-неравенстваполучим,+г(АА)к.фиксированномиАнау(/"D)А,А)-,АустремимиТаквыполненногопоследнегог(АА)0,►—-^то+А)-}'(х)как/D)==0,таквсилуимеем:+г(А)какТейлораформулепоток) > а\к\^(/"D)А,А)к,малыхдостаточноУЛеК".(/"(х)Н,условия/D€частиПосколькунулю.ко(|А|2))=чтоДостаточность.хобеРазделим(/"D)А,А)>0при(г(АА)0^г>(к)^|Л|2).о(\к\=+Г(А)> 0Следовательно,1осгшп/.■пЗамечание.=минимума}"(х)=(отрицательной)(ац)"(максимума)-=1являетсяфункционала(}(х)функционаловквадратичныхположительнойусловиеАДля=определенностидостаточнымстационарнойа^Х{Х^матрицыабсолютногоусловиемв]Г)точке.ми-§1.2.3.1.КонечномерныеКритерийматрицыНапомним,ктогда,■А-1..

Нвсе0,>2.кеекогданачинаяс3.4.^1.главныет.небудетк)1.2.4.Дляуравнений[10,следуетточкичисленным0)^тогдатолько^^п,к=толькоис1,. .положительностьнеположи-,п.(неотрица-последователь-положительности==(метод—аположительностиусловию260]).с.А=чтобытого,и-4;, . г*начинаяг*ДлянеотрицательностиусловияглавныхпоследовательныхглавныхнеотрицательностьНьютонаМетод^..всехА&(^1(Нь Н2))(@, -Л2),тогда(неотрицательности)условиеу матрицыстационарные^г\неотрицательностьнулю{Азнак,неотрицательностиследуетравны0)^знак,п.т.е.равносильно(см.не=е.толькои1,.

.,=(Аниже,чтоусловияизе.тогдаматрицы.-минорыт.чередуютположительностиматрицыДействительно,{АН,1 ^показаноОтметим,следовательно,гттолькоип.минорыминоровтак,0,0)неотрицательны,равносильнаминоровглавныхне<минорык>определеначередуют^0,Как2.минорови,неположительно,значенийглавныхвсех1,. .=еематрицыЗамечаниеэтокп,(Аопределенаминоры(—1)*-4;,. .4т.е.(— 1)*<1е1.41.. це.главныеАсобственныхпоследовательныхтогдаположительны,главныенеотрицательно^г*ЗамечаниевсехномерамиТогда0)>минорыпоследовательныееевсе(неотрицательность)сматрица.(АопределенаотрицательноАкогданеположительного,главныет.Матрицатогда,последовательныема-определительстолбцовисимметричная—определенаеевсе..АI.называетсястрокположительноотрицательного,когдаг-1 ^ПустьАвсеМатрицатогда,АизАматрицы«1*\•••1,.

.,п.=Матрицатогда,260.]Акогда1 ^с.Матрица1.составленнойкритерияминорами(«11матрицык,х[10,Теорема.главными-4^.. ^миноромразмерапомощьюсустанавливаетсяпоследовательнымичтоГлавным13ограниченийСильвестраЗнакоопределенностьСильвестра.матрицыбеззадачиматрицы.оА/оI=0),матрицыминоров.но~Н22<0онанеотрицательной:являетсянефк2приглавныепоследовательные.0.касательных)решитьзадачурешенияспособомуравненияможнобезограничений/'(ж)воспользоваться=0.Длянужнонайтирешениятакихзамечательным0,14Глававосходящимприемом,Экстремальные1.задачиИтак,Ньютону.кпустьтребуетсянамрешитьуравнениеР(х)РЗдесьБудемискатьрешениеЕслиприближений.значениехкA)уравненияоднойпере-последовательныхметодомприближенное—значениекорня,точноетокорня±гдефункциядифференцируемаянепрерывнодважды—переменной.A)0.=ккмало,и0Пренебрегая=Р(Л)Р{хк=поправкувкк)+=о(Л*),слагаемымB),формулуРфункциидифференцируемостисилувB)кк,+хк=Р{хк)находим,получим+Р\хк)ккчтоккновоео{кк).+—Р(хк)-~.—г-РВнеся(хк)этуприближенноеуточненноекорня:значениеТакимобразом,мыимеемследующееГеометрическиу(см.рис.=методР(х)1).касательной,соотношениерекуррентноехк=кривойНк.приближенийпоследовательныхнахождения+=ХкХк+1кнулюC)-Р'(хкУНьютонаэквивалентенпроведеннойРис.дляA):уравнения1дугизаменевнекоторойточкекри-кривой§ 1.

КонечномерныеПустьопределенностидлянаходящийсянаПроведемкачествепервогоэтойпересечениякривойприближениякпроводимкасательнойуабсциссах^хкорняточкииточкикоторойпересечениякасательнойуравнениечто(хо,Р(хо)).=точкуЬ.—пере-(ж1,^(а;1))сновавтороедает1).(рис.т.д.х0абсциссаберетсяЧерезA),уравненияПоложим(Ь,Р(Ь))точкевОх.осьюкорень0.>Е(х)=Х\скасательную,приближениеОчевидно,найтиР(Ь)Р"(Ь)и15ограниченийнадонамЬ][а,отрезкекасательнуюВбеззадачиточке(хк,Р(хк))имеемформулувестьР'(хк)(х-хк).ПолагаяэтомвОуравненииР{хк)=Заметим,0,(а,Р(а)},выборэтомПустьприближения[а,€х0вычислитьсзнакиР'{х)Р"(х)ЕслиР'(%к)Такой=методзаменяем[а, Ь],т.е.быоказалсяначальнымправильным0.>0),Ь].[а,Р(а)функциизначения<€хРфункцияТогда,изприближе-начальногокореньпри-отрезкенаР(хо)Р"(х0)единственныйР(Ь)имонотоннаисходянеравенствумало0,>можноР{х)уравнениякометоде0,1,2,.

.=(хк,Р(хк)}точкахвычиположитьчтоозначает,прямымиНьютонаможноП.первойпараллельнымиДемидовичпрочитатьвиИ.Азаме-мы(жо,^(а;о)).точкеБ.илимодифицированнымспособэтотЬ]можно:называетсяуравнениявматематики»=C)формулев[а,отрезкенатокорняГеометрическивменяетсятрудоемко,значенийнахожденияпостроеннойПодробнеевычислительнойвсехдлякасательныекасательной,точкевотрезкаНьютонаметодеслучаеЬ],К),Р'{х)слишкомНьютона.методомР(х)=точности.производнаяР'{хк)Р'(%о)С2({а,(Р(а)Р(Ь)Ньютонаметодустепеньювычислениеследовательно,и,увнеР(хо)Р"(хо)€ф 0 VудовлетворяющегоЬ],полюбойа—кривойлежащуюданномв(Хк)хк-=х0вусловиеРразныеЬ],Х\,C)следующаяТеорема.принимаютхк+1кзначенияявляетсяместо<=>положитьточкуобразом,хИмеетхк)касательнуюпроведяначальногоприближениемхк+\,=случаебыТакимнеудачным.[а,то,х-нашемвполучилимыприесли<0,=Р'(хк)(хк+1+чтоР(хо)Р"(хо)уМарон«Основыкниге[11].016Глава1.3.ПравилоДлязадачирешенияконечномернойрешенияВыписать1)Экстремальные1.беззадачинеобходимоеограниченийНайти(этиточких,условийвыполнениеа)еевыполнениезнакоопределенность,ЕслиониееЕслиминимумвыполняютсядостаточныезнакоопределенность,определителиматрицкразмераЕслик,4,-,.

.,^е.не1,. .,0,1 ^выполняетсят.точкажвсекогданедоставляете.А—столбцови■(Аопределенной^г*к1,. .,—точкатоп,(—1)минорыглавныеА^.. ^локальныйх/.(А ^ 0),определеннойее0),%неотрица-минорып,% 1осггшгнеположительнонеположительного,то■главныеее^..хявляетсянеусловие,п,^г\строкиз■всеминимум,Аматрицас=^локальныйдоставляете.когданадослабую•••неотрицательноусловие,томатрицысоставленныхIV «,у,йе1:—являетсяневыполняетсят.начинаякАматрицаЕслит.А{1.. ^г»:г1}.. ,точкаееминоры/«М,номерамито,п,исследовать—главныех1,.

.экстремума,условийпосчитатьт.е.знак,чередуютк~0,условиянеобходимыхвыполнението1остш/.6миноры>1,. .,п,=1остах/.6хмаксимум,незадаче,АО,х(—1)*<1е1.4.1. .*т.е.локальныйЕслипроверитьиссле-—главные>главныеотрицательного,доставляетвпоследовательныеееА^,.*т.е.локальныйвсесэкстремумапоследовательныепосчитатье.положительны,доставляетначинаянеотрицательны,каждойвА:всехусловийдостаточныхт.матрицыминорынепорядкапроизводныхвторыхматрицуПроверитьисследоватьт.е.Iэкстремуматочке.ВыписатьЬ)I порядкаусловиюстационарными).2) Проверитьточканеобходимомуудовлетворяющиеназываютсяточкистационарнойнеаналог—Ферма:теоремысследует:I порядкаэкстремумаусловие1^*1^..^0,максимум,знак,чередуют^жг*0 1остах/.^п,§ 1.

Конечномерные1.4.}{х)1.Необходимоех2)}(х\,=Решаясистему,Матрица€€1осппп/.аЪяшп/,а(&НхУ\I/(х)2.Необходимое(хьх2)Iсистемух2)/(жьпорядкаПодостаточномууслоточкатоквадратичным,х\+х\-2х\Х2-\ 4х32х\-2а?1-@,0).=-2х2Поопределена.2-2ствиюИт|ж|—»оо=Вейерштрассатеоремыиз}{х)/(-1,-1)-2.=(-2МатрицаIниотрицательно-2\_.Iх\их\+онаA,1),Следовательно,минимума.-2)-2)поположительноопре-функцииэкстремумалокальногоA,1)/.Шп|х|—>ооПосколькуСильвестракритериюточкифункцииминимумпоусловиюпеременных(-2\-21,0)„I.„=производных:вторыхдостаточномунесколькихположительно,-2\ж1условийпроверки=100.=точкиДля(-1,-1)__еххг.-+стационарныеж3(-1,-1),A,1)(Iкри-переменныхнаходим-.,поI порядка:матрицуМатрицаA,0).=I)являетсях\=уравнений,выписываемж.,\~1дх2=(I=0.=-1\2несколькихэкстремумах1A,1),-1++оо.условиеэтуех1г.—+2х2+-XIопределена.==Х2точкуIфункциифункционалдхгРешая*—\дх{дх^/^=1Поскольку5тах+стационарнуюединственнуюэкстремумаПример\положительнолокального2х\—I порядка:производныхСильвестратериюх2дх2находимвторых+Х\Х2—экстремумаусловиеэтух\=дххA,0)A,0)17ограниченийПримерыПримерусловиюбеззадачи(-1,-1)—локальныйдоставляют(х,ух2)+—€критериюСильвестраопределенной.Она5пш,аЪшип,неявляетсятопослед-абсолютногосвоегодостигает(-1,-1)+сх>,являетсянеположительно=/A,1)ни=поло-18определеннойматрицейусловиелокальногоПосколькуОчевидно,(Аматрицейопределенной0).[А^Экстремальные^0)2Л45тах=что3.Примержз>—-+оо.Найтинеотрицательно/(ж3)=ж3кх\+~Частные2хх-д/производныедРдРдхт,дРдРдхгдх2дхт,дх3(х)и+д/дхт.=ОХ2-4)-^B*3-О,ОХ2I порядка:(*)_найденнуюг2хгР(х1,Х2,х3)A,-1,-2)иДляж2находим2-О,=производныхправой—-1-=-—=ОХ2ах\0,ХхИХ2,посХ2иучетом1д2х.0:второех2первоех\д2х392а;з=х2уравнениеправойчастиПОЛУЧИМ'д2вторыхимеем=дифференцируяАналогично,ПО4)=матрицу(*)4'-(^ьж2,ж3)=Дифференцируяточке.уравнений92а;зBх3х1выписатьнадопорядкасистемычастиуравнениезаданноевточкистационарнойдхт,дхт,условияIкаждойв-1.=A,-1,6)=условийA,-1)=стационарныедве(*ьж2,ж3)=проверкиуравнение(жьжг)точку0,(*)дхт,+B*3-4)—-=0.2находим-—ОХ22 +0.=ж,=пере-двух-10-—дх\2а?!-экстремума_4ж3-дхт,=дх\дх2условиеПодставляя1остах/.^функции2х2+уравнений:0*з(*)0,фж3тозаданнойнеявноПосколь-01осгшп/.еслих3)Необходимое@,0)=малыхприопреде-необходимоевыполняетсянеэкстремумыР(хг,х2,Решение.являетсянеПоэтому0/(Х[,Х2),=изадачиСледовательно,минимума.-к)/(Л,переменныхиз1.Главад2х20.системы(*)§Очевидно,АчтоКонечномерные1.д2хг-—-—дгхъ=поМожнопоказать,ноиположительноявляется^ост|ппорядкабудутэтоО-1/4ОПоэтомуопределенной.отрицательновторогочто=локальныетольконеГостах2,—несколькобезэкстремумы,примеровсвойствразличныхэкстремумовза-вограничений.ПримербесконечномАбсолютные4.числеПример5.минимумиминимумыдостигаютсямаксимумыбеско-вточек:/(ж)К-+К,/:Функцияограничена,Функцияограничена,&тх.=абсолютныйдостигается,максимумнет:—6.Примерабсолютныеноимаксимумминимумдостигаются:не/:ПримерФункция7.иПример8.ноабсолютныеминимумы,вместетемкоординатначалоК2/:Действительно,/(ах2,Х2)Зх2,)(ах2^0=-/@)х1)(ах2прихх2)прямой-малыхв(ал—хг-х\{ах{минимума:Значит,3x1).-аах2,=~пря-минимум,локальногох22)(Х1-любуюналокальныйнулеточкойвида3x1)х.плоскости,наявляется=яп■имеет/(агьлюбойна=агс1§заданнойнеК,->—мини-идостигаются:не}(х)функции,координат,началомаксимумылокальныеминимумК,-+абсо-ноточки,стационарныеимеетиОграничениечерезс+Кх.достигаются:ограничена,максимумагс18=имеетминимумФункция9./(х)К,->не/:ПримерпроходящуюКограничена,максимумабсолютныепрямую,6.=глобальные.ПриведемзадачеСильвестраА\^2условию^-1/4_'1/4/4 укритериюматрицаадостаточномупо4ах2образом,ОА\ц19ограниченийА/4_МатрицафункцияТаким-—-—.=определенной,нобеззадачихт){а~на^Х2)любой€К,=функ-Х2(а2~прямой20ГлававидаХуАналогичноах2функциипрямойх2=наСдругойстороны,влюбойокрестностилокального/ имеетфункцияпараболенах110.2х\=естьфункцииминимумжх2)/Bх2,0==0<х2—точкойявляетсяненуле.вминимумфункцияточкаАнало-нуле.вимеетх1=/.Имеетсяединственныйлокальныйэкстремум,яв-неабсолютным:являющийсяК2/:Необходимоебез/B^,0)Тонуля.задачилокальный0=минимумаПримерЭкстремальные1.}(хих2)К,-+условиех\=х\-I порядкаэкстремума2е~хК+конечномернойвзадачеограничений:^М0^=^М=!2х1-4х1е-х2^0;0^=дх2дхг\-2х20,="^1=0,х2Получаемж3задачев=Для=0.стационарныетри(-\/Е2,0).IусловийпроверкипроизводныхпорядкагМатрицаСильвестракритериюА24 >=0точкастационарнаяXIпри\лив_„00точке-2ХуА\второго8аЬсаакчто^0)иположительно,ниявляетсяниненеотрицательновыполняется0\0__„ниотрицательноIкри-2—0,<стацио-(/(ж^О)+сх)-+„поСиль-критериюопределеннойопределеннойматрицейнеположительноопределеннойнеобходимоепо=порядка+оо=/41п2I@,0)=определенной:условиюОчевидно,нинетогоСледовательно,.отрицательнопроизводныхявляетсяне(.40-2VI1остах.вторыхболеематрицейевторых/41п2Лдостаточномупо8х\е~^++СХ)).-+Матрицавестра,-2являетсяПоэтомуж10.матрицу0производныхвторых4е~х*-1-20(\/1п2,0),=точке:2.ж2@,0),=выписатьнадостационарнойкаждойвж1точкиусловиематри-(.4нилокального^0).1.§нимаксимума,5а)Э5тах+оо—+Х\прилокальныйединственныйэкстремумфункцииухточкевПример11.малойМожноэтойминимум,точкислеватонуля/(ж)Контрпример:Ясно,ичтожсправа,слевафункция/убывает,Имеется12.асправаНеобходимоед/(х)_—_К2а;B=+_^\'/(Х1,Х2)сок-х~,значения,—У"=-2х,номаксимумов,Г*!°;=_(о, |=&тх2-хг.0;=Лусловийкж),+к&Ъ.стационарнойматрицувыписатьнадопорядка-апаг2"(А@,1+2шг)„)_.Ахпорядка=-2вторыхточке:0IФ О,т.е.I порядка:Iкаждойввторогоокрестности^)ктлокальныхчислоК,-+хкпроверкиопределенной:любойотрицательныеиэкстремуматочкиМатрица0.вубывает.Гд/(х)—производных}'{х)бесконечноеусловие—СтационарныеДлястороны,=минимума:/:—_другойтакилокальногох)'5[п+хпроизводнаявозрастает,иПримеродногоСположительные,какB{^=аЪ&тт/.О €—ипринимаетотрицательнопеременной?Нет.условиюимеетсядостаточнофункцияточкиотоднойнекоторойв—являющийсянефункцияесличтолокальныйточкеокрестностивозрастаетниутверждать,лилибокакойв/@,0),=абсолютным.имеет/(х1,0)функцияЗначит,+оо.—+ж2,точкистационарныеДействительно,+оо.=21ограниченийПоэтомуминимума.что2е~~Х1+беззадачилокальногож3 01осех1г/.Очевидно,хгКонечномерныеСильвестракритериюпо<@, |Аг0,+2птг)=2>€1остах0.~20отрицатель-являетсяПоэтому/Vдостаточномупоп€2.нет22ГлаваIМатрица@.