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