Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 10
Текст из файла (страница 10)
е. хан 1осш!п1, если ~'~'(х)( О, то 1(х+х)— — 1(х)< 0 при достаточно малых х, т. е. х я 1остах1. (> 2.1.2. Экстремумы функций неекольких переменных и функционалов. Пусть 1 — отображение нормированного пространства Х во множество действительных чисел й, обладающее некоторой гладкостью, т. е. определенными свойствами дифференцируемости. Гладкой задачей без ограничений называется задача об отыскании экстремумов этой функции )(х)-ь.ех1г. (з) Теорема 1 (аналог теоремы Ферма для нормированных пространств), Пусть Х вЂ” нормированное пространство, функционал 1, определенный в окрестности точки х, дифференциру-. ем по Фреше (имеет вариацию по Лагранжу) в точке 2.
Тогда, если хан!осех1г1, то ~'(х)=0 (6~(х, Ь)=0 УйаиХ). <) Если йы1осех1г(, то ЧЬеиХ точка нуль — локальный экеа стремум функции одного переменного: Л-ьчр(Л; Ь)=1(х+ЛЬ). Значит, ~р.'(О; Ь)=0, и, пользуясь определением вариации по Лагранжу, получим, что б)(2, Ь) =О. Если функционал 1 дифФеренцируем по Фреше в точке 2, то в этой точке он имеет ва- риацию по Лагранжу.
Поскольку х~!осех1г/, из уже доказанного следует, что эта вариация равна нулю. Отсюда /'(Я) =О в силу определения дифференцируемости по Фреше (п. 1.3.2).!> Из теоремы 1 следует, что если точка х доставляет локальный экстремум дифференцируемой в точке х функции нескольких переменных: /:Й +К, то все частные производные функции / в этой точке 2 обращаются в нуль, т. е. у /'(х)=бьь /( ) =... = /(х) =О.
дк, дхь Т е о р е м а 2. Пусть Х вЂ” нормированное пространство, (/евб/(х, Х), /:(/-4, /енР(х). Необходимые условия экстремума: если хан ен1осш)п(шах)/, то /ь(й) =О, /п(я)[х, х3>0 (/"(2)[х, х]<0) Ъ'хан Х. Достаточные условия экстремума: если/'(х)= =Ои /'(х)[Х, х])аЦхЦ' (/" (х)[х, х]( — аЦхЦз) УхенХ (1) при некотором а>0, то Ьы1осш)п(шах)/. 0 По формуле Тейлора (п. 1.4.3) /(х+х)=/(х)+/'(х) [х]+(1/2)/" (х) [х, х]+г(х), Цг(х) Ц=о(Цх Ц'). ~ Докажем теорему для случая минимума. Случай максимума аналогичен.
Необходимость. Поскольку хЫосппп/, 'то во-первых, по теореме Ферма (н. 2.1.3) /'(х)=0, во-вторых, /(к+ах)— — /(х)ъО при достаточно малых Х. Поэтому в силу формулы Тейлора /(х+ьх) — /(х) = (Рз/2)/п(2)[х, х]+г(Лх) ~0 при малых Х. Отсюда /" (2) [х, х]ъО Чх~Х. Достаточность.
Так как /'(Я~=О, то по формуле Тейлора в силу условия /" (х) [х, х]~аЦхЦ имеем /(х+ х) — /(х) = — / (х) [х, х]+ с (х) ) — Ц х Цз+ г(х) ) 0 2 2 при достаточно малых х. Следовательно, хен1осш)п/, (> Неотрицательная определенность второй производной для функций и переменных означает неотрицательную определен/ д'/(х) 1 ность матрицы [ ). дх;дх/ ) Условие (1) называется условием строгой положительности (отрицательности) второй производной в смысле Фреше функционала /. 44 Отметим, что в конечномерных пространствах ! д~~ (х) .яожнтельной определенности матрицы дх!дх! л Х д'1("> Ь,Ь,=-О ту =(Ь„..., Ь„) К", дх;дх! с!.=1 т.
е. условие Ь~ьО, гарантирует строгую положительность второго дифференциала (и, значит, является достаточным условием минимума в ста,ционарной точке). В бесконечномерных пространствах зто не так [АТФ, с. 2421. Положительная и отрицательная определенности матрицы устанавливаются с помощью критерия Сильвестра. Теорема (критерий Сильвестра). Матрица А является положительно (отрицательно) определенной тогда и только тогда, когда все ее главные миноры йе(Ах, где Ах=(а!!)'!,г=ь ,Ь=1„...,п, положительны (( — 1)хйе1Ах)0, Ь=1,,п). Доказательство этого, утверждения приведено в [АГТ, .с.
2191. 'с (х, Х) = У Ч1(х) )с-ь выполняется условие стационарности .У„(х, ) ) = О с=ь дУ (х, Х) =О 1 = 1 ... и ьх ~~ Ь;[;(х) =О. ~! Е=О <) Проведем доказательство от противного. Предположим, 'что условие стационарностн не 'выполняется, т. е. векторы 45 2.2. Гладкая конечномерная задача с ограничениями типа равенств 2.2.1. Постановка задачи. Пусть !пй" — «К„(=0, 1,..., !и,— функции и переменных, отображающие пространство К" в Й. 1(онечномерной экстремальной задачей с ограничениями типа равенств называется следующая задача в Й": 1 (х)-~-ех1г; )',(х)=0, 1=1, ..., и.
(з) .Далее считаем, что все функции !" обладают определенной гладкостью. 2.2.2. Правило множителей Лагранжа. Теорема. Пусть х — точка локального экстремума в задаче (з), а функции ,)и 1=0, 1,..., т, непрерывно дифференцируемы в окрестности точки Х (условие гладкости). Тогда существует ненулевой вектор множителей Лагранжа Х=(Хь, Ьь ..., Х ) впав"'+', такой, .что для функции Лагранжа задачи (з) ~~'(х), 1=0, 1,...,т, линейно независимы. Это означает, что / д)~ (х) ранг матрицы Л = ~ )о о равен т+1. Тогда по дх) ) ';= о1' "" о теореме о ранге матрицы существует матрица М порядка (т+ +1) Х(т+1) с определителем, отличным от нуля. Допустим для определенности, что этой матрицей является матрица, со- *о ставленная из первых столбцов матрицы Л: д)о (х) дго (х) дх1 дх„,~~ г)е( = г(е( М ч~ О. д(,„(х) д),х (х ) дх1 дх,щ.„ Не ограничивая общности, считаем, что )о(х) =О, Действительно, если )о(х)ФО, то следует рассмотреть функцию )о(х) = =)о(х) — ~о(х), Положим для вектора х= (х„..., х„+,):Р(х) = =(Ро(х),...., Р (х)) =(~о(х, х„+го ..., 2„), ...
( (х, х .~„ .. ...,х )); Р отображает некоторую окрестность точки х= = (х„ ...,, х +,)а=К"+' в К +' и является (в силу условий гладкости' теоремы) непрерывно дифференцируемым отображением этой окрестности, Р(х) =О. Кроме того, бе1 ' = о(е1 М ча О. дх) /о-ол,.... х /=-1,...,~во о По теореме об обратной функции в конечномерных пространствах (п. 1.44) существует обратное отображение Р— ' некототорой окрестности нуля, такое, что )Р '(у) — х~~К)у~ с некоторой константой К)0. В частности, для достаточно малого по модулю е найдется вектор х(е) =Р-'(е, О,..., 0), такой, что Р(х(е) ) =(е, О, ..., 0), т. е. 1о(х(а)) =е, );(х(е)) =О, (=1,..., т, (1~ где х(е) = (х, (е),..., х„,+1(е), х в..., хо) и при этом )х(а) — х1 ~К~а(ч=' )х(е) — й(~К~а(.
(2г 1 Из соотношений (1), (2) следует, что вектор х не доставляет задаче экстремума, ибо вблизи его существуют допустимые. векторы х(а), на которых функционал (о принимает значения как большие, так и меньшие )о(х) (напомним, что )о(х) =0). Получили противоречие с тем, что йФ!осех1гз. Таким образом, наше предположение (противного) неверно н тем самым теорема доказана. ~> 3 а меч ание 1.
Из соотношения (1) следует, что если векторы г1'(х),...,1»'(х) линейно независимы, то АоФО. 46 Замечание 2. В правиле множителей Лагранжа для задач с ограничениями типа равенств можно, вообще говоря, не обращать внимание на тип экстремума и, убедившись, что 1«о~О, полагать 1«о любой отличной от нуля константой. Для задач, где присутствуют неравенства н включения, знак Ло существен. Сформулируем в этом же пункте необходимые условия экстремума в задачах с равенствами и неравенствами. Пусть 1;:й «-14, 1=0, 1,..., т, — функции и переменных.
Конечномерной экстремальной задачей с ограничениями типа равенств и неравенств называется следующая задача в Й'. ~о(х) ч)п1' «««(х) <О 1 1; .. т «»'(х) — 0 (=т + 1 ... т, (з) Теорем а. Пусть 2 —, точка локального минимума в задаче (з), а функции Ть 1=0, 1,..., т, непрерь«вно дифференцируемы в некоторой окрестности точки х (условие гладкости). Тогда существует ненулевой вектор множителей Лагранжа )о= =()оо, 1««,..., 1«)енй"'.+«, такой, что для функции Лагранжа задачи (з) Я(х, А) = т 1««1«(х) 1-о выполняются условия: а) стационарности У„(х, )о) = О о» э')«;1;(х) = 0 о» ("' = О, 1 = 1, ..., и; дх1 б) дополняющей нежесткости )ч)«Щ=О, 1=1,, т' в) неотрицательности Х)0, 1=0, 1,..., т'.
Доказательство этой теоремы будет приведено в и. 2.4 в бо.лее общем случае. 2.3. Задачи выпуклого программирования 2.3.1. Задачи без ограничений; Выпуклой задачей без огра.ничений называется следующая задача: Т(х)- (п1. (з) Здесь )':Х-~-й — выпуклая функция, отображающая некоторое линейное пространство Х в расширенную прямую Т ео р е м л (аналог теоремы Ферма). Для того чтобы точка х доставляла в задаче (з) абсолютный минимум, необходимо и 4 достаточно, чгобьо выполнялось соотношение О~д)(2). <1 хенаЬзш!пзь»7(х) †!(х) >0=(0, х — х)о:»Оенд!(х) ~> 2.3.2.
Постановка задачн выпуклого программирования. Задачей выпуклого программирования (нли выпуклой задачей» называется следующая экстремальная задача: 1о(х)-»(п1; 1;(х) <О, 1= 1,...,т, хенА. (з) Здесь )иХ-~.Й, 1=О, 1,...,т, — выпуклые функции (функционалы), отображающие некоторое линейное (не обязательно нормированное) пространство Х в расширенную прямую, А— выпуклое подмножество в Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
