Ф.П. Васильев - Методы оптимизации (1125241), страница 24
Текст из файла (страница 24)
Конусом Арутюнова точки е множества (10) будем называть подмножество Л.(е) таких точек Л е Л(о), для которых существует подпространство П = П(Л) пространства Е", обладающее следующими свойствами: г(1гп П(Л) > гпах(п — [Х(о)[; О); (11) П(Л )С багет С'(е)=(6 а Е": < д,.'(е), Ь > =О, 4 еХ(е)), С=(дг, ТЕХ(е)); (12) (л, (е, Л)6, 6) >0 1г'Ь ЕП(Л).
(13) Как и в определении 3, подпространство П(Л) со свойствами (11) — (13) будем называть сопровождающим подпространством точки Л еЛ.(е). Рассуждая также, как в случае множества (1), нетрудно убедиться, что и здесь Л,(о) действительно является конусом. Заметим, что при [1(о)[ > гг каждая точка Л еЛ(е) обладает нулевым сопровождающим подпространством П(Л) =(0).
Поэтому конус Л.(о) =Л(е) при [1(о)[ > и. Те о р е м а 3 (Арутюнов [441). Лусть о — точка локального минимума функции 1(х) на множестве (10), пусть функции 1(х), д,(х),..., д,(х) дваждьг непрерывно дифференцируемга в некоторой окрестности точки о. Тогда Л,(о) фо, (14) гпах (С„(о, Л)6, 6) > 0 УЬ е К(е), (1'(о), Ь) < О, (15) ллл( ори-г ™ гдв К(е) = (6 Е Е": (д,'(о), 6) < О, 4 Е 1(е) Гг (4: 1 < 4 < гп), (д,'(е), 6) =О, 4 = гп+ 1,..., г) (16) — конус критических направлений множества (10) в точке е. 4 4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 77 (18) Доказательство этой теоремы проводится с помощью метода штрафных функций в $5.16.
Сделаем несколько замечаний. Замечание 2. Прежде всего убедимся, что при т =0 теорема 3 превращается в теорему 2. Для этого покажем, что неравенство (1'(е), 6) < 0 из (15) в случае гп = 0 может быть опущено без потерь. В самом деле, очевидно, для любого вектора Ь е Е" выполняется одно из двух неравенств: (1'(е), Ь) ( 0 или (1'(о), 6) > О, и справедливо равенство (С„(е, Л)6, 6) = (С,(о, Л)( — 6), ( — 6)). Кроме того из (1'(е), 6) < 0 следует, что (1'(е), ( — Ь)$ > О.
Отсюда ясно, что если неравенство (9) выполняется для ЧЬ е К(о), (1'(о), 6) < О, то оно выполняется и для ггЬ а К(о), ~')' ,~= Х'(е), 6) > О. Это значит, что при гп = 0 в условии (15) требование Х'(е), 6) < 0 может быть спущено, а тогда теорема 3 превращается в теорему 2. 3 а м е ч а н и е 3. Если о — точка локального максимума функции 1(х) на множестве (10), то утверждения (14), (15) сохраняют силу, нужно лишь конус Л,(о) заменить на Л„(о), а в условии (15) неравенство (~'(е), 6) < 0 заменить на (Х'(е), 6) > О. Конус Арутюнова Л.(е) для точки е локального максимума функции 1(х) на множестве (10) определяется также, как конус Л.(о), нужно лишь вместо Л(о) взять конус Л (о) (см. замечание 3.2). Обсудим понятия анормальной и нормальной точки для множества (!0).
Мы здесь будем придерживаться трактовки этих понятий, принятой в [44). О п р е д е л е н и е 5. Точка о множества (10) называется анормальной, если 0 < гп < г и градиенты д„~,'(е),..., д,'(о) линейно зависимы, т, е. существуют числа Л л„..., Л„такие, что Л,д',(е)+...+Л,д,'(о)=0, (Л,„...,Л,)фО При гп = г, когда в (10) ограничения типа равенств отсутствуют, во множестве (10) анормальных точек нет по определению. Если г — гп > и, то все точки множества (10) являются анормальными.
Нетрудно видеть, что всякая анормальная точка о множества (10) является подозрительной на экстремум для любой дифференцируемой функции 1(х), так как пара (е, Л), где Л имеет координаты Л = Л, =... = Л =О, а Л„~„..., Л, взяты из (18), является решением сйстемы (3.13). Как и в случае множества (1) можно показать, что точка о локального минимума дифференцируемой функции 1(х) на множестве (10) будет анормальной тогда и только тогда, когда конус Л(е) О (О) является неострым, т.
е. содержит прямую. В самом деле, если набор (Л„~„..., Л,) удовлетворяет условию (18), то набор ( — Л,„~„..., — Л,) так™же удовлетворяет этому условию, поэтому наборы Л = (Л = О, Л, = О,..., Л„= О, Л„„..., Л,) и (-Лс) = (Лл = О, Л, =О,..., Л„= О, — Л„ч „..., -Л,) принадлежат Л(о), Поскольку Л(о) конус, то точки гЛ и г( — Лл)еЛ(е) при всех г >О. Следовательно, прямая Л(г) = ЙЛ, — со < $ <+со, принадлежит Л(о) О (0), т, е.
конус Л(о) О(0) неострый. Обратное, если конус Л(о) О (О) содержит некоторую прямую Л(Г) = сгТ, -оо < г <+со, р, =(р,..., гг) ф О, то точки Л(1) = р и Л( — 1) = — р принадлежат Л(о). Поскольку у всех точек Л конуса Л(о) координаты Ло > О,..., Л > О, то ро > О,..., р >О, Это значит, что условия л,,(е, р) =О, йфО из системы (3.13) превращаются Гг.
2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА В 4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 79 з) (20) в условие (18) с (Л +, — — р„„..., Л, = р,) ф О. Тем самым показано, что если конус Л(х) ы (0) неострый, то я — анормальная точка множества (10). Аналогично доказывается, что точка )) локального максимума дифференцируемой функции 1(х) на множестве (10) анормальна тогда и только тогда, когда конус Л (0) О (О) неострый. Заметим, что если в (10) т = г, то конус Л(и) О (0) или Л (0) с) (01 не может содержать прямую. В противном случае нашлись бы точки Л, ( — Л) ЕЛ(я) или е Л ())).
Это означало бы, что Л, > О,..., Л„> О, — Л, > >О,..., — Л >О, а Ль>0, — Лз>0, либо Л,<0, — Л <О, отсюда следует, что Л =О. Однако, Оф Л(я) и 0)р Л (х). Противоречие. Приведенные соображения оправдывают определение 5, когда в (10) т = г. Таким образом, понятие анормальной точки множества (10), выражая лишь специфическое свойство (18) этого множества, автоматически является подозрительной на экстремум для любой дифференцируемой функции 1(х), Поскольку при 0 < т < г наличие анормальнои точки у множества (10) не такое уж редкое явление, то возможность использования теоремы 2 для их анализа иа экстремум, представляется весьма важным.
О яр еде л е н не 6. Точка )) множества (10) называется нормальной, если система линейных уравнений и неравенств относительно неизвестных 2 Л!д! (с) =О, Л)д!(я)=0, Л > О, 4 =1,..., т, (19) имеет лишь нулевое решение. Как видим, при т = 0 определение 6 совпадает с определением 1 нормальной точки для множества (1), Как и в случае множества (1) нетрудно заметить, что если точка я, подозрительная на экстремум функции 1(х) на множестве (10), является нормальной, то в конусе Лагранжа все точки Л =(Л„..., Л,) имеют координату Ль ~ О, В самом деле, если бы в такой точке существовал набор Л =(Ль = О, Л„..., Л,) фО, то как видно из (3!13), система (19) имела бы решение. Верно й обратное: если в конусе Лагранжа у всех точек Л координата Ла Ф О, то 'я — нормальная точка множества (10).
Заметим, что если в нормальной точке множества (1) конус Лагранжа состоял из одного луча, то в случае т > 0 этот конус, вообще говоря, богаче. Кроме того, не следует думать, что если точка множества (10) не является анормальной, то она непременно будет нормальной, Так, если т = г, то в множестве (10) по определению 5 нет анормальных точек.
Однако если, например, при этом д,'())) = О, 4 = 1,..., т, и имеются активные ограничения, то система (19) будет иметь бесконечно много решений, и, следовательно, точка я не является нормальной. Таким образом, в множестве (10) могут быть точки, которые не являются ни нормальными, ни анормальными, Конечно, всякая нормальная точка множества (10) не может быть анормальной, так как конус Л())) любой анормальной точки содержит Л с Лз = О. Покажем, что я будет нормальной точкой множества (10) тогда и только тогда, когда: 1) векторы д„+!'())),..., д„'())) линейно независимы, 2) существует вектор !! Е Е", для которого (д,'())), !!) = О, в' = т+ 1,, г, (д,'())), !!) < О, ))4 Е 1())) Г) (1 < 4 < т), где 1(и) — множество номеров активных ограничений точки е (возможность т = 0 или т = г здесь не исключается), Это условие в литературе по экстремальным задачам (особенно зарубежной) часто называют условием Мангасариана — Фрамоеш!а. Убедимся, что при выполнении перечисленных условий точка я будет нормальной.
Допустим, что это не так, Тогда система (19) имеет хотя бы одно решение Л, и для него в 0=(2; Л!д,.'())), г!) = 2,' Л!(д,'(я), )1) <О, что возможно только при Л,. =0 ! = ! ' я г(е) Л)4Е1()))Г)(1< 4 <т), так что Л,=...=Л =О. Если при этом т=г, то это означает Л =О, что противоречит тому, что Л вЂ” решение системы (19). Если же т < г, то равенство ',) Л)д,'())) =0 превращается в 2; Л,д,.'(я) =О, =! +! что может быть только при Л„+, —— ...
— — Л„= О. Таким образом, и в случае т < г получаем Л = О, что невозможно для решения системы (19). Следовательно, система (19) не имеет решения, т. е. )) — нормальная точка множества (10). Докажем обратное: если е — нормальная точка множества (10), то условия Мангасариана — Фрамовица выполнены, Пусть это не так. Тогда либо векторы д „'())),..., д,'())) линейно зависимы, либо система (20) несовместна. В первом случае найдутся числа (а„„„ ...,а,) ф О, такие, что в а д ()))=О.
Тогда Л =(Л,=О,..., Л =О, Л „, =а,„„„..., Л,=а,)— '=и +! решение системы (19), что противоречит нормальности точки )). Во втором случае, когда система (20) несовместна, из теоремы Моцкина (см. упражнение 3.5.14) следует, что совместна система р, д.'(я) = О, р. > О, 4 Е 1())) П (4! 1 < 4 < т), (р), 4 Е 1(я)) ф О. яц ) Тогда вектор Л =(Л! = р!, 4 Е 1(я), Л, =О, 4 ф 1(э)) будет решением системы (19), что опять-таки противоречйт нормальности точки я.