Ф.П. Васильев - Методы оптимизации (1125241), страница 26
Текст из файла (страница 26)
с — анормальная точка множества (1)), А (с) р ««, п«ах (с„(с«л)ь, ь) >0 а Лел,!«),!Л1=! УЬ е К(о), где л,(х«Л) = Л Лзд,.(э), А(и) — множество всех Л, удовлетворяющих усло«=« эию (24), А,(с) — подмножество тек Л е А(э), для которых существует сопровождающее подпространстэо П=П(Л) со свойствами (б)-(7) при замене а (7) С на С.
Указание: убедиться, что точка с будет изолированной точкой множества (!) тогда и только тогда, ко- гда ь — точка локального минимума функции 1(х) = -[х — с[, и затем к функции Дх) на 2 множестае (1) применить теорему 2. В. Применяя к функции 1(х) =-[х-о[2 на множестве (10) теорему 3, получить необходимое условие изолированности точки э множества (10), Э 5. Достаточные условия экстремума Продолжим исследование задачи поиска экстремума функции 1'(х) на множестве Х=(хюЕ": д(х)<0, 2=1,...,т; д(х)=0, з=т+[,...,э).
(1) Приведенное в Я 3, 4 условия первого и второго порядков являются лишь необходимыми условиями экстремума, и поэтому те точки, которые отбира- $5. ДОСТАТОЧНЫВ УСЛОВИЯ ЭКСТРЕМУМА 83 (2) ются с их помощью, являются лишь подозрительными на экстремум и, как мы видели на примерах, в этих точках не всегда реализуется ожидаемый экстремум. Для выяснения характера экстремума в отобранных точках предназначены достаточныг условия, в формулировке которых используются производные второго и более высокого порядков для функций 1(х), дз(х), 2 = 1,..., г. Здесь мы ограничимся достаточными условиями, которые формулируются с помощью второй производной функции Лагранжа.
Т е о р е м а 1. Пусть функции 1(х), д,(х), з = 1,..., э, дважды нгпоерывно диффгргнциругмья в окрестности точки и е Х, пусть конус'гуагранжа Л(и) этой точки непуст и (С (и, Л)6, 6)) >0 зЬ фО, Ь хК(и), (лг'(и), 6) <О, л ел(,1, !л! = « гдг шах (Ю (и, Л)6, 6) >0 !УЬ фО, Ь еК(и), (1'(и), 6) >О, (3) то в точке и реализуется строгий локальный максимум функции 1'(х) на множестве (1). Замечание 1. Так как конус Л(и) г)(0) замкнут, то множество (Л е Л(и), [Л[= 1) компактно и максимум в (2) при любом фиксированном 6 достигается хотя бы в одной точке Л = Л(6) е Л(и), [Л(6)[= 1.
Как мы видели в примерах 4.3, 4.8, одной «универсальной» точки Л, в которой реализуется максимум в (2) одновременно для всех Ь е К(и), (16(и), 6) < О, может не быть. Аналогичное замечание справедливо и для условия (3). Если в (1) ограничений типа неравенств нет (т = 0), то в условиях (2), (3) ограничения (1'(х), 6) < 0 (> 0) могут быть опущены без ущерба— этот вопрос мы уже обсуждали в замечании 4.2. При т = э = 0 теорема 1 превращается в теорему 2.2.
Доказательство теоремы 1. Если и — изолированная точка множества (1), то, по определению, и — точка строгого локального минимума [максимума]. Поэтому далее предполагается, что и не является изолированной точкой множества (1). Допустим, что условие (2) выполнено, но точка и не является точкой строгого локального минимума, Тогда найдется последовательность (х.), такая, что хь г- и дг(хь) <О, 2 =1,..., т, дз(х„)=0, 2 =т+1 1(*.)<П ), 6=1,2,.„, (*,,) . (4) Точки х, можем представить в виде хь =и+ 1ьйь, где й = л, 1 = [х.— ь=[,„' „[. ь= »- в и[ — «О при Ь -«оо.
Так как [йл[ = 1, й = 1, 2,..., то, выбирая при необходимости подпоследовательность согласно теореме Больцано — Вейерштрасса, (и) = (" ю ю: (д, (и), 6) < О, 2 Е 1(и) П (з: 1 < 2 < т), (д«(и), 6) = О, 2 = т -[- 1, г) 1(и) — множество индексов активных ограничений точки и. Тогда в этой точке реализуется строгий локальный минимум функции 7(х) на множестве (1). Если Л (и) фи (см.
замечания 3.1, 3.2) и, кроме того, 34 Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА $5. ДОСТАТОЧНЫЕ УСЛОВИЯ ЭКСТРЕМУМА 1 можем считать, что («1,,1- с(„~с?е~ =1. С учетом (4) и дифференцируемости функций 1(х), дс(х) в точке х = е имеем 0 > 1(х„) — 1(е) = (5'(е),с(,)1„ + о(г„), 0 > дс(х ) — дс(е) = (д,.'(е), с(„) в + о(зв), «Е 1(е) Г! («: 1 < «< т), 0= д;(х ) — д,(е) =(д,'(е), с(«)зв+о(с«), « =т+1,..., в, й =1,2, Разделив эти соотношения на г, > 0 и устремив й — оа, получим (1'(е), Й ) <О, (д,'(е), с?в) <О, «Е 1(е)П(«: 1 < «< т), (д,.'(е), Ив) =О, «' =т+1,..., в, (с?е)=1 Это означает, что с(«принадлежит конусу К!(е) =(е Е К(е), (1'(е), д,) < 0) и с?е ф О. Если конус К!(е) состоит лишь из точки О, то уже получим противоРечие.
ПУсть К (е) ф(01, Возьмем точкУ Л = Л(д«) ЕЛ(е),)Л(с(в))=1, в которой достигается максимум в (2) при Ь = с?е, Тогда (,С„„(е, Л(д,))д„с(в) > О. С другой стороны, учитывая (4), неравенства Л! > О, ! =О,..., т, и соотношения дс(е) = 0 !?«Е 1(е) П («; 1 < «< ги), д«(е) < 0 и Л, = 0 при «!Р 1(е), Л! д (е) = О, « = 1,, т, д (е) = О, « = т + 1,,, в, имеем: Г(х Л(с?е)) = Лоу(х«)+ Е Л дс(х«) < ЛОХ(х«) < ЛОУ(е) = « =ЛОУ(е)+ Е Л,дс(е)=.с(е, Л(с?е)), й =1,2, Отсюда с помощью формулы Тейлора с учетом равенства Ю„„(е, Л(Ы )) =0 получаем О >.С(х„, Л(с( )) — «",(е, Л(ов)) = — 2„'(в".„(е, Л(дв))с(„, с(«)+о(«,'), й = 1, 2, Разделив это неравенство на Г,'> 0 и устремив й . оо, будем иметь (А".„(е, Л(с(,))с?е, 4,) < О, что противоречит (2) и определению Л(с?ч).
Следовательно, е — точка строгого локальною минимума функции 1'(х) на множестве (1). Аналогично доказывается, что если для точки е выполнены условия (3), то е — точка строгого локального максимума функции 1'(х) на множестве 1). Теорема 1 доказана. П Ь я иллюстрации теоремы 1 приведем пример. П р и мер 1. Задача; требуется найти точки экстремума функции 1(х)= = 2; )х — х,.~' на шаре Х =(х ЕЕ; (х)' < 1); здесь х„..., х, — заданные с=! точки из Е". Эта задача была исследована в примере 4.3 с учетом конкретных особенностей задачи. Убедимся, что использование теоремы 1 упрощает анализ точек, подозрительных на экстремум, Поучительно также и то, что в некоторых точках теорема 1 «не работаете — с ее помощью не удается распознать характер экстремума точки.
В этой задаче .С„(х, Л) = 2(Л р + Л,)1„, где 1 — единичная матрица и х и, Переберем точки, подозрительные на п экстремум, в том порядке, как они перечислены в примере 4.3. Р 1) точка е, = х = — 2; хс пРи ~хв~ < 1. Нам известны соответствУющие =! е, два набора нормированных множителей Лагранжа: Л,, = (Л = 1, Л, =0) и Л! в =(Л, = — 1, Л, =0). Набор Л,, =(1,0) принадлежит конусу Л(е,); для него имеем (х..„(е„Л ь,)Ь, Ь) = 2р|Ь)в > 0 ЧЬ е Е", Ь | О, в частности, для ЧЬ Е К(е), (1'(е), Ь) < О. Отсюда следует, что условие (2) выполняется. Следовательно, е, — точка строгого локального минимума. А что мы получим, если точку е, аналогично проанализируем, используя набор Л,, = ( — 1,0)? Набор Л,, принадлежит конусу Л (е,); для него (х.„(е„Л ! )Ь, Ь) = — 2р(Ь(в < 0 ссЬ ф О, В этом случае конус Л (е) = (Л = = вЛ !Ло г > О). Отсюда видно, что условие (3) не будет выполняться на конусе Л (е,).
Это означает, что, используя набор Л!дм с помощью теоремы 1 нам не удалось распознать характер экстремума точки е,, Впрочем, нетрудно проверить, что здесь Л.(е,) = О и согласно теореме 4,3 и замечанию 4„3 точка е, не может быть точкой локального максимума. 2) е = ~ при )хв) > 1, Лв=(Л =1, Л, = р()Ц вЂ” 1) >0). Здесь Л, ЕЛ(ев) Ь) и (А". (е, Лв)Ь, Ь) =2р1хзйй)в > 0 «Ь фО, Таким образом, здесь условие (2) выполнено, и е, — точка строгого локального минимума. 3) ез — — ~~~ при 0< (хв) < 1, Лв —— ( — 1, Л, =р(1 — )хз)) >0) Е Л (ев). Здесь ~вв (,С„.(ев, Л в) Ь, Ь) = — 2р~ х Щ' < 0 ЧЬ фО.
Отсюда и из того, что здесь конус Лагранжа Л (е,) =(Л = гЛ, 2 > О), заключаем, что условие (3) не выполняется. Таким образом, в точке е теорема 1 «не работает». В примере 4.3 из других соображении было выяснено, что е не является точкой экстремума, К такому же выводу мы придем, показав, что точка е, не удовлетворяет необходимым условиям второго порядка (теорема 4.3, замечание 4;3). 4) е, = — — при )хз! > О, Л« = (Лв = — 1, Л, = р(1+ ~ ха() > 0) Е Л (е«). Здесь ) о~ Ю„(е„Л«)Ь, Ь) = 2р(1«~~ > 0 ЧЬ ~ О. Условие (3) заведомо выполняется, ледовательно, е, — точка строгого локального максимума.
5) при х = 0 все точки е, ~е,~ = 1, подозрительны на экстремум; им соответствует нормированный множитель Лагранжа Л = (Л, = — 1, Л, = р > 0). Здесь Лв ЕЛ (е ) и («,„(ев, Лв)Ь, Ь) =0 !УЬ ЕЕ" и ЧЛ ЕЛ (ев). Отсюда ясно, что условие (3~ не выполняется, и пользуясь лишь теоремой 1, мы не можем судить о характере экстремума в точках е,. Здесь нам не могут помочь и необходимые условия второго порядка (теорема 4.3, замечание 4.3), которые„как нетрудно проверить, выполняются для всех точек е,. В примере 4.3 из других сообрахсений было выяснено, что при х =0 все точки единичной сферы ~х~ = 1 являются точкой глобального максимума и 1(х) = 1'„.
При сравнении теорем 1 и 4.3 возникает интересный вопрос, насколько велик «зазор» между необходимыми и достаточными условиями второго порядка? Не вдаваясь в подробности, отметим, что исследования, проведенные в 143; 44), показывасот, что для широких классов экстремальных задач этот «зазор» является минимально возможным при использовании вариаций, имеющих второй порядок малости. В заключение этой главы заметим, что с помощью изложенных выше условий экстремума лишь в редких задачах удается найти и проанализировать все точки экстремума.
Поэтому может создаться впечатление, что эти Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА условия имеют лишь теоретическое значение. Однако это не так. Как увидим ниже, многочисленные методы в той или иной степени представляют собой итерационные процессы, подсказанные условиями экстремума и предназначенные для решения систем уравнений и неравенств, составляющих суть этих условий. Нередко даже беглый теоретический анализ условий оп> тимальности позволяет получить немало информации о свойствах решений конкретной задачи, которая может быть использована при конструировании и реализации численных методов. Упражнения 1.
Применить теорему 1 для исследования задач из упражнений к Я 2-4. 2. Пусть точка ь принадлежит множеству (1), пусть функции д. (х), 1 = 1,..., э, дважды непрерывно дифференцируемы в окрестности точки ь, Пусть конус А(ь) = (Л = (Л >,..., Лэ): лгО л! ~)0,..., л >О, Я л д> (ь)=0)гм> и гпак ([ ~; л д (ь)) ь ь) >О >уьфО, 2=1 ЛЕЛ!г),)Л~=! Ы=! Ь Е К(ь)=(Ь Е Е"; (д (ь), Ь) <О, 1 Е1(ь) Г> (1: ! < 1 < гп), (д,'(ь), Ь)=0, а=гп Ч-1,..., э). Доказать, что тогда е — изолированная точка множества (1).
У к а э а н и е: рассмотреть задачу минимизации функции Пх)= — )х — ь) на множестве (1) и применить к ней теорему ! 2 (см. упражнения 40, 4,а). у 6. Вспомогательные предложения Ниже приводятся некоторые формулы и различные другие сведения, которые будут использованы в дальнейшем изложении. д. Сначала напомним некоторые формулы для конечнь)х приращений функций конечного числа переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
