В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров, Сборник задач по оптимизации (теория, примеры, задачи) (1155771), страница 7
Текст из файла (страница 7)
е. определенпымн свойствами дифференцируемости. Гладкой элементарной задачей беэ ограничений называется задача об отыскании экстремумов этой функции: 1(х) — ех$г. (з) Лналогичная задача без ограничений возникает при отыскании экстремумов функционала ~, обладающего некоторой гладкостью и определенного в нормированном пространстве Х. 2 1.2. Правило решения. 1. Формализовать задачу, т. е. привести ее к виду (з). 2. Выписать необходимое условие /'(х) О. 3.
Найти стационарные точки, т. е. решения уравнения ~'(х) =О. 4. Отыскать решение среди стационарных точек или доказать, что решения нет. 2Л.З. Теорема Ферма. Т е о р е м а 1. Пусть ~ — функция одного переменного, определенная в некотором интервале, содержащем точку х, и дифференцируемая в точке х. Тогда, если х есть точка локального экстремума функции ~, то /'(х) =О. (1) а Д у, х =1о ш1п~, ~'(х)=х 'О и, для определенности, сг,(0. Задав е = !а!/2, найдем из определения производной такое 6= О, что прн О( !Ь! ~6 ~(х+ Ь) =Х(х)+ ай+ т(й), !г(й)! (!а! !Ь|/2.
Тогда для 0 ~ Ь ~ о получаем /(х+ Ь) = ~(х) + хй + т(Ь) < ~(х) + ай + !а!Ь/2 = /(х) — !а!й/2 (1(х), т. е. х Ф1осш(п~. Полученное противоречие доказываег теорему. Лналогично теорема доказывается для случая х ее 1ос шах 1'. Т е о р е м а 1' (аналог теоремы Ферма для нормированных пространств).
Пусть Х вЂ” нормированное пространство, Ж ~АХ), й Ж, /: Я вЂ” Н и функционал 1' имеет вариаци~о по Лагранжу (дифференцируем по Фреше) в точке х. Тогда, если х я 1ос ех(г /, то о/'(х, х) = 0 7х~ Х (/' (х) = 0). (1') °:) Если х ее1ос ех$г /', то Чх ~ Х точка нуль является локальным экстремумом функции одного переменного: бег Х г~(),; х) =~(х+Хх).
Пользуясь определением вариации по Лагранжу и соотношением (1), получим 6((х, х) =О. В силу произвольности х приходим к (1'). Если функционал ) дифференцируем по Фреше в точке х, то в этой точке он имеет вариапию по Лагранжу. Поскольку х~ гв1осех1г (, то из уже доказанного следует, что эта вариация равна нулю. Отсюда /'(х) =0 в силу определения дифференцируемости по Фреше (п. 1.4.1). > Из теоремы 1 следует, что если точка х доставляет локальный экстремум дифференцируемой функции нескольких переменных: 1: В" В, то все частные производные функции ~ в точке х обращаются в нуль, т. е. ~' (х) = 0 <в.:- — = ...
= — = О. д~ (х) д~ (х) дх ''' дхц 2Л.4. Элементарная задача линейного программирования. В ~ 4 мы познакомимся с выпуклыми задачами, частный подкласс которых образуют задачи линейного программирования. Здесь будет рассмотрена самая простая из задач этого класса. Она интересна тем, что при ее рассмотрении мы познакомимся с важными условиями экстремума, возникающими в задачах с неравенствами,— условиями неотрицательности и дополняющей не- жесткости.
Элементарной задачей линейного программирования называется следующая задача: ~~)~~ а,х;-+ 1ш, х;~)О, ~=-1,...,и (Х=В ), (з) ~=1 Т е о р е м а. Для того чтобы точка х = (х„..., х„) доставляла абсолютный минимум в задаче (з), необходимо и достаточно, чтобы были выполнены: а) условия дополняющей нежесткости а,х, = О, 1 1,...,п; ,б) условия неотрицательности а, ~ О, 1 = 1, ., и, Доказательство этой теоремы совершенно очевиднр. 2.2.
Гладкая конечномерная задача с ограничениями типа равенств. 2.2Л. Постановка задачи. Пусть |: В" - В, ~= О, 1..., , т,— функции и переменных, отображающие пространство В" в В. Конечномерной экстремальной задачей с ограничениями типа равенств называется следующая 40 задача в Н": ~,(х)- ех$г; ~~(х) =О, ~ 1,,, и. (з) Далее считаем, что все функции ~, обладают определенной гладкостью. 2.2.2. Правило решения. 1. Составить функцию Лагранжа: 2. Выписать необходимое условие: Ж (х, М = О Х )~;~;„ (х) = О, ) = 1... „ и, ь=в 44 3. Найти стационарные точки, т.
е. допустимые решения уравпений и. 2, в которых не все множители Лагранжа ) „Х„..., ). равны нулю. При этом бывает полезно отдельно рассмотреть случаи Хо =О и Х, чьО. Во втором случае можно положить Х, равным единице или любой другой положительной константе в задаче на минимум и равным минус единице или любой другой отрицательной константе в задаче на максимум. 4. Отыскать решение среди всех стационарных точек илн доказать, что решения нет.
3 а м е ч а н и е. В правиле множителей Лагранжа для задач с ограничениями типа равенств можно, вообще говоря, не обращать внимания на тип экстремума и, убедившись, что Хо Ф О, полагать ), равным любой отличной от нуля константе. Для задач, где присутствуют неравенства и включения, знак Х, существен, 2.2.3. Правило множителей Лагранжа. Теорема. Пусть Х = В", Я ~ 0(Х), х гз %, ~;: 'Я- й, ~ = О, 1, ..., и,— непрерывно дифференцируемые функции в мноэкестве % (условие гладкости).
Тогда, если х есть точка локального экстремума в задаче (з), то существует ненулевой вектор Х = Йг, Хо ..., Х ) такой, что Ю (ж,Х) О~ ' О, 1'=1, ...,ие~ дУ (2, х) Б соотношении (1) Ы(х,)) =,~~~),~,(л) — функция 4=0 Лагранжа рассматриваемой задачи, а ).„).„..., )...— множители Лагранжа. 0 А) Обозначим через Л линейное отображение из В" в В" +', определяемое соотношением Лх=((~о~х),х),...,(~'.(х),х)) с=:- А(х„...,х„) = Возможен один из двух случаев: 1) Л отображает В" в собственное подпространство Ь пространства В"'+', 2) Л отображает В" на все В +'. Б) Если реализуется случай 1), то по лемме об аннуляторе в конечномерном пространстве (п, 1.3.1) найдутся числа Хо, Х„..., Х„„не все равные нулю и такие, что ';~~ Х;у; = О Уу н= Ь ~=о-,'~~ Х; (~; (х), х) = О Чх нв В", д~о~~) й~И дх ' ' ' ' ' дтщ+ = дес ЛХ~= О, оеС дУ (х) д1 (х ) дх ' ' ' '' дх,„+ и теорема доказана.
В) Покажем, что случай 2) невозможен. Действительно, если образ Л есть все пространство, то ранг соответствующей этому отображению матрицы Л = дУ; (~) 1 о~,. ),, также равен т+1. (Этот факт прямо следует из известной в алгебре теоремы Кронекера— Капелли.) Тогда по теореме о ранге существует минор матрицы Л порядка (т+ 1) Х (и+ 1), отличный от нуля. Допустим для определенности, что этим минором является минор, составленный из первых т + 1 столбцов матрицы Л: Положим (хо ..., х 1+1) = (Фо(х~..... хюп+1), ..., Ф,.(хне ..., хам+1)) = (/о(х, ..., х, +,, х„,.„..., х„) — ~,(х), ),(х„..., х +„х„+„..., х„)..., /п2(хо ° ' ) хм+о хи+21, ° о хи))) Ф отображает некоторую окрестность точки (х„. ° .
..., х„,+,) ~ В"'+' в К +' и является (в силу условия глад- кости теоремы) непрерывно дифференцируемым отобра- жением в этой окрестности. При этом г)е1 ~ ' в, /~=о,,~ — — де(МФ О. /дф,.(х,...,х + )~( По теореме об обратной фупкцпи (и. 1,5.4) существуют е,'.> О и константа К~ О такие, что ~е ~ ( — е„е,1 най- дется вектор (х,(е), ..., х„,+~(е)), для которого Ф(х, + х,(е), ..., х +, + х +,(е)) = (е, О, ..., О) «=~. ~=' ~,(х1 + х,(е), ..., х +, + х +,(е), х„,+....., х„) — У,(х) е, ~~ (х1 + х~ (е)~ ° .,1 хп1+1 + хы+1(е)у хи~~ 2~ ° ' '~ хп) = О, (=1,...,т, ~т~-1 '~1г и при этом ~ Х х,'(е)~ ~(К(е~.Из написанных соотношений сразу следует, что вектор (х, + х,(е), ..., х.,+, + + х.,„,(е), х,.+~, ..., х„) является допустимым в задаче (з) и что вектор (х„ ..., х„) = х не доставляет задаче экстремума, ибо вблизи от него существуют допустимые векторы, на которых функционал принимает значения и большие, и меньшие.
чем ~,(х). (> 3 а и е ч а н н е. Из соотношения (1) следует, что если г / 1 ( Ъ л век1оры ~, ~х),..., ), (,х) линейно независимы, то Х, ч О. (з) 43 2.3. Гладкая задача с равенствами и неравенствами (общий случай). 2.3.1. Постановка задачи. Пусть Х, У вЂ” нормированные пространства, Р: Х вЂ” У, ~,: Х вЂ” й, 1=0, 1...,, т.
Гладкой задачей с равенстваии и неравенствами называется задача ~,(х) — пЛ; Р(х) =О, Цх) ~ О, 1=1, ..., т, если отображение Р и функционалы ~, обладают некоторой гладкостью. 2.3.2. Правило решения. $. Составить функцию Лагранжа: Я' (х, у*, Х) = ~ ХД (х) + (у*, Р (х)), где у* ее У~, ) = Й„..., Х ) — множители Лагранжа. 2. Выписать необходимые условия: а) стационарности юи Я'„~х, у*, Х) = 0 с=~ ~ ),Д(х) + (Р' (х))* ув = О, где (Р'(х))* — оператор, сопряженный к отображению Р'(х): Х- У; б) дополняющей нежесткости )4,(х) =О, 1=1, ..., и; в) неотрицательности Х,~О, ~=0,1,...,т. 3.
Найти критические точки, т. е. допустимые точки, удовлетворяющие необходимым условиям п.2 с множите- лями Лагранжа Х и у*, одновременно не равными нулю. При этом бывает полезно отдельно рассмотреть случаи Х,=О и Х~ФО. Во втором случае можно положить Х, рав- ным единице или любой другой положительной константе, 4. Отыскать решение среди критических точек или до- казать, что его нет. 2.3.3. Необходимые условия экстремума. Т е о р е м а. Пусть Х, У вЂ” банаховы пространства (условие банаховости), % с 0(Х), х ез Я, Р: Я вЂ” У, ~,: М вЂ” В, )',ее Я)(х), ~ =О, $, ..., т, Резях, У) (усло- вие гладкости) и Р'(х)Х замкнуто в У (ослабленное усло- вие регулярности).
Тогда, если х есть точка локального экстре.к~ума в за- даче (з), то существуют вектор Ая В"'+' и функционал у*~ У'", не равные одновременно нулю и такие, что вы- полнены условия: а) стационарности Ы.(х, у',)) = О~Х Ч~(х)+(Р'(х))*у*= О; б) донояняюи)ей нежесткоети ХУ(х) =О, 1=1,..., т; в) неотрицательности Х,~О, К=О, 1, ..., т. Доказательство см.
в ЛТФ, с. 257, а также п, 4.41. 2.4. Примеры. Пример 1. ~(х) =ах'+ Ьх+ с- ех(г (аФ 0). Р е ш е н и е. 1. Применяем правило решения гладких задач без ограничений (п. 2 1.2). 2. Необходимое условие — теорема Ферма. ~'(х) =0 ~=: с=:. 2ах+ Ь = О. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
