А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 11
Текст из файла (страница 11)
Мы отметим прежде всего простейшиеитерационные методы решения задачи минимизации, наиболее полноучитывающие специфику одномерных задач.Вычислим функцию на концах отрезка и в двух внутренних точках я 12и х < х1. Будем считать, что эти точки симметричны относительно середины отрезка (а, 6). В методе золотого сечения точки х' и х2 выбираютсятак, чтобы отношение длины всего отрезка [а, Ь] к длине большей из егоГлава 7.
Задачи минимизации функций92частей [а,я 1 ] равнялось отношению длины большей части [а,х1] к длинеменьшей части [ж',Ь]:h — п.г —а(7.4)х' - а ж" - аДалее проводится сравнение значений функции в четырех точкаха,ж 2 ,ж',Ь и выбирается точка, в которой значение функции наименьшее.Пусть это будет точка х2, тогда минимум функции достигается в одномиз прилегающих к этой точке отрезков: [а,х2] или [ж2,ж1] и поэтомув дальнейшем можно рассматривать проблему минимизации на отрезке[а,х'].
После этого процесс повторяется — в соответствии с правиломзолотого сечения делится точкой ж3 отрезок [а,ж'].Для минимизации функции одной переменной широко используютсяметоды полиномиальной интерполяции. В этом случае с использованиемранее найденных точек строится интерполяционный полином, точкаминимума которого принимается за очередное приближение. В методепарабол используется интерполяционный многочлен второго порядка.Пусть, например, известны три приближения ж*-2 < ж*"' и2ж*" < хк < хк~\ причем f(xk) < /(ж* - 2 ) и /(ж*) < /(ж*" 1 ). Новоеприближение ищется как решение задачи минимизацииL2 (ж) —> min,(7.5)где Ь2{х) — интерполяционный многочлен второго порядка, построенныйпо узлам ж* - 2 ^* - 1 и хк.Интерполяционный многочлен Ньютона имеет видЬг(х) = /(ж*) + (х~ ж*)/(ж\ж*-') +(х-хк)(х-хк-*)/(хк,хк-\хк-2),+где/ 0 е >х)=~к—ZiTiх —х'„ J ,*-, ^ _ /(»*-,*fc-2)-;(«V-')/(Ж ,ж ,ж ; ^к2^к— разделенные разности первого и второго порядка соответственно.Решение задачи (7.5) приводит нас к следующей формуле для новогоприближения для точки минимумаоJfc+l _ * .
_*-•/ V Е 'Х )/7А\/(ж*,д.*-1 хк~2]2ж = ж + ж - —т-г—._,....(7.6)7.2. Методы решения задач оптимизации93Для дифференцируемой функции f(x) строятся итерационные методы, основанные на решении уравнения (необходимое условие минимума)/'(*)=0.(7.7)Корень этого уравнения х* € X является точкой минимума, если/"(ж) > 0 (достаточные условия минимума). Для приближенного решения нелинейного уравнения используются итерационные методы.В итерационном методе Ньютона новое приближение для точкиминимума определяется в соответствии с формулой„*+> _хкх_f \х ).
_ „ ,/ 7 сч= 01(7 8)~ 7ч^)' * ' '"---Различные модификации метода Ньютона рассматривались в главе 7.7.2.2. Минимизация функций многих переменныхДля функции многих переменных f(x), х — {xi,X2,-.. ,хп} определимвектор первых частных производных (градиент)'<•>-{£<"}•{&«<<•>ЫМатрица вторых частных производный (гессиан) в точке х есть'<•>-{*&<•>}•Будем рассматривать задачу безусловной оптимизации (7.3).
Пустьфункция f(x) дифференцируема в точке локального минимума х = х*,тогда (необходимые условия оптимальности)/V) = 0.(7.9)Пусть функция f(x) дважды дифференцируема в точке х = х* и выполнено (7.9). Если матрица /"(х) положительно определена, т. е.(/"(**)», у) > 0,Vj/^0,(7.10)94Глава 7. Задачи минимизации функцийтогда х* — точка локального минимума. Условия (7.9), (7.10) есть достаточные условия оптимальности.Для итерационных методов минимизации будем использовать обозначениях*+| =xk + akhk, fc = 0 , l , . . . ,(7.11)где hk — вектор, который определяет направление (fc + 1)-го шага минимизации, а коэффициент а* — длину этого шага.Вектор h задает направление убывания функции /(х) в точке х, если/(х + ah) < /(х) при достаточно малых а > 0.
Если вектор ft* задаетнаправление убывания функции /(х) в точке хк, а ак > 0 такое, чтоf(xk+i)<f(xk),то итерационный метод (7.11) называется методом спуска. В фадиентномметодеft*= -/'(х*), т.е.xk+t=xk-akf'(xk),k = 0,1,....(7.12)Особое внимание уделяется выбору итерационных параметров а*,к — 0,1,... в методе (7.11). Их можно определять из условияf(xk +akhk) = min / (хк + ah"),т. е. из решения дополнительной одномерной задачи минимизации.В вычислительной практике широко используется процедура дробления шага, когда параметр а уменьшается, например, в два раза, до техпор пока не будет выполнено неравенство/(х* +aft*) </(**)•При применении метода Ньютона для решения системы нелинейныхуравнений (7.9) получимf"(xk){xk+l-xk)+ / ' ( * ' ) = 0,* = 0,1,-...(7-13)Он записывается в виде (7.11) приa, = l, ft* = - ( / " ( * * ) ) " № ) •(7-14)7.2.
Методы решения задач оптимизации95Среди модификаций метода Ньютона отметим метод Ньютона с регулировкой шага, когда вместо (7.14) используется«*>о, л» = -(/"(«*))-у(«*).В квазиньютоновских методахft* = - Я * / ' ( * * ) ,где Нк — матрица, которая аппроксимирует матрицу (/"(ж*)).7.2.3. Задачи условной минимизацииПри минимизации функций с ограничениями широко используются подходы, аналогичные разработанным для задач безусловной минимизации.Наиболее просто это реализуется при переходе от задачи условной минимизации к задаче минимизации без ограничений.Рассмотрим задачу минимизации с ограничениями типа равенств:/(z)-»min,gi(x) = 0,z=l,2,...,m.(7.15)Эту задачу можно записать в общем виде (7.1), задав допустимое множествоХ = { х € К " | л ( * ) = 0, » = l , 2 , . . . , m } .При некоторых ограничениях задача условной минимизации (7.15)эквивалентна задаче безусловной минимизации функции ЛагранжатФ{х,у) = f(x) +^2yi9i(x),:=lгде j/j — неизвестные множители Лагранжа.
Тем самым мы приходимк задаче минимизации функции п + т переменных.Более сложно перейти к задаче безусловной оптимизации при учетеограничений в виде неравенств. Рассмотрим, например, задачу/(ж)-ишп,#(х)<0,i=l,2,...,го,т.е. в (7.1)X = {х € R" | 9i(x) ^ О, i = l , 2 , . . . , r o } .(7.16)96Глава 7. Задачи минимизации функцийВместо функции fix) в методе штрафов минимизируется функция<b(x,e) = f(x)+f(x,e),(7.17)где 1р{х,е) — штрафная функция, е > О — параметр штрафа.
Выборштрафной функции на допустимом множестве подчинен условиям•ф(х,е)^0,ip(x, е) -» 0, если е —• О,х е X,а вне допустимого множества —•ф(х, е) -* оо, если е -+ 0,a; g X.В качестве характерного примера приведем штрафную функцию для задачи условной минимизации (7.16):f(x,s)1 ™2= -2_,[тах{0,з,(а:)}] .После этого рассматривается задача безусловной минимизацииФ(х,е) —• min,ас € R".Помимо выбора штрафной функции в методах этого класса очень важенвыбор величины параметра штрафа е.7.3. УпражненияПриведены примеры решения задач, связанных с построением и исследованием численных методов приближенного решения задач минимизациифункций.Упражнение 7.1. Пусть точка х] проводит золотое сечение отрезка [а,Ь],причем х1 > а+ (Ь — а)/2, ах2— точка золотого сечения отрезка [а,х ].Покажите, что точки х\х2 расположены симметрично относительносередины отрезка [а,Ь] и поэтому х' есть точка золотого сечения и отрезка [х2,Ь].Решение.
Точка х1 является точкой золотого сечения, еслиb— аа;1 - ах1 — аЬ - ж1977.3. УпражненияИсходя из этого определения имеемх = а+2va).Аналогично для х2 имеемх1 - ох2 — аи поэтомух =а+х2 - ах1 - х232В силу этогох'-(с-~Va).v»-.Ч_a+o-- aт.е. точки х1 и х 2 расположены симметрично относительно центра отрезка [а, Ъ].Упражнение 7.2. Функция f(x) называется выпуклой на X, если/(А* + (1-Л)у)<А/(*) + (1-А)/(у)для всех х,у & X и \£ [О,1J. Пусть функция f(x) выпукла на R" и дифференцируема в точке х* € R". Покажите, что если выполнено/'(**) = 0,(7.18)то х* — точка минимума функции / ( х ) .Решение. Для любых х € R" и А € (0,1] имеем/(Ах + (1 - А)х*) < А/(х) + (I - А)/(х*).Принимая во внимание дифференцируемость функции / ( х ) в точке х*,получим/(х* + А ( х - х * ) ) - / ( х * )/(*)-/(*•)£X( / ' ( х * ) , А ( х - х ' ) ) + о ( А ) о(А)АА 'Предельный переход А —» 0 дает искомое неравенство /(х) ^fix*).Глава 7. Задачи минимизации функций98Важно отметить, что условие (7.18) есть необходимое условие минимума.
Мы установили, что это условие является и достаточным при поискеминимума выпуклой функции.Упражнение 7.3. Покажите, что итерационный метод Ньютона сходитсза одну итерацию при минимизации квадратичной функции/ 0 Е ) = -(Ах,х) + (Ъ,х),где А — симметричная положительно определенная матрица пхп.Решение. В нашем случаеf'(x) - Ах -b,f"(x) = A.При применение метода Ньютона (7.13) при произвольном начальномприближении ж0 имеемf'(x*) = Axl - 6 = 0,!*т. е. х — х .Упражнение 7.4.
Для задачи условной минимизации (7.16) приведите несколько примеров штрафных функций.Решение. Ограничения в виде неравенств д,(х) < О, г = 1,2,... ,т учитываются выбором штрафных функций1 т•Ф(х,е) = -^2[тях{0,д{(х)}]р,6р>\,i=iV>(a;,e) = X ] e x p ( ё9'(хЧ'(7.19)«=i(гр(х,е)=<mj]С~7л't=1если5i v*/S. (*) < °, *= 1,2,...,тп,оо, в противном случае,т(х,е)-е 5 3 In [-9i(x)},если &(а;) < 0, * = 1,2,..., m,i=lоо, в противном случае.7.4. Задачи99Наиболее часто используется квадратичная штрафная функция (7.19)с р = 2.7.4.
ЗадачиЗадача 7.1. Найдите длину отрезка локализации минимума одномернойфункции после N шагов минимизации на отрезке [о, Ь] методом золотогосечения.Задача 7.2. В методе дихотомии первая пара точек есть1ха+b=—+*,а+ьс«= —-«.2Каждая последующая пара точек выбирается на расстоянии 6 по обестороны от середины отрезка локализации. Проведите анализ вычислительных аспектов метода дихотомии и сравните его с методом золотогосечения.Задача 7.3.
Пусть А — симметричная положительно определенная матрица п х п и при минимизации квадратичной функции/0*0 = -^{Ах,х) + {Ь,х)используется итерационный метод (7.11). Найдите оптимальное значениеитерационного параметра из условияf(xk + akhk) = min/(x* + ahk).Задача 7.4. Рассмотрите метод кубической интерполяции при минимизации одномерной функция f(x), который основан на построении многочлена третьей степени ц>{х) на отрезке локализации [х* _ ',х*] по условиямфк)= f(xk),>р'(хк) = /'(**)•100Глава 7.
Задачи минимизации функцийЗадача 7.5. Рассмотрите условия сходимости градиентного итерационного метода (7.12) при минимизации функции /(ж), для которой™(У, У) ^ (f"(x)y, У) < ЩУ, У), т > 0.Задача 7.6. Покажите, что если матрица f"(xk) положительно определена, /'(ж*) Ф 0, то направление hk = -(/"( ж *))~ /'(**) являетсянаправлением убывания функции /(ж) в точке ж*.Задача 7.7. Получите оценку сходимости метода Ньютона (7.13) при минимизации дважды дифференцируемой функции /(х) при предположениях(/"(«)», у) > т(у, у),т > 0,\\Г\х)~Г\у)\\^М\\х-у\\.Задача 7.8.
Проекцией точки а € R" X С R" называется точка Рг(л) € Xтакая, что||Pjr(o)-o||<||x-a||,Vx€X,т.е. точка, ближайшая к а среди всех точек X. Рассмотрите методпроекции градиента при решении задачи условной минимизации (7.1),когдаxM=Px(xk-akf'(xk)),k = 0,1,....Задача 7.9. Покажите, что штрафная функция1 mi>(x,e) = -УЧтах{0, А (х)}] р ,Р> 1является выпуклой непрерывно дифференцируемой функцией, если функции g,(x), i — 1,2,... — выпуклые непрерывно дифференцируемыефункции.Задача 7.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
