Ф.П. Васильев - Методы оптимизации (1125241), страница 22
Текст из файла (страница 22)
определение 2.2). Воспользуемся критерием неотрицательности матрицы, приведенном в замечании 2.2. Если Л =(Лв >О, Л, =О, Л, =0), то неравенство / — 1 0 ОЛ Е (О,Л)=2Л 1 Π— 1 О) >О 0 0 1 невозможно ни при каком Лл>0. Если же Л=(Л„=О,ЧЛ„ЧЛ,), то неравен- 12Л, Л ОЛ Е,„(О,Л)= Л, — 2)с, 0 >О 0 0 0 также невозможно, так как с(е1, 2), ~ = — 4Л вЂ” Л, < 0 и(Л„Л,) фО, 2Л, Л 1 2 Аналогично исследуется случай Л„> О, (Л„Л,) ф О.
Таким образом, теорема 1 в анормальных точках перестает быть справедливой. Следовательно, необходимые условия экстремума второго порядка для анормальных точек должны формулироваться как-то иначе, чем в теореме 1. А как? Ниже приводится необходимое условие второго порядка, справедливое в общем случае, независимо от того, является ли точка и нормальной или анормальной. Этот интересный и изящный результат принадлежит А. В. Арутюнову !44] и в учебной литературе излагается впервые. О пределе н ие 3.
Пусть и — точка локального минимума функции 7" (х) на множестве (1) и Л(и) — соответствующий ей конус Лагранжа. Конусом Арутюнова Л. = Л.(и) будем называть конус, состоящий из таких наборов Л =(Л„..., Л„) е Л(и) для каждого из которых существует подпространство П = П(Л) пространства Е", обладаюсцее следующими тремя свойствами: с(!ш П(Л) > снах(и — в;О), где с!!ш П(Л) — размерность П(Л); (5) 7 д '! П(Л) С 1сег С'(и)=(ЬеЕ": (д,'(и), 6)=0, 4=1,..., в), С = ...; (6) (7) (х, (и, Л)6, 6) > 0 ЧЬ Е П(Л) Подпространство П(Л) со свойствами (5) — (7) будем называть сопровохсдаюи(им подпространством точки Л еЛ„(и). Убедимся, что множество Л.(и) в самом деле является конусом. Возьмем произвольные точку Л ЕЛ,(и) и число сх > О.
Для точки ссЛ в качестве сопровождающего подпространства можно взять то же подпространство П(Л), которое является сопровождающим для точки Л. Свойства (5), (6) не требуют доказательств, а свойство (7) вытекает из того, что (х, (и, ссЛ)6, Ь) = = сс(С (и, Л)6, 6) >0 ЧЬ Е П(Л), Чсх >О. Это значит, что Л„(и) — конус. Заметим, что при в > и каждая точка Л е Л(и) обладает сопровождающим подпространством П(Л) = (0).
Следовательно, Л„(и) =Л(и) при в > и. Т е о р е м а 2 (Арутюнов [441). Пусть и — точка локального минимума функции 7" (х) на лсногкестве (1), пусть функции 7(х), д,(х),..., д,(х) двахсды непрерьсвно дифференциругмы в некоторой окрестности скачки и. Тогда Л,(и) ф И; (8) снах (С (и, Л)6, 6) >0 (9) л в л.СИ, СС1 = 1 сУЬеК(и)=(6 е Е": (д,'(и), 6)=0, а=1,..., в). Доказательство этой теоремы будет дано ниже в Э 5.16.
Сейчас мы прокомментируем ее и проиллюстрируем примерами. Сразу же заметим, что в условиях (7) и (9) участвует одна и та лсе квадратичная форма (х.„(и, Л)6, 6), и у читателя может сложиться впечатление, что оба этих условия как-то связаны с неотрицательной определенностью указанной формы. Условие (7) в самом 'деле означает неотрицательность этой формы на сопровождающем подпространстве П(Л ). А условие (9) гарантирует лишь то, что для каждого фиксированного Ь е К(и) найдется своя точка Л = Л(6) Е Л,(и),)Л(6)) = 1, для которой значение квадратичной формы (С (и, Л )Ь, 6) > О, что вовсе не исключает того, что в какой-либо другой точке Ь е К(и) значение той же формы будет <О.
Как увидим' ниже на примерах, бывают, конечно, случаи, когда максимум в (9) достигается в одной и той же точке Л при всех Ь е К(и), и для такого Л квадратичная форма (с". (и, Л )Ь, 6) в самом деле будет неотрицательной на К(и). На примерах мы также увидим, что такого универсального Л, не зависящего от Ь, может и не существовать. Заметим также, что условие (8) непустоты конуса Л„и) вовсе не вытекает из условия Л(и) ф !с1 и весьма содержательно. 4 осмотрим, во что превращается теорема 2, когда и — нормальная точка множества (1). Тогда, как было выяснено выше, конус Лагранжа Л(и) = = (Л = Л,(1, р), Лв > 0) — открытый луч с направляющим вектором (1, р) где р — решение системы (2) при Л„= 1.
Согласно теореме 2 конус Л (и) ф фИ. Отсюда и из включения Л (и) с Л(и) следует, что Л.(и) =Л(и). Далее, в нормальной точке и конус !сег С'(и) является подпространством в' Е" размерности и-в >О. С другой сторонй, сопровождаюсцее подпространство П(Л) точки Л Е Л„(и) в силу (5), (6) имеет размерность с!1ш П(Л ) > и — в, и П(Л) С 1сег С'(и).
Следовательно, П(Л ) = 1сег С'(и) 1УЛ ЕЛ„(и), т. е. все точки Л е Л„(и) обладают одним и тем же сопровождающим подпространством, совпадасощим с (сег С'(и). Кроме того, в рассматриваемой задаче Еег С'(и) = = К(и), и условие (7) означает, что (с".„(и, Л)6, 6) > 0 ЧЬ Е П(Л) = К(и) 73 4 4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 72 Гв. 2, КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА и ЧЛ е Л.(е) = А(е).
Отсюда следует, что условие (9) в нормальной точке е совпадает с условием (7), так как множество (Л е А,(е), ) Л) = 1) состоит из единственной точки и знак максимума в (9) можно опустить. Таким образом, если точка локального минимума е функции >"(х) на множестве (1) является нормальной точкой этого множества, то теорема 2 превращается в теорему 1.
Теперь рассмотрим другую крайность, когда е — точка локального минимума, является анормальной точкой множества (1), и, более того„пусть д,'(е) =... = д,'(е) = О. Тогда конус кег С'(е) = Е", и условие (6) тривиально выполняется для всех Л е А,(е). Для истолкования условий (5), (7) здесь удобно воспользоваться понятием индекса квадратичной формы. Как известно из линейной алгебры 1192; 213; 349; 351; 353), всякая квадратичная форма (Ах, х) с помощью невырожденного линейного преобразования может быть приведена к каноническому (диагональному) виду, причем число положительных, число отрицательных и число нулевых членов в канонической форме не зависит от способа приведения (закон инерции квадратичных форм).
Поэтому имеет смысл Определение 4. Число полохсительных членов в каноническом виде квадратичной формы (Ах, х) называется положительным индексом этой формы, число отрицательных членов — отрицательным индексом. Если при приведении квадратичной формы (Ах, х) к каноническому виду используются лишь ортогональные преобразования, то коэффициенты канонического вида квадратичной формы совпадают с собственными числами матрицы А, причем положительный индекс этой формы равен числу положительных собственных чисел матрицы А, отрицательный индекс — числу отрицательных собственных чисел этой матрицы (с учетом их кратности).
Ниже нас будет интересовать лишь отрицательный индекс, и мы его для краткости будем называть просто индексом квадратичной формы. Можно доказать, что индекс квадратичной формы совпадает с размерностью максимального подпространства Х пространства Е", на котором форма (Ах, х) отрицательна, т: е.
(Ах, х) < 0 тх е Ь, х ф О, или еще иначе, индекс формы равен коразмерности максимального подпространства 5~, на котором форма неотрицательно определена. Напомним, что коразмерность подпространства Ь~, по определению, есть число (и-йш Ь~) )192; 213; 349; 353). Отсюда и йз (5), (?) получаем содержательное утверждение: если 0 < в < < и и кег С'(е) = Е" в анормальной точке е локального минимума функции у'(х) на множестве(1) индекс квадратичной формы (л,„,(е, Л)Ь, Ь) не превышает в при всех Л ЕЛ.(е), или, иначе говоря, количество отрицательных собственных чисел матрицы л, (е, Л') не превышает в при УЛ е Л,(е).
В общем случае, когда в анормальной точке подпространство кег С'(е) ф Е", можно показать, что количество отрицательных собственных чисел матрицы Р(е)С (и, Л)Р(е) не Превышает в — гапд(д,'(»),..., д,'(е)), где Р(е)— матрица оператора проектирования пространства Е" на подпространство кег С'(»), гана(д,'(е),..., д,'(е)) обозначает ранг матрицы, столбцами которой явля>отея векторы д,'(е),..., д,'(е). Заметим, что Р(»)С„.(е, Л)Р(е)— симметричная матрица, так как симметричны матрицы Р(е), С,„(е, Л), 3 а м е ч а н и е 1. Учитывая, что всякая точка локального максимума функции у(х) на множестве Х является точкой локаяьного минимума функции ( — ?(х)) на том же множестве, из теорем 1,2 нетрудно получить необходимые условия второго порядка для точки локального максимума. Пред- лагаем читателю убедиться, что все утверждения теорем 1, 2 полностью сохраняются, нужно лишь конусы А(е), Л,(») заменить соответственно конусами А (е), А,(е).
Определение конуса Арутюнова А.(е) для точки е локального максимума функции 7(х) на множестве (1) получается из определения 3 заменой конуса А(») на конус А (»), в котором, в отличие от А(е), все наборы Л = (Л,..., Л,) имеют координату Лв < 0 (см.
замечание 3.1). Для иллюстрации теоремы 2 рассмотрим несколько примеров, П р и м е 3. Задача: ф~= — (х~)в — (хв)в+ (хв)в — ~1п(, х Р Х = (х = =(х', х', х ) ЕЕ>: д,(х) =х х =О, д,(х)=(х')в — (х')'=О). Эту задачу мы уже рассматривали в примере 2 и убедились, что точка» =(О, О, 0) глобального минимума является анормальной точкой множества Х и теорема 1 к нет неприменима.
Теорема 2 к этой точке, конечно, применима, и тем не менее интересно посмотреть, как конкретно устроен здесь конус А.(0), подпространства П(0) и т. п. Конус Лагранжа А(0) для точки с =О, как мы уже знаем, состоит из всех точек Л =(Лв, Л „Л,) ~ 0 с произвольными Л, > О, Л, Л,, а конус 1сег С'(0) = Е'. Покажем, что конус Арутюнова Л,(0) =А(0). В самом деле, возьмем >ГЛ е А(0) и подпространство П = (Ь = (Ь', Ь', Ь') е Е': Ь' =О, Ь'= 0). Здесь и =3, в = 2, и йгп П = 1 = 3 — 2, Пс кег С(0) = Е'. Кроме того, (й (О, Л)Ь, Ь) =2Лв(Ьв)' > 0 >>Ь еП.
Таким образом, для всех Л е Л(0) нам удалось указать одно и то же сопровождающее подпространство П. Это значит, что А.(0) = Л(0). Заметим, что для некоторых Л е Л(0) можно указать и другие сопровождающие подпространства. Например, для Л,=(0, 1, 0) квадратичная форма (С (О, Л,)Ь, Ь)=Л,Ь'Ь'>О для всех Ь е е П=П(Л )=(Ь=(Ь', Ь', Ьв): Ь'=уЬ>) с >>'у > О. Ясно, что йпт П(Л,)=2 >1 и все свонства (5) — (7) выполнены. Нетрудно проверить, что индекс квадратичной формы (й„,(0, Л ) Ь, Ь) при всех Л ~ А„(0), как и положено по теореме 2, не превышает 2, причем для некоторых Л, например, для Л,=(0, 1, 0) этот индекс равен 1, для Л,=(1, О, 0) индекс равен 2. Теперь обратимся к условию (9). Здесь (с (О Л)Ь Ь) 2Л ( (У1)в (Ьв)г+(Ьв)в)+2Л Ь~Ь>+2Л ((Ь~)г (Ьв)г) В примере 2 было показано, что условие (л, (О, Л ) Ь, Ь) > 0 УЬ е К(0) = Е' не может выполняться ни при каких Л е Л(0) =А (0).