Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 88
Текст из файла (страница 88)
Следовательно, е = т(и — ю) Е Е. Поэтому д = 0 = (Х'(ю), е,) < (Х'(ю), е). Пользуясь теоремой 4.2.2 тогда имеем (0 $9. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ 292 Гл. б. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 293 1(и) — 7(ю) > (Г'(ю), и — ю) =(Г'(ю), е)Ь ' > 0 при любом и Е Х.
Это значит, что ю Е Х„т. е. задача (1), (2) решена. Рассмотрим вторую возможность; )2 < О. Тогда е, — возможное направление убывания функции 7(и) в точке ю. В самом деле, при достаточно малых сх > 0 с учетом того, что е, — решение задачи (13), имеем 7(ю+ ае ) — 7(ю) = (1(ю), е )а+ о(а) = а()3+о(а)/а) < 0; если з ЕХ(ю) или их+1<э < а, то (а,, ю+ае )=Ь'+а(аг, е ) < Ь'; если з ф7(ю), 1<э <их, то (аг, ю) < Ь' и (ца ю+ ае,) < Ь'. Тогда в качестве искомой точки х = Х, 1'(г) < 7(ю), можно взЯть х = ю+ аое„где ао > 0 — достаточно малое число, которое может быть найдено за конечное число шагов, например, перебором чисел сто = 2 э, р= О, 1,.... Описание 3-го этапа закончено, Отправляясь от точки х, полученной на 3-м этапе, можно снова перейти ко 2-му этапу при и = г, затем к 3-му этапу и т.
д. В результате будет построена последовательность особых точек, на которой функциями(х) строго убывает. Так как при С > 0 число особых точек конечно, то на каком-то шаге процесс, состоящий в последовательном применении 2-го и 3-го этапов, закончится нахождением решения задачи (1), (2). Таким образом, описанный метод позволяет за конечное число шагов найти решение задачи (1), (2) при С > О. Существуют конечные методы решения задачи квадратичного программирования (1), (2) и пои С > 0; об этих методах читатель сможет прочесть, например, в (1; 33;18; 61; 203; 204; 222; 273; 319; 422; 471; 481; 586; 603; 606; 608; 612; 670; 738; 746; 759).
О задачах кубического программирования и, в общем случае, полиномиального программирования, когда минимизируемая функция является многочленом, см, 170; 83; 84; 527). Упражнения 1. Уточните описание каждого этапа приведенного выше метода для задачи (1), (2) при С=1 — единичная матрица, а также при Х = Е" или Х =(о=(ы,..., о ) е Е: аа < и < (Да, 1 =1,...,и). 2. Поимените описанный выше метод к задачам квадратичного программирования из упрв>к- нения 3 к й 4.9. 3.
пусть х=(п=(з, у)без: — 1<м у<1) или х=(и=(м, у)без: 0<и, у < Ц, найдите особые точки задачи минимизации функций 7(о) = (х — а) + (у — Ь), 1(и) = (ам+ Ьу) на 2 2 этих множествах при различных а, Ь, 13 4. Доказать, что множество точек минимума квадратичной функции 1"(х) =)Ам — Ь) на Е совпадает со множеством решений системы А Аэ = А Ь (см. пример 4.2.4), т б. Доказать, что квадратичная (нлн кубическая) функция достигает своей нижней грани на множестве (2), либо неограничена снизу 194). 9 9. Метод сопряженных направлений В описанных выше методах, использу>ощих градиент функции, на каждой итерации учитывается информация лишь о линейной части приращения минимизируемой функции в окрестности полученной точки.
С помощью этих методов точку минимума квадратичной функции удается найти лишь за,бесконечное число итераций. Возникает вопрос: нельзя ли придумать метод, использующий лишь градиент функции, который позволяет найти точку минимума квадратичной функции на всем пространстве за конечное число шагов? Если бы такой метод существовал, то можно было бы ожидать, что он сходится к точке минимума гладких функций быстрее градиенкного метода, поскольку в окрестности точки минимума гладкая функция достаточно хорошо аппроксимнруется квадратичной функцией. Оказывается, методы с упомянутыми свойствами существуют. Одним из таких методов является метод сопряженных направлений.
Опишем один из вариантов этого метода. 1. Сначала рассмотрим квадратичную задачу; ,7(х) = -(Ах, х) — (Ь, х) ч (п(; х ш Х =Е"1 где А — симметричная положительная матрица, Ь Е Е". Тогда, как было показано выше, справедливы формулы 7'(х) = Ах — Ь, Гл(х) = А, и, кроме того, 7(х) сильно выпукла на Е" и достигает своей нижней грани на Е" в единственной точке х„ такой, что ,7'(х,)=Ах„— Ь=О или х,=А 'Ь, (2) Возьмем произвольную начальную точку х е Е" и вычислим р = 1'(хо). Если 7'(хо) = О, то х = х, — задача (1) решена. Поэтому пусть 1'(х ) Ф О. Тогда положим х1 = хо — аорш ао > О где величина ао определяется условием до('хо) = шг'1 до('х)1 до(с" ) = 1(хо аРо) Таким образом, первая итерация метода сопряженных направлений совпадает с итерацией метода скорейшего спуска. Заметим, что д,(а) сильно выпукла, поэтому величина ао существует и определяется однозначно (см.
ниже фоРмУлУ (14)). ПосколькУ д '(0) = — (Г'(хо), Ро) = — ~У'(хо) 1~ < О, то а > О. Следовательно, д'(сг ) =0= — (Г'(хо — а р ), ро) = — (Г'(х,), р ) = — (Г'(х,), Г'(х )). (3) Можем считать, что 1'(х,) ф О, иначе х, = х„и задача (1) решена Так как ро ФО, то Ар, Ф 0 и множество Г, = (х Е Ь™: (Аро, х — х,) = О) представляет собой гиперплоскость размерности и — 1, проходящую через точку х,. Важно заметить, что искомая точка х„ также принадлежит ГР В самом деле, поскольку матрицы А, А ' симметричны, то с учетом равенств (2), (3) имеем (Ар, х„— х,) = (Аро, А 'Ь вЂ” х,) = (р, Ь вЂ” Ах,) = = — (р„у'(х, )) = О.
Поэтому дальнейший поиск точки х, ймеет смысл проводить в гиперплоскости Г,. Для этого нужно найти какое-либо направление р„параллельное гиперплоскости ГР Можно искать р„например, в виде Р~ = 1 (х,) — ЯРо, )уо = сопз( 294 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ пусть (4) (5) (6) (Ар,, р ) = О, г ф У', О < т', У' < й— У(,>,рз>=О, О<у « ' й, (г'(х.) г'(х.)) =О, г ф~, 0< т', 3' ~ ~й' Условие параллельности р, гиперплоскости Г, дает равенство (Арю р,) = = (Ар, 7"'(х,) — Д,ро) = О, т. е.
)7а = ( 4ро,7'(х1))/(Аро ро) Поскольку Г'(х1) ф О, то р фО. В самом деле, если бы р, = О, то Г'(х ) = )уор, и согласно (3) тогда (,Г'(х,)!' = )Ур(рю,7'(х,)) =0 — противоречие с условием 7"'(х,) ф О. Йз р, ~ 0 следует, что Ар, ф О. Положим х,=х, — а,р„а, >О, где величину а, будем определять из условия д (а,) =ппп д (а), д (а) = у(х1 — ар,). С учетом равенств (3) имеем д,'(0) = (Г(х,), -р,) = (7'(х,), — 7'(х,)+ Д,р,) = = — (7'(х,)!' < О, поэтому а, > О. Тогда д,'(а,) =0 = (У'(х, — а,р,), — р~> = — (7'(а~), р,) =О. Заметим, что Г'(х,) — 7'(х,) = А х, — Ь вЂ” Ахт + Ь = а1 Ар,.
Тогда в силу (3) и выбора р, получаем (Г( ) Г( )> = (Г( й) ро> = (Г(х ) — а1Аро р > = О Отсюда следует равенство (7'(*) Г( »=(Г( ) р +доро>=0 Таким образом, первые две итерации метода сопряженных направлений для задачи (1> описаны. Показано, что (Г'(х~) ро) = (Г'(х1) 7'(хо)> =О (Арз р~> = (Ар1 рь> =0 (7'( ),,) =(Г(хз), о) =(7'( ),Г(х И =(Г( ),7'(хо)) =0 Кроме того, заметим, что векторы Ар, Ар, линейно независимы. В самом деле, если т Арз+ т,Ар, = О, то, умножая это равенство скалярно сначала на р, затем на р„получим у = у, = О.
Можем считать, что 7'(х,) ф О, иначе х, = х„— задача (1) решена. Теперь у нас есть основание сделать следующее индуктивное предпо- ложение: пусть при некотором й > 2 уже найдены точки х„ х„..., х„ хс = х,. — а,.р., т' = О, 1,..., й — 1, где ь р,. = Г'(х,.) — )7,.р, фО, 13, = (7"'(хс), Ар,,)/(Ар,. „р,,), а величины а,.
> 0 определены из условий д„(а,) = ппп д,(а), д,(а) = 7(х; — арс), з' = О, 1,, й — 1; ьо е в. метОд сОпРяженных нАпРАВлений 295 и, кроме того, пусть Г'(х,.) ф О, ~ = О, 1,..., й, и система векторов (Арь, Ар„..., Ар, 11 линеййо независима. .'4 Тогда множество :1. Г„= (х Е Е": ('АРс, х — х ~,> = О, т' = О, 1,..., й — 1Т представляет собой гиперплоскость (аффинное множество — см. пример 4.1.5) размерности и — й. Поскольку из (5) следует (Ар,, х„— х...) = (р,, Ах, — А хс „) = (р,, У'(хД вЂ” У'(хс „, )) = 0 для всех г = О, 1,..., й — 1, то х„е Г .
Замечательно то, что х, е Г, так как согласно (2), (5) (Ар„х„— х, „) = (Ар,, А 'Ь вЂ” х,. „,) = (р,, Ь вЂ” Ах, „,) = = (р,, — 7"(хс,)> = О, г = О, 1,..., й — 1. Поэтому дальнейший поиск точки х„целесообразно продолжать в гиперплоскости ~„. Для этого нужно найти направление р, параллельное Г„ т. е. удовлетворяющее условиям (Ар,, р,) =О, 4 =О, 1,..., й — 1. Будем искать р„в виде Заметим, что р =Г(х ) — Кр (7) (12) » 'т ' 7(х) Г(х;.„,)=Ах, — Ах,, =а Ар ~ — О 1 й 1 (8 Из (4), (6), (8) следует (Ар,, р„) = (Ар„Г'(х ) — 13„р,,> = (Ар,, У'(х„)>— — Я(Арс, р 1) = (7'(х ) — У'(х ~,), 7'(х ))а,. ' = 0 для всех г = 0,1,..., й — 2 при любом выборе 13 в (7).
Поэтому для параллельности направления р, гиперплоскости Гь остается удовлетворить равенству (Арь „р„) =О. Отсюда имеем (Ар, п,Г'(х„) — )1„р„,> = = (Ар, о,у'(х„)) —,9 (Ар„„р„,> = 0 или А=(Ар, „Г( ь»7(Ар,, „р,,) (9) Заметим, что Р„ ф О, ибо в пРотивном слУчае 7'(х„) = 13ьР, „ и тогда в силу (5) имеем ~У'(х,)Г=Д,(7'(хь), р,) =О, что противоречит индуктивному предположению Итак, учитывая выбор направления р, и равенства (4), имеем (Ар,, рт) = О, ъ ф у', 0 < а, у' < й. (10) Следующее (й +1)-е приближение будем искать в виде хь ~, = хь — а„р„, аь > О, (11) где а„ определяется из условия д„(а,)=пппд (а), д„(а)= 7(х„— ар ).
Поскольку д,(а) — сильно выпуклая функция, то величина аь существует и единственна. С учетом предположений индукции и формулй (7) имеем дь'(0) =(7'(хь), — Р ) = (7'(х ), — 7"'(х,)+Д,Р,) =-(7'(х„)) <О. 296 Гл. З. МЕТОДЪ| МИНИМИЗА((ИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЪ|Х $9. метОд сОпРяженных нАпРАВлений 297 Это значит, что а„>0 и дг'(аг)=0=(У (хг+г) Рг) или (Г(х 1) Рг) (13) Отсюда нетрудно получить явное выражение для а,.
В самом деле, 0 = (7'(х„„,), р,) = (Ах„„— Ь, рь) = = (Ах„— огАЄ— Ь, р„) = (7'(х„), р„) — аг(АР„Р,). Так как р„~ О, то (Ар„, рг) ~ 0 и из последнего равенства вытекает Далее, заметим 7"'(хг) — 7'(х, х,) = Ах„— Ах +, —— о„АР,. Отсюда и из (4), (5) имеем (7 (хгх|) Рг) =(7'(хг) ггАРг Р) =О г =О 1 "— 1. Собрав все равенства (5), (13), (15), получим (Х'(х,), рз) =О, 0< г' < г < й+ 1. Из предположения индукции и равенств (16) следует (1'(хах,), ~(хг)) = (7(х„„,), р,.
+ Др,,) = О, г = 1,..., й, (7г(х„„), 7'(хь)) = ()'(х„~,), рь) = О. (15) (16) Отсюда и из (6) имеем (7'(хг), 7'(х,)) =О, гф~', 0<г, з<й+1. Наконец, покажем, что система (Ар,..., Ар,,) линейно независима, В самом деле, если 7 АР + 7 Ар, +...+7„Ар„=О, то, умножая это равенство на р| скалярно, с учетом (10) получим 77(АР,, р|) =О, у' = О, 1,..., й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
