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