XIV Аттетков и др. Методы оптимизации (1081420), страница 55
Текст из файла (страница 55)
Метод ироеяции еитигредиеита т.е. нетривиальная (поскольку Л ф 0) линейная комбинация 00 линейно независимых векторов а„г е,у', равна нулевому я вектору. Это противоречие доказывает, что р~ у= О. Спуск в направлении вектора р но нарушит ограничение (а.,х) < бз которое при построении матрицы Р„* уже не рассматривается как активное, если (а~, р~) < О. Убедимся в этом, для чего умножим (8.58) скалярно на вектор Р',а. и запишем (Р~а~,ю') — Л.
(Ряа.,а ) — ~ Л; (Р~а.,а;) =О, (8,59) Поскольку (Р*аз, а,) = О., г Е А, .то сумма в левой части (8.59) равна нулю. Поэтому, .учитывая, что матрица Р* симметрическая и неотрицательно определенная, из (8.59) получаем (Рь'а,яо ) =(а.,Р,'то ) =(ао,р ) =Л, (Р~'ау,а ) <О, (ь) -ь поскольку Л < О. Следовательно, вектор р задает возможное направление спуска.
Если ~ре ~ < ез, то предстоит новая проверка условия прекращения последующих итераций, приводящая либо к завершению решения задачи, либо к удалению из множества,7~ еще одного индекса, у, для которого множитель Лагранжа Лз < О, и Ф) 1 построению очередной проекционной матрицы и т.д. Если же ~р ~ > ез, то для определения направления спуска, которое задано вектором ре, при помощи (8.51) и (8.о5) проводим описанную выше процедуру выбора значения тгя и нахождения точки х, ь что позволяет затем перейти к 1Й + Ц-й итерации.
Пример 8.9. Решим методом проекции антиградиента зо,- дочу неае1ротичного нроерамиироеания < Д(хмхз) = 2х~1+2х~~ — 2х1хз — 4х1 — бхз — ~ пцп; хо+ха — 2(0, х~+5хз — 5(0, — х1(0, — хя(0. 3. ЧИСЛЕННЫЕ МЕ ХОДЫ Целевую функцию представим в виде Хв1х) = — Ях, х) + 1 + 1с, х), х е Кз, где т с = ( — 4 — 6) .
Вычислим антиградиент этой функции ю = — 8гас1Уо(х) = — Ох — с = 4 — 2 х~ — 4 4 — 4х1+ 2хэ т и в соответствии с (8.52) обозначим а1 = (1 1), Ь1 = 2, аз = =(15), Ьз=5, аз=( — 10), а =(Π— 1) и Ьз=Ь1=0. В качестве начальной точки возьмем х" = (О, 0), а параметр точности поиска ез = 0,1. Первая итерация. В точке х~ в соответствии с (8.60) , т имеем ш~ = (4 6) . В этой точке активны лишь ограничения неотрицательности параметров оптимизации х1 и хз, т.е. Я = = (3, 4). Поэтому А =(а. а4) =, А1А1 = Р=4(А.4»1 ~0 1)' Р1 Т Р ~0 О) т Так как р1 = Р1" и~1 = (О О), то,.
используя (8.56), вычисляем Л1 = (А1А,) ~А1ю' = В данной задаче ограничения типа равенства, отсутствуют, так что отрицательными оказались оба множителя Лагранжа при активных ограничениях типа неравенства. Удалим из множе- 383 8 от Метод проекции антитрадиента ства Д индекс г' = 4 и для нового множества Я = 13) найдем л, = (-1 о), л,л,' = (-1 о)(-1 о)' = 1.
0 ' (-10)= О 0 Р* =12 — Р1 = Теперь получим = 1о1*лн причем (р') = 6 > еа = 0,1, так что вектор р' определяет возможное направление спуска. ,Для неактивных в точке жл = (О, 0) ограничений вычислим (ам р ) = 6 > О, (ая, р ) = 30 > О. При этом 6~ — (а1,ю ) 1 бо — (ая, ао) 1 (ае, р1) 6 (а1, р1) 3 Поэтому в соответствии с (8.ое5) ае1 = 1/6, при спуске в на- правлении вектора р' первым будет нарушено ограничение с индексом г' = 2 (рис.
8.13). Рис. 8.18 Подставим ж = ж~ + атр в матричное представление целевой функции: 2 Ях) = — Яр, р ) + те (с, р ) = ф1(ае). 8. ЧИСЛЕННЫЕ' МЕТОДЫ Функция ф1(~г) принимает минимальное значение при (с,р) 1 И~1 1) 4 Так как тг~ > ~сы то в (8.46) полагаем ж1 = м1 = 1/6 и находим ж' = же+ х1р' = (О, 1) (см. рис. 8.13). Вторая итерация. В точке х1=(0, 1) из (8.60) пахот дим юз = (6 2) . В этой точке активными являются ограничения с индексами г = 2 и г = 3, т.е. Я =12, 31-, т ( 1 51 „т т Аа = (аз, аз) = ), Р~' — — Тя — Аз(А Аз) Ая = Оя 1 -1 О)' и рз = О.
При помощи (8.56) вычислим Лз = (АзА~~) 1Аятоз = т = (2/5 — 28/5) . Из множества,уз удаляем индекс г = 3, соответствующий отрицательному множителю Лагранжа, и получаем Аз = (1 5), АзА2 = (1 5)(1 5) =26, -т - -т,- 1 (2о — о~ 1г г ~ Р," = 1з — Аз (АзАз ) Аз = — ( 26 1,— 5 1/ и рз = Р~ иР = (14/13)(5 — 1), причем ~рз ~ = ъ/26 > ез = 0.,1. Следовательно, вектор р определяет возможное направление спуска. Так как для дальнейших вычислений на этой итерации длина вектора р не имеет значения, то для упрощения примем 2 (5 Цт Для неактивных в точке з~ = (О,. 1) ограничений вычисляем (аьР~) =4 > О, (ая,.РЯ) =1 > О. ПРи этом 51 — (ама ) 1 (ан рз) 4' Таким образом, в соответствии с (8.55) тгя = 1/4, т.е.
при спуске в направлении вектора р первым будет нарушено ограничение с индексом г = 1 (см. рис. 8.13). 385 о.5. Метод проекции антитрадиента Подставляя х = х~ + аер в матричное выражение для целевой функции и учитывая симметричность матрицы Я, находим Цх) = — (Яр, р ) + ае((Ях, р ) + (с, р ) + (с, х )) = 4з(и). Функция уЗз(те) достигает минимального значения при М р')+( р') фр р) 31 4 Поэтому в (8.46) принимаем атз = 7/31 и получаем хз = х'+ + аезрз = (35/31, 24/31).
Третья итерация. В точке хз в соответствии с (8.60) т вычисляем ацз = (32/31)(1 5) и устанавливаем, что активным является лишь ограничение с индексом г = 2, т.е.,7з = (2). Поэтому Аз = аз — — (1 5) = Аз, (АзАз ) 1 = 26, Рз — — Рз* и Так как (рз~ = 0 ( ез = 0,1, то, используя (8.56), находим Лз = = (АзАз) зАзшз (1726)(1 5)(32131)(1 5) = 32~31 ) 0 Таким образом, единственный множитель, Лагранжа в функции Лагранжа (8.57), имеющей в данном случае вид 32 7 (,Л) =Ь(х)+ — 1((оз,х) -5з), положителен.
Поскольку на этой итерации рз = О, то точка хз = (35/31, 24/31) является стационарной для функции Лагранжа. Квадратичная целевая функция Д(х) с положительно определенной матрицей Я сильно выпуклая. Поэтому х~ = х'— точка наименьшего значения целевой функции при заданных ограничениях (см. рис. 8.13). В этой точке целевая функция принимает значение Д(х*) = 6882/961 7,1613. 8. НИСЛЕННЫЕ МЕТОДЫ Нелинейные ограничения.
Если среди ограничений в задаче оптимизации есть нелинейные, то поиск минимума целевой функции 1в(т) на допустимом множестве усложняется. Пусть для определенности й = 1т Е в;": д1(щ) < О, г = 1, п1 1, где д;(щ) — - дифференцируемые функции, и на й-й итерации известна точка а Е й, для которой активными являются ограничения с индексами г Е ХЬ = (г Е И: д;(щ ' ) = О). Составилл матрицу Аы строками которой являются матрицы-строки т (~тас1д1(щ" ')), ~: 6 Хы предполагая, что они линейно незави- т т симы. Тогда проекционная матрица Р~* — — 1„— А~(АьА~) Аь спроектирует антиградиент юь = — игаса 1е(ть ~) целевой функции в точке щ ' на направление, ортогональное градиентам всех функций д;(щ), г Е Хя, задающих в этой точке активные ограничения.
По в общем случае может оказаться, что это направление не будет направлением спуска, поскольку оно может лишь касаться в точке ж ' Е дй границы дй множества й (на рис. 8.14 эта ситуация представлена на плоскости при одном активном ограничении в точке жь '). Ясно. что любое продвижение точки в найденном направлении спуска может вывести ее из допустимого множества, так что хь ф й. Поэтому шаг спуска на каждой а-й итерации обычно приходится сочетать с последующим проектированием точки и на множество й. Рис. 8.14 8.5. Метод проекции алтигрвдиеятв Рассмотрим на конкретном примере некоторые особенности поиска точки минимума целевой функции в случае, когда допустимое множество Й задано одним нелинейным ограничением типа неравенства, т.е.
П = 1х е Б'.: д(х) < О). Пример 8.10. Решим задачу выпдкяозо прозраясясировапия с ,10(х1~х2) = 2х1 — 4х1+хз — 2х2 1шсп; и+и — 2х <О. 2 В данном случае целевая функция является квадрати.шой и 1 ее можно записать в виДе 1о1х) = — 1с,сх, х) + (с., х), гДе Единственное ограничение задачи имеет вид д(х) < О, где д(хс,хг) =хс+х~ ~— 2хз. В качестве начальной возьмем точку хо = (О, 0), а в условии прекращения поиска ~х~ — х~ ~ < сс положим в = 0,01. Вычислим антиградиент целевой функции ш = — кгас1Ь(х) = — 9х — с = и градиент левой части ограничения 8гас1д(х) = (1 2хз — 2) (8.61) Рассмотрим подробнее первую (се = 1) итерацию при решении этой зада си методом проекции антиградиента. 1. Поскольку (сос, 8гас1д(хв)) = О, то антиградиент сос = о т = 14 2) и градиент бгас1д(хо) = (1 — 2) в начальной точке хв ортогональны.
Следовательно, нет необходимости вычислять проекционную матрицу Рс*, которая в данном случае является т единичной, а рс = Р1'шс = шс = 14 2) 388 8. лТИСЛЕННЫК МЕТОДЪ| 2. При помощи исчерпывающего спуска из точки х" в направлении вектора р' находим значение /10 5'~ и точку х1 = х~+ае1р = ~ —, — ~. Ясно, что продвижение из точки х Е Й в направлении вектора р выводит за пределы допустимого множества, т.е. х' ф Й, так как д(х') = 25/81 > > О. Точка х1 лежит на касательной к кривой Г, заданной уравнением д(х) = О, в точке хс. 3.
Спроектируем точку х' ф Й на допустимое множество Й, т.е. найдем точку х1 Е Й кривой Г, наименее удаленную от точки х~. Так как функция д(х) дифференцируемэя., то точка х~ будет основанием кратчайшего перпендикуляра, опущенного из х' на кривую Г (см. 8.4). Эту точку можно найти, решая задачу ~8.20) мегодом последовательных приближений* х', = х,'., — д(х',,) ',, в Е М, где ал = 8гас1д(х,',).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
