XIV Аттетков и др. Методы оптимизации (1081420), страница 17
Текст из файла (страница 17)
Второе неравенство справедливо в силу выпуклости 112 Х МИНИМИЗЛЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ функции 6(г). Эти неравенства показывают, что функция ф(х) является выпуклой на множестве Й. Если дополнительно функция 6® возрастает, а функция ~р(х) строго выпукла, то при х1 ф- х~ и о Е (О, 1) в соотношениях (3.12) первое неравенство является строгим, а это означает, что функция ф(х) в этом случае будет строго выпуклой на множестве Й. ~ Пример 3.8. Функция е' является возрастающей и строго выпуклой на множестве Б', Поэтому если функция у(х), определенная на выпуклом множестве Й С К", является выпуклой (строго выпуклой), то и функция ед'~ также является выпуклой (строго выпуклой) на Й. Из примера 3.8 вытекает следующее достаточное условие выпуклости (строгой выпуклости) функции многих переменных: если функция д(х) на выпуклом множестве Й принимает только положительные значения, то для ее выпуклости (строгой выпуклости) достаточно, чтобы выпуклой (строго выпуклой) была функция 1пд(х).
Согласно примеру 3.7, выпуклой является линейная функция, определяемая равенством (3.8). Поэтому функция (3.13) где х = (хм ..., х„), а ехр(1) = е~ экспоненциэльная функция, также является выпуклой. Обратим внимание на то, что функция у(х) не является строго выпуклой, так как она на любой гиперплоскости а1х1+...
+ аох = с принимает постоянные значения. Это говорит о том,что во втором утверждении теоремы 3.9 условие строгой выпуклости 1(х) нельзя заменить условием строгой выпуклости 6(Р). Теорема 3.9 допускает обобщение. Введем для векторов х = = (хм ..., х„) и у = (ум ..., у„) обозначение х ( у (векторное 113 л.2. Вынуклые функции неравенство), если выполняются неравенства х,, < у,, 1 = 1, и.
Как обычно., строгое неравенство х < у означает, что х < у и х ~ у, т.е. хотя бы одно из неравенств х, < у„1 = 1, и, является строгим. Теорема 3.10. Если ~р;(х), г = 1, гп„— выпуклые функции на выпуклом множестве Й С И'."', а 6(у) — скалярная функция многих переменных, выпуклая на множестве ек~ и неубывающая по каждому своему аргументу, то сложная функция ф(х) = 6(Ф~ (х),..., р~(х)) является выпуклой на множестве Й, Если к тому же хотя бы одна из функций ~р,(х), г = 1, ги, строго выпукла на множестве Й с К"', а функция 6(у) возрастает по каждому своему аргументу, то функция ф(х) является строго выпуклой на Й. ~ Рассмотрим векторную функцию многих переменных р(х) = = (~р1(х), ..., ~р~(х)).
Тогда ф(х) = 6(~р(х)), а для функции р(х) при любых х1, хз е Й и Л Е (О., Ц выполняется векторное неравенство ц>(лх~ + (1 — Л)х~) < Л~р(х~) + (1 — Л)~р(х~), (3.14) каждая составляющая которого означает выпуклость соответствующей координатной функции д,(х) векторной функции ~р(х). Условие неубывания функции 6(у) по каждому аргументу означает, что 6(у1) < 6(у~) при у1 < у~. С учетом этих соображений цепочка соотношений (3.12) из доказательства предыдущей теоремы воспроизводится практически без изменений.
Действительно, для любых х1, хв е Й и Л е (О, 1) имеем ф(л '+(1 — л), ') =6(р(л '+(1 — л) ')) < < 6(л~р(х') + (1 — Л)~р(х~)) < Л6(~р(х')) + + (1 — Л)6(р(х~)) = Л4 (х') + (1 — Л) ф(хз). (3.15) Дополнительное условие строгой выпуклости одной из функций р,,(х) означает, что при х' ф хз и Л е (О, 1) векторное неравенство (3.14) становится строгим. А дополнительное усло- 114 3. МИНИгМИЗАЦИН ВЫПУКЛЫХ ФУНКЦИЙ Пример 3.9. Рассмотрим функцию ГДЕ Х = (Х1, ..., Хп) Е ггг,""; ап Е К, 1 = 1, т, У' = 17 и; С, ) О, 1 = — 1, 771.
Эта функция определена на всем линейном простран- стве Кп. Представим ее в виде Пг, гр(х) = ~ ~с;гр,(х), (3.16) г=1 где грг (Х) ехр ( ! ОгзХ7) 1=1 (3.17) Каждая из функций гр,(х) является выпуклой на множестве йп (см. пример 3.8). Поэтому, согласно теореме 3.8, функция 7Р(х) также выпукла на 1к". Если т < и, то функция ф(х) не является строго выпуклой, так как она постоянна на каждом аффинном многообразии, определяемом системой уравнений 011Х! + 012Х2 + ..
° + и1ПХП вЂ” б1 и2! х! + О22х2 + .. ° + огп хп = б2, а7п1Х1 + игп2Х2 + + игппхгг бггг~ где б1, ..., б — некоторые числа, которые всегда можно подобрать так, что эта система будет совместной. Рассмотрим случай т = п и предположим, что матрица А записанной системы вне возрастания 6(у) по каждому аргументу означает, что 6(у') < 6(у2) Прн у' < у2. ПОЭтОМу, КаК И В тЕОрЕМЕ 3.97 Этн два дополнительных условия гарантируют, что в соотношени,ях (3.15) первое неравенство будет строгим., а сложная функция гр(х) — строго выпуклой, ь 115 3.2, Выиуклыв функции уравнений является невырожденной. Тогда систему равенств д! = амж! + а12Х2 +... + а1н.Г„. д2 = Н21ж1 + О22т2 + + Н2пжн~ д~ — О~! и! + О~2 т2 +...
+ вин тн можно трактовать как замену старых координат и1, ...., ти новыми координатами д1....., д„. В новом базисе функция !!!!ж) имеет вид !д1у) = с1е"'+с е"'+... +с„ед" Выберем в Кн произвольным образом несовпадающие точки у' = (д~', ..., дб~), г = 1, 2, заданные своими координатами в новом базисе. Тогда для произвольного Л Е !О, 1) и р = 1 — Л с учетом выпуклости экспоненциальной функции ехр1ж) = ел имеем и ф~Лд'+дд ) =~с,ехр!Лд +дд~ ) ( 1=1 н ( ~ с,1Лехр1д, ) + рехр(д; )) = 1.=1 и и = Л~~ с,ехр!д, ) +д~ с,ехр!д; ) = Л!д!у ) +ддн',у ). !3.18) 1=1 1=1 Так как у' ф у, то для некоторого номера 1 выполняется неравенство д, ~ д, В силу строгой выпуклости экспоненциальной функции для указанного номера г выполняется строгое неравенство ехр!Лу,ц+рд, ~1) ( Лехр1д1П)+!2ехр(д~ 1).
Поэтому в соотношениях !3.18) неравенство является строгим, а функция ф(у) строго выпуклой. Если и! > и и ранг матрицы А равен и, то в представлении функции !н1а) можно выделить н слагаемых, отвечающих 116 З. МИНИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ базисным строкам матрицы А и в сумме дающих строго выпуклую функцию. Следовательно, в этом случае ф(ж), как сумма строго выпуклой функции и нескольких выпуклых функций, является строго выпуклой. З.З. Дифференцируемые выпуклые функции Дифференцируемость функции позволяет сформулировать простые признаки, с помощью которых можно выяснить, является ли она выпуклой функцией. Напомним [Н], что дифференцируемая на промежутке (а, 6) действительная функция 6(й) одного действительного переменного является выпуклой (строго выпуклой) на (а,, 6) тогда и только тогда, когда ее производная 6'(й) на этом промежутке не убывает (возрастает).
Отсюда с помощью формулы конечных прирвацений легко заключить, что для выпуклой функции 6(1) при любых 11 и 82, а < 81 < ~2 < 6, выполняется двойное неравенство 6 (с1нс2 — с1) < 6(с2) — 6(с1) < 6 (12пс2 — й~). (3.19) Действительно, в силу формулы конечных приращений 6(12)— — 6(21) = 6'(С)(~2 — Р~), где С е (Р~,22), а в силу выпуклости ф1'нкции 6 (с1) ~ (6 (С) ~ (И (с2). Двойное неравенство (3.19) является не только необходимым условием выпуклости функции 6(у), но и достаточным, поскольку из него вытекает неравенство 6'(с1) < 6'(12), означающее, что производная функции 6(й) не убывает. Соотношения (3.19) записаны в предположении, что 11 < 12.
Однако это требование не существенно. В самом деле, умножим неравенства (3.19) на число — 1. В результате придем к эквивалентным неравенствам 6 (~2)(~1 ~2) ~ ~6(11) 6(12) ( 6 (~!)(~1 ~2)~ которые сводятся к (3.19), если в них поменять местами ~~ и 12.
3.3. Дифференцируемые выпуклые функции 117 Нетрудно показать, что замена неравенств (3.19) строгими неравенствами дает критерий строгой выпуклости дифференцируемой функции 6(т). Критерий (3.19) выпуклости функции одного переменного не лучше традиционного критерия монотонности производной, но обладает важным преимуществом: его можно обобщить на случай функции многих переменных. Теорема 3.11. Пусть скалярная функция 1'(х) дифференцируема" на выпуклом множестве й С Р'. Тогда для выпуклости функции 1(х) на й необходимо и достаточно,.
чтобы для л~обых двух точек х1, х~ б й было выполнено неравенство (11гас11(х~), Ь) < 11х1) — ~(х~) < (уат1~(х1), Ь), (3.20) где Ь = х — х и дгао7'1х) градиент функции 11х) в точке х. ~ Необходимость. Пусть функция 1'(х) выпукла на й. Рассмотрим сечение ~р1с) = 1(йх~ + 11 — с)х~) функции Дх), заданное произвольными точками х', х Е й.
Функция ~р(г) определена и дифференцируема по крайней мере на отрезке ~0, Ц. Согласно теореме 3.7, функция д(г) выпукла на [О, Ц, а потому для нее справедливы неравенства (3.21) В силу правила дифференцирования сложной функции р'1г) = (цгас1~(х), Ь), х = 1х'+ (1 — 1)х~. (3.22) Поэтому ~р'(О) = (рас1~(хз), Ь) и ~р'(1) = (рас1~(хз), Ь).