Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 54
Текст из файла (страница 54)
замечание 2 2. 1). Пользуясь этим условием, для функции /(и) = х'+2ахд+дд'+ох' 180 Гл. 4. ЭЛЕМЕНТЫ ВЪ|ПУКЛОГО АНАЛИЗА 4 3. СИЛЬНО ВЫПУКЛЫЕ ФУНКЦИИ 181 из примера 2.2 находим, что У(и) будет сильно выпукла на Ез тогда и толь- ко тогда, когда Ь вЂ” а' > О, с > О. Далее, для функции У(и) = (Аи, и)/2 — (Ь, ы), и Е.Е", из примера 2.3 сильная выпуклость на Е" будет тогда и только тогда, когда А — положительно определенная матрица. Аналогично для функции У(и) = !Аи — Ь!т из примера 2.4 сильная выпуклость на Е будет тогда и только тогда, когда матрица А тА — невырожденная.
3. Рассмотрим теперь сильно выпуклые функции У(х) из класса С" (Х), т. е. гладкие сильно выпуклые функции, градиент которых удовлетворяет условию !У'(и) — У'(и)! < Х !и — з), и, и Е Х. (15) Полезно установить связь между постоянными х, )ь, Ь из (1), (9), (12), (13), (15). Из условия (12) с помощью неравенства Коши — Буняковского и усло- вия (15) имеем )г < Ь. При доказательстве теорем 3, 4 было установлено, что (г = х. Поэтому х < Ь.
Из определения 1 видно, что если неравенство (1) имеет место при неко- тором х, то оно будет иметь место и для всех меньших положительных значений х.Можно поставить вопрос об определении самой большой, точ- ной постоянной х в (1). Очевидно, такой постоянной в (1) будет аУ и + 1 — а У е — аи+ 1 — а з х = !и! [и! г О<зч! ю,\ ех а(1 — а)[и — е! У2 Аналогично самые большие постоянные в (12), (13) соответственно имеют вид [и , )г! = [и [и — — гъжг г з,ззх еех |еыьх сто Из доказательства теорем 3, 4 следует, что ро =)г, = хо, причем для функций из С" (Х~ все эти постоянные не больше Ь. Заметим, что для функции П(х) = )х! на Я" имеем )т =)ь! = хо = Ь = 2.
4. Продолжим рассмотрение сильна выпуклых функций У(х) е С ' (Х). Для таких функций 1,1 из (12) и (15) имеем неравенства р[и — е[з < (У~(и) — У'(е), и — е) < ь[и — е[, и, э е х. (16) Оказывается, как в теореме 2.16, два неравенства (16) можно записать в виде одного равносильного (16) неравенства [24; 234; 525[, полностью характеризующего класс сильно выпуклых функций из сь (х) при !п! х т' и с данными постоянными ь, и, ь > и > О, Теорема 5.
Пусть Х вЂ” выпуклое мнокггстго иэ Е", !и! Х та Ег и У(х) е С'(Х). Тогда для того чтобы дгункция У(х) была сильно выпуклой с постоянной к = и > 0 и удовлетворяла условию (15) с постоянной Ь >О, необходима и достаточно, чтобы [У(и) -У(з!'+ Ь~ [и- е!' < (Ь + р)(У(и) -У(з), и- е) (17) при всех и, ю е Х. Докавательство. Необходимость. Пусть фуннция У(х) е С!''(Х) и сильно выпукла на Х. Тогда справедливы неравенства (16). Введем функцию д(и) = У(и) — и!и[а/2, и е х. Имеем д'(и) = У'(и) — ди, Тогда из левого неравенства (!6) следует (д'(и) — д'(ю), и — з) = (У'(и) — У'(ю), и — е) — у[и — е! В >О, Уи, е Е Х, а из правого неравенства (16) получим (д'(и) — д (з), и — е) < (Ь вЂ” И)[и — е[з 'ти, е е Х.
Объединяя оба полученных неравенства, имеем 0((д (и) — д (е) и — е) ((Ь вЂ” М)[и — е[з Чи ю Е Х Таким образом, функция д(и) удовлетворяет неравенствам вида (2.18). Согласно теореме 2.16 эти дза неравенства равносильны одному неравенству !д'(и) — дг(е)!з < (ь — р)(д'(и) — дг(ю), и — ю) Ущ е е х. Подставляя сюда д" и) = У (и) — ри, после несложных тождественных преобразований получаем неравенство (17). До с тат о ч н о с т ь. Пусть некоторая функция У(х) е С'(Х) и удовлетворяет неравенству (17). Покажем, что тогда функция У(х) сильно выпукла с постоянной к = р и тдовлетворяет условию (15) с Ь, где д, Ь взяты иэ (17).
С помощью неравенства Коши — Буняковского из (17) имеем [У'(и)-У'( )!'+Ьр! — !'4(Ь+р)[У'(и) — У'(з)! !' -з! Приняв х=[У'(и)-У'(з)[, последнее неравенство можно переписать в виде х -(Ь+р)[и- 2 — э[к+ Ьи[и — е! < О. Квадратный трехчлен в левой части этого неравенства имеет корни х1 — — и[и — е[, хз — — Ци — е!. Поэтому х! < х < хз, т, е.
и[и — е! ( !У (и) — У (е)! ( Ь[и — е! Уи з е Х (18) Тогда (У'(и) — У'(з), и — е) < Ь[и — ю[з — правое неравенство (16) получено. Используя левое неравенство (18), из (17) имеем и [и-е! +Ьр[и — е! < (Ь+н)(У'(и)— — У'(е,и — ю). Поделив обе части этого неравенства на Ь + и > 0 придем к левому неравенству (16). Таким образом, из (17) получили неравенства (18) и (16).
Левое неравенство (16) согласно теореме 3 означает сильную выпуклость У(и) с постояннои к = р, а правое неравенство (1б) (или (18)) дает условие (15).О Из (17) вытекает неравенство (У(и) — У(е), ю — ю) ( 4(Ь + р)[и — ю!' — у+В-/и — ю! ти, е, ю е Х +д Оно доказывается так же, как и подобное неравенство (2.20). Упражнения 1. При каких а, Ь, с функция У(и) = ахз+25ху+суэ переменных и =(х, у) е Ез будет сильно выпукла на Ет? 2. Найти области сильной выпуклости функций У(и) = з!п(х+ у+ к), У(и) = з!п(х + у л ). 3. Рассмотреть функцию одной переменной !г хз(1+ июп(!п[х!)), хфО [О, х = О. При каких значениях параметра ю и на каких отрезках а < х < Ь эта функция выпукла? Строго выпукла? Сильно выпукла? Нарисуйте графин этой функции, 4. Доказать, что функция У(х) сильно выпукла на выпуклом множестве Х с постоянной сильной выпуклости к > 0 тогда и только тогда, когда функция д(г)=У(э+ !(и-е)) переменной г, 0 < ! ( 1, при любых и, е е Х сильно выпукла с постоянной сильной выпуклости к[и-з[т [364!.
5. Пусть функция У(х) сильно выпукла и дифференцируема на выпуклом множестве Х. Пользуясь теоаемами 1-5, доказать, что; з) У(и)фУ(з) чи,еех, иРе; Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 182 )Аз[я+ АМ[с]~ < (ь +в)(Ае, с) уе Е Е" и) Рис. 4.6 Рис. 4.7 (ю — и,е — ю)>0 теЕХ (ю — и, е — ю) = 0 тге й Х. (2) б) )е — е]< — „)у'(е)! при всех еЕМ(е)=(еЕХ: 1"(в)<у(е)), еЕХ; в) 0< 7(е) — А < — [у'(е)[, )и — е ] < — [7"'(е)[ Уе е Х. 8.
Для того чтобы симметричная матрица А порядка и х и была положительно определен ной, необходимо и достаточно существования постоянных о, ж 0 < и < ь, таких, что Доказать, Убедиться, что в приведенном неравенстве в качестве д можно взять минимальное собственное число матрицы А, в качестве А — максимальное собственное число. У к а з а н и е: к функции 7(х) = (Ах, х)/2 применить (17). 7. Пусть Х вЂ” выпуклое множество, 7"(х) е С (Х). Показать, что для того, чтобы функция 1 7(х) была сильно выпуклой и удовлетворяла условию (15), необходимо и достаточно выполнения неравенств (18) при каких-нибудь постоянных Тч р, 0 < М < о. 8. Можно ли утверждать, что сильно выпуклая функция обладает более лучшими диференциальными свойствами по сравнению с выпуклыми функциями? Рассмотреть функцию (х) = (х, х) + д(л), где д(х) — выпуклая функция, 9.
Пусть Х вЂ” выпуклое множество, 7"(х, х) при каждом значении параметра и Е А сильно выпукла на множестве Х с постоянной сильной выпуклости и(п), ш1 и(о) >ив >О. Докагл зать, что функция 7(х)= зпр У(х, о) сильно выпукла на Х с постоянной ио. Указание: ел воспользоваться схемой доказательства теоремы 4.2,7. 10. Функция 7(х), определенная на выпуклом множестве Х, называется сильно квазивыпдклой на Х, если существует постоянная и > О, такая, что у(хе 4 (1 — о)е) < шах(7(е);7(е)) — — п(1 — п)х]е — е] Уе, е Е Х, Уо с [О,!] 1 х 2 (ср. с упражнением 2.33).
Доказать, что: 1 а) функция д(т) = [1+ о[ сильно квааивыпукла на любом отрезке [О, с] с х = —, но не является сильно выпуклой а — па амет, об П); б) функция д(т)= (1+а) +Ь вЂ” о сильно выпунла на [О,с] с постоянной х=(Ьз— -в )(шах(д(0), д(с))) з и сильно квазивыпукла нв [О, с] с постоянной х =(гпах(д(0), д(с))) ~ (о, Ь вЂ” параметры, о Ь Е П); в)функция 7"(х)= ~х[,х ее", сильно квазивыпукла на любом ограниченном выпуклом множестве Х с постоянной х = Д, где Л вЂ” радиус шара, содержащего Х, и не является сильно 1 квазивыпуклой на неограниченном множестве Х.
Функция 7"(х) = [х] не является сильно выпуклой ни на каком выпуклом множестве Х с 1п1 Х Ф Я [364]. й 4. Проекция точки на множество 1. При описании и исследовании некоторых методов минимизации ниже нам понадобится понятие проекции точки на множество. О и р е д е л е н и е 1. Пусть Х вЂ” некоторое множество из Е". )Трогкцией точки и из Е называется ближайшая к и точка ю множества Х, т. е. точка ю е Х, удовлетворяющая условию [и — ю! = !и[ ]и — е[.
т<Х Проекцию точки и на множество Х будем обозначать через 'Р (и) = ю. Поскольку р(и, Х) = 1п[ ~и — е~ — расстояние от точки и до множества тех Х, то из определения 1 следует, что р(и, Х) = [и — Р (и)[ < [и — е[ Уе Е Х, )?и ~ Е" 5 4. ПРОЕКЦИЯ ТОЧКИ НА МНОЖЕСТВО 183 Если и Е Х, то,,очевидно, всегда 'Р„(и) = и. Однако проекция на множество существует ие всегда, Например, если Х = (и Е Е": ~и[ < 1) — открытый единичный шар в Е", то ни одна точка и ф Х не будет иметь проекции на это множество. Однако если множество Х замкнуто,, то любая точка и е Е" имеет проекцию на Х вЂ” это было доказано в следствии 1 к теореме 2.1,3.
Проекция точки на множество может определяться неоднозначно (рис. 4.6). Однако, как показывает следующая теорема, для выпуклых множеств такая ситуация невозможна (рис. 4.7). Т е о р е м а 1. 77усть Х вЂ” выпуклое замкнутое множество из Е". Тогда: !) всякая точка и е Е" имеет, и притом единственную, проекцию на это множество; 2) для того чтобы точка ю е Х была проекцией точки и на множество Х, необходимо и достаточно выполнения неравенства (см. рис. 4.7) 17ри этом если Х вЂ” аффинное множество (см. пример 1.4), то вме- сто (1) можно писать Доказательство. Рассмотрим функцию д(е)=[е — и[з переменной е Е Е" при произвольной фиксированной и Е Е".
Поскольку д(е) сильно выпукла на Е , то по теореме 3.1 эта функция достигает своей нижней грани на Х в единственной точке ю Е Х. Это означает, что [е — и['> )и — и[' или [е — и[> ~ю — и~ при всех е е Х, причем равенство здесь возможно только при е = ю. Остается принять Р (и) = ю. Докажем второе утверждение теоремы, Согласно теореме 2.3 для того, чтобы функция д(е) достигала минимума на Х в точке ю, необходимо и достаточно, чтобы (д'(ю), е — ю) = 2(ю — и, е — ю) > 0 при всех е Е Х, что равносильно неравенству (1). Наконец, пусть Х = (и е Е": Аи = Ь) — аффинное множество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
