Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 76
Текст из файла (страница 76)
В качестве начального приближения берется и, = ш Пусть известно к-е приближение и,~н 0', г'(и,)< у(и). Определим вспомогательное приближение й, как решение задачи (11) при 1 = 1(и„) = П: 1 < ~ ~ и, (аь и,) = 30. Поскольку и„еи )', то у(й,) < г'(и,)(1(и). Поэтому если й,ш У, 818 методы минимизАции Функций мнОГих пегедшнных [Гл, з то в качестве требуемой особой точки можем взять и> = й,. Допустим, что й,Ф <у. Тогда <аь йд> ) Ь' хотя бы для одного у Ф Ф 1(и,) (1 ( у < т), так что множество индексов 1, = = (уй <аь й„> ) Ь', у Ф 1(ид), 1 ~ у < т) Ф 8.
Положим ид+, = ид + яд (ид — ид), ид = шш [(Ьу — (ау, ид>)1(а„ид — ид>1. унт, (12) Из определения 1, н включения и, ~Й УУ следует, что (ау, и — и,> (ЬУ вЂ” (а, и,>)+((а, и,> — ЬУ) поэтомУ 0< ад(1. Покажем, что ид+1~в 11. Из выпУклости множества У и из ид ш У, йд ш У следует, что ид, ~ У, где У взято нз (11) при 1= 1(ид). Остается доказать, что <аь и,+,> ~ Ь' при всех у Ф1(и„) (1 < у < т). Если у ш 1„то с учетом определения (12) величины а, имеем <аь и,и,> <аь и„> + аа<аь й„ вЂ” и„> ( Ь', уж 1,.
(13) Если у Ф 1, 0 1(ид) (1 ( у < т), то <аь и,„,> = а,<аь йд> + +(1 — ад) <а„и,> < Ь'. Таким обРазом, показано, что и,а, ж 1У. Далее, поскольку 1(й„) ~1(и,) ~ 1(Р) и функция 1(и) выпукла, то 1(и,+,) ( а,у(йд)+ (1 — а„) 1(и„) ( 1(Р). Далее, пз включения и,+, ш У, где У взято нз (11) при 1=1(и„), следует, что 1(и,)с <=1(и,+,) = П: <аь и„.„> = Ь*', 1(1(т), В то же время для тех у, ш1„для которых в (12) реализовывается минимальное значение при определении и„, неравенство (13) превращается в равенство, так что у, ш1(и„~,), но уоФ1(и,). Следовательно, множество 1(и„+,) содержит по крайней мере на один элемент больше, чем 1(и,).
Таким образом, следующее приближение и,+,~и <У со аначением 1(и,ь,) <1(Р) построено, причем множество 1(и,+,) существенно шире 1(и,). Однако множества 1(и„)ж(1, ..., т) не могут бесконечно расширяться, и поэтому описанный процесс закончится на какой-то уа-й итерации, когда й,ш <у, причем ю й, — особая точка вадачи (1), (2) со значением 1(и) ( 1(в). Поскольку решаемая па каждой итерации задача (11) с 1=1(и,) имеет вид (1), (8) и для ее решения существует конечный метод, то н весь переход от точки и к точке и осуществим за конечное число шагов. Па 3-м этапе выясняется, не будет ли особая точна ю, построенная на 2-м этапе, решением задачи (1), (2), и в том случае, если и~ф<уа, осуществляется переход к следующей точке г ш <у, для которой 1(г)(1(ю), Для этих целей достаточно совершить один шаг несколько модифицированного метода условного градиента, приняв в качестве начальной точку и~, полученную на 2-м этапе.
А именно, сначала можно решить следующую квадглтичнон пгоггаымиРОВАнпи з»н задачу линейного программирования <1'(ю), е> = <Си»+ с, е> — !п1, е»и»з =(е =(е», ..., е")ш ~ Е": <ае е> <О, »ш1(и»)=(»: 1 <»<»и, <аь и»> = Ь'), <аь е> = О, » = и + 1, ..., г, — 1 < е' < 1, у = 1, ..., и). (14) Пусть е= ее †решен задачи (14), которое может быть получено, например, спмплекс-методом. Так как е 0»н»э, то Р = = (1'(и»), е ) = ш!п(1'(и»), е) ((1'(и»), 0) = О. Поэтому имеются »ял' две возмох»ности: либо р = О, либо э < О. Покажем, что в случае р = О точка и» вЂ” решение аадачи (1), (2). С этой целью возьмем произвольную точку и»я У, иФ и», и положим е = »(и — и»), где »>0 столь мало, что [е»[=»[и» вЂ” »а»~ <1 (1= 1, ..., и).
Если »»я1(и»), то <аь е> = <а„и — и»>1= (<а„и> — Ь')»~О. Если т+ 1 <»< г, то <аь е> = »(<а», и> — Ь»)= О. Следовательно. е = 1(и — »а)ые». ПоэтомУ Р= 0= (1 (ю), ее)((1'(и»), е). Пользуясь теоремой 4.2.2 тогда имеем 1(и) — 1(ю)> <1'(и»), и — и»> = <1'(и»), е>»' »>О при любом и»н У. Зто значит, что»генУе, т. е. задача (1), (2) решена.
Рассмотрим вторую возможность: р<0. Тогда ез — возможное направление убывания функции 1(и) в точке и». В самом деле, при достаточно малых с»> 0 с учетом того, что ее — решение задачи (13), имеем 1(и»+ аез) — 1(и) =(1'(и»), ее)а+ + о(и) = и([) + о(с»)/а)<0; если»ен1(и.) нлп и+ 1(»(з, то (аь и»+ ае. ) = Ь»+ а(а», е„,)(Ь~; если»4й1(и») (1(~»(п»)„ то (а», »а) ( Ь и (аь ю + аез) ( Ь . Тогда в качестве искомой точки з = <», 1(з) < 1(и»), можно ваять х = »е+ азез, где а» > 0— достаточно малое число, которое может быть найдено за конечное число шагов, например, перебором чисел и,=2 з (р=О, 1, ...). Описание 3-го зтапа закончено.
Отправляясь от точки з, полученной на 3-и этапе, можно снова перейти ко 2-му этапу при и = з, затем к 3-му этапу и т. д. В результате будет построена последовательность особых точек, на которой функция 1(и) строго убывает. Так как при С > 0 число особых точек конечно, то на каком-то шаге процесс, состоящий в последовательном применении 2-го и 3-го этапов, закончится нахождением решения задачи (1), (2). Таким обрааом, описанный метод позволяет за конечное число шагов найти решение задачи (1), (2) при С > О.
Существуют конечные методы решения задачи квадратичного программирования (1), (2) и при С > 0; об этих методах читатель сможет прочесть, например, в [7, 12, 13, 19, 21, 23, 30, 33, 41, 102, 111, 135, 159, 250, 256, 257, 261, 271, 3!4, 320, 330). О задачах кубического программирования и, в общем случае, полпномпнального программирования, когда з»инимизируеман функция является многочленом, см. [44, 52]. 32О МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [ГЛ, Ь Увражи евпя, 1.
Уточните оппсапие каждого этапа врпведеивого выше метода для задачи (1), (2) прп С =1 — едяввчиая матрица, а также при (1=Е«+ илв 0=(в = (в', ..., в«) шЕ«ч аз (в'(()ь 1=1, ..., в). 2. Примените описанный выше метод к задачам квадратичного программвровапвя вз упражвепвя 3 к 1 4.9 3. Пусть Г1 = (и = (х, у) зи Е'. — 1 ( х, у ( Ц вли 11 = (и = (х, у) еи ш Ез: О < в, р ( Ц. Найдите особые точкв задачв мвпвмвзацвв функций 1(и) = (х — а)'+ (у — Ь)', 1(в) = (ах+ Ьу)з ва этих множествах прв различных а, Ь, 4. Доказать, что множество точен мппямума квадратичной функции 1(и) = )Аи — Ь!з иа Е" совпадает со множеством решеввй системы АтАи = = АтЬ (см. пример 4.2,4).
5. Доказатть что квадратичная функция (1) либо достигает своей нижней грани ва множестве (2), либо кеогравячева связу. 3 8. Метод сопряженных направлений В описанных выше методах, использующих градиент функции, на каждой итерации учитывается информация лишь о линейной части приращения минимизируемой функции в окрестности полученной точки. С помощью этих методов точку минимума квадратичной функции удается найти, вообще говоря, лишь за бесконечное число итераций. Возникает вопрос: нельзя ли придумать метод, использующий лишь градиент функции, который позволяет найти точку минимума квадратичной функции на всем пространстве за конечное число шагов7 Если бы такая метод существовал, то можно было бы ожидать, что он сходится к точке минимума гладких функций быстрее градиентного метода, поскольку в окрестности точки минимума гладкая функция достаточно хорошо аппрокснмируется квадратичной функцией. Оказывается, методы с упомянутыми свойствами существуаот.
Одним из таких методов является метод сопряженных направлений. Опишем один из вариантов этого метода. 1. Сначала рассмотрим квадратичную задачу: .У(и) = — (Аы, и) — (Ь, и) — «-(п1; иен(1 = Е", (1) где А — симметричная положительная матрица, ЬшЕ". Тогда, пак было показано выше, справедливы формулы з'(и) = Аи — Ь, 1«(и) = А, н, кроме того, 1(и) сильно выпукла на Е" и достигает своей нижней грани на Е" в едияственной точке их такой, что 1" (их) =Аив — Ь = 0 или ые = А 'Ь. (2) Воаьмем произвольную начальную точку и, ш Е" и вычислим р, = з' (и.) .
Если Г (из) = О, то из = и — задача (1) решена. По- 32 о 5 81 метод сопРяженных нАЛРАВлении этому пусть Х'(и,) Ф О. Тогда положим и, =и,— а,р„а,>0, где величина ио определяется условием ~о (ао) = ш(п ~о(а), ~о (а) = Х(и, — ар,). а)~ Таким образом, первая итерация метода сопряженных направлений совпадает с итерацией метода скорейшего спуска.
Заметим, что (о(а) сильно выпукла, поэтому величина а, существует и определяется однозначно (см. ниже формулу (14)). Поскольку /о(0) = — <Х'(и,), ро> = — /Х'(ио))о(0, то ио>0. Следовательно, ~ (а,) = 0 = — <Х'(и, — аоро), ро> = — <Х'(и,), ро> = = — <Х'(и,), Х (и,)>. (3) Можем считать, что Х'(и,)Ф О, иначе и, = ио и задача (1) решена.
Так как р, Ф О, то Ар, оа 0 и множество Г,=(и~Е": <Ар,, и — и,> =0) представляет собой гиперплоскость размерности и — 1, проходящую через точку и,. Важно заметить, что искомая точка и также принадлежит Г,. В самом деле, поскольку матрицы А, А ' симметричны, то с учетом равенств (2), (3) имеем <Аро, ио — и~> = (Аро А ~Ь вЂ” ио> = (А ~Аро Ь Аи ) = <ро Х'(ио)> = О. Поэтому дальнейший поиск точки ио имеет смысл проводить в гиперплоскости Г,. Для этого нужно найти какое- либо направление р„ параллельное гиперплоскости Г,. Можно искать р„ например, в виде р, = Х'(и,) — рор„ро = сопИ.
Условие параллельности р, гиперплоскости Г, дает равенство <Ар„р,> = <Ар., Х'(и,) — второ> = О, т. е. ро = <Ар„Х'(и,) >/<Ар„ро>. Поскольку Х'(и)чьО, то р~ ФО. В самом деле, если бы р, =О, то Х (и) = )4р, и согласно (3) )Х'(и,)!' = ро<ро, Х'(и,) > = 0 — противоречие с условием Х'(и,) ФО. Из р,оьО следует, что Ар, ФО. Положим и,=и,— ар„а,>0, где величину а, будем определять из условия ~ (а,) = шоп ~, (а), ~, (а) = Х (и — ир,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
