Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 44
Текст из файла (страница 44)
Теорема 4. Пусть П вЂ” выпуклое множество из Е", Х(и)ш ш С'(П). Тогда для сильной выпуклости функции Х(и) на П необходимо и достаточно существования такой постоянной р > О, что <у-(и)$, $>>И[У* (13) при всех иш П и всех $ =Д', ..., З'), принадлежащих подпространству Ь = Еш П, параллельному афинной оболочке множества П (в частности, если !п1ПФИ, то (13) выполняется при всех с ~н Е") . Д о к а з а т е л ь с т в о. Для функции д(и) = з (и) — и! иР ее вторая производная равна у" (и) = Х" (и) — 2к1, где 1 — единичная матрица.
Отсюда ясно, что неравенство (13) с р = 2к равносильно неравенству <д"(и) $, $> ) 0 ч'и я П, чаек Ь. Отсюда и из леммы 1, теоремы 2.5 следует справедливость теоремы. Замечания. 1. Если !п$ПФО, то Е=Е" и условие (13) должно выполняться при всех зшЕ". Пример 2.1 показывает, что при !и! П = И условие (13) может и не выполняться при каждом $ шЕ". 2. Для функций одной переменной неравенство (13) имеет вид Х' (и)> !г>0 при всех и~и П. Отсюда нетрудно вывести, что функция 7(и)= из при любом р> 1 будет сильно выпукла на множестве Г.
= (ишЕ'. и > з) при всех е > 0; если здесь с < О, то такая функция сильно выпукла лишь при р = 2. Функция г (и) = з!и и сильно вьгпукла на П, = [ — я+ з, — з) при всех е (О < е (л/2), но не сильно выпукла на [ — и, О]. 3. Условие (13) в теореме 4 не может быть заменено условием <Х" (и)$, $>)0 вияП, 1з$еп Ь, $фО. (14) Например, для функции з'(и) = е (и ш П = Е' = Ь) имеем <У" (и)$, ~> =е"$'> 0 при всех иш П, $ ~вХ, $ФО, но эта функция не является сильно выпуклой. Однако если !и! П Ф В, Х" (и) = А = (а„) — постоянная матрица, то условие (14), означающее положительную определенность квадратичной формы ЭЛЕМЕНТЫ ВЫПУКЛОГО АН.АЛПЗА (ГЛ. 4 (Ай, $> = ~ ао)ь1Е), влечет за собой условие <Ай, 4»(4(~)о Ьз=г (3 онЕ"), где )4 = (п1 (А$, $>> О. )и=4 Как известно (93, 164), для положительной определенности квадратичной формы <Аь, з> необходимо и достаточно, чтобы все угловые миноры 11" и были положительны.
Пользуясь этим условием, для функции Х(и) = х'+ 2аху+ Ьу'+ сз' из примера 2.2 находим, что Х(н) будет сильно выпукла на Е' тогда и только тогда, когда Ь вЂ” а'> > О, с>О. Далее, для функции Х(и)= <Аа, и>/2 — <Ь, и>, и ~Е", из примера 2.3 сильная выпуклость на Е" будет тогда и только тогда, когда А — положительно определенная матрица. Аналогично для функции Х(н) = )Ан — Ь)о яз примера 2.4 сильная выпуклость на Е" будет тогда и только тогда, когда матрица А'А — невырожденная.
3. Рассмотрим сильно выпуклые функции Х(и) из класса С" (П), т. е. гладкие сильно выпуклые функции, градиент ноторых удовлетворяет услови4о У'(и) — Е(п)) (Е(и — о), и, У~Ь(. (15) Полезно установить связь между постоянными х, )4, Е из (1), (9), (12), (13), (15). Из условия (12) с помощью неравенства Коши — Буняковского и условия (15) имеем )4 ~5. При доказательстве теорем 3, 4 было показано, что )4 = 2х. Поэтому 2н (Ь. Из определения 1 видно, что если неравенство (1) имеет место при некотором х, то оно будет иметь место и для всех меньших положительных значений к. Можно поставить вопрос об определении самой большой, точной постоянной к в (1). Очевидно, такой постоянной в (1) будет аХ (и) + (1 — а) Х (и) — Х (а и + И вЂ” а) и) х = (п1 ш1 о<и<4 и,о=о а(1 — а)(и — о) Аналогично самые болыпие постоянные в (12), (13) соответственно имеют вид <Х' (и) — Х' (и], и — и> ро — - гп1 2 и,инп ) и — и( рг = 1п1 1п1 <Х' (и) $, 4> игп $ныипл~о ) $( 187 ОПЛЬНО ВЫПУКЛЫЕ ФУНКГ11ыг Из доказательства теорем 3, 4 следует, что р,= ра = 2м„причем длн функций иэ С" (Бт) все эти постоянные не болыпе л.
Заметим, что для функции Й(и)=!и[* на Е" имеем р, =)ьг= 2ме= =1 =2. ть Продолжим рассмотрение сильно выпуклых функций 1(и) си С" ((т). Для таких функций из (12) и (15) имеем неравенства к[и — о[э ( (1'(и) — 1'(о), и — и> ( ци — о[с, и, о ем (1. (16) Оказывается, как в теореме 2.16, два неравенства (16) можно записать в виде одного равносильного (16) неравенства [29), полностью характеризующего класс спльно выпуклых функций пз С' '(Ь) с данными постоянными Ц р (Ь > (г > О). Теорема 5.
Пусть (7 — выауялое множество ив йв и 1(и) шС'((7). Тоеда для тово етобы функция 1(и) была сильно выауалой с настоянной и = р/2 > О и удовлетворяла условию (15) с настоянной Ь > О, необходимо и достаточно, чтобы [1'(и) — 1'(с) [Я+ Бр[и — о[в ( (5+ р)(1 (и) — 1 (о), и — в> (17) ари всех и, о еи (7. Доказательство. Необходимость. Пусть 1(и) шСь'(ьг) и эти функции сильно вьшуллы на бт. Тогда справедливы неравенства (16). Введем функцию у(и) = 1(и) — О[и[92, иш (7.
Имеем б'(и) = 1'(и — ри). Тогда из левого неравенства (16) следует (у' (и) — б' (о), и — о> = (1' (и) — 1' (о), и — о> — р [ и — о [в > О, ь, ° и, а из правого неравенства (16) получилг (д' (и) — у' (о), и — о) ( (Ь вЂ” р) [ и — о)э 'Уи, и ш С. Объединяя оба полученных неравенства, имеем О(((у' (и) — б'(о), и — о> ((б — р) [ и — о[Я Уи, ош (1.
Таким образом, функция д(и) удовлетворяет неравенствам вида (2Д8). Согласно теореме 2.16 этп два неравенства равносильны одному неравенству ) у' (и) у' (о) )е ((Ь вЂ” р) (у' (и) — у' (о), и — о> )(и, о ш (т. Подставляя сюда у'(и) = 1(и) — ри, после несложных тоткдественных преобразований получаем неравенство (17). Достаточность. Пусть некоторая функция 1(и) енС'(бт) и удовлетворяет неравенству (17). Покажем, что тогда функция 1(и) сильно выпукла с постоянной н = р12 и удовлетворяет условию (15) с Ц где р, Ь взяты из (17).
С помощью неравенства Кошп — Буняковского из (17) имеем [1'(и) — 1'(о) [т+ бр[и — о[э ( (б+ в[1 (и) — 1'(о) [ [и — о[. Приняв х = [1'(и) — 1'(о) [, последнее неравенство можно переписать в виде х' — (Ь+ р)1и — о[х+ бр[и — о['(О. Квадратный трехчлен в левой части этого неравенства имеет корни х~ = в[и — о[, х, = Ц и — о[. Поэтому х, ( х ( хь т.
е. р) и — о[() 1' (и) — 1'(о) ) (<А [ и — о[ 1т'и, ош С,'. (18) Тогда (1'(и) — 1'(г ), и — о) ( Ц и — о[' — правое неравенство (16) получено. элементы Выпуклого АПАлтсзА !Гтв 4 Используя левое неравенство (18), из (17) имеем ил]и — е!'-(- + Еи]и — и)л < (Е+ и) (Х'(и) — Х'(и), и — а). Поделив обе части этого неравенства на Ь+ и ) О, придем к левому неравенству (!6).
Такилс образом, из (17) получили неравенства (18) и (16). Левое неравенство (16) согласно теореме 3 означает сильную выпуклость 1(и) с постоянной к = = и(2, а правое неравенство (16) (или (18) ) дает условие (15). Из (17) вытекает неравенство 1 Еи (Х (и] Х (а), е — о) < 4 (5+ )л) ] и — о] — т „] и — и]з Ыи,а, ош(У. Опо доказывается так же, нак и подобное неравенство (2.20). Упражнения.
1. При каких а, Ь, с функция 1(и) = ахт+ 25ху+ + су' переменных и = (х, у) ш Е' будет сильна выпукла на Ет) 2. Найти области сильной выпуклости функций 1(и) = з!п(х+ у+ л), 1(и) = з!п(х'+ у'+ лл). 3. Можяо ли утверждать, что сплыло выпуклая функцяя обладает более лучшими дифференциальными свойствами па сравнению с выпуклыми функциями? Рассмотреть функцию У(и) = (и, и)+у(и), где у(и) — выпунлал функции. 4. Доказать, что функция Х(и) сильно выпукла на выпуклом множестве П тогда и только тогда, когда функция д(с) 1(а + с(и — а)) переменной с (О < с < 1) является сильяо выпуклой на [О, 1] с одной и той же для всех и, аж П постоянной сильной выпуклости. 5. Пусть функция У(и) сильно выпукла и дифференцпруема на выпуклом множестве (У.
Доказать, что: а) 1'(и) Ф 1'(а) (и, и = (У, и Ф а); 1 б) ] и — е(( — ] Х' (е) ]л при всех и сп АУ(и) = (и ш (У: У(и) < 1(и)), а ш (У; 1 1 в) О<.У (и) — Х„< —, ] Х' (и) ]л, ] и — и ]( — ] Х'(и) ] (и ш (У). 6. Для того чтобы симметричная матрица А порядка п )( и была положительно определенной, необходимо и достаточно существования постоянных Уз и (О < и < Е) таких, чта ! Ае]с+ Ер] е]'((Ь+ Сл) (Ае, е) Ые ш Е".
Доказать. Убедиться, что в приведеннолс неравенстве в качестве и можно взлть минимальное собственное число матрицы А, в качестве Š— максимальное собственное число. 7. Пусть (У вЂ” выпуклое множество, У(и) ли С'((С). Показать, что для того, чтобы функция Х(и) была сильно выпуклой и удовлетворяла условию (15), необходима и достаточно выполнения неравенств (18) при каких-нибудь постоянных Е, и (О ( и < Е) .
8 4. Проекция точки нн множество $. Прп описании и исследовании некоторых методов минимизации ниже нам понадобится понятие проекции точки на множество. Определение 1. Пусть УУ вЂ” некоторое множество из Е". Проекцией точки и из Е" называется ближайшая к и точка ш мноисества (у, т. е. точка и сп [У, удовлетворнющая условию ] и — и ] = лп! [ и — п [.
емп ПРОЕКЦИЯ ТОЧКИ НА МНОЖЕСТВО 5 4! 189 Проекцию точки и на множество У будем обозначать через Уо(и) = ю. Поскольку р(и, У) = (п1 !и — о! — расстояние от точки и до вао множества П, то из определения 1 следует, что р(и, П) = !и — Уо(и)/</и — о! Моя У, 4вияЕ". Если и ж Г, то, очевидно, всегда Ув(и) = и. Однако проекция на множество существует не всегда.
Например, если У=(и4и жЕ": |и! < 1) — открытый единичный шар в Е", то ни одна точка иФ П не будет иметь проекции на это множество. Однако если множество П замкнуто, то любая точка и 4н Е" имеет проекцию на П вЂ” это было доказано в следствии 1 к теореме 2.1.3. Проекция точки на множество может определяться неоднозначно В* ~Ч4 Рис.
4.6 Рвс. 4.7 (рис. 4.6). Однако, как показывает следующая теорема, для выпуклых множеств такая ситуация невозможна (рис. 4.7). Теорема 1, Пусть У вЂ” выпуклое замкнутое множество из Е". Тогда: 1) всякая точка и ж Е" имеет, и притом единственную, проекцию на зто множество; 2) для того чтобы точка ю4н У была проекцией точки и на множество Г, необходимо и достаточно выполнения неравенства (сл4. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
