Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 14
Текст из файла (страница 14)
1.7, 6). 11олученный отреаок [а„, Ь„] таков, что [а, Ь ] с [а ь Ь Д, У'(а + 0) < О, У'(Ь вЂ” 0) ) ) О. п согвасно теореме 8.0 тогда Га < (а,, Ь„). Выясним, в какой точке функция р„(и) = шах(р» ~(и)1 р(и, и„)) достигаот своего минимума па [аи Ь|). Из рпс. Е7 видно, что 52 методы минимизАции ФункциЙ ОднОЙ Переменной [Гл. 1 Далее, в силу теоремы 8.8 д(а, ь и«) (1(а, ~). Если 8(а ь и ) = = 1(а,), то из той же теоремы следует, что 1(и) = «(и, и„) при и зн ш (а„и и„], и поэтому д'(а«ь и«) = У'(а ~+О) и 1(и) = у(и, а« ~) (иш (а„ь и„)).
Тогда 1(и„) = 8(и«, а ) = д(и, а ~) = р« ~(и«). Однако выше было показало, что при выполнении (8) зто невозможно. Следовательно, д(а, ь и ) ( У(а„,) = а(а ь а ~). Аналогично доказывается, что Е(Ь ь и ) (1[Ь« — ~) «Е(Ь ь Ь ~). Таким образом, при выполнении (8) имеем д(ию и„) = 1(и ) ) ) р„,(и ), Е(а ь и ) (Е(а ь а ~), у(Ь ь и ) (д(Ь„о Ь ~). Это а„' и, а," а,, и Г Ю Рис. [рд а) У'(и — О) ) О, б) У'(и + О) ( 0; Л — график а(и, а« ~), СВ— графин а(и, Ь„,), ЕР— график Е(и, и ) значит, что касательные л(и, а,) и д(и, и ) пересекаются в некоторой точке с абсциссой и (а«1( и«( и«У', а касательные у(и, и«),у(и, Ь« ~)— в точке с абсциссой и«(и < и„< Ь ), причем а(и, и„) ) р (и) при и,(и(и„, з(и, а ))з(и, и«) при а (~и(и«, з(и, Ь«1))з(и, и,) при и„( и( Ь, Отсюда следует, что р„(и] = шах д(и, иг) )~ осек« вЂ” 1 й 1Е) МКТОД ПОИСКА ГЛОБАЛЬНОГО МИПИМУМА 53 ) )д(и, а, д) ) У(и, в„) пРи ад< н < ин, Р„д(и)~ )д(в, Ь„) > д(и, и„) при и„< и~~ Ьг.
Таким образом, формула (9) доказана. Из предположении индукции следует, что рю ~(и) строго возрастает па и„, Ьг1 н строго убываот на [аг, и„], так что минимум р (и) на [ап Ь|] достигается в одной из точек и„пли и„. Нетрудно видеть, что при У'(и — 0) ) 0 минимум функции р (и) достигается в точке и„, а при У'(и + 0] < 0 — в точке и„(см. рис. 1.7).
Вспоминая определение точен в„, и„, а„Ь, можем сделать следующие выводы: минимум р„(и) достигается в точке и ю ь являющейся абсциссой точки пересечения д(и, а„) и ю(и, Ь ) (аю < и„ш < Ь ), причем Л(и, аа), иш [аа, иаьд], р„(а) =— л(,ь), [и,, ь], функция р (и) на [аь июею] строго убывает, а па [и„ы, Ь|] — строго возрастает Индуктивное описание метода касательных для выпуклых функции закончено.
При его реализации будем иметь систему вложенных друг в друга отрезков [а,, Ь ] с... с [аь Ь,], причем согласно теоремам 8.5, 8.6 процесс либо завершится при каком-лнбо а определенном точки ииюн(У», либо (Га~(аа, Ь„) при всех в = 1, 2, ... Теорема 1 остается верной и для этого метода.
Посковьку минимум рю(и) на [аь Ь,] достигается на [а, Ью] точке июьь то информацию о ломаной р (и) впе [а, Ь ] хранить в памяти ЭВМ нет необходимости. Это значит, что на п-м шаге в памяти ЭВМ достаточно хранить величины а„, Ь„, У(а ), У(Ью), Л(а„+ 0), У'(Ью — 0). Нотрудно видеть, что для гладкой выпуклой функции описанный вариант метода касательных совпадает с методами п. 1, 2, прииенонными к отрезку [а+ б, Ь вЂ” 7] с выбором начальной точки и, = а+ б; попутно получено строгое доказательство равносильности методов из и.
1, 2. У п р а ж н е н и с. Применить метод касательных для минимизации функций У(и) = ]и~, У(и) = и', У(и) = [и~ + (и — 1)' на отрезках [ — 1, 1], [ — 1, 2], [О, 1], [1, 2]. 9 [О. Метод поиска глобального минимума В 1 6, 7 были рассмотрены методы, пригодные для поиска глобального минимума функций, удовлетворяющих условию Лппшица. Эти методы требовали для своей реализации знании постоянной Лившица минилшзируемой функции.
Опигпом другой метод поиска глобального минимума [279], не требующий априорного знания постоянной Липшица и вместо этого использующий угловые коэффициенты хорд минимизируемой функции меюкду определенными точками, получающимися при поиске минимума, Итак, пусть функция У(и) определена на отрезке [а, Ь]. Поиск минимума функппп У(и) на этом отрозке начинается с выбора двух точек ию = = аю= а, и,= г, = Ь и вычислония величины ею= ~1(и1) — У(ию) [У(ию — аю).
После этого полагаем й~ = р~ьа при Уа ) 0 и й~ = с при Уа = 0; здесь т ) О, р~ ) ! — параметры метода. Затем определяем следующую точку сю = (и~+ ию)!2 — (У(и~) — У(ию))((26,). Нетрудно показать (см. нике общий случай), что ию < юю < иь Пгрснумеруом точки ию, иь г, в порядке их возрастания, приняв и, = = а, ию = сю, ию = Ь. Предположим, что уже сделано Ь шагов и найдены точки ию, нь ..., аю (Ь ) 2), причем ию = а < ию « ..
ию-ю < ию = Ь. 54 мктоды 11ннпыпзлгнп! Фуннпнп ОднОЙ пнгк11ннноп !Гп. ! Опишем й+ 1-5 шаг метода. Определим величины (8'(и!) —,/ (и. ) ! 5 = ша. А 1игой иг — и1-1 Р,йз, бь)О, 8(е = 5Ь=-О, (2) лд(1) — ! (и — и )+ 1 (8 (и!) — 8 (и! )) З (и! — и, ) — 2 (8 (и!) + У (иг,)), 1 = 1, ..., 78. (3) После атого веребором значений Ль(!) (1 = 1...., (8) определим минимальный помер 8, па котором достигается !пах л„(!), т.
е. 18!8Ь Лй (8) = шах Ль (!), Лй (1) < Ль (8), 1= 1, ° ° °, 8 — 1 ° (4) 1и!8з Затеи положим и88! = (и, + и, !)12 — (7(и8) — 3(и,-!))/(2А) (5) н псрепумеруем точки ио, и1, ..., из, 81+! в порядке их возрастания, чтосы ис = а < и! « ... иь < и!81 = Ь. Метод описан. Будем предполагать, что параметры пз (2) таковы, что (6) т)О! р )р)1, й=12,,; вирр <оо. Ь>1 Точки 88 или ип получаемые методом (1) — (6), будем кратко называть иоискозыми точками. Из описания метода видна, что каждая поисковая точка имеет двойную пуморацню и двойное обоаначение; если точка появилась впервые и зто случилось на 8-м шаге, то она получает номер 8 и ооозначается через и„на каждом последующем шаге с помером й ) 8 та жо точка и, в зависимости от своего местоположения на (а, Ь) получает один нз номеров ! (О < ! < й) и обозначается через и! — адесь номер ! = !(й) зависит от номера шага.
В аависимости от обстоятельств мы будем пользоваться обоими обозначениями поисковых точек. Покажем, что точка 88+1, определяемая формулой (5), удовлетвори! т неравенствам и,, < иь+! < и, (здесь 8 = 8(й)). Б самом деле, из (5) имеем 11 8 8-1) !7) Поскольку в силу (1), (2), (6) ('("!)-'("1-1) ~ бй (8) то из (7) следует, что и, ! < и!8! < и,. где 1 ) О, рь) 1 — пара!гетры метода, выбираемые вычислителем.
Для каждого отрезка (и! „и1) введем сл!дующуго числовую характеристику: МЕТОД ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА 9 <е) 55 Таким образом, вслед за новой поисковой точкой ойчб па й+ 1-м шаге нонвляются два новых отрозка [и, ь ийтб] н [гй+н и„], длина которых с помощью (7), (8) оценивается так: (и, — и, ~) (1 — 1/р)72 < ш!п(и, — бътб гйьб — и, ~) ( ( шах(и, — гьтб гйы — и.
б) ( (и, — и, ~) (1+ 1<д)!2, (9) гдеО(д=(1+1!р)/2(1, г=г(й) (й=1, равенства (6.7) внеси ] У (иб) — У (иб <) ] /,1 [и,) — У [гй+ ) ] иб — иб — 1 !', — ой+1 2, ...). Проис того, пз нс- ]1[о' 1) — У(,,)] й+< иб — г Это значит, что ййт~ ) Пг (<с = 1, 2, ...). Поэтому еслп Уй = 0 (й = 1, 2, ...), то согласно (2), (6) дй = г я 0 (<г = 1, 2, ...); если нес Уб=ОпРнй=<,...,уг — 1, Ьй )О, то г<„)ш1п[т< Ру ])О (й= йе =-1, 2, ...).
11саче говоря, сущ< ствуст постоянная с1 такал, по б<й)д)0, 1г=<,2,... (10) С другой стороны, если фупкцпя 1(и) па [а, Ь] удовлетворяет условию Лнпгпнца, т. е. ]У(и) — У(г) < < Х(и — г], бр и, г би [в, Ь], 5 = сопж > О, (П) то 1.б ( Уч н следовательно, д<((юах(т< Уапррй[(со, й=1, 2, й>г ") (12) Т с о р е и а 1. Пусть убуббкб<ия 1(и) на отрезке [а, Ь] удовлетворяет условию (1!). Пусть последовательность (сй) построена лбетодом (1) — (6) и г — какая-либо предельная точка (гб).
Тогда 1пп У (г<,) = У (гв) и, кроме й того, .1 (г„) ( У [и<), г = О, 1, (13) Доказатольство. Поскольку ггФгь прп <Фй игв — продгльпан точка (гг), то существует последовательность отрсаков [и„нй. ь и„псе] (й. = 1, 2, ...), каждый пз которых содержит точку га п бесконечно много пансковых точек, отличных от г„п, кроне того, и, пб-б ( ибпьтп б ( < ит Птп ( ибогб (й = 1, 2, ...).
Введем гпюжоство дг(г„), состоящее пз всех тех п только тох номеров й ) 1, для которых либо июбгб — б < ибнйтп ь либо и ньтп ( и пьь Это чпачкт, что прп й бы Аб(г,) понскован точна сйтб попадает внутрь отрезка [и <ь< ь ибньб], образуя один нэ копцов следующего отрезка [и бьтп-б, ибнйг О]. Отбсгода в силу условия (4) внеси П„(т(й))~П,(<), б=<, ...,<г, йод~(г.), (14) где 0 ( у ( 1, Отсгода н из счетпостп пнонгоства Л" (гв) следуот, чтп 1пп (и <,) — и <й< ) = О, 1пп о„,<„) д -— - 1(ш и <й) — — г . (15) й-баб й <б ю Поскольку кагкдый иа отрезков [июп, ь ибнь<] содержнт бесконечно нного поисковых точек, то множество Дг(гг) также содержит бесконечно нного номеров.
Согласно оценка (9) 0 ( ию<й+<) — им<<,+ ) т ( У (ию<й) — июОО ), й ш Х (гв), 56 МЕТОДЫ МИНИМИЗАЦИИ ФУННЦИИ ОДНОЙ ПЕРЕМЕННОЕ )ГП ! Перепишем формулу (3) в виде Х(из) — д (иг,) Тз Л (!) =д,(иг — и ) (1+,, „, ) — 4д(иг), "аг 1 из — 1) (16) Взяв здесь 1 = тл(й), с учетом соотношений (8), (11), (12), (15) получим 1пп Н, (т (й)) = — — 42 (ов). (11) Далее, из (16) и (14) следует, что — 41(и») < Ль(1) ( Н»(тл(й)) дли каждого й»и Д»(ов) и всех 1= 1, ..., й. Кроме того, если (3) запишем в виде д (из) — д (из )», з Л (1) =-дь(и.— ие ) (! — ' — 4/(и. ), 1=1, ...,й, "Ь и1 — и»-1 (18) и примем здесь 1 = 1, то с учетам (14) будем имать — 41(и») ( Ль(!) ( ( Ль(ю(й) ) (й ш Л (о )).
Таким образом, 4д(и,) ) — Л»(тл(й)) при всех 1 = О, 1, ..., й (йш Л(о )), т, е. 4 ппп д(иг) > — Л„(т(й)) (йшЛ'(о )). Поскольку осела ппп д(из) = ппп х(о,) ( ппп д(о,) при лзобом р ( 1», то из продыдуОсгкн ЕК»ЛЬ ЕЛ»СО »цето неравенства имеем 4 ппп /(ог) > — ль(пг (йП для всех р(~й (й ем ел»чу шЛ'(ов)). Перейдем здесь к пределу прп й-+ оо, й»н д» (о ). С учетом (17) получим ппп д(ог)~)д(ов) при каждом фиксированном р) 1. Оценка елгкр (13) доказана.
Докажем, что 1пп д (од) = д (оь), Пусть с — какая-либо предельнаи ь точка последователшюстн (л (оь)) п пусть с = )пп д(оь ). Выбирая при ьн) необходвмостп подпоследовательность, можем считать, что (оь ) сходится к некоторой точке и . Тогда пз (13) следует, что д (ов) ~ (Х (юь) = с. С другой стороны, так как оценка (13) доказана для произвольной предельной точки (оа), то д (юв) ( У(о ) (1=0, 1, ...) и, следовательно, д(ю )(д(ов).
Таким образом, д (ю ) = — с = д (о ), т. е. (Х(о )) имеет единственную предельную точку с = у(о ). Это означает, что 1пп Х(о ) = Х(ов). ь Теорема 2. Лусть выполнены все условия теоремы 1 и, кроме того, пусть Функция г(и) на (а, Ь] имеет конечное число локальпь»к экстремумов, Тогдп любая предельная точка последовательности (оь) является точкой локального минимума Фуняции !(и) со значением с .= Пш д (оь). Доказательство. Сначала покажем,что если предсльпанточка оь последовательности (оь) такова, что а < оь < Ь, то из (о») можно выбрать две подпоследовательности, одна пз которых стремится к ов слева, другая — справа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
