Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 13
Текст из файла (страница 13)
Исследуем скорость сходимости метода касательных, считая минимизируемую функцию дважды дифференцируемой. Т е о р е м а 2. Лусть функция /(х) дважды непрерывно дифференцируема на [а, 6), !и! /"(х) >О, х. — точка минимума /(х) на [а', Ь[. и ч (к ь) Лусть последовательность (х„) получена методом касательных при х = а по схеме (4), (5), а, =а, Ь, = Ь, причем х„~ х, (и =О, 1,...). Тогда, для любого числа г > 0 существует номер Аг = )ч'(е) такой, что !х„— х,/ < ((1+ е)/2)" н(6, — ан), и > Аг. (6) Дока з а т ел ь с т в о. Из теоремы 8.9 следует выпуклость функции /(х) на [а, 6]. Кроме того, так как /'(х) строго возрастает, то множество Х, состоит из единственной точки х„. Тогда из теоремы 1 имеем !!гп х„= х..
Поскольку [а „„6„,,[ с [а„, 6„[ (и =1, 2,...), то последовательность (а„) монотонно возрастает, а (6„) — монотонно убывает, причем а„ < х, < Ь„ (и = 1,2,...). Покажем, что 1!ш а, = !нп Ь„ = х.. и са и-~са В силу (4) либо (а„), либо (Ь ) является подпоследовательностью последовательности (х„) и сходится к х.. Пусть для определенности !нп а„ = х,. Допустим, что (Ь ) не сходится к х„. Тогда согласно (4) последовательность (6„) не может быть подпоследовательностью для (х ), т.
е. найдется номер и > 1 такой, что Ь„ = Ь при всех и > и . При и - со из (5) получим /(х,) =/(Ь. )+/'(Ь )(х„— Ь ). В силу теоремы 8,4 это возможно только тогда, когда /(х) = /(Ь ) + /'(Ь )(х — Ь ) (х, < х < Ь ). Отсюда /'(Ь ) =/'(х,) = О, что противоречит условию /'(Ь ) > О. Тем самым доказано, что обе последовательности [а„), [6„) сходятся к х,.
$9. МЕТОД КАСАТЕЛЬНЫХ Из представления (5) для точки х... с помощью формулы Тейлора имеем у(а„) — у(ь,) — у'(ь )(а„— ь ) 1 г"(4 ) ~(Ь„) — У(а„) — У'(а„)(܄— а„) 1 У" (~„), где 5„, и„, )ь„— некоторые точки из отрезка [а„, 6„). Отсюда получа- ем, что Ь„~, — а„э, < шах(х„ь, — а„; ܄— х„„,) < д„(܄— а„)/2, где д„= = шах~/'Я.)//"(р„);/"(и„)//"(р„)).
Поскольку последовательности д„), (и,), (и„) вместе с (а ), (Ь ) стремятся к х„то в силу непрерывности функцйи /"(х) и условия !и[ /(и) >0 имеем 1пп д„=1, В Е 1к Ь! Следовательно, для любого г > 0 найдется номер АГ = Аг(е) такой, что д„< 1+ е при всех и > 1У. Тогда 6„„, — а„+, < д(6„— а„) (п > Аг), где д = =(1+ г)/2.
Отсюда ܄— а„< д" "(܄— а, ). Следовательно, )х„— х„! < (܄— а„) < д" "(Ьн — а„), п >Аг, 4. Оценка (6) означает, что метод касательных сходится со скоростью, не меньшей скорости сходимости геометрической прогрессии со знаменателем д = (1 + г)/2 ю 1/2. Конечно, существуют выпуклые функции, для которых этот метод будет сходиться гораздо быстрее (возможно, например, что точка минимума найдется за конечное число шагов). Однако нетрудно привести пример, показывающий, что на классе дважды непрерывно дифференцируемых функций оценка (6) по порядку не может быть улучшена. П ример 1. Пусть/(х)=х'( — 1<х<2).
С помощью формулы(5) легко проверить, что касательные к параболе в точках а, Ь„пересекаются в точке х„ь, = (а„+ 6„)/2. Возьмем х = а, = — 1, х, = Ь, = 2. )огда х, = 1/2. С помощью индукции нетрудно показать, что а„=-1/2"-', 6„=- 1/2" ', х„ И=1/2" при нечетных и и а„= — 1/2" ', 6„=1/2 ',х„„ = — 1/2 при четных и.
Отсюда получается точная оценка !х, — х„)=!х.! = 1/2" ', в то время как, используя методику вывода оценки (6), имеем !х„ — х,) < Ь, — а = 3/2 ' (и > 1). Таким образом, из примера 1 следует, что метод касательньгх на классе гладких выпуклых функций не лучше метода деления отрезка пополам. Более того, для этого класса функций нетрудно предложить вариант метода деления отрезка пополам, требующий лишь вычисления значений производных минимизируемой функции.
А именно, положим х = а = а, х, = Ь, = 6, вычислим значения /'(а,) = = /'(а+О), /'(6,) =/'(Ь вЂ” О). Если /'(а,) > 0 или /'(Ь, ) < О, то по теореме 8,5 имеем а Е Х, или Ь Е Х„вЂ” задача решена. Поэтому пусть |'(а,) < О, /'(6,) > > О. Тогда Х„с (а„Ь,). Пусть отрезок [а„„6„,1 (и > 2) уже построен, причем /'(а„,) < О, /'(6,) > О, так что Х„с (а„„Ь„,). Положим х = = (а,, + Ь„,)/2 и вычислим /'(х„). Если 3" (х„) = О, то х„е Х, — задача решена.
Если /'(х„) ~0, то определим точки а„Ь„по формулам (4), приняв в них х. = (а„, + 6„,)/2. По построению /'(а,) < О, /'(6„) > О, н согласно теореме 8.6 Х„с (а„, Ь„). Кроме того, ясно, что Ь вЂ” а„=(Ь„, — а,)/2=(6, — а,)/2" а=1, 2, Описанный метод деления отрезка пополам выгоднее применять при минимизации тех гладких выпуклых функций, у которых значения производ- Упражнения 42 Гл.
1. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ ных вычисляются проще, чем значения функции. Если же значения и функции, и ее производных вычисляются достаточно просто, то метод касательных может оказаться предпочтительнее — хотя, как мы выше убедились, метод касательных на классе гладких выпуклых функций в целом не лучше метода деления отрезка пополам, но в то же время нетрудно привести примеры таких выпуклых функций, для которых метод касательных сходится гораздо быстрее описанного метода деления отрезка пополам.
Заметим, что метод касательных можно описать и без требования дифференцируемости выпуклой функции, используя лишь односторонние производные во внутренних точках отрезка (а, [ь] (148!. 1. Применить метод касательных для минимизации функций 7"(а) = в, 7(х) = [в[, 7"(х) = г = [в[+(в — !)з на отрезках [ — 1, 1], [-1,2], [О, 1], [1,2). ГЛАВА 2 Классическая теория экстремума функций многих переменных В этой главе собраны основные факты о задачах на безусловный и условный экстремум функций конечного числа переменных, обычно излагаемые в учебниках по математическому анализу[327; 350; 352; 534], Кроме того, приводятся необходимые условия экстремума перво. го порядка для задач с ограничениями типа неравенств (см., например,[14; 286; 358; 374; 605; 6!7; 670)).
Впервые в учебной литературе излагаются новые необходимые условия экстремума второго порядка, принадлежащие А. В. Арутюнову [44]. В последнем параграфе этой главы приведены некоторые вспомогательные формулы и оценки, необходимые для дальнейшего изложения. ф 1. Постановка задачи.
Теорема Вейерштрасса 1. Сначала введем обозначения и напомним некоторые определения из линейной алгебры и математического анализа. Через К" будем обозначать т»-мерное вещественное линейное пространство, состоящее из вектор- столбцов с действительными координатами ю*', у', х',... (ь = 1,..., т»); сумма х+ р двух вектор-столбцов и произведение стю вектор-столбца ю на действительное число сг в К" 'определяется обычным образом: ю+д= ..., гтх= вектор-столбец »- [...] называется нулевым. Вектор-строку, полученную транспонированием вектор-столбца ю, обозначим через хт = (ю',...,х"). Там, где не могут возникнуть недоразумения, вектор-столбец или вектор-строку из К для краткости мы часто будем называть просто вектором или точкой, а знак транспонирования «Т» будем опускать.
Если в К" ввести скалярное произведение двух векторов (ю, у) = = 2 , 'ю'ту*, ю, у Е К", то К" превращается в ть-мерное евклидово простран$=! ство, которое будем обозначать через Е . Длина вектора или корма вектора 45 44 Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА 4 ! . ПОСТАНОВКА ЗАДАЧИ. ТЕОРЕМА ВЕЙЕРШТРАССА «и в Е" определяется так1х!=(х, х) ~ = ~~;1х*!') . Величину '=! , (*, у) =! — у! = (Е 1х! — у'Г) называют евклидовым расстоянием между точками х, у е Е".
Для любых точек х, у, г 6 Е" справедливо неравенство 1х — у! < 1х — г) + 1г — у(, называемое неравенством треугольника. Когда важно подчеркнуть, что скалярное произведение, норма, расстояние взяты именно в Е",мы будем писать (х, у) ., 1х! „, 1х — у! .. В Е" справедливо неравенство Коши— Буняковского 1(х, у)1 < 1х ! ° 1у ( 'ь'х, у Е Е, причем неравенство превращается в равенство тогда и только тогда, когда векторы х, у колинеарны, т. е. х = ау при некотором «х. Иногда мы будем пользоваться и другими нормами векторов из К", та- «Ф кими, как ~х(, = ( ~„~х«Ц, 1 < р < оо, 1х) = шах (х«~. Как известно «=! !»«»л [192), в конечномерных пространствах все нормы эквивалентны. Это зна- чит, что если ) ), ~ (, — две нормы в К", то существуют числа т, >О, тп >О, что т«~ ° 1 < ~ ° ~ < хп ) ° ) '!«хе 1в'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
