Ф.П. Васильев - Методы оптимизации (2002), страница 8

ДОКаватЬ, Чта РЕШЕНИЕ ураВНЕНИя (4.1) ПрЕдСтаВИМО В ВИДЕ /Ьч = [-1) узч !С!З+ + [-1)" !Р„з/ь! (и =3,4,...). Отсюда вывести закон изменения погрешности величины А„, если Ь,,„аз заданы неточно. 8. Доказать, что последовательность Я /Рзхт !) сходится к г! — — (т/5 — 1)/2, монотонно возрастая, а Я !/7гз ) сходится к т! монотонно убывая. 9. Используя утверждения упражнений 7, 8, доказать, что метод золотого сечения является единственным симметричным методом, удовлетворяющим условию (4.4) при всех п = 1, 2...

10. Пусть дан симметричный метод с начальными отрезками С!!, Сгз, пусть Аг > 2 — заданное натуральное число. Используя утверждения упражнений 7, 8, указать промежуток изменения отношения С!з/Ст!, чтобы метод удовлетворял условию (4.4) при всех и = 1,..., Аг. И. Пусть дан некоторый симметричный метод, удовлетворяющий условию [4.4) при и = = 1.

Используя утверждения упражнений 7, 8, указать максимальное число Аг, прн котором условие (4.4) выполняется для всех и = 2,, Аг. Описанные выше методы часто приходится применять без априорного знания о том, что минимизируемая функция является унимодальной. Однако в этом случае погрешности в определении минимального значения и точек минимума функции могут быть значительными. Например, применение этих методов к минимизации непрерывных на отрезке функций приведет, вообще говоря, лишь в окрестность точки локального минимума, в которой значение функции может сильно отличаться от искомого минимального значения на отрезке.

Поэтому представляется важной разработка методов поиска глобального минимума, позволяющих строить минимизирующие последовательности и получить приближенное решение задач минимизации первого и второго типов (см. э 1) для функции, не обязательно унимодальных. Здесь мы рассмотрим один из таких методов для класса функций, удовлетворяющих условию Липшица, О п р е дел е н не 1. Говорят, что функция /(х) удовлетворяет условию Липшица на отрезке [а, 6), если существует постоянная Х, > О такая, что [/(х) — Х(у)[ < Х ]х — у) !/х, у Е [а, Ь).

(1) Постоянную Х называют постоянной Липшица функции У(х) на[а, 6]. Условие (1) имеет простой геометрический смысл: оно означает, что угловой коэффициент (тангенс угла наклона) ]/(х) — /(у)] [х — у]-' хорды, соединяющей точки (х, /(х)) и (у, /(у)) графика функции, не превышает постоянной Х для всех точек х, у Е [а, Ь). [43 (1) следует, что функция /(х) непрерывна на отрезке [а, 6), так что по теореме 1.1 множество Х, точек минимума /'(х) на [а, 6) непусто, Т е о р е м а 1, Пусть функция /(х) непрерывна на отрезке [а, 6] и на каждом отрезке [аг, а! „] (з = 1,..., гп), гдв а, = а, а т! = Ь, удовлетворяет условию (1) с постоянной Х;. Тогда /(х) удовлетворяет условию (1) на всем отрезке с постоянной Х = !пах Х, ! < 'ях Доказательство. Возьмем две произвольные точки х,уЕ [а,6).

Пусть а,, < х < а„, а, < у < а,т ! при некоторых р, з. Тогда [/(х) — /(у)[=]Х(х) — /(а )+ 2 (/(а!) — Х(а! !))+/(а,)— !=р — /(у)[< Х„!)х — а,[+[2" Хг(а!+! — а!)([+Х,]а, — у[< Х ]х — у]. П !=г Т е о р е м а 2, Пусть функция /(х) диффвренцируема на отрезке [а, 6] и гг производная /'(х) ограничена на этом отрезке. Тогда /(х) удовлетворяет условию (1) с постоянной = зпр [/'(х)], хе[ха) Доказательство.

По формуле конечных приращений для любых х, у е [а, Ь) имеем /(х) — /(у) = /'(у+ 0(х — у))(х — у) (О < д < 1). Отсюда и из ограниченности /'(х) следует утверждение теоремы. П Пусть функция /'(х) удовлетворяет условию (1) на отрезке [а, 6). Зафиксируем какую-либо точку у е [а, 6) и определим функцию д(х, у) = У(у)— — Х]х — у] переменной х (а< х < Ь). Очевидно, функция д(х, у) кусочно линейна на [а, 6), и график ее представляет собой ломаную линию, составленную из отрезков двух прямых, имеющих угловые коэффициенты Х и — Х и пересекающихся в точке (у, /(у)).

Кроме того, в силу условия (1) г(х) — д(х, у) > (Х вЂ” ~/(х) — /(у)[[х — у[ ')]х — у[ > О, х ф у, д(х, у) = /(у) — Х ]х — у] < /(х) Чх Е [а, 6], (2) причем д(у, у) = /(у), Это значит, что график функции Х(х) лежит выше ломаной д(х, у) при всех х е [а, Ь) и имеет с неи общуго точку (у, /:(у))г Свойство (2) ломаной д(х, у] можно использовать для построения следугощего метода [257], которыи назовем методом ломаных.

Этот метод начинается с выбора произвольной точки т е [а, 6] и составления функции д(х, х ) = /(х,) — Х ]х — х [ = р (х). Следующая точка х, определяется из условий ро(х,) = ппп р (х) (х, е [а, 6]); очевидно, х, =а или х, = Ь. Далее 1~ И 26 Гл. 1. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ б~рется новая функция р,(х) = тах(д(х, х!)! ро(х)), и очередная точ находится из условий р,(х ) = ппп р,(х) (х к)а, 6]) и т, д. (ри 1 2) е Е!Е Ь! Пусть точки х, х„..., х„(п > 1) уже известны. Тогда составляется функция Р (х) =тах(д(х, х„), р„,(х)) = тах д(х, х!), ольке и следующая точка х„ , определяется условиями р„(х„„)= ппп р (х), х„, ~ [а, 6].

(3) Если минимум р„(х) на [а, 6] достигается в нескольких точках, то в качестве х„, можно взять любую из них. 64етод ломаных описан. Очевидно, р„(х) является кусочно линейной функцией и график ее представляет собой непрерывную 'ломаную линию, состоящую из отрезков прямых с угловыми наклонами Х или — Х,. Из теоремы 1 следует, что р (х) удовлетворяет условию (1) с той же постоянной Х, что и функция /(х). Ясно также, что р„,(х)= тах д(х, х!) < тах д(х, х,.)=рк(х),, хе [а, 6]. (4) Кроме того, согласно (2) функция д(х, х,.) < /(х) (х Е [а, 6]) для всех'ь'= Х = О, 1,..., п, поэтому р„(х) < /(х), х Е [а, 6], и=0,1,...

(5) Таким образом, на каждом шаге метода ломаных за- О дача минимизации функции /(х) заменяется более простой задачей минимизации кусочно линейной функции р„(х), которая приближает /(х) снизу, причем согласно (4) (р„(х)) монотонно возра- С стает. Докажем теперь, Рко. 1АЕ АВС вЂ” график ро(х)=е(ж,го), А  — график что при неограниченном ро(к) = е(и х!), АВс,В! — гРафик РЬ(е), Аз~оса — гра- увеличении и метод ломафкк е(ьь га), АВВЬВаеьВ, — график гьд(е) Т е о р е м а 3. Лусть /(х) — произвольная функция, удовлетворяющая на отрезке [а, 6] условию (1). Тогда последовательность (х„), полученная с помощью описанного метода ломаных, такова, что: 1) 1пп /(х„)=!пп р„(х„,)=/,= 1п! /(х), причем справедлива оценка и ео е е *а|К Ь! 0 < /(х„е Ь) — /, < /(х„е !) — р„(х„„,), п = О, 1,...;, (6) 2) (х„) сходится к множеству Х, точек минимума /(х) на [а, Ъ] т.

е !пп р(х„, Х.) = О. 4 6. МЕТОД ЛОМАНЫХ 27 Доказательство. Возьмем произвольную точку х, е Х,. С учетом условий (3) и неравенств (4), (5) имеем р„,(х„) = ппп р„,(х) < е |к ь! < р„,(х„,) < р„(х„,,) = пип р„(х) < р„(х„) </(х.) =/„, т. е. последова- ЕЕ|ЕЕ! тельность (р„(хее!)) монотонно возрастает и ограничена сверху. Отсюда сразу следует оценка (6) и существование предела !пп р„(х „,)= р„'< ~;.

Покажем, что р, = /„. Последовательность (х ) ограничена и по теореме Больцано — Вейерштрасса обладает хотя бы одной предельной точкой. Пусть с„— какая. либо предельная точка последовательности (х„). Тогда существует подпоследовательность (х„), сходящаяся к о„, причем можем считать, что и, «... и„, < и„<... Заметим, что /(х!) =д(х|, х!) <р„(х!) < /(х;), т. е.

/(х!) = р„(х ) при всех ь = О, 1,, и. Тогда О < р„(х ) — т!и р„(х) = /(х,.)— е|к ь! — р (х„„, ) = р (х ) — р (х„,, ) < Х ]хь — х„„] при любом п и ь = О, 1,, и. Принимая здесь и = иь — 1, ь = иь, < иь — 1, получаем 0 < /(х„)— — р„,(х„) < Х [х„— х„] ()о > 2). Отсюда при 6 — со имеем /, < /(о„) = = 1пп /(х„ ) = 1пп р„ ,(х ) = р„ < /„, т. е. 1пп /(х„ ) = !!гп р„ ,(х ) = = р, = /,. Пользуясь тем, что рассуждения проведены для произвольной предельной точки о, последовательности (х„), убеждаемся в справедливости первого утверждения теоремы. Второе утверждение следует из теоремы 1.1.

С) Таким образом, с помощью метода ломаных можно получить решение задач минимизации первого и второго типов для функций, удовлетворяющих условию (!). Проста и удобна для практического использования формула (6), дающая оценку неизвестной погрешности /(х„е!) — /„ через известные величины, вычисляемые в процессе реализаций метода ломаных.

Этот метод не требует унимодальности минимизируемой функции,:и, более того, функция может иметь сколь угодно точек локального экстремума на,рассматриваемом отрезке. На каждом шаге метода ломаных нужно минимизировать кусочно линейную функцию р,(х), что может быть сделано простым перебором известных вершин ломайой р„(х), причем здесь перебор существенно упрощается благодаря тому, что ломаная р„(х) отличается от ломаной р„,(х) не более чем двумя новыми вершинами. К достоинству метода относится и то, что он сходится при любом выборе начальной точки *о.