XIV Аттетков и др. Методы оптимизации (1081420), страница 18
Текст из файла (страница 18)
Подставляя найденные выражения для производных в неравенства (3.21), получаем неравенства (3.20). "Дифференцируемость функции в какой-либо граничной точке множества й предполагает, что функция определена в некоторой окрестности этой точки. 118 3. МИНИЛ1ИЗЛЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ Д о с т а т о ч н о с т ь. Пусть для произвольных точек х ~ и х~ множества Й выполняются неравенства (3.20). Возьмем произвольные точки у, у Е Й и рассмотрим соответствующее сечение ф(1) = ~(1у'+ (1 — с)ув). Выберем произвольные значения Рс и 1з из области определения ф(1).
Точки х' = Цус + (1 — 1с)уз, г = 1,2, принадлежат Й, и для них выполняются неравенства (3.20). Из равенств (3.22) при 1 = Р~ и 1з получаем ~'(1с) = (8гас1~(х'), у' — у ), г = 1, 2. Поскольку Ь = х — х~ = (~з — ~с)(у~ — у ), го (8гас11(х'), Ь) = (8гасс~(х'), у — у ) (сз — сч) = = ф'(1,)(1з — 1с). 1 = 1, 2, и неравенства (3.20) равносильны следующим: ~Ф сс1в~8з — Р~) К 'асс:з) 'фссГ~) ~ Ф ссра) сс'з — 1с) Значения ~с и 12 из области определения ф(1) выбирались произвольно. Следовательно. функция сд(с) является выпуклой. Итак, мы показали, что при выполнении неравенств (3.20) любое сечение дифференцируемой функции )'(х) является выпуклой функцией. Значит, согласно теореме 3.7, 1(х) выпуклая функция на Й.
~ Замечание 3.1. Повторяя ход доказательства теоремы 3.11, несложно установить, что для строгой выпуклости функции 1(х), х Е Й., непрерывно дифференцируемой на выпуклом множестве Й С ~", необходимо и достаточно, чтобы для любых двух различных точек х~, х~ е Й было выполнено неравенство (8тас17'1х~), Ь) ( ~(х') — 1(х~) ( (дгас1~(х'), .Ь). ~с (3.23) Проверить выпуклость или строгую выпуклость функции ~(х) с помощью критериев (3.20) и (3.23) можно, но практически довольно сложно. Задача упрощается, если функция 1(х) 3.3. Дифференцируемые выпуклые функции 119 дважды дифференцируема. В этом случае ответ можно получить, исследуя матрицу Гессе функции 11х). Напомним, что симметрическую матрицу А называют положите,льне (отрицательно) определенной, если она является матрицей положительно (отрицательно) определенной квадратичной формы 1эту квадратичную форму можно записать в виде х Ах, где х Е кч" --- вектор-столбец, или с помощью стандартного скалярного произведения в виде (Ах, х)).
Введем аналогичные понятия неогприцагпельно ( неполоэсигпельно) определенной матрицы как матрицы неотрицательно 1неположительно) определенной квадратичной формы, а также энанонеопределенной матприл4ы как матрицы знаконеопределенной квадратичной формы. Сначала рассмотрим одномерный случай. Как уже было отмечено, критерием выпуклости функции ~р11) одного переменного является неубывание ее производной. Если функция ~р(1) дважды дифференцируема, то из условия неубывания ~р'(й) вытекает, что ~р~'(~) неотрицательна.
Верно и противоположное утверждение. Если рп(в) > О, то функция р'(1) не убывает, а функпия ~р1ь') выпукла. Теорема 3.12. Для того чтобы дважды дифференцируемзя на открытом выпуклом множестве Й С К" функция 3'1х) была выпуклой, необходимо и достаточно, чтобы ее матрица Гессе Н(х) была неотрицательно определена в любой точке х Е й. ~ Необходимость. Выберем в й две произвольные точки х и х и рассмотрим сечение р(в) = у(вх +(1 — й)х ) функции 3" (х), заданное этими точками. Функция у(1) определена в окрестности точки 0 1при й = 0), так как функция 3 (х) определена в окрестности точки х~. Как сложная функция, ~р® дважды дифференцируема при 1 = О, и ~р 10) = 1Н1хз)п, й), где й = х~ — хз. Если функция 11х) выпукла на 1), то ее сечение ~е(1) является выпуклой функцией одного переменного. 120 3.
Л1ИЕ1ИЛ1ИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ Поэтому ~рл(0) > О. В силу произвольного выбора х' и х~ за- ключаем, что (Н(х )Ь, 6) > 0 для любого вектора й Е х;". По это и означает, что матрица Гессе Н(х ) в произвольной точке х Е Й неотрицательно определена. Достаточность. Пусть матрица Гессе Н(х) неотрицательно определена в каждой точке х Е Й, т.е. (Н(х)й, Ь) > О, Ь б -ч". Выберем произвольные точки х', хз Е Й и соответствующее им сечение у(1) = 1'(1х' + (1 — 1) хз). Так как ул(1) = (Н(х)6, Ь), где х = 1х' + (1 — 1)х~, а Ь = х' — х~, для всех значений 1 из области определения ~р(1) выполняется неравенство ~р"(1) > О. Следовательно, функция ~р(1) выпукла, а в силу теоремы 3.7 выпукла и функция 1(х).
~ Замечание 3.2. Можно было бы предположить, что критерием строгой выпуклости на множестве Й дважды дифференцируемой функции является положительная определенность в Й ее матрицы Гессе. Действительно, нетрудно показать, что, как и в теореме 3.12., положительная определенность матрицы 1"ессе на всем множестве является достаточным условием строгой выпуклости.
Однако это условие не является необходимым. Соответствующий контрпример можно привести уже в одномерном случае. Функция у = х строго выпуклая, однако ее вторая производная р" = 12хз обращается в нуль в точке х = О. Аналогичный пример можно построить при любой размерности. Так, в двумерном случае функция 1(х1, хз) = х~1 + х~з является строго выпуклой в К~, но ее матрица Гессе в точке (О, 0) является нулевой.
7Г 3.3. Диффереицируеыые выпуклые функции 121 Проверку свойств матрицы Гессе можно строить на основе ее собственных значений. Для неотрицательно определенной матрицы все собственные значения неотрипательны, а для положительно определенной матрицы все собственные значения положительны [1У]. Для проверки положительной определенности матрицы Гессе можно также использовать критерий Сильвестра. Если функция является квадратичной, то элементы матрицы Гессе этой функции постоянны. В этом случае проверка выпуклости или строгой выпуклости такой функции существенно упрощается. Пример 3.10. Проверим, является ли выпуклой квадратичнаа фУнкциЯ 1'(хм ха) = Зх~1 — 4х1хз + 2хзэ+ х~ — 2хя. Найдем матрицу Гессе этой функции: Угловые (или главные) миноры этой матрицы положительны: Ь1=6>0 и Ьз=де1Н=6 4 — ( — 4) ( — 4)=8>0.
Поэтому, согласно критерию Сильвестра, матрица Н положительно определенная, и в соответствии с замечанием 3.2 рассматриваемая функция строго вь1пуклая. Проверка положительной определенности матрицы небольшого размера (второго или третьего порядков) с помощью критерия Сильвестра, как правило, проще, чем аналогичная проверка путем анализа собственных значений. Вполне естественно в таких ситуациях исследование на неотрицательную определенность 1если матрица не является положительно определенной) также проводить без вычисления собственных значений.
Существует критерий неотрицательной определенности матрицы, аналогичный критерию Сильвестра. Минор матрицы А назовем диаеональным минором, если строки и столбцы, входящие в этот минор, имеют одинаковые номера. 122 3. МИНИМИЗАЦИЯ ВЪ1ПУКЯЪ|Х ФУНКЦИЙ Теорема 3.13. Необходимым и достаточным условием неотрицательной определенности симметрической матрицы является неотрицательность ее диагональных миноров.
~ Пусть А — симметрическая неотрицательно определенная матрица, т.е. (Ах, х) > О, х Е К". Рассмотрим квадратичную форму Ях) = (Ах, х) + с(х, х) = ((А+ е1)х, х), где 1 — единичная матрица соответствующего порядка, а с>0 параметр. Ясно, что );(х) — «(Ах,х) при с — «+О. Для любого числа с > 0 квадратичная форма 1, и ее матрица А+ а1 являются положительно определенными, так как при х у'= О 1г. (х) = (Ах, х) + с)(х)! > с))х)!' > О. Любой диагональный минор матрицы А + а1 путем изменения номеров ее пар строк и столбцов можно превратить в ее угловой минор. Такое изменение соответствует изменению порядка переменных квадратичной формы и сохраняет условие положительной определенности квадратичной формы и матрицы.
В силу критерия Сильвестра заключаем, что диагональные (не только угловые) миноры матрицы А+ е1 положительны. При с — «+О все миноры матрицы А+ с1 стремятся к соответствующим минорам матрицы А. Значит, все диагональные миноры неотрицательно определенной матрицы А неотрицательны. Теперь предположим, что все диагональные миноры матрицы А неотрицательны. Можно показать, что определитель матрицы А+ с1 есть многочлен от переменного с, причем старший коэффициент этого многочлена (при степени св) равен единице, а коэффициент многочлена при степени с~, .й = О, и — 1, сумме всех диагональных миноров матрицы А порядка и — й. Так как все диагональные миноры матрицы А неотрицательны, то и коэффициенты многочлена неотрицательны. Следовательно, Ое$(а+ е1) > 0 при с > О. Сказанное относится не только к самой матрице А, но и к любому ее диагональному минору: диагональный минор 3.3.
Диффереицируеыые выпуклые функции 123 Рь + с1ь (1ь — единичная матрица порядка к) матрицы А+ с1 порядка й есть многочлен переменного с степени Й, причем старший коэффициент многочлена равен единице, а остальные коэффициенты равны сумме диагональных миноров матрицы А соответствующего порядка, входящих в минор Рь, и, следовательно, неотрицательны.
Это означает, что минор Рь+с1 при с > О является положительным. Итак, у матрицы А+ с1 при с > О все диагональные (в том числе и угловые) миноры положительны. Согласно критерию Сильвестра, матрица А+ с1 является положительно определенной. Отсюда вытекает, что квадратичная форма 1е1.в) = = (Ат, ж) с матрицей А+ с1 при с > О положительно определена, т.е.
1е(ж) > О, если ж у. -О. Но тогда для квадратичной формы ~(з) = (Ах, х) при любом векторе х Е 1к", щ ф О, имеем 1"(ж) = !пп )',(:и) > О, -ео ' а это означает, что квадратичная форма у,в и ее матрица А являются неотрицательно определенными. > Исследование симметрической матрицы А на неотрицательную или положительную определенность рационально начинать с вычисления ее определителя <1есА. Если Не1А = О и диагональные элементы матрицы А неотрицательны, то можно рассчитывать на неотрицательную определенность матрицы А. В этом случае проверяются диагональные миноры, причем проверку диагональных миноров на знак можно прекратить, как только один из них окажется отрицательным.
Это будет означать, что матрица знаконеопределенная. Если с!е1 А > О и все диагональные элементы матрицы А положительны, то можно ожидать, что эта матрица положительно определена. Поэтому следует проверить на знак все угловые миноры матрицы. Проверку можно прекратить, как только очередной угловой минор окажется отрицательным, что означает знаконеопределенность матрицы. Если очередной угловой 124 3, зз1ИИИМИЗАИИИ ВЫИУ1зЛ1з1л' ФУИИИИЙ минор окажется нулевым, то матрица не будет положительно определенной, и в этом случае следует перейти к проверке всех диагональных миноров, чтобы определить, является ли матри- ца неотрицательно определенной. Пример 3.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
