XIV Аттетков и др. Методы оптимизации (1081420), страница 16
Текст из файла (страница 16)
Если же !2, > О, то Л„уЛ, Л,г л; —.р;=л,— — р,=р.;( — ' — — ) >о, Р!г Р! рв в котором хотя бы один из коэффициентов р,, отличен от нуля. Положим р! = — ~, рь Тогда с учетом равенства (З.З) получим г=2 1об 3. Л1ИЕ1ИК1ИЗАЦИЯ ВЫПУКЛЫХ ФУИКЦИЙ так как разность в скобках неотрицательна в силу выбора номера к, а и, > О.
Таким образом, в линойной комбинации (3.5) все коэффициенты неотрицательные, их сумма равна единице. Значит, эта линейная комбинация являотся выпуклой. Отметим, что в соответствии с выбором параметра о имеем Лл — оие = О. Следовательно, выпуклая комбинация (3.5) имеет не тп слвгаемь1х, а не более т — 1. Итак, представив элемент х выпуклой комбинацией из т слагаемых, мы при т > и+1 построили для х новую выпуклую комбинацию, в которой не более т — 1 слагаемых. Однако число т есть наименьшее число слагаемых в выпуклой комбинации. Полученное противоречие указывает на то, что предположение т > и+ 1 неверно.
~ 3.2. Выпуклые функции Определение 3.2. Функцию 1: й — + 2, определенную на выпуклом множестве П С 2", называют вьтуклой функцией на этом множестве, если для любых точек х1, хз Е Й и любого Л Е [О, 1) выполнено неравенство 7(Лх'+ (1 — Л)х') < ЛДх') + (1 — Л)~'(х'). (3.6) Функцию 1 нззыввлот строго выпуклой, если для любых х', хз Е П при Л Е [О, 1) и х1 ф хз выполнено строгое неравенство 7'(Лх~ + (1 — Л)хз) ( Л 7(х') + (1 — Л)7'(х~). (3.7) Понятия выпуклой (строго выпуклой) функции многих переменных на выпуклом множестве аналогично понятию выпуклой вниз (строго выпуклой вниз) в интервале функции одного переменного [1Ц. 107 2.2.
Выпуклые функции Пример 3.7. а. Выпуклой иа множестве й = Ы' является линейная функция и 1'(х) = ~~1 а х, 1=1 (3.8) где х = (х1, ..., х„), о,. Е Б' 1 = 1, н. Действительно, для произвольных точек х1 = (х~~ ), ..., х~~ ~) и хя = (х~~ ~, ..., х~~ ~) и произвольного Л Е [О, 1] имеем и 1(Лх +(1 — Л)х ) = ~~ а (Лхэ~ ~+(1 — Л)хэ~ )) = 1=! = сл ~1 о, х . ~ + (1 — сл) ) а х . ~ = сл((х ) + (1 — о)2 (х ). 1=1 1=1 ЦЛх'+ (1 — Л)х2!! < Л!!х !!+ (1 — Л) Цх !!. В частности, выпуклыми являются функции и и 11(х) 2~~ х~: У2(х) ~' ~хг~; Ь(х) алак ~х1~; г=1 л=1 ~=1,п ГДЕ Х = (Х1, ..., Хп). ЭтИ ФУНКЦИИ СООтВЕтетВУЮт СВКЛидОВОй, октаэоринеской и куби 1сской нормам в К".
Пусть функция 1: й -+ К определена на множестве 11 С лл". Множество С(1) = ((х, у) Е Б'."~' 1(х) < у) назьлвают надграфиком функции 1(х). Неравенство (3.6) равносильно утверждению, что надграфик функции является выпуклым множеством. действительно, если точки (х1, у1) и (х2, у2) принадлежат б.
Рассмотрим в лл" какую-либо норму ~~х~~. Функция 1'(х) = = (~х~~ является выпуклой на множестве 1и", поскольку для любых точек х', хз Е И" и любого числа Л Е (О, .1), согласно определению нормы, верно неравенство 108 3. МИПИ51ИЗДЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ С(1), то выполняются неравенства у(х') < у' и !'(х2) < у2. Из неравенства (3.6) заключаем, что !(Лх'+ (! — Л)х ) < Лу(х')+(! — Л)у!х~) < Лу'+ (! — Л)у2. Следовательно, точка Л(х~, у1) + (1 — Л)(х~, уэ) принадлежит надграфику функции. Наоборот, .если надграфик функции является выпуклым множеством, то вместе с точками (х1, у1) и (х, у ), где х, х Е Й, у' = 1(х ), у = 1(х ), надграфику принадлежит и их выпуклая комбинация (х, у), где х = Лх'+ + (! — Л)х, у = Лу1+ (! — Л)у . Но если точка (х, у) принадлежит надграфику функции !(х), то !(х) < у, а это равносильно неравенству (3.6). Повторяя эти рассуждения для произвольных выпуклых комбинаций и используя теорему 3.1, приходим к следующему заключению.
Теорема 3.5. Для того чтобы функция !': Й вЂ” 1 1т, определенная на, выпуклом множестве Й с Ка, была выпуклой, необходимо и достаточно., чтобы для любых элементов х' Е Й, г = 1, к, и илюбых чисел ол >О, ! =1, и, ~ ст, =1, выполнялось неравен1=1 стиве Иенсена* Аналогичное утверждение имеет место и для строго выпуклых функций. Теорема 3.6. Для того чтобы функция 1: Й вЂ” > ет, определенная на выпуклом множестве Й с Ка, была строго выпуклой, необходимо и достаточно, чтобы для любых попарно различных элементов х' е Й, 1 = 1, к, и любых чисел сн > О, г = 1, п, *И.Л, Иенсен (1859 — 1925) — — датский математик.
109 3.2. Выпуклые функции и ~; ол = 1, выполнялось строгое неравенство 'и и ~(~о,х*) ( ~ о,~(х'). Пусть Й вЂ” выпуклое множество. Выберем в Й две точки х и х и рассмотрим числовое множество Я = Я(й,х,х ) тех значений 1, для которых точка 1х + (1 — 1)х принадлежит й. Нетрудно показать, что множество Я(й,х,х ) является выпуклым подмножеством числовой прямой, т.е. промежутком. Пусть 1(х) — — произвольная функция, определенная на выпуклом множестве Й. Функцию у(~) = 1(нх'+ (1 — ~)хз) одного действительного переменного, заданную на промежутке Я(й,х',хз), будем называть сечением функции ~(х). Теорема 3.7. Для того чтобы функция у(х), определенная на выпуклом множестве Й С Кп, была выпуклой (строго выпуклой), необходимо и достаточно, чтобы любое сечение этой функции было выпуклой вниз (строго выпуклой вниз) функцией.
4 Для произвольных точек х и х в Й рассмотрим сечение ~р® = 1(гх' + (1 — 1)хз) функции 11х), представив его в виде у(г) = ) (хз+ 1р), где р = х1 — хз. Предположим, что функция у(1) определена для значений 11 и 1з, т.е. точки р = х + 1~р и уз = х~+ 1зр принадлежат Й. Тогда для произвольного Л е ~0, 1] и у=1 — Л имеем Лу + Ну = Л(хе + 11р) + р(х + Хзр) = х + (ЛХ1 + риаз)р, откуда заключаем, что д(Л' +М ) = ~Р|'+ рй').
Если функция у(х) выпукла, то ~р(Лй~ + низ) = ~(Лу + ну ) (~ Л~(у ) + д~(у ) = Л~р(1ч) + 1ир(1з). по 3. МИНИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ Так как значения 11 и 1з из области определения гр(г), а также Л Е [О, 1] можно выбирать произвольно, заключаем, что гр(1) выпукла. Допустим, что каждое сечение функции у(х) является выпуклой функцией. Тогда для произвольных точек х1 и х~ в П и любого Л Е [О, 1] имеем У(Лх'+рхз) =97(Л) =Чр(Л.1+И 0) < < Лггг(1) + 1гггг(0) = ЛУ (х ') + Р~ (х') г где р, =1 — Л.
Доказательство теоремы в случае строго выпуклой функции анажн ично. ~ Теорема 3.8. Если функции Ях), г = 1, т, определенные на выпуклом множестве г1 С ггг", являются выпуклыми на 11, то для любых чисел ен ) О, г = 1, пг функция )(х) = ~~ аг1г(х), х е гг, г=1 (3.9) ~(Лх'+ (1 — Л)х ) < ЛЯх')+(1 — Л)Л(х~), г =1, ик (3 10) Умножая эти неравенства на неотрицательные числа аг и скла- дывая, получаем у(Лх +(1 — Л)хз) =~~ о;Д(Лх'+(1 — Л)хз) <ЛЯа;Х,(х')+ г=1 г=1 ггг + (1 — Л) ~~ агат(х ) = Л~(х') + (1 — Л)~(х~). (3.11) г=1 выпукла на множестве 11.
Если к тому же одна из функций ),(х) строго выпукла, а соответствующее этой функции число а, положительно, то функция у(х) строго выпукла. м Поскольку все функции Ях) выпуклы, в силу определения выпуклости для любых точек х', х~ е 11 и любого Л Е [О, 1] выполнены неравенства л.2. Выпуклые функции Тем самым доказано, что функция ~(ж) является выпуклой на множестве Й. Если функции 7",(х) являются выпуклыми на Й, причем среди них хотя бы одна функция строго выпукла на Й, то при .в1 ф- х2 и Л Е (О, 1) хотя бы одно из неравенств (3.10) является строгим.
В этом случае в (3.11) неравенство является строгим, а функция 1(т) строго выпуклой. ~ Следствие 3.1. Сумма выпуклой (строго выпуклой) и линейной функций является выпуклой (строго выпуклой) функцией. ~ Согласно примеру 3.7, линейная функция является выпуклой в Ю', а значит, и на любом выпуклом множестве. В силу теоремы 3.8 сумма линейной и выпуклой функций, как сумма двух выпуклых функций, является выпуклой. Аналогично сумма строго выпуклой и линейной функций является строго выпуклой. ~ Теорема 3.9.
Если у(х) выпуклая функция на выпуклом множестве Й ~ К", а 6(г) — выпуклая неубывающая функция одного действительного переменного, определенная, по крайней мере, на множестве ~р(Й), то сложная функция ф(ж) = 6(~р(в)) является выпуклой на множестве Й. Если к тому же ~р(ж) - строго выпуклая функция., а функция 6(с) возрастающая на множестве К, то функция ф(ж) строго выпукла на множестве Й. ~ Для произвольных точек ж1 и хз из Й и любого числа Л Е (О, 1) имеем Ф(Лж + (1 — Л)ж ) = 6(97(ЛХ + (1 — Л)ж )) ( ( 6(Л~р(х') + (1 — Л)~р(ад)) < Л6(~р(ж~)) + + (1 — Л)6(у(хз)) = Лф(х')+ (1 — Л)ф(жз) (3 12) В этой цепочке соотношений первое неравенство справедливо, поскольку функция 6(~) неубывающая, а функция ~р(т) выпуклая.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
