Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 81
Текст из файла (страница 81)
(4) Здесь подразумевается, что матрица Х'(и„и„— рдХ'(ид)) невы- рожденная. Если 3дФО, У„;(и,) ~0 при всех /= 1, ..., п, то согласно формуле (3) для определения элементов матрицы Х (ид, ид — рдХ (ид)) достаточно знать первые производные У„;(и) в точках и = ид и и = (ид — рдХ„д(ид),..., нд — ~дХ„~(ид), ид"',... ..., ид)) (у = 1,..., и). Если же У„;(ид) = 0 при некотором /, то в силу (3) для определения /-го столбца матрицы Х'(и„и„— — рдХ'(ид)) придется вычислять вторые производные У ~ г(и) в точке и = (ид — рдУ„д (ид),..., ид — ~дХ„;,(ид), йд, ..., ид). Если при некотором й ~ 0 оказалось Х'(и,) = О, то про- цесс (2) или (4) прекращается: в этом случае и, — стационар- ная точка, и для выяснения того, будет ли ид ~ Гв, при необ- ходимости нужно провести дополнительное исследование.
По- этому будем считать, что Х'(и,)Ф О. А тогда для определения матрицы У'(и„, и,— 3„Х'(ид)) потребуется вычислить заведомо не все вторые производные У„;;(и), и в этом смысле метод (2) имеет преимущество перед методом Ньютона. С другой сторо- ны, оказывается, метод (2) на классе сильно выпуклых функ- ций сходится с такой же скоростью, как и метод Ньютона (9.8). А именно, справедлива Теорема 1. Пусть функоия Х(и)ш С'(Е"), 9~ и — о(д~<(У'(и) — Х'(о), и — о) 1ти, о~ Е", )д~О, (5) (Х' (и, о) — У'(о,в)(<К((и — о!+ (о — ю!) эи,о, юен Яэ, К)0, (6) где Яэ =)не=К":(и — и,(<В = шах~ — + (); ~~(Х'(и,)(~,(Рд(< ~ .
() (/е = О, 1, . „); начальное приближение и, таково, что (7) 34О методы минимизАции Функции многих пеРеменных [гл, 5 Тогда последовательность (и„), определяемая методом (2), сходится и решению ио задачи (1), причем справедлива оценка !ид — из)( — (Х'(и )!д', й = 0,1,... (8) Доказательство. Из условия (5) и теоремы 4.3.3 вытекает сильная выпуклость функции Х(и). Отсюда и из теоремы 4.3.1 следует существование и единственность точки ио. По индукции докажем идв=Яо, ад=)Х'(ид))(д '!Х'(и,)!, й=0,1,... (9) о При й= О действительно и, п Я„ад= [[' '!Х'(ио)!. Пусть при некотором й~ 0 точка и, уже найдена и справедливы соотношения (9). Поскольку у< 1, то из (9) следует, что а,(а.. Тогда из (5) при и= и,, и = и„имеем [д!ид — и,Р < 2а,(и,— и.! или 2 )ид — ио(( ~— ао (10) Обозначим х„= и„— рдХ'(ид) .
Заметим, что в силу (10) (хд — и, <(! ид — и, ! + ! Рад ! ! Х' (ид) ! ( — ао + анод < ~ — + Р)аз<В, 2 /2 так что хвои Я,. Далее, с учетом условия (7) имеем ! ид — х[, ! ~ (р ! Х' (ид) ! = Раад ( (Иао ( Р 2,Т [2~„.+ И) (~ 2я (11) Отсюда и из (6) следует ИХ'(ид, х„) — Х" (и„) И = ИХ'(и„х,) — Х'(и„и,) И (К(ид — х,! < [[/2. Тогда с помощью теорем 4.3.3, 4.3.4 получаем (Х' (ид, хд) $, Е/ = (Х" (ид) Е, $) + ((Х' (ид, хд) — Х" (ид)) $, $/ -з." > р ! Б !о — ([о/2) ! Б !' = ([о/2) ! В )о И вн Е" (12) Из (12) вытекает, что система уравнений Х'(и„, хд)$= 0 имеет единственное решение $=0, так что матрица Х (им хд) невы- рожденная, и точка идон определяемая условиями (2) или (4), существует.
Полагая в (12) $=(Х'(ид, х,)) 'з, зонЕ', получим ([о/2) !(Х'(и„х)) 'з!'~ <з, (Х'(и„х)) 'з) < !З(!(Х'(и„хд))-'з! или [(Х'(и„х,)) 'з! ~(2/[д) !з!, з жЕ". Это значит, что И(Х (и„х,)) 9[ с 2/[о. (13) Отсюда и из (2), (10) имеем (ад+1 ио! ~ ~[идо, ид)+ )ид — ио! <(2/[о)ад+ +(2/р)а, <(4/[д)а, < В, 341 % пд МЕТОД СТЕФФЕНСЕНА т. е. и„+, ы Я,.
Далее, из (3) следует ~ уп (и, и) (ии — о') = ~ (у„; (ид,..., и' ', и',, и")— Е=д д=д '~~д (и 1 ' 1 ~ 1 и 1 и 1И ) ')~~д (и) '~д1(и)~ 1 11' ' ' лг г. е Г (и, и) (и — и) = Г (и) — Г (и) ч и, и ее К". (14) Полагая в (14) и= идти и=и„и пользуясь (2), имеем Г(ид+ ) = Г(и„)+ Г(ад+о ид) (и+, — и,)= = (У (ид хд) 1 (ад+1 ид) ) (1 (ид~ хд) ) У (ид), Отсюда с помощью (2), (6), (11), (13) и предположения индукции (9) получим 2 ад+„= ) Г (ид+д) ) ( К (! ид+, — ид ! + / ид — хд )) — ад ( и (К~ — ад+ рад) — ад = К( — + р) — ад( 4+ ~) — (Ч" 'а 7 = д +— Рассуждения по индукции закончены, существование последовательности (и,), определяемой методом (2), и соотношения (9) доказаны. Наконец, из (5) при и = ими = ид сучетомравенства Г (и„) = О имеем р ~ ид — ид ~д ( (Г (ид) — Г (и ), ид — и„) ( ад ( ид — ид) или )ид — ид )(ад((д.
Отсюда и из (9) следует оценка (8). Теорема доказана. Недостатком метода (2), как видно из (7), является требование достаточной близости начальной точки и, к искомой точке ид. 2. Как мы убедились, описанные выше методы Ньютона, Стеффенсена на классе сильно выпуклых функций имеют квадратичную скорость сходимости. На основе этих методов, немного усложнив их, можно получить методы, имеющие более высокий порядок сходимости. Примером такого метода является следующий (316] юд = и~ (У (ид хд) ) Х (ид) ад+1 юд (У (ид хд) ) Х (ид) (15) где х,= и„— рдГ(ид), рд — числовой параметр, й= О, 1, ... На каждой итерации метода (15) последовательно решаются две системы линейных алгебраических уравнений вида (4) с одной и той же матрицей, но с разными правыми частями. Таким з4з мктоды минимизации егнкции многих пкгвмвнных [гл.
з обрааом, метод (15) не намного сложнее метода (2). Можно показать [83, 316), что на классе сильно выпуклых функций при выборе хорошего начального приближения метод (15) имеет кузь бическую скорость сходимости: ) иа — из [( (Сд (й= О, 1,...). Если в (15) считать р„ (й = О, 1, ...), то х, = и„, У'(им х,) = = Х" (и,) и в результате приходим к модифицированному методу Ньютона, в котором матрица вторых производных обновляется через два шага и который также имеет кубическую скорость сходимости.
Об итерационных методах высокого порядка сходимости для решения задачи минимизации (1), для решения систем уравнений см., например, [4, 8, 19, 20, 45, 54, 73, 76, 111, 209, 238, 239, 301, 330). 4 11. Метод покоординатного спуска [ь1 рд=е;, 4=й — и[ — )+1, (2) где [ — [ означает целую часть числа Ып.
5'еловке (2) обеспе(ь1 чивает циклический перебор координатных векторов е„е„..., е, т. е. р, = е„..., р„, = е„, р„= е„..., р,„, = е„, р,„е„... Вычислим значение функции У(и) в точке и =иь+а,р„и про. В предыдущих параграфах мы рассмотрели методы, которые для своей реализации требуют вычисления первых или вторых производных минимиаируемой функции.
Однако в практических задачах нередко встречаются случаи, когда минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление ее производных с нужной точностью требует слишком большого объема работ, много машинного времени. В таких случаях желательно иметь методы минимизации, которые требуют лишь вычисления значения функции.
Одним из таких методов является метод покоординатного спуска [4, 11, 153, 171, 326). 1. Сначала опишем этот метод для задачи У(и)- 1п1; и«У=Е". (1) Обоаначим е,=(0, ..., О, 1, О, ..., 0) — единичный координатный (базис) вектор, у которого 1-я координата равна 1, остальные равны нулю 1= 1, ..., и. Пусть и,— некоторое начальное приближение, а а, — некоторое положительное число, являющееся параметром метода. Допустим, что нам уже известны точка и,« «Е" и число а, > О при каком-либо й > О. Положим МЕТОД ПОКООРДИНАТНОГО СПУСКА $111 верим неравенство 1 (ив+ а„р,) < 1 (и,) .
Если (3) выполняется, то примем иьь1 = иь+ и,рм а„+, — — и„. (3) (4) Б том случае, если (3) не выполняется, то вычисляем значение функции 1(и) в точке и = и, — а,р, и проверяем неравенство 1 (и„— сл,р,) < 1 (и,) . (5) В случае выполнения (5) положим (6) иьь~ = иь — иьрм яь+ю = яа. Назовем (к + 1)-ю итерацию удачной, если справедливо хотя бы одно из неравенств (3) или (5). Если (й + 1)-я итерация неудачная, т. е.
не выполняются оба неравенства (3) и (5), то полагаем Хид, 1д = П, иь = ид „т„ аз+1 — †, 1Ь Чьи ИЛИ из Чань- +1 или 0(й ( и — 1; (7) из+1 —— иь, здесь ). (О < Х < 1) — фиксированное число, являющееся параметром метода. Условия (7) озпачают, что если за один цикл иэ и итераций при переборе направлений всех координатных осей е„ ..., е. с шагом а, реализовалась хотя бы одна удачная итерация, то длина шага и„ не дробится и сохраняется на протяжении по крайней мере следующего цикла из и итераций. Если же среди последних и итераций не оказалось нн одной удачной итерации, то шаг а, дробится.
Таким образом, если на итерации с номером к = й„произошло дробление ам то 1(иь,„+ аь е1))1(иь ), 1(иь — иь е1)>1(иь ) (8) при всех 1=1, 2, ..., и. Метод покоординатного спуска для задачи (1) описан. Справедлива Теорема 1. Пусть функция 1(и) выпукла на Е и принадлежит классу С'(Е"), а начальное приближение и, таково, что множество М(и,) = (и ж Е: 1(и) < 1(и,) ) ограничено. Тогда последовательность (иь), получаемая описанным методом (2)— (7), минимизирует функцию 1(и) на Е и сходится ко множеству (Ть.
Доказательство. Согласно теореме 2.1.2 1 ~ — со, 17 Ф 8. Из описания метода (2) — (7) следует, что 1(и,„,)< < 1(и,) (к = О, 1, ...), так что (и~~ я М(и,) и существует 11ш1(иь)) 1в. Покажем, что найдется бесконечно много номеров йь ..., к„, ... итераций, на которых шаг сс„дробится, и поэтому З44 мвтоды минимизации вгнкции многих пвгвмвнных ~гл. ъ Пшад = О.Допустим противное: пусть процесс дробления конед в чен, т. е. ссд=а> О при всех 1с > Х Обозначим М„=(и: и = =и„+аге,~иМ(и), и=1, ..., п, г=О, ~1, ~2, ...) — сетку (решетку) с шагом а. Из описания метода покоординатного спуска при а„ =а, й ~ А7, следует, что начиная с номера Ас все последующие циклы из и итераций будут содержать хотя бы одну удачную итерацию, и на каждой удачной итерации бу- дет происходить переход от одной точки сетки М к другой со- седней точке этой сетки.
По определению удачной итерации переход от точки к точке сопровождается строгим уменыпением значения функции У(и), поэтому каждая точка сетки М„ бу- дет просматриваться не более одного раза. Но множество М(и,) по условию ограничено, и поэтому сетка М„состоит из конеч- ного числа точек. Следовательно, процесс перебора точек этой сетки закончится через конечное число итераций определением точки ид (й ) Лс), для которой выполняются неравен- ства (8) при всех 1 = 1, ..., и.
А тогда вопреки допуще- нию придется дробить число ад = а. Полученное противо- речие показывает, что процесс дробления ад бесконечен н Пш ад = О. д-~оэ Пусть Й, < 1сд «... Й„<...— номера тех итераций, на ко- торых длина шага а„дробится и выполняются неравенства (8).
Так как последовательность (и,) принадлежит ограниченному множеству М(и,), то из (ид ) можно выбрать сходящуюся под- последовательность, Вез умаления общности можем считать, что сама подпоследовательность (ид ] сходится к некоторой точке и . С помощью формулы конечных приращений из (8) имеем (Х'(ид +0 ад е;),е;)ад )О, (Х'(ид — 0 ад,„е;), е;)( — ссд ) ) О, откуда Х;(ид + О~ад е;) О, Х;(ид — О„,ссд е;) ( (О, 0<0~, 0 <1 при всех 1=1, ..., и и т=1, 2, ...
Пользуясь тем, что Х(и)сн С'(Ь'") н 1пп ад = О, отсюда получим Х д(ие) = т = О (1 = 1,..., п), т.е. Х'(и ) = О. В силу выпуклости Х(и) тог- да нее= Па. Следовательно, 1пв Х(ид) = 1пп Х(ид ) = Х(иа) = д 7В = Хе. Таким образом, последовательность (и„) является миними- зирующей. Отсюда и из теоремы 2 1.2 следует, что р(иь Уе)-д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
