XIV Аттетков и др. Методы оптимизации (1081420), страница 51
Текст из файла (страница 51)
П е р в а я и т е р а ц и я . 1. Вычисляем Д|1 = В, 'Д|1 = (2 1) и приведенный градиент в точке х~: ж Нд (дно дало'1 дно|| ~ах, д.,! ая, = ( — 2х|+ 2хз 2хз) — (2х| — 2хг)Д11 = ( — 1 2) — (2 1) = ( — 3 1). Так как из = — 3 и из — — 1, то в соответствии с (8.16) име- Ж емрз = цз =3 ирз = — цз хз = 1, тю ри=(3 1) О) ' О) , '1) ' 111 50 Переходим к п. 2 алгоритма, поскольку ~р~~,~ = ъ'Р01 ) ез = 0,1.
См.: Рсклейтис Г., Репввндран А., Рэясдел Л. 8.2. Использование приведенного градиента 353 2. Из (8.13) находим р18 — — — Я1р~, — — — (2 1)(3 — 1) = — 5 и формируем вектор р' = ((рн1) (р~1) ) = ( — 5 3 — 1), задающий возможное направление спуска из точки хо. При помощи (8.17) на множестве Х1* = (1 Е,7: р~~ ( 0) = 11, 3) вычисляем *з ~1 Р1 Рз Минимизируя в полуинтервале (О, зс1] = (О, 1/5) функцию ф1(зс) — /О(Х +лср ) — —,(Я(Х +лср ), Х +лср )— 2 = — (Ях, х ) +зс(с1х, р ) + — Яр, р )., находим 11,1хо р') 1 1 Юр1, р') 13 ' 5' вычисляем точку х1 = х" + зс~р' = (8/13, 19/26, 12/13) и переходим ко второй итерации, возвращаясь к п. 1 алгоритма.
ВтОрая ИтЕрацИя. 1. МНОжЕСтВа ИпдЕКСОВ,1о И,уо не изменились, и поэтому %2 = %1 = (2 1). Вычисляем приведенный градиент в новой точке х; 2 х в 73 241 3 9 — ~+ 1.18 1З) 13 13 Поскольку базисное переменное осталось прежним, то вектор рл, найдем как сопряженный с вектором р1, 2 1 2 2 124 ! 1 ра,— — -и + ра,—— )241)2 9 1 (9/13)2(12 + 3') 3 18 Переходим к п. 2, так как )р2~/ = 450/169 ) сз = 0,1. 354 В. ЧИСЛЕННЫЕ Л1ЕТОДЪ| 2. При помощи (8.13) находим вектор 18 т 180 рй = — Х~ри — — — —,(2 1)(7 — 24) 169 169 и формируем вектор р ((рв) (рн~) ) (10 7 24) определяющий направление спуска из точки а~. Длина этого вектора для дальнейших вычислений на этой итерации не т имеет значения. Поэтому примем рг = (10 7 — 24) . ИспользУЯ (8.17), на множестве 2г — — (г 6,7; Р~~ ( О) = 13) вычислЯем 00 <ц Яг = шш Минимизируя в полуинтервале (О, нг) = (О., 1/26] функцию находим (д' р') г = ~Щ,г рг) — 26— и вычисляем точку х = ж'+игр = (1,.
1, .0). Поскольку нг —— = хг, то переходим к п. 3. 3. Так как индекс 1 = 3 Е,7г принадлежит множеству,7.~ = =,71~ = 12, 3), т.е. обратилось в нуль свободное переменное из, то переходим к третьей итерации, возвращаясь к п.1 алгоритма. Третья итерация. 1. Снова множества индексов,7~ н и,7~ остались прежними, и поэтому Хз = Х1 = (2 1). Находим приведенный градиент в новой точке жг: из =д~~ — дзнХз = = (О 0) — 0- (2 1) = (О 0). В соответствии с (8.16) будет нулевым и вектор р~~,.
Так как )рз~,,( = 0 ( ез = 0,1, то дальнейшие 8.2. Использование приведенного градиента 355 вычисления прекращаем и полагаем ш* = шз = (1, 1, 0), Д(,в*) = = уо(жз) = О. Функция Д(а) является выпуклой. Поэтому а* — точка наименьшего значения этой функции на множестве й, определяемом заданными ограничениями. Применение сопряженных направлений позволило найти точку ш* за две итерации, поскольку минимизируемая функция является квадратичной, а свободных переменных всего два. Выполним вторую итерацию по основному алгоритму метода приведенного градиента и убедимся, что для достижения точки ш* потребуется большее число итераций.
Согласно и. 1 этого алгоритма, используя координаты вычисленного в точке а~ = (8/13, 19/26, 12/13) приведенного градиента и2 = (9/13 27/13), в соответствии с (8.16) находим координаты р~~ ~ = — и2~ ~т~~ 1 = — 171/328 и р~~ ~ = — па~ ~л~~ ~ = — 324/169 вектора р~~„—— (9/328)( — 19 — 72) . Ясно, что ~р~~,~ ) ез = 0,1. Поэтому переходим к п. 2 алгоритма. -г 496 Вычислив вектор рн — — — М2ра, — — — (в данном случае этот 169 вектор число), сформируем вектор ря = (110 — 19 — 72) опуская множитель 9,1328. На множестве Х~ — — (2, 3) находим йз = ш1п~ — а ) =шш(, ) = — -0,01282. етт~, рР)) 26 19' 13 72 78 1 Р„ Функция ~~2(и) = Д(:и + ир ) достигает минимума при (Яш1, р2) 4230 ) 26 43450 0 00374 < Итак, получаем точку жз =,в1+ йзр = (1.,0333, О 6596, 0,6535).
Сравнение расстояний (ж1 —,и'! = 1,0356 и (:вз — и") 0,7376 показывает, что вторая итерация, выполненная по основному алгоритму метода приведенного градиента, привела лишь к некоторому приближению к точке ш'. 8. ЧИСЛЕННЫЕ МЕТОДЫ 8.3. Проектирование точки на множество Выше (см.
8.1) отмечено, что непосредственное применение к численному решению общей эидачи (8.1) нелинейного программирования одного из мегподов спуска может привести к тому, что точка х ', найденная на некоторой й-й итерации, выйдет за пределы доеьиспсимого мноэесества й. Чтобы этого избежать, можно полученный при помощи рекуррентных соотношений (4.20) или (4.36) результат подвергнуть операции проектирования точки на множество Й. Определение 8.2. Проекцией точки х Е К" на лвноэесесгпво й С Жа называяот ближайшую к х точку у Е й этого множества и обозначают ее Рп(х), т.е.
такую точку у = Рп(х), что (у — х! = 1пГ ~я — х! = р(х, Й), вен (8.18) где р(х,й) расстояние от точки (элемента) х до мнолеества Й. 1. Если х Е й, то Ро(х) = х. *Сил Васильев Ф.П. х На рис. 8.4 дана геометрическая интер- претация определения 8.2 в случае плос- Р,„йяд кости. Если х Е Й, то в соответствии с (8.18) Рп(х) = х. Проекция точки х ф й Ф ьл на множество Й может и не существо- вать вовсе. Например, в случае, когда Рис.
8.4 Й = (х Е К"; ~х ~ < 1) — открытый единичный шар в 2", для любой точки х ф й имеем р(х,й) = )х) — 1. но не существует точки у Е Й, для которой было бы выполнено (8.18), т.е. )у — х~ = )х~ — 1. Следовательно, не существует и проекции точки х ф Й на открытый шар Й. Пере 1ислим основные свойства оперещии проектирования* точки на множество. 357 8.3. Проектирование точки на множество 2. Если й замкнутое множество, то любая точка х имеет проекция! у = Рп(х) на множество й. Если при этом й— выпуклое множество, то проекция точки х на Й единственна.
На рис. 8.5 точка х имеет две проекции у! и уя на невыпуклое множество Й и единственную проекцию у на выпуклое множество Й. Рис. 8.6 Рис. 8.8 3. Точка у является проекцией точки х Е К" на замкнутое выпуклое множество Й тогда и только тогда, когда для любой точки я Е Й выполнено неравенство (8.19) (я — у,х — у) <О, т.е.
угол со между векторами я — у и х — у не является острым !рис. 8.6). 4. Если Й выпуклое замкнутое множество. у! —— РП1х!) и у2 = Р!!(х2) - - проекции точек х! и х2 на й, то Ь! У2! ~~ 1х! х21~ т.е. длина проекции отрезка на выпуклое множество не превосходит длины самого отрезка (рис. 8.7). Эти свойства, важны для обоснования Рис. 8.Т и анализа сходимости методов, использующих операцию проектирования точки на допустимое множество й. Докажем наиболес часто применяемое неравенство 18.19). Для этого рассмотрим функцию Ф1я) = ~я — х~2, я Е й, при произвольной фиксированной точке х е Ев. Эта !рунн!!ил 358 3. ЧИСЛЕННЪ|Е МЕХОДЪ| 0 < (8гас1Ф(у), л — у) = 2 (у — х, я — у) = — 2 (в — у, х — у), что равносильно (8.19) для любых я Е Й.
Из проведенного доказательства следует, что проекцию фиксированной точки х Е ж" на замкнутое выпуклое множество Й с вг' можно найти путем решения задачи минимизации Ф(я)=~я — х~ — ~шш, ябЙ, (8.20) квадратичной функции на множестве Й„что согласуется и с определением 8.2. Однако трудность решения этой задачи непосредственно связана с формой задания множества Й. Рассмотрим примеры множеств, проектирование точки на которые не представляет особых затруднений. Пример 8.3. Вели Й = 1л Е ~и: ~в — хв~ < Ц замкнутый единичный шар с центром в точке хв Е |С", то, согласно определению 8.2 проекции точки на множество, для точки х ф Й имеем !у — х! = 1п| 1я — х~ = 1х — хо~ — 1 ~~-жь!<1 Нетрудно проверить, что этому равенству удовлетворяет точка х — хв у = Рп(х) = хо+ ~х — хв~ ' (8.21) Используя неравенство Коши Буняковского, убеждаемся, что она для любой точки я выпуклого замкнутого множества является сильно выпуклой на замкнутом выпуклом множестве Й С Ки (см.
пример 3.14), а значит, и просто выпуклой, Так как она определяет квадрат расстояния между точками а и х, то, согласно определению 8.2, проекция точки х е Ки на множество Й должна быть точкой минимума этой функции. В силу теоремы 3.15 выпуклая функция Ф(я) достигает минимума в точке у Е Й тогда и только тогда, когда выполнено неравенство (8тас|Ф(у), я — у) > О. В данном случае 8тас1Ф(я) = 2(в — х) и, следовательно, 8.3.
Проектнровннне точки на множество й удовлетворяет неравенству (8.19): = ( — — — — ) = х — хо х — хо 1 я — хо— ,х — хо— (х — хо!' (х — хо!) 1 ) (л — хо, х — хо) — ~х — хо~+1 ( (х — хо! 1 ) 1я — хо! ~х — хо~ — ~х — хо!+1 = ~х — хо~ — (1 ~х хо!) (1 !з хоИ ( О, (в — у, х — у) = (1- <(1 поскольку (х — хо~ ) 1 при х ф й и ~я — хо( ( 1 при я Е Й. Множество й = (я Е ~н: ~я — хо~ = 1) замкнутое, но не выпуклое. Для точки хо ф й существует бесконечное множество проекций на Й, а для всех других точек х такая проекция единственна и может быть найдена при помощи (8.21). Пример 8.4. Гиперплоскость Й = (я б Б'.": (и, я) = 6), (8.
22) у = Ро(х) = х+ (Ь вЂ” (и, х))п. (8.23) Убедимся, что точка у, определяемая соотношением (8.23), удовлетворяет неравенству (8.19) при любых я Е й, т.е. при (п,я) =Ь (в — у, х — у) = (л — х — (Ь вЂ” (и, х))п, х — х — (6 — (и, х))и) = = — (6 — (п,х)) (я,п)+ (Ь вЂ” (и.,х)) (х,п)+(Ь вЂ” (п,х)) /и/~ = = — 6 + 6(п, х) + 6(х, п) — (х, и) + (Ь вЂ” (и, х)) = О. где и Е К" - единичный нормальный вектор этой гиперплоскости, а 6 постоянное чинно, является замкнутым выпуклым множеством (см. 3.1). Проекцию точки х ф й на множество й будем искать в виде у = Ро(х) = х+ Ли, Л = сопяС. Найдем число Л из условия у Е й, т.е. (и, у) = (и, х+ Ли) = 6. Отсюда Л = 6 — (п,х),поскольку (п,п) = )п)з = 1,и 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
