XIV Аттетков и др. Методы оптимизации (1081420), страница 53
Текст из файла (страница 53)
Поэтому после суммирования обеих частей (8.34) по й Е Я получим Это неравенство означает, что ряд в его правой части сходится ~1Х). Следовательно, так как в > О, то !нп (х~ ' — х~! = О. (8.35) ь — ~сю Если множество Хв ограничено, то все элементы хь релаксационной последовательности (х ) принадлежат этому множеству, т.е. (хь) является ограниченной последовательностью и, согласно теореме Больцано Бейерштрасса [1], имеет хотя бы одну предельную точку х", которая будет пределом при Й, — ~ оо некоторой подпоследовательности (х *), выделенной из (х ). Тот же предел в силу (8.35) имеет и подпоследовательность (х"' ь).
Поэтому, переходя в (8.33) к пределу при й = й, — ~ оо, с учетом непрерывности Ига Тв(х) приходим к (8.31). ~ Можно показать*, что если выполнены все условия теоремы 8.1 и, кроме того, функция Тв(х) выпукла на допустимом множестве й, то справедлива оценка О < Тв(х~) — 1, < Сф, й Е 1Ч, С = сопв$ > О. Если же при этом целевая функция сильно выпукла и при построении при помощи (8.28) релаксационной последовательности (х ) выполнено условие О < вв < ь < жь = н < 2Ч/Т~, где э < Т вЂ”.- паримвтр сильной вьтуклости функции 1в(х), то последовательность (хя) сходится к точке х' минимума целевой функции на множестве Й и справедлива оценка ~х~ — х*~ < у"'~х — х*~, и Е И, причем О < д = = (1 — 2эх+ хзЬ~)'Тз < 1.
Отметим, что при выборе н = Ч/Аз знаменатьль геометрической прогрессии принимает минимальное зна шние о = (1 — "~з~йв)1~я. Смн Васиаьвв Ф.П. 8.4. Метод проекции точки на множество Нроиллюстрируем возможности метода проекции точки на множество на конкретном примере. Пример 8.7. Минимизируем квадратичную целевую функ- цию ув(хм х2) = 10х ~ — 4х1х2 + 7х2 — 4ъ 5(5х1 — х2) — 16 на допустимом множестве Я ((х ха) ~ $,2, х х2,Д О) В качестве начальной точки выберем хв = (О, — ъ 5) и используем два правила выбора значения жь в (8.28): постоянные значения вс = 0,1 (рис.
8.9, а) и вс = 0.,05 (рис. 8.9, б) и выбор вся = тся в процессе исчерпывающего спуска (рис. 8.9, в). На каждой и-й итерации проектирование точки х~ на множество й выполняем в соответствии с (8.23) по формуле х =Ро(х )=х +(5 — (п,х ))и, (8.36) где 5 = ~/5/2 и и = (1/у'2, — 1/~Г2) — нормальный вектор прямой, заданной уравнением х1 — х2 — у~5 5= О. Условием прекращения поиска точки х* = (х'„ х.*) минимума целевой функции является выполнение неравенства (х~ — х~ 4~ ( е1 = 0,01, после чего принимаем х' — х и )(х*) — 1(х ). Точное решение рассматриваемой задачи дает х* = (ъ'5, 0) и 1(х*) = — 66, причем ~/5 2,2361 с точностью 5 10 ".
Результаты численного решения, представленные в табл. 8.2, показывают, что по числу Лс итераций и достигнутому Таблица 8.9 приближению к точке х" в Х ив дс х данном примере предпочтение следует отдать вариан- тс = ":10 6 (2 234 0 002) ту метода проекции точки тс = 0,05 7 (2,235, — 0,001) с использованием исчерпы- все 4 (2,236, 0,000) вающего спуска. 8. ЧИСЛЕННЫЕ МЕТОДЫ Обратим внимание на различие в траекториях поиска точки х' при постоянных значениях ~г (см. рис.
8.9, а и б). Видно., что при большем из двух значений (при х = 0,1) точка минимума целевой функции достигнута за меньшее число итераций. Рис. 8.9 8.б. Метод проекции аитиградиеита 8.5.Метод проекции антиградиента Й = (х е Б'.": (а„х) = Ь„а = 1., т ~?, (8.37) где а; Е 1ч' и Ь, Е Ж -- заданные векторы и числа соответственно. Отметим, что в силу линейности ограничений множество Й является выпуклым. т Составим вектор Ь= (Ь1 ...
Ь„ц) и матрицу А размера тх т х и, строками которой являются матрицы-строки а,, а = 1, т. Без ограничения общности можно принять, что ВяА = т ( и (см. 8.2). В этом случае векторы а, г = 1, .т, линейно независимы. т Отметим, что для любой матрицы А матрица АА является симметрической, поскольку (АА ) = (А ) А = АА . Если векторы а; Е ат", 1 = 1, т, линейно независимы, то, согласно лемме 8.1, матрица АА невырождена и имеет обратную матрицу 1АА ) ', причем симметрическую, так как матрица АА симметрическая. Результатом проектирования точки х Е К" на замкнутое множество й с ~" является точка у б й, .либо совпадающая с х, если х Е й, либо лежащая на его границе дй (см. 8.3).
Это свойство операции проектирования позволяет при численном решении задачи оптимизации с о раничениями на каждой к-й итерации использовать обычный метод градиентного спуска в направлении антиградиента из точки х~ 1 в точку х~, а затем находить проекцию х Е Й точка х на множество Й (см. 8.4). Если при этом ххв ф й, то операция проектирования как бы возвращает ее обратно в допустимое множество й. Естествен вопрос: нельзя ли предварительно найти такое направление спуска, движение точки по которому при определенных ограничениях вообще не выводило бы ее за пределы допустимого множества й? Сначала рассмотрим случай, когда множество Й задано при помощи линейных ограничений типа равенства в виде 370 3.
ЧИСЛЕННЫЕ МЕТОДЫ Квадратная матрица Р=А (АА ) 'А (8.38) порядка п является симметрической, поскольку Р =(А (АА ) 'А) =А (А (АА ) ') =А ((АА) ') (А) =А(АА) 'А=Р. Кроме того, РР= (А (АА ) "А)А (АА ) 'А = = А (АА ) '(АА ) (АА ) 'А = А (АА ) 'А = Р., (Мгн, гн) = (М~гн, и~) = (Мгн, Мгн) = ~Миз~~ ) О. Собственными значениями идемпотентной матрицы могут быть только числа О и 1. В самом деле, если х ~- 'Π— собственный вектор идемпотенгной матрицы М с собственным значением Л,то Лх =Мх =М х =М(Лх) = Л х. Следовательно, (Лз — Л)х = О и Лз — Л = О, так как х ф О. Уравнению Лз — Л = О удовлетворяют только числа О и 1.
Очевидно, что собственными значениями проекционной матрицы также могут быть только числа О и 1. Нетрудно показать, что если Р проекционная матрица, то и Р* = 1„— Р . —. также проекционная матрица. Действи- т.е. Рз = Р. Квадратную матрицу М, удовлетворяющую соотношению Мз = М, называют идемпотентпной матрицей, а симметрическую идемпотентную матрицу . проекционной.
Отметим, что проекционная матрица является неотрицательно определенной,так как 8.5. Метод проекции аятитрядиеяти тельно, (Р*) = (1„— Р) =1„— 2Р+Рэ =1„— Р=Р* (8.39) ( *) = (1„— 1') = 1и — Р = Р'. (8.40) (Рш, (1„— Р)ю) = (ю, Р(1и — Р)ю) = О. (8.41) Вектор Рю является проекцией вектора ш на линейное подпространство т".р = (а Е К": ж = Рш). Если матрица Р имеет вид (8.38), то базисом в пространстве,Ср являются векторы а,, г = 1, тп, так как в этом случае для любого вектора у Е Ер имеем ти у = Рш = А (АА ) 'Аш = А д = ~е1,а,, (8.42) где д= (АА ) ~Аш, ай;, г'=1,те координаты вектора д.
Обозначим Р* = 1„— Р. Линейное подпространство,Ср* всех векторов вида Р" ю, ю е К", является ортогональным дополнением линейного подпространства т".р, так как для любых юншз ЕКи (Ршн Р'ш2) = (шм Р(1„— Р)шз) = О. Поэтому вектор ю~ = Рью ортогонален каждому вектору а;, г = 1, т. Таким образом, вектор ю~ ортогонален нормальному вектору а, Е К" каждой гиперплоскости (а„ а) = б;., г = 1,.т, ограничивающей множество й (8.37).
Следовательно, направление, задаваемое вектором ш~, параллельно этим гиперплоскостям и движение в этом направлении из любой точки а~ Е Й не выводит за пределы множества Й. При помощи матрицы Р любой вектор ю Е К" можно представить в виде суммы ю = Рю+ (1и — Р) ю, в которой слагаемые Рю и (1и — Р)ш ортогональны. Ортогональность слагаемых вытекает из равенств Р(1„— Р) = Р— Р~ = О, в соответствии с которыми 372 3. ЧИСЛЕННЫЕ МЕТОДЫ Линейные ограничения типа равенства.
Пусть в задаче оптимизации допустимое множество Й определено ограничениями типа равенства, т.е. имеет вид (8.37), а целевая функция Ях) дифференцируема в Ка. Предположим, что известна точка х Е Й. Рассмотрим функцию Ф(у) = То(х + Р'у), у Е Б'.", (8.43) где матрица Р определена соотношением (8.38). Для этой функции в силу правила дифференцирования сложной функции и симметричности матрицы Р справедливо равенство' 8гас1 ~р(у) = Р* 8гас1 Те(х), (8.44) где х и у связаны соогношением х=х +Р*у, х,уев".
(8.45) Теорема 8.2. Если у* стационарная точка функции у(у), то соответствующая ей точка (8.46) х =х+Ру удовлетворяет необходимому условию минимума целевой функ- ции 7е(х) на допустимом множестве Й вида (8.37). ~ Прежде всего убедимся, что х* Е Й. Используя представление (8.46) и условие хв е Й., заключаем, что (а„х') = (а, х )+(а„Р*у*) = (аох") =5,, в=1,.уп, поскольку вектор 1а'у' ортогонален каждому вектору линейного подпространства Ер, в том числе и векторам аь Следовательно, х* Е Й. Здесь и далее градиент функааи трактуется как всктор-столвеа.
8.й. Метод проекции аититрадиеята Так как у* является стационарной точкой функции Оо(у), то 8гас11р(у*) = О, и поэтому, учитывая (8.38) и (8.44) при у = у* и х = х', находим Р*8тас11о(х'") = 8тас17о(х*) — А (АА ) 'Абтас17о(х*) = = ятас1 )о(х*) + А Л = ягас1Д(х*) + ~ Лсас = О, (8.47) с=1 яс Цх, Л) = Ях) + ~~> Л,((ст,, х) — 6,), (8А8) т.е. удовлетворяет необходимому условию минимума целевой функции Д(х) на множестве й (8.37). ~и В соответствии с теоремой 8.2 стационарные точки целевой функции Д(х) на допустимом множестве можно определять, решая задачу безусловной минимизации функции 1р(у). В общем случае функция ~р(у) может иметь несколько стационарных точек, причем каждой ее стационарной точке у* будет соответствовать стационарная точка х* (8А6) функции ,Лагранжа (8.48).
При этом теорема 8.2 не гарантирует, что через минимизацию функции о1(у) можно найти все стационарные точки целевой функции. Однако если целевая функция является выпуклой функцией на выпуклом множестве Й, то для решения задачи минимизации такой функции достаточно найти хотя бы одну стационарную точку целевой функции в й, поскольку в любой стационарной точке выпуклая функция достигает наименьшего значения (см.
3.4). Отметим, что строго выпуклая функция может иметь лишь одну стационарную точку, так как где Л = — (АА ) 1А8гас1Д~х*), а Лс — координаты вектора Л Е К'и. Представив ограничения (8.37) в виде Ях) = (ас, х)— — 61 = О, г = 1,тн, и учитывая равенства гас1Ях*) = а„заключаем, что точка х' является стационарной точкой функции Лагранжа 374 8, ЧИСЛЕННЫЕ МЕТОДЫ она может достигать наименьшего значения на выпуклом мно- жестве только в одной точке. Пример 8.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
