В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров, Сборник задач по оптимизации (теория, примеры, задачи) (1155771), страница 10
Текст из файла (страница 10)
Доказать неравенство между средним арифметическим и средним геометрическим: < ~~ 1)и ~~ Х, П х,~ -': '=' ух, : О, 1 = 1, ..., и, и 2.70. (Р) Доказать неравенство Гельдера: ,~~ х,а; 1=1 1~~р. 2.71. Доказать неравенство Минковского.' Х ~х +у~" ~ Х 1х1" + Х ~у~" 1~~р, В задачах 2.72 — 2.76 методом Ньютона решпгь уравнения с заданной начальной точкой х,. 2.72.
е" — 2=0, х, 1: 2.73. 5х1 2+ 2х,х — 2х,х + 4х,' + 4х~х, + хз~ + 2х, + + х + х = О, х = (1, 1, 1). 2.74. 4х1 — 2х,х +2х~х + Зх; + 2х~з — х, + х~ — хз = О, хз = (1, — 1, — 1), 2.75. 6х', + 4х,х... — 2х,х, + 5х', + 6х,х + 4хз + Зх,— — 2хй + хз = О, хо = (2, 1, 1). 2.76. (2х, + х, + х,)'+ (х, + х., — х,)'+ (х, — х, + Зх,)' =О, х,=( — 1,1, — 1). 2.77. Вычислить методом Ньютона отрицательный корень уравнения х' — Зх'+ 75х — 10 000 = 0 с пятью верными знаками. 2.78.
Найти по методу Ньютона наименьший положительный корень уравнения ф х = х с точностью до 0,00001. 2.79. Вычислить с точностью до 0,0005 единственныи положительный корень уравнения х' — х — 0,2 = О. $ 3. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА ЗА. Основные понятия. ЗА.1. Выпуклые множества и функции. Пусть Х вЂ” вещественное линейное пространство. Множество А с=Х называется выпуклым, если из условия х„х, ~ Л следует, что [х„х2) = (х!х= хх, + (1 — а)х„я е= (О, 1)) с=-Л. Пустое множество выпукло по определению.
Множество Кс=-Х называется конусом, если из х ~ К следует, что ах ~ ее К ~ и ) О. Выпуклые конусы — зто конусы, являющиеся выпуклыми множествами.. С каждой функцией )': Х вЂ” В, принимающей значения в расширенной области действительной прямой, связаны два множества: оош) =(х~~(х) <+ ), ер1 ~ = ((а, х) ~ В Х Х~ а ~ 1(х), х ~ дол ~), называемые эффективным множеством и надграфиком (эпиграфом) функции ~. Функция ~ называется выпуклой, если ер1 ~ — выпуклое множество в В Х Х. Функция, у которой 6ош ~ Ф 8 и ~ (х) ~ — оо ух, называется собственной. Функцшо р: Х вЂ” В будем называть выпуклой однородной, если ер1р — выпуклый конус в В Х Х.
Простейшие свойства выпуклых множеств и функции, з также ряд сопутствующих понятий (выпуклая, коническая, линейная и аффпппая комбинации и оболочки, выпуклый многогранник, симплекс и т. и.) описаны в ЛТФ, с. 208 — 216. Напомним только два обозначения: сопч А — выпуклая оболочка и соне А — кони 1еская оболочка множества А, Пусть Х вЂ” нормированное пространство, Х" — к нему сопряженное.
Пересечение всех выпуклых замкнутых множеств, содержащих данное множество А, называется выпуклым замыканием А и обозначается сопчА. Функция 1, определяемая условием ер1 ~ = ер1 ~, называется замыканием 1, а функция сопч ~, задаваемая соотношением ер1 сопч1 = сотл ер~ /, называется выпуклым замыканием ~.
таким образом, сопч ~ есть наибольшая пз выпуклых замкнутых функций, не превосходящих ~. Функция 1 называется замкнутой, если )' =~. 3.1.2. Основные операторы. Особенность выпуклых объектов состоит в возможности их двойного описания — в основном и сопряженном пространствах. В выпуклом анализе известно несколько преобразований, связанных с такого рода двойными описаниями. Важнейшие среди них— операции сопряжения для функций и конусов, поляры для множеств и субдпфференцпрованпя для выпуклых однородных функций.
Преобразованием Лежандра — Юнга — Фенхеля функции ~, или функцией, сопряженной с ~, называется функция на сопряженном пространстве: ~*(х*) = апр ((х*, х) — ~(х)). Функция ~**(х) = епр ((х*, х) — ~*(х*)) пазывается второй сопряженной к 1, Из определения сопряженной функции следует неравенство <х*, х>:== ~ )(х) + ~*(х*), называемое неравенством Юнга. Полярой множества Л называется следующее множество в Х*: А' = (х" ~ Х* ~ (х~, х) ~ 1 Чх ~ А).
При этом А" = (х е=- Х ~ ( х', х) (1 'Кх* ~ Л'~, Сопряженным конусом к конусу .К называется конус в Х~: К~ = (х~ ~ Х~ ~ (х*, х) ) О 7х ~ К~. При этом К~* = (х ~ Х ~ (х*, х) ) О Чх~ ~ К*). Субдифференциалом выпуклой однородной функции р называется следующее множество в Х*: др = (х*~ Х~1<х~,х) =:р(х) Чх~ Х), Субдифференциилом выпуклой функции ~ в точке х называется следующее множество в Х~: д~(х) = (х~ я Х~~ <х~, х — х> ~ ~(х) — ~(х)). Таким образом, если ~ выпукла и однородна, то д~ = д~(0). Пусть А — подмножество Х.
Важную роль в выпуклом анализе играют следующие функции: а) индикаторная функция О, х~А, ЬА(х) = б) функция Минковского О, ах~А Ча)0, оо, ахф А 7а-: О, гп( (а ) 0 ~ а-'х ~ А) в остальных случаях, рА(х) = в) опорная функция ° зА (х~) = зпр (х~, х). 60 3.2. Основные теоремы и формулы выпуклого анализа.
В этом пункте всюду Х вЂ” нормированное пространство, Х~ — его сопряженное. 3.2Л. Теорема инволютивности. Напомним, что оператор называется инволютивным, если его квадрат является единичным оператором. Теоре ма. а) Для того чтобы для собственной функции ~ имело место равенство ~**=~, необходимо и достаточно, чтобы ~ была выпукла и замкнута. б) Для того чтобы для непустого множества А имело место равенство А" =А, необходимо и достаточно, чтобы А было выпукло, замкнуто и содержало нуль. в) Для того чтобы для непустого конуса К имело место равенство К~* = К, необходимо и достаточно, чтобы К был выпуклым и замкнутым.
Утверждение а) называют теоремой Фенхеля — Моро, 3.2.2. Двойственность опорной функции и субдифференциала. Т е о р е м а. а) Для того чтобы для некоторой однородной функции имело место соотношение здр = р, необходимо и достаточно, чтобы р была выпуклой и замкнутой. б) Для того чтобы для множества А имело место соотношение дзА =А, необходимо и достаточно, чтобы А было выпукло и замкнуто. 3.2.3.
Основные формулы субдпфференцпального ис- числения. Обозначим (У~ 'ч'Уг)(х) = птах(У,(х), ~~(х)Е Теорема 1. а) Пусть ~, и ~~ — выпуклые функции на Х и в некоторой точке х, где ~, конечна, функция 1, непрерывна, Тогда в любой точке х ~ Х имеет место формула д(~1 + ~~) (х) = д~1(х) + д~г(х).
б) Пусть ), и ~, — выпуклые непрерывные в точке х функции на Х и ~,(х) = Дх). Тогда имеет место формула дЦ, Ч ~,)(х) = сопч (д~,(х) 0 д1,(х)). (Для выпуклых однородных функций х=0, а фор- мулы приобретают вид д(р, + р,) = др, + др, и д(р, ~/ р,) = сопч(др, 0 др,).) Утверждение а) называют теоремой Моро — Рокафел- лара, утверждение б) — теоремой Дубовицкого — Милю- тина. Этот последний результат допускает значитеяьное усиление, принадлежащее в окончательной форме В. Л.
Левину. Те о р е м а 2 (об очистке). Пусть Т вЂ” компакт, И, х)— 1(т, х) — функция на ТХВ", выпуклая и замкнутая по х при каждом 1, полунепрерывная сверху по 1 при каждом к~В" и такая, что функция х- ~И, х) непре- рывна в х при любом ~~ Т. Положим ~(х) =-~йах)И, х), с Т,(х) = (Ея ТЗУ(х) = КИ, х)). Тогда всякий элемент уез ~ д~(х) представим в виде у =,~~~ а;у;, где т < и+ 1, г=т т и, ) 0,,~» и; = 1, у; ~ дД(1~, х) (субдифференциал по х), 1=1 (~ ез То(х), 1= 1, ..., г. 3.2.4.
Основные формулы выпуклого анализа. Исчис- ление выпуклых множеств и функций включает в себя ряд формул, связывающих введенные в п. 3.1.2 преобра- зования с операциями над множествами и функциями. Определим сначала некоторые наиболее употребительные операции, Операции над функциями. 1) Сумма: Ц, + ~,)(х) = )',(х) + 1,(х). 2) Конволюция: ф ~ ~,)(х) = 1п1 (~,(х,) + Дх,) ~х, + -т х, =х). 61 3) Максимум: (У~ Ч УгИх) = п1ах (У~(х), Уг(х) ). 4) Выпуклая оболочка минимума: ф сопч Д ~г)(х) = ш1п (афх~) + (1 — айаг(хг) ~0 ~ а ~ 1, ах, + (1 — а)хг = =- х). Операции над множествами.
1) Сумма: А, + А, = (х~х = х, + х„х, ~ А„х, ~ А,). 2) Кцнволюцпя: А1[+~Аг = Ц (аЛ, П (1 — а) А,). о~а<1 3) Выпуклая оболочка объединения: Л, сопч 0 Л, = = сопч (Л, 0 А,). Таблица д(р1 + рг) ~ др1 + дрг~ д(р1 ~ рг) = др1 Я дрг, г(А1 + А г) = гА, + гА,„ д(р, Ч р ) м др1 сопч Ц др.„ д(р, сопч Л рг) = дрг П др.,', г(А1П Аг) ы гА1 сопи Л гАг ы ы гАг 9 гАг г(А, сопч ()Аг) = гАг Ч гАг', г(А (+ А,)ж А,чгА„ (А + А г)'= 4 о (+ ~ А о ~БА )о ~о+ ~о р.(Аг + Аг) ю рА, г7 )гА„ р(Аг Я Аг) м рА1+ рА „ (А1П Аг)о м А о сопч 0 Ао; (А1сопч 0 А )о = Ао Д Ао' р(А1 П Аг) =- рА1 'Ч' рА,„ )г(А1 сои ч Ц А,) = )гА1 сопч Д Л )гАг = — рА1 9 рАг' (Кг + Кг)* — К, П К,, (К1ДКг)* вк К + К .
Мы пишем =, если равенство имеет местобевдополнительных допущений, и ж, если оно имеет место лишь при некоторыхтребованнях относительно непрерывности функций или наличия внутренних точек многкеств. 4) Пересечение: А, П А,, Операции над выпуклыми однородными функциями. Помимо тех операций, которые имеют место для функций, введем еще одну: р, Ч р, = впр (ар, ® (1 — а) рг~О ~ сс ~ 1). Операции над конусами. Здесь имеются те же операции, что и в случае множеств, но при этом надо иметь и виду, что для конусов копволюция равносильна пересечению, а выпуклая оболочка объединения — сумме. Результаты, относящиеся к операции сопряжения для функций, выделим в виде теорем, а остальные сведем в таблицу, Теорема. а) Пусть ~, и ~г — функции на Х.
Тогда (~, В ~г) = ~1 + 1г*. Если же ~, и )г — выпуклые соб- 62 ственные функции и существует точка х, в которой /, конечна, а /, непрерывна, то (/, + /з)* = /, 9 /,. б) Пусть /, и /,— функции на Х. Тогда (/,сопч /~ Л /9) = Й~ Ч /з. Если лсе /, и /. выпуклы, конечны и непрерывны на Х, то (/, ~/ /,)* = /, сопч Д /,'. 3.2.5. Доказательстве теорем. Все утверждения, сформулированные в этом, пункте (за исключением теоремы об очистке), мы редуцируем к теореме о свойствах преобразования Лежандра — Юнга — Фенхеля (пп.
3.2.1 и 3.2.4). Для удобства полезно обозначить /з через Ц; А' — через яА, К* — через оК. Далее, 1, л, а, д, г, р и б рассматриваются как операторы, действующие па соответствующих объектах. Например, 1 переводит функции на Х (Х~) в функции на Х* (Х), л переводит множества из Х (Х~) в множества Х'з (Х), д переводит выпуклые однородные функции на Х (Х*) в множества пз Х* (Х) и т.д. Приведем несколько простейших формул, связывающих введенные операторы (А — множество, р — выпуклая однородная функция, К вЂ” конус): ве1 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
