Алексеев В.М., Тихомиров В.М., Фомин С.В. - Оптимальное управление, страница 9

Здесь мы напомним лишь основное определекне (в бесконечномерном случае принадлежащее ' Фреше). Функция(: й"- 1«п переменных называется дифференцируемой в точке х, если найдутся числа (а„..., сь„) (кратко обозначим их через сс) такие, что » ) (х+Ь) =1(х)+ ~~~,'а,Ь, +г(Ь), ~=1 где-~г(Ь)~=о(~Ь~),т. е. для любого в» 0 найдется 6> 0 )Й)-л7х.—..~ц(6 ~у, (,ь~(« (в (Ь (.

Набор а=(а„..., сь,) называется производной 1 в точке х и обозначается также 1' (х). Подчеркнем, что 1'(х) — это набор из п чисел. При этом число сьь = = 1пп [1" (х+Ле;) — 1(х)~!Л, где е;=(О, ..., 1, ..., О) (вднх о ница стоит на 1-м месте), называется 1-й частной произдт водной 1 и обозначается 1„(х) или — (х). Таким абра. С дх; зом, )' (х) =(),(х), ..., )«„(х)). Соотношение 1 (х) =0 означает, что 1"„(х) =... =1,„(х) =О. Из «одномерйой» теоремы Ферма вытекает очевидное следствие: Следствие (теорема Ферма для функций и переменных).

Пусть [ — функция и переменных, дифференцируемая в точке х. Если х — точка локального минимума функции ), то 1 (х)=Овэ)»,(х)=0, 1=1, ..., и. (2) Точки хай", в которых имеют место равенства (2), также называются стационарными. Д о к а з а т е л ь с т в о с л е д с т в и я. Если х доставляет экстремум функции 1, то точка нуль должна быть экстремумом функции Ч~; (Л) =1(х+Ле,). По теореме Ферма «м чч (0) = О.

Но 'р1 (0) = 1,, (х). 43 46 1.3.2. Правило множителей Лагранжа. Этот пункт посвящен гладким конечномерным задачам. Еще раз напомним о причудливости исторического развития нашей темы. Вслед за методом решения одномерных экстремальных задач наступила эра классического вариационного исчисления. Для задач вариационного исчисления с ограничениями, т.

е. в бесконечиомерной ситуации, Лагранж сформулировал в «Аналитической механике» (1788 г.)') свое знаменитое правило множителей, и только спустя примерно десятилетие в «Теории аналитических функций» в 1797 г. он применил его к конечномерным задачам. Конечномерной гладкой экстремальной задачей с ограничениями тица равенств (или задачей об условном экстремуме) называется задача 7»(х)- ех1г, 1,(х)=.;. =1„(х)=0. (1) Функции 7а: П" — й, й=О, 1, ..., т, должны здесь обладать некоторыми свойствами гладкости (т.

е. дифференцируемости). В этом пункте будем предполагать, что в некоторой окрестности У пространства К" все функции 7а непРеРывно диффеРенциРУемы (в том смысле, что все частные производные д)а!дхе существуют и непрерывны в У), Точка хЕУ, )а(х)=0, я=1, 2, ..., т, доставляет локальный минимум (максимум) в задаче (1) в том случае, когда найдется такое н ) О, что если точка хЕ У удовлетворяет всем ограничениям (7';(х) =О, 1=1, ..., т) и 1х — х~<а, то 7«(х)»7е(х) (соответственцо 7«(х).:: <У (х)).

Функцию .У =.Р(х, д, Х,) = ~~.", Х„7» (х), (2) где Х=(Х~, ..., Х ), называют функцией Лагранжа задачи (1), числа Х„Х„, ..., Մ— множипмлями Лагранжа. Правило множителей Лагранжа. 1. Пуснзь в задаче (1) все функции 7"„7м ..., 7„непрерывно дифференцируемы в окрестности точки х. Если х — точка локального экстремума в задаче (1), то найдутся мно- т) Л а г р а нж )К. Аналитическая механика.— М.— Лл Гоетехнадат, 4950. 42 жители Лагранжа Х =(Ъ„..., Х ) и л„не разные адно- временно нулю и такие, чта выналюиотся условия стационарнасти Функции Лагранжа на х Я„(х, 1„Х,)=О вам' .(х, 1„..., Х, Х,)=О, (3) 1=1,2, ...,н.

2. Для того чтобы ).,-ь О, достаточно, чтобы векторы Д(х), ..., 1' (х) были линейно независимы. Таким образом, для определения х, Х и Х, волучается н+т уравнений: с н+т+1 неизвестными. Следует учесть, что множители Лагранжа определены при этом с точностью до проиорциональности. Если известно, что ),,~0 (а это — важнейший случай, ибо если ),,=О, то соотношения (3) от-.

ражают лишь вырожденность ограничений и не связаны с функционалом), то можно, умножив все гч на константу, добиться равенства ь,=1. Тогда число уравнений сравняется с числом неизвестных. В более симметричной форме уравнения (4) записы. ваются так: .2'„=О, .2' =О. (4') Их решения называются стационарными тачками задачи (1). Со времен Лагранжа (слова Лагранжа приводятся чуть ниже) почти на протяжении целого века правило множителей формулировалось с А,=1, хотя без дополнительных предполажений, например линейнбй независимости, в таком виде оно неверно.

Для подтверждения сказанного рассмотрим задачу х, — 1п1, х,'+4= О. Очевидным и единственным ее решением является х=(0, О), ибо это — единственная допустимая точка. Попробуем теперь составить функцию Лагранжа с Х,=1 и применить далее алгоритм(3). Имеем.У=х,+Х(х+Ц), 48 откуда дЯ вЂ” -О=гь2Лх,+1=9,, -О~2),-О д,к дх1 охг и первое из этих уравнений несовместно с уравнением х,'+ хгг = О. В качестве условия регулярности, гарантирующего, что Х,~О, обычно используют линейную независимость производных Д(х), ..., г' (х) (см.

выше утверждение 2 теоремы). Однако проверка этого условия обычно сложнее, чем проверка непосредственно нз уравнений (3) того, что $ь не может равняться нулю (см. решения задач в 3 1.6). Поэтому приведенная выше формулировка теоремы, не содержащая никаких дополнительных предположений, кроме гладкости, очень удобна. Доказательство теоремы опирается на одну из важнейших теорем конечномерного дифференциального исчисления — теорему об обратной функции [14, т.

1, с. 4551, 19, т. 1, с. 2591. Теорема об обратной функции.' Пусть ф,(х„..., х,), ..., ф,(х„..., х,) — в функций в пгргмг нных непрерывно диффв ргнц иругмых в некоторой окрестностии точки х. Пусть при этом якобиан у=де((~ ~"') отличен от нуля. Тогда существуют такие г, > О и 5, ) О, что для любого т)=(ч1„..., ц,), ~ Ч~(з, найдется $, ~$~(б„такое, что ф(х+$)=~>(х)+тьиприэтомс О, когда т1- О. Более общие варианты этой теоремы будут доказаны в 3 2.3. Доказательство правила множителей Лагр а н ж а.

Пусть точка х доставляет локальный минимум в задаче (1). Возможно одно из двух: или векторы Д(х), ..., Г' (х) линейнгв зависимы, или эти векторы линейно независимы. А) Пусть векторы линейно зависимы. Тогда ненулевые Хю я=О, 1, ..., т, для которых имеют место условия (3), можно подобрать по определению.

Б) Пусть векторы линейно независимы. Приведем это к противоречию с тем, что х †локальн минимум в задаче (1). Рассмотрим отображение Ф (х) = (1, (х) — 1, (х), 1„(х),... ..., 1„(х)). По условию векторыД(х), ..., )„'(х) линейно незавйсимы, т. е. ранг матрицы д(р (х) дЛ, (х) дх, ' ' ' '' дх„ А= д( (х) д(,х(х) дх, ' ''" дхх равен я+1.

Допустим для определенности, что первые и+1 столбцов матрицы А линейно независимы, т. е. дно (х) д(о (х) дх, ' ' '' дх,х+1 бе( ° - ° ° ° .. Ф О. д(,х (х) д),„(х) дх, ' '''' дх„,+д Следовательно, функции ф,(х„..., х„„)= = 1х (хо . ° °, Хх+о х,„+„..., х„) —.~, (х„..

„х„), фх(хо ' '~ ха+1) =11(х1 ' ' ха+а хюх+й~ ' ' хх)~ ° з фхтр~-1(хо ' ' ~ Ха+1) ~х(Хо ' ' '~ Хщ~х Х~х+м ' ' '~ Хх) удовлетворяют условиям теоремы об обратной функции. По этой теореме для любого е, О<в<а„найдутся х,(з), ...„х„,,(е), такие, что ~,(х,(е), ..., х„э,(з), х„+„..., х„) — 1,(х)= — е, ~,(х, (з), ..., х„„(з), х„„,..., х„) = О, (5) )„(х,(е),,, х„+~(е), х„+„..., х„) =О, причем х, (з) — х, при е — О, ( = 1, 2, ..., гп+ 1. Но из (5) прямо следует, что точка х не является точкой локального минимума. Искомое противоречие получено.

Утверждение 2 теоремы очевидно.(йй1 Обобщение правила множителей Лагранжа на беско- нечномерные задачи с равенствами и неравенствами будет дано в гл. 111. А теперь †е несколько слов об истории. Первое упоминание о правиле множителей содержится в работах Эйлера по изопериметрическим задачам (1744 г.). Затем оно было выдвинуто Лагранжем в его «Аналитической механике» (1788 г,) для широкого класса задач вариационного исчисления (так называемых задач Лагранжа, очем будет егце сказано), В 1797 г. в книге «Теория аналитических функций» Лагранж затрагивает вопрос и о конечномерных задачах').

Он пишет; «Оп реп1!ев гедшге а се рНпс(ре яепега1е. 1.огз г(и'ппе 1опсПоп де р!цв1епгв чаг1аЫез до!1 е1ге нп шахппшп ои а1п(шшп, е1 г!и'П у а еп1ге сев чаг(аЫез цпе оп р!пв(еигв ейпа11опз, П ви1!!га б'а)оц(ег,а !а !опсПоп ргоровее !ев !опс1юпз ош бо!чеп1 е(ге пиПев, пш!- 11р!1еев сЬасппе раг ипе г!пап111е 1пде(егш(пес, е1 1а с)гегс(гег епзш1е 1е шах!пппп ои т!пппшп сопппе з1 1ев чаНаЫев е(а(еп1 !пберепг(ап1ев; 1ев ег(па1!опв г(и'оп 1гоичеез, вегч!гоп1 а Йе1егпйпег 1оп(ез 1ез !псопппев». «Можно высказать следующий общий принцип. Если ищется максимум или минимум некоторой функции многих переменных при условии, что между этими переменными имеется связь, задаваемая одним или несколькими уравнениями, нужно прибавить к мкнимизируемой функции функции, задающие уравнения связи, умноженные на неопределенные множители, и искать затем максимум или минимум построенной суммы, как если бы переменные были независимы.

Полученные уравнения, присоединенные к уравнениям связи, послужат для определения всех неизвестных». Не будет преувеличением сказать, что основная часть этой книги посвящена раскрытию замысла Лагранжа в применении к задачам разной природы. Изложим здесь еще раз основную мысль Лагранжа. Пусть требуется найти экстремум в задаче (1). Тогда следует составить функцию Лагранжа (2) и рассмотреть задачу .У (х, Х, ь«)— ех(г без ограничений.

Необходимое условие в этой задаче без ограничений в соответствии с теоремой ферма для функций и переменных дает нужные уравнения .У„=О. Итак, в соответствии с принципом Лагранжа уравнения для экстремума в задаче с ограничениями совпадают с уравнениями для задачи .Р (х, Х, "ь«) — ех1г без ограничений при надлежащем выборе множителей Лагранжа Х, "ь«. *) !.«кгапке Ю, !., та«ог!е де»!оп«поп» ааа!умчи«в, Р«г!«,' !8!3.

б! Мы увидим далее, что для очень большого числа задач общий замысел Лагранжа оказывается правильным, 1.3.3. Теорема Кума — Танкера, В этом пункте мы рассмотрим задачи выпуклого программирования, для которых идея Лагранжа приобретает наиболее завершенную форму, Этот класс задач стали изучать сравнительно недавно. Основы теории линейного (а это частный случай выпуклого) программирования были заложены в работе Л. В. Канторовича в 1939 г. Теорема Куна — Таккера— основной результат этого параграфа — была доказана в 1951 г. Рассмотрим следующую экстремальную задачу (задачу выпуклого програльяирования): (,(х) (п1, ~;(х)(0, 1=1,...,т, х~А, (1) где Х вЂ линейн пространство (не обязательно конечно- мерное), 1; †выпукл функции на Х, А †выпукл подмножество Х.

Отметим, и это существенно, что (1) — это задача минимизации, а не максимизации. Напомним, что множество С, лежащее в линейном пространстве называется выпуклым, если вместе с любыми двумя своими точками х и у оно содержит также и весь отрезок 1х, у] = (г ~ г = ах+ (1 — сь) у, 0 ч ' сс ( 11.