341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 47
Текст из файла (страница 47)
Прп неуда шом выборе хо последовательность (13) может расходиться. Если жс точка то достаточно 6>лизка к х', то эта последовательность сходится к х' достаточно быстро. Оценка скорости сходит>ости может быть сформулирована следук>- шим образом. Пусть г" (х) — дважды диффсрснцируемал на К функц>иц, причем у" (х) > р > 0 при всех х б К и 1" (х) уловлетворяет условии> Лившица на К с константой Е.
Тогда, если начальное приближение тс Е УдовлетвоРкет Условию 9 = —,)У" (хо)! < 1, то последовательность (13) 2,э сходитсн к единственной топ>е минимума х' функции у(х) на К, причем 2>т .„ )х' — х„) < — дх, и = О, 1, ... Е Пример 9. Методом Ньютона найти точку мшн>л>уь>а х* и минимальное значение у* функции у(х) = (х — 2)" — 1пх с точностью !У>(хв)~ < 10-'.
а Выберем хс — — 3 и проведем вычислснпп по формуле (13), записывал результаты в таблице 1.6. Таблица 1.6 В задачах 17.84-17.89 минимизировать функцию )'(х) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства )1"'(х„)! < 10 4: Окончательно х* 2,4662656,(* = -0,8554408. Метод Ньи>тона часто используется на завершающем этапе минимизации, когда точка минимума х* грубо найдена другим, менее трудоемким л>стодоь> и требуется найти х* с болыпой то >пастью. Гл. 17. Методы оптимизации 340 17.84. Дх) = ха+ е *.
17.85. ('(х) = 2х+ е *. 17.86. Дх) = хт + т, + а!их. 17.87. у'(х) = хт — х+е *. 17.88. )'(х) = е* + е тх + 2х. 17.89. 1(х) = 2х~ + х+ совах. 17.90. Найти точку минимума х* функции Дх) одной из задач 17.76-17.83 методом Ньютона, используя в качестве начального приближения решение, найденное методом касательных. Вычисления закончить при ]у'(х„)[ < 10 е. 9 2. Безусловная минимизация функций многих переменных 1.
Выпуклые множества и выпуклые функции. Пусть ń— я-мерное евклидово пространство арифметических векторов х = (х,, хж .. х„). Множество б| С Е„называется выирклыл|, если вместе с любыми двумя точками хй>, х|т! б У оно содержит и отрезок, соединяющий эти точки, т. е. ахбй + (1 — а)хйй б У для всех а б [О; 1]. (1) Пример 1. Показать, что множество точек х = (х|, хт) плоскости У = ((х! , 'хт)]х! + хт ~~ 1) вь|пукло. <! Пусть х||! = (х ~, хт ~) и х|т! = (х~ ~, х~~ ~) е У, а х = (х|, хт) = = ах|0 + (1 — а)хбй — точка отрезка, соединяющего точки х||! и х|т!.
Покажем, что х б У. Имеем х! + х2 [ах! + (1 а)х! ] + + [ах~ + (1 — а)х~ ~] = а [(х~ ~)т + (х~ ~) ] + (1 )2[( (2))2 ! ( ~2))2] + 2~(1 — )[х ~х~ ~ + х, Используя неравенства (х!'~)т+(х~|~)т < 1, Рис. 28 ! = 1, 2 (так как х!'! Е У) и 2х~ |х~ ! < ( (х( ~)т+ (х( ~)т, получим хт|+х~ ~( от+(1 — а)а+2а(1 — а) = 1 т,е. хе с!. Выпуклость множества У ясна из рис. 28. Так как У вЂ” круг, то отрезок, соединяющий любые две точки х|Ц, хбй Е У, целиком лежит в У. > з 2. Безусловная минимизация функций многих переменных 341 Проверка условия (1) в большинстве случаев требует громоздких выкладок, поэтому на практике при исследовании выпуклости множеств в пространствах сг и сз часто используют геометрические иллюстрации, подобные рис.
28. В задачах 17.91-17.100 установить, являются ли выпуклыми мнонгества У: 17.91. ь ь = ((хь, хг)[2хь + хг < 2, 2хь — хг ) — 2, хг > 0). г' = ((х!, тг)]хьюг > 1, хь > 0). 17.93. У = ((хь, хг)[хг ) хг). 17.94. сь = ((ть, хг)[хьхг < 1, хь > О, хг > 0) 17.99.
и = (( „г) [,„х, < 2,г +,г < 4) 17.96. У = ((хь, хьц хз)[хз > хг + хг). 17 97 У = ((хь, хг, хз)[х', < х', + хг). 17.98, У = ((хь, хг, хз)]хг + хг < 1), 17.99. сь = ((хь,хг, хз)хь + хг + хз < 1,хь ) О, хг > О). 17.100. У = (т, хг, г;з)[хг + †'г + з > 1 Функция у'(х), заданная на выпуклом множестве 1ь' с Еа, называется вььпуклай на этом множестве, если для любых точек хОь, хьгь б У и произвольного числа о б [О; Ц справедливо неравенство у[охиь + (1 — о)хь~~] < оу(хь'ь + (1 — гь)у(хбп). (2) На практике обычно используют следующий критерий выпуклости функции; Если ь'(х) — — дважды дифференцируемал на выпуклом множестве У с Е„функььил и матрица ее вторых ььраььаваднььх ььн(х) = = (дг ь"(х)ььдхь дх ) (гессиан) положительно определена при всех х й 1ь', то функция у'(х) лвллеьпсл вьтуклвй на множестве У.
Применяя критерий Сильвестра к льатрице вторых производных, можно сформулировать это утверждение в более удобном для проверки виде: Если все угловые миноры матрицы у' (х) паложитасльны при Х б 1У, пю функция г(х) выпукла на множестве У. П РимеР 2. ВыЯснить, Явлнетса ли фУнкцин У(хь, хг) = 2хг+ха г+ + вп (хь + хг) выпуклой в пространстве Ек Гл. !7. Методы оптимизации 342 а Запишем матрицу вторых производных д~у(х) дх! дхг дгу(х) д, г дтпл(х) д.г дгу(х) дхг дх! у" (х) = 4 — в1п (:г! +:Гг) — Яп (,т1 + г г) — гбп(х! + х ) 2 — в!и (х! + хг) г! НайДЯ Угловые миноРы втой матРицы Ь! — — 4 — гбп (х! + хг), 4 — 31п (х! + хг) — Б!и (х1 + хг) = 8 — беби(х! +хг), — в!и (х! + хг) 2 — в!п (х! + хг) убеждаемся, что Ь! ) О, ! = 1, 2, при всех х Е Ег, т.е, функдня у(х) выпукла. С> Выпуклые функции играют большую роль во многих вопросах оптимизации в связи с тем, что всякий локальный минимум выпуклой функции является одновременно и глобальным.
В задачах 17.101 — 17.106 убедиться в выпуклости функции у (х) во всем пространстве Ен! 17.101. ~(х1, хг) = 4хг! + хг г— 2хгхг + бх1 — хг — 2. 1!.102. 11, 1= /1!-*~~-*,. 17.103. У(х!! хг) = х, + хг — сов 17.104. г (х1, хг) = х! + хг+ х, + хг+ х,хг. 17.105. у(х1, хг, хз) = е*!ч*г+*г 17.106. у(х1, хг, хз) = 5хг! + 5хгг + 4хзг + 4:с! хг + 2хгхз В задачах 17.107 — 17.110 указать множества У, на которых функции 2 (х) являются выпуклыми; , 2 17.107.
у(х) = — '. Х2 17.108. У(х) = в(п (х! + хг). 17.109. ~(х) = х, + 2хг — в!п(х! — хг). 1 17.110. ~(х) = хг+хг+ Х! + Х2 Во многих задачах оптимизации рассматриваются квадро!Пичныс функции, т.е. функции вида у(х) = ~~! с,!х!хг + ~~! г хг. Если поло!,г=1 1=! 2.
Безусловная минимизация функций многих переменных 343 1 у'(х) = -Ях, х) + (г, х), 2 (3) где х = (ты,тз,..., .т.„), г = (гы гз, ..., г„) — векторы-столбцы, (х, у) — скалярное произведение векторов х и у 6 С„. Градиент и матрица вторых производных функции (3) равны бгайДх) = У'(х) = Ях+ г, (и(х) = Я = (Уо). Таким образом, для того чтобы функции (3) была выпуклой в Е„, достаточно, чтобы матрица Ч была положительно определена. Пример 3. Пусть у(х) = 2хзз — 2хзхз+ Зхзхз+ тз з— 2хзхз+ 4хзз + + хз + 2хз + Зхз.
а) Найти матрипу су и вектор г в представлении (3) функции у(х). б) Найти градиент т"'(х). в) Выясним, явлнстсн ли функции У'(х) выпуклой. < а) В данном случае сы — — 2, сзз — — — 2, сы = 3, сзз —— 1, сзз —— — 2, 4 2 3 1 ем=4,г, =1,гз — — 2,гз=3,позтоыуЯ= -2 2 — 2,г= 2 3 — 2 8 3 б) Используя найденные матрицу Я и вектор г, запишем 7(х)=Ях+г= — 2 2 — 2 тз + 2 4х1 — 2хг + Зхз + 1 — 2хз + 2тз — 2тз + 2 Зтз — 2хз + 8тз + 3 в) Найдем угловые миноры Ь, матрицы ) "(х) = Ц; 4 — 2 3 — 2 2 — 2 3 — 2 8 4 — 2) Ь! =4, Ьз — — 2 2~=4, Ьз= = 22.
Так как Ь, > О, з' = 1, 2, 3, то функция Дх) выпукла в Ез. с 17.111. При каких а, б и с функция Дх) = ат1~ + бх1хз + схз~ явлнется выпуклой в Ез? 17.112. При каких значениях а функцин )'(х) = те~ + хат+ лаз + + ах,тз выпукла в Ез? В задачах 17.113-17.116 выписать матрицу Ц квадратичной функции у(х), найти ее градиент Г'(х(о)) в точке х(о) и убедиться в выпуклости Дх) в Е„: жить б„= см + с О то полУчим симмстРическУю матРицУ Я = (бо), с помощью которой можно представить квадратичную функцию в виде Гл.
17. Методы оптимизации 344 17.113.,)'(х) = хг~ + 5х ~ хт + Зхт ~+ х~ — хз, х(о) = (1, 1). 17.114. у(х) = х( — Зх~хт + 10хт ~+ Взй — Зхз, х(о) = (2, 1). 17 115. у(х) = хд+2хз~+Зхг+2х~хз — хзхз+ 2х~ + ха, х(о) = = (1, О, — 1). 2 2 17115 1(х) = х~+-хз+тз+х~хз+х~хз+хзхз+5х~ — хг — Зхз, х(о) (1 2 З) 2. Методы безусловной минимизации, основанные на вычислении первых производных функции.
Постановка задачи минимизации функции и переменных у(х) = 7(хм хт, ..., х„) на множестве У С б„нс отличается от постановки в одномерном случае. Если У = Еч, то говорлт о безусловной минимизации функции у(х). Длл решения задачи бгзусловной минимизации функции у(х) наиболее часто применяют приближенные методы, в основе которых лежит вычисление производных г"(х) первого порядка. Такие методы обы шо называют градиентными.
В ряде других методов требуется вычислснш не только первых, но и вторых производных функции у(х). Метод градиентного спуска. Пусть у'(х) — выпуклал дифферснцирусмал во всем пространстве б„функция и требуется найти ес точку минимума х*. Выбрав произвольное начальное приближенис х~о~ 6 5„, построим последовательность х~ " ~ = хйй — агу'(хйц), й = О, 1, ..., (1) где величины ог ) О (парамстрические шаги) выбираются достаточно малыми для того, чтобы выполннлось условие у(х~ь+0) < у(х~"~), л = О, 1, (5) В качестве условия окончания вычислений обычно использустсп близость к нулю градиента у'(х~"~), т. с.
выполнение неравенств ду(х~" ~) <г, г=1,2,...,п, Ох, или йу (х~ ~)ц = ~ < е (6) (ОУ(хбй)) г дх; (г — заданнос достаточно малое число), после чего налагают х' = х~ь . Г Г(хйб). Если при некотором й условие (5) нарушается, то шаг оь в (4) уменьшают (дробят) в заданное число раз до выполнения неравенства (5) и продолжают вычисления. 3 2. Безусловная минимизацин функций многих псрсаюнных 345 Пример 4. Минимизировать в Еа функцию у(х) = >(хм хт) = хт1 + 2хт + е"+" методом градиентного спуска, завершив вычисления при ~ОУ(х>а>)/дх,~ < 0,05, 1 = 1, .2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
