Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 24
Текст из файла (страница 24)
Обсудим понятия анормальной и нормальной точки для множества (10). Мы здесь будем придерживаться трактовки этих понятий, принятой в 144]. Определение 5. Точка о множества(10) называется анормальной, если 0 < т < г и градиенты д„,'(е),..., д,'(о) линейно зависимы, т.
е, существуют числа Л„~ „..., Л„такие, что Л„~,д„'„,(о)+... + Л,д,'(е) =О, (Л ъ„..., Л,) фО. При въ = г, когда в (10) ограничения типа равенств отсутствуют, во множестве (10) анормальных точек нет по определению. Если г — т > и, то все точки множества (10) являются анормальными. Нетрудно видеть, что всякая анормальная точка в множества.(10) является подозрительной на экстремум для любой дифференцируемой функции Х(х), так как пара (е, Л), где Л имеет координаты Л = Л, =... = Л =О, а Л „„..., Л, взяты из (18), является решением сйстемы (3.13). Как и в случае множества (1) можно показать, что точка е локального минимума дифференцируемой функции Х(х) на множестве (10) будет анормальной тогда и только тогда, когда конус Л(е) Ы(0) является неострым, т, е. содержит прямую.
В самом деле, если набор (Л ън..., Л,) удовлетворяет условию (18), то набор ( — Л„ъ„..., — Л,) также удовлетворяет этому условию, поэтому наборы Л = (Ль = О, Л, = О,..., Л„= О, Л + „..., Л,) н (-Ль)=(Л =О, Л, =О,..., Л„=О, — Л„~„...,-Л,) принадлежат Л(в). Поскольку Л(е) конус, то точки ъЛь и ъ(-Ль) е Л(е) при всех ъ > О. Следовательно, прямая Л(ъ) = ъЛы — со < ъ <+со, принадлежит Л(е) О (О), т. е. конус Л(о) 0(0) неострый. Обратное, если конус Л(е) 0(0) содержит некоторую прямую Л(ъ) = ъ ъТ, — оо < ъ <+со,,й= (р,..., и ) ф О, то точки Л(1) = ъТ и Л( — 1) = — ъТ принадлежат Л(е).
Поскольку у всех точек Л конуса Л(е) координаты Л„ > О,..., Л,„ > О, то р > О,...,,и > О, Это значит, что условия х,,(е, ъТ) = О, йфО из системы (3.13) йревращаются Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА в условие (18) с (Л„в, = а„„п..., Л, = а,) ~0. Тем самым показано, что если конус Л(о)О (0) неострый, то е — анормальная точка множества (10). Аналогично доказывается, что точка е локального максимума дифференцируемой функции 1(х) на множестве (10) анормальна тогда и только тогда, когда конус Л (0) О (0) неострый. Заметим, что если в (10) т = в, то конус Л(е) с! (0) или Л (0) О (О) не может содержать прямую.
В противном случае нашлись бы точки Л, ( — Л) Е Л(е) или Е Л (о). Это означало бы, что Л, > О,..., Л > О, — Л, > > О,..., — Л„> О, а Л > О, — Л > О, либо Л, < О, — Л, < О, отсюда следует, что Л =О. Однако, Оф Л(е) и Оф Л (е). Противоречие.
Приведенные соображения оправдывают определение 5, когда в (10) т = в. Таким образом, понятие анормальной точки множества (10), выражая лишь специфическое свойство (18) этого множества, автоматически является подозрительной на экстремум для любой дифференцируемой функции 1(х). Поскольку при 0 < т < в наличие анормальной точки у множества (10) не такое уж редкое явление, то возможность использования теоремы 2 для их анализа на экстремум, представляется весьма важным.
О п р е д е л е н и е 6. Точка е множества (10) называется нормальной, если система линейных уравнений и неравенств относительно неизвестных Л,.д,.(е)=0, Л,. >О, 4 =1,..., т, (19) Л,д,.'(е) = О, ~ =1 (д,.'(е), г() = О, 1 = тп + 1,..., в, (д,'(е), д) < О, Чг Е 1(и) П (1 < 4 < тп), (20) имеет лишь нулевое решение. Как видим, при тп = 0 определение б совпадает с определением 1 нормальной точки для множества (1).
Как и в случае множества (1) нетрудно заметить, что если точка е, подозрительная на экстремум функции 1'(х) на множестве (10), является нормальной, то в конусе Лагранжа все точки Л = (Л,..., Л,) имеют координату Л ~ О. В самом деле, если бы в такой точке существовал набор' Л = (Ло =О, Л„ ..., Л,) ~0, то как видно из (3.13), система (19) имела бы решение. Верно й обратное: если в конусе Лагранжа у всех точек Л координата Л фО, то е — нормальная точка множества (10). Заметим, что если в нормальной точке множества (1) конус Лагранжа состоял из одного луча, то в случае тп > 0 этот конус, вообще говоря, богаче.
Кроме того, не следует думать, что если точка множества (10) не является анормальной, то она непременно будет нормальной. Так, если т = в, то в множестве (10) по определению 5 нет анормальных точек. Однако если, например, при этом д,.'(е) = О, 4 = 1,..., т, и имеются активные ограничения, то система (19) будет иметь бесконечно много решений, и, следовательно, точка и не является нормальной. Таким образом, в множестве (10) могут быть точки, которые не являются ни нормальными, ни анормальными.
Конечно, всякая нормальная точка множества (10) не может быть анормальной, так как конус Л(е) любой анормальной точки содержит Л с Лв,=О, Покажем, что е будет нормальной точкой множества (10) тогда и только тогда, когда: 1) векторы д „,'(е),..., д,'(е) линейно независимы, 2) существует вектор Ы Е Е", для которого $4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 79 р,.д,.'(и) =О, р,.
) О, 4 Е 1(е)Г!(4: 1(4 < т), (р,, г' Е1(е))Э40. '41',' '„"' 'тГ(э) Тогда вектор Л =(Л,. = р,, 4 е 1(и), Л,. =О, г ф 1(е)) будет решением системы (19), что опять-таки противоречит нормальности точки е. Таким образом, установлено, что условие Лйангасариана — Фрамовица равносильно но мальности точки и множества (10). окажем, что в отличие от множества (1), в нормальных точках е множества (10), подозрительных на экстремум, в условии (15) операция взятия максимума, вообще говоря, не может быть опущена.
С этой целью, как мы уже это делали неоднократно, позаимствуем пример из [44], Поимев 8. Рассмотрим задачу: 1(х) = — х' — !п( х е Х = (х = = (х, х~, х ) е Я'. д,(х) = х'+ 2х'х~ — в((х') + (х')') ( О, дв(х) = х— — 2х'х — в((х')в+(х )в) < О, д (х) = х~+ ~(х') — (хв)в) — в((х') +(х~)в) < О, д,(х) = хв — (х')в + (хв)в — в((х')в + (х') ) < О), в ) О. Сначала убедимся, что е = (0,0, 0) =0 — решение этой задачи. На плоскости (х', х') введем полярную систему координат: х' = т сов !о, х'= т ь1п р, 0 < !о < 2я.
Тогда д (х) = х'+тл(ып 2!о — в), д (х)= х' — тв(з!п 2 р+в), д,(х)= х'+т'(соь 2р — и), д,(х) = х' — т (соь 2у + в). Выберем в > 0 таким, чтобы ш!п(ь!и 2ьо, — ь!п 2~р, соь 2~р, — соь 2ьо) — ь < 0 Фр, 0 ( ~р < 2я, например, можно взять в = 1/4. Тогда хотя бы в одном из неравенств хв < — тв(йп 2 р — ь), хв < тв(ь|п 2!о+в), хв < — 1'(соь 2 р — в), хз < тв(соь 2!о+ + в) правая часть отрицательна при каком-либо у, 0 < !о < 2к, и любых 50 Гл.
2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА $4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА г > О, и все правые части = 0 при т = О. Это значит, что у всех точек х = (х', х',х') Е Х координата х' < О. Следовательно, 1п1 Г(х) = 0 = Г(0) ~ох и е =0 — решение рассматриваемой задачи. В точке е =0 выполняется условие Мангасариана — Фрамовица с вектором и' =(0,0, — 1). Следовательно е = 0 — нормальная точка множества Х. Конус Лагранжа точки в=О равен А(0)=(Л =(Л, Л„Л„Л„Л,): Л =Л,+Л,+Л,+Л4>0, Л! >О, г = 1,..., 4). Поскольку в точке е = 0 все ограничения д!(х) < О, 1 = 1,..., 4, активные, то [Х(0)) =4 > и = 3 и каждая точка Л е Л(0) имеет тривиальное сопровождающее подпространство П(Л) = (0). Следовательно, в рассматриваемой задаче конус Арутюнова А.(0) = А(0). Согласно теореме 3 в точке минимума о = 0 условие (15) выйолняется при всех Ь е К,(0) = = К(0) Г!(Ь: ( Г!(0)1 6) ( 0) = (Ь е Е'! (д.'(0), 6) < О, 4 =1,..., 4, (у(0), 6) < 4 < 0) = (Ь =(Ь', Ь', Ь' =0)).
Однако (4".„,(О! Л)6, 6) = ([ 2 Л!д,"(0)) Ь„Ь) = !=1 =2[6!'[А(Л) з!и 2оо+ В(Л) сов 2!Р— з] при каждом Ь =(Ь' = /6[сов !!о, Ьо = = / 6[ з!и ~о, Ьо = 0) е К (0), Л е А(0); явные выражения величин А (Л ), В(Л) нам не понадобятся, поэтому мы их не будем здесь приводить. Отсюда видно, что для !УЛ е А(0) = А„(0), [Л [ = 1 найдется р, 0 < э! < 2я, такой, .~(Г!.ю ш~+вр! ар — =~л*о!~.в!л! п!!р+О! — *~о (здесь !Р вспомогательный угол, 0< 4 < 2я, определяемый равенствами — "-е! ! о = —,-кэ — р ! !г!.'-а !г>~0! т. 'ЗД 'о!' ' ~З!Г! В~О! ким образом, при любом выборе Л ЕЛ (0), [Л[= 1 найдется Ь Я К(0), Ь ~0, что (4".„,(О, Л)6, 6) < О.
В то же время условие (15) согласно теореме 3 выполняется. Это значит, что даже в нормальной точке экстремума знак максимума в (15) не может быть опущен. 3. Кратко обсудим один известный прием сведения задач с ограничениями типа неравенств к задачам с ограничениями типа равенств.
Этот прием, по-видимому, впервые был предложен Н. Н. Гернет [221] для исследования задач вариационного исчисления с односторонними ограничениями. Опишем его для задачи поиска экстремума функции Т"(х) на множестве (21) Х =(хе Е": д!(х) < О,...! д,„(х) < 0) Введем вспомогательные переменные и = (и',..., ю") и в пространстве переменных у=(х, и)=(х',..., х", и',..., и") рассмотрим задачу поиска экстремума функции Г"(х) на множестве 1'' = (У = (х, и) Е Е"'"'": д (у) = д (х) + (и!)' = О, г = 1,, т). (22) Нетрудно видеть, что эта задача равносильна исходной задаче на множестве (21). В самом деле, если х„— точка локального минимума [максимума] функции Дх) на множестве (21), то точка у, = (х„, и,), где и, = = (и,',..., и„), и,' = ( — д,(х.))но, г = 1,..., гп, будет точкой локального минимума [максимума] фуйкции Г(х) на множестве (22) и наоборот, если у„= (х„ю,) — точка локального минимума [максимума] функции Г(х) на множестве (22), то х„— точка локального минимума [максимума]'функции Г(х) на множестве (21).