XIV Аттетков и др. Методы оптимизации (1081420), страница 57
Текст из файла (страница 57)
Кроме того, согласно формуле Тейлора с остаточным членом в форме Пеано и равенству д;(х~ ~) = О, для .любого индекса г Е Хя найдется такое стг > Ог что при ст Е (О, ои) Уг(х +сгр ) — Уг(х +стР ) Угдх ) = (8тас1д,;(хл с ) г ор ) + о(о) < сгт1я + о(сг) < О. Так как дс (х~ с ) < 0 при любом / гс Хю то благодаря непрерывности функции дс(х) найдется такое оу > О, что для всех о Е (О, ос) будет выполнено неравенство дс(х~ ' + орв) < О. Таким образом, имеем дг(х~ +ар") < О, г =1, т„сге (Ог сто)г сго = шш сг; > О, г=ьт т.е.
вектор р определяет допустимое направление в точке хв ' Е П относитечьно множества г1. При необходимости число оо > 0 можно выбрать еще меньшим, чтобы при сг Е (Ог оо) было 3. ЧИСЛЕННЪ|К МЕТОДЪ| выполнено и неравенство = (Исае||в(х '), ор ') + о(о) < опе + о1а) < О. В итоге получаем, .что вектор р~ задает, согласно определению 8.1, возможное направление спуска из точки х~ ~ Е й на множестве й.
Перемещение в этом направлении приводит на к-й итерации в точку х =х '+ньр, жь Е (О,йе), (8.71) где нл > О это наибольшее значение ж, при котором верно соотношение хв '+тр Ей, т Е (О, и). Если й - выпуклое мнолееетво, параметр й~ > О можно определить формулой нв = шах1.н > О: х + жр Е 11). (8.72) Отметим, что в случае неограниченного множества й 1в том числе и выпуклого) для некоторых направлений спуска значение хе может быть бесконечно. Различные способы выбора значения не в (8.71) приводят к различным вариантам алгоритмов, реализующих спуск в найденном на каждой итерации возможном направлении.
Эти алгоритмы обычно объединяют общим названием метод возможных направлений. Один из способов выбора нь состоит в минимизации функции фе(н) = Тв(х~ ~ + нр~) в полуинтервале 10, х|), для чего можно использовать методы одномерной оптимизации (см. 2). Для целевой функции, удовлетворяющей условию ~8гас1Ях) — 8тас1 1о(У)~ < А~х — У~, х, У Е й, где А > О, полагают нь = пнп Яв, — ~. Наконец, если оценка à — ~ш~1 значения нь затруднона, то можно применить метод дробления Сме Ниевлвев Ф.П.
8.7. МЕтОд вюзможных нанравлвний 397 шага: выбрать некоторое исходное значение зсо, найти при зсг = = зсо, используя (8.71), точку х~, и если х~ гр Й, то дроблением значения зсг добиться выполнения условия х Е Й. После этого ь следует вычислить значение Д(х~), и если Ях~) > Уа(х" '), то продолжить дробление значения зсг до тех пор, пока не будет выполнено неравенство Д(х") < Д(хл с). При этом в случае множества Й, не являющегося вьтуклым, необходимо проверить, не нарушено ли при последующем дроблении условие х~ЕЙ. Вернемся к задаче линейного программирования (8.70) и рассмотрим случай, когда ее решением является точка яь = = (р", 0) Е всн г~, т.е. г1ь =гз' = О. Покажем, что это равносильно выполнению в точке х~ ' = х' Е Й необходимого условия минимума функции Д(х) на множестве Й (8.68), т.е.
существованию неотрицательных и не всех равных нулю множителей Лагранжа Ло и сго г Е Хы для которых выполнено равенство Лодгаг1Д(х*)+ ~~г д,8гас1у,(х*) = О. (8.73) ет„ Для любого решения яв = (р~, пя) этой задачи выполнены неравенства, задающие допустимое множество Игя. Первое из них умножим на Ло > Ог а каждое из неравенств для индексов г Е Хв ---- на р, > 0 и после сюжения полученных произведений с учетом (8.73) и линейности скалярного умножения запишем Ло(дгас1~о(х*) Рь) + ~г Р;(8гас1У,,(х*), Р ) = геТ,, = (ЛоКгаг1Хосх*)+ ~ Р Кгассу сх*)г Р ) =0 < гйг(Ло+ ~ Рг).
ген, Так как коэффициент при г1я положителен, то Ог > О. Но выше установлено, что Ог, < О. Следоватсльног выполнение необходимого условия минимума в точке х Е Й равносильно выполнению равенства тсг = О. Можно доказать*, что если функции Смл йввгглвев Ф.П. 398 3. ЧИСЛЕННЫЕ МЕХОДЫ Хс(х) и д,;(х), 1 = 1, т., являются аыпдклььии, .а множество П имеет внутренность, то для того, чтобы в точке х~ ' достигался минимум функции (с(х) на Й, достаточно выполнения равенства пь = О. Таким образом, в качестве условия прекращения итераций в методе возможных направлений можно принять выполнение неравенства ~г1ь~ ( ет где еч ) 0 заданный параметр точности поиски Рассмотрим особенности применения этого метода к минимизации квадратичной целевой функции при линейных ограничениях.
Пример 8.11. Решим методом возможных направлений задачу квадратичного проераммирования, уже рассмотренную в примере 8.9: 1с(хмхз) = 2х~1+2х2 — 2х1ха — 4хь — бха — ь пнп; х1+хз — 2(0,:г1+5ха — 5(0, — х1(0, — хз (О. Как и в примере 8.9, целевую функцию представим в виде Хс(х) = — Ях, х)+(с, х), х Е и'., где В соответствии с (8.60) ее градиент имеет вид / 4х1 — 2хз — 4 1 .(* =~ .~) (8.74) 1 — 2х1+ 4ха — 6) Обозначим левые части неравенств д1(х) = х1+ хь — 2, дь(х) = = х1+ 5ха — 5, уз(х) = — хм дч(х) = — х2 и запишем их градиснты бга<1у~ = (1 1) ., Игае1дз = (1 5), бгабдз = ( — 1 0) и 8таг1д~ = т = (Π— 1) .
Так как множество П задано линейными ограничениями, то оно является выпуклым. Его представление в плоскости х10хз показывает, что оно ограничено (рис. 8.16). 399 8.7. Метод возможных направлений Рис. 8.16 В качестве начальной выберем точку жо = (О, 0), в которой 76(хе) = О, и примем ео — — 0,01. Первая итерация. В точке жо в соответствии с (8.74) т имеем 8тас)(е(ао) = ( — 4 — 6) . а активными являя~тон лишь ограничения неотрицательности переменных и~ и тав т.е.
множество индексов Х~ = (3, 4). Поэтому для поиска направления (О (1) ' спуска из точки ж, определяемого вектором р = (р~ рз ) следует решить задачу (8.70), т.е. минимизировать переменное т) на множестве И71, заданном неравенствами — 4р~ — бр2 < и, — р~ < ц, — ро < ц, ~р~ ~ < 1, ~ря~ < 1. (8.75) Наименьшее возможное значение т) ограничено в (8.75) вторым И тРЕтЬИМ НЕРаВЕНСтВаМИ вЂ” Р1 ( т) И вЂ” Ро ( т) ПРИ МаКСИМаЛЬНО допустимых значениях р~ = рз = 1, т.е. 7) = — 1. При этом первое неравенство в (8.75) также будет выполнено. Таким образом, т р = (1 1), причем этот вектор определен однозначно. Ясно, что при движении точки ш = ж~+ этр в направлении вектора р ограничения дз(ш) < 0 и дэ(т) < 0 неотрицательности переменных не будут нарушены.
Найдем, при каких значениях эе станут активными ограничения д ~ (ш) < 0 и дз(в) < О, т.е. д1 (ж) = и, ) + эер ~ + т ) + эер ) — 2 = 2эе — 2 = О, дз(ш) = х~ + эер) + 5из + 5этрз — 5 = бэе — 5 = О. Отскэда следует, что эе < эт~ = 5/6. 400 8. ЧИСЛЕННЪ1Е МЕХОДЪ| Значение м1 выберем., минимизируя функцию ~11м), задан- НУЮ РаВЕНСтВОМ ~~1(м) = ЯХ" + мР'), ИЛИ 1 ф11м) = — (фж~ + мр )., х" + мр~) + 1с, х + мр~) = 2мз — 10х 2 на отрезке ~0, х1). Отсюда получаем м~ — — х1 = 5/6, а затем вычисляем ж1 =,ве + х1р' = (5(6, 51'6) и 7в(ж1) = — 125,118 — 6,9444 1см.
рис. 8.16). Вторая итерация. В точке ж1 при помощи 18.74) нат ходим рад 1'е1а1) = ( — 7/3 — 13,13) . Активным является лишь ограничение дз(ж) < О, т.е. множество индексов Хз = (2). Следо- (2) 00 вательно, для нахождения вектора р = 1р1 рз ), определяющего направление спуска из точки а, следует минимизировать переменное о на множестве И~з, заданном неравенствами 7 13 3 3 — — р1 — — рз ( д, р~+5рз (и,. ~р1( (1, ~рг~ (1.
18.76) Умножив второе неравенство на 7/3 и сложив с первым нера- 11 венством, получим и > —.рз. Так как о < О, то и рз < О. Теперь умножим второе неравенство на 13/15 и после сложения 14 с первым найдем р1 > — — и., т.е, 1И > О. Отсюда следует, что наибольшему возможному значению р1 = 1 соответствуют наименьшее возможное значение Н = — — и рз = — —. При этом 14 14 все неравенства в 18.76) выполнены. Таким образом, получаем рз =11 — 5/14) . При движении точки и = а~ + мр в направлении вектора рз ограничение дз(,в) < 0 не будет нарушено, так как оно является активным в точке а ~.
Ограничение дз(т) < 0 также не нарушается, так как оно означает, что и1 > О, а в точке ж + мр 1 2 для первой координаты имеем ж, + хр = — + м > О. Выясним, Ю 00 а при каких значениях м выполняются ограничения д1 1х) < 0 и 401 8.7. Метод воаможныл направлений 94(х) < О, т.е. когда д1(х) =х1 +лер1 +х2 +лер2 — 2= — лт — —, <О, 1 П 12) 11 1 12) 9 1 14 3 111 60 д4(х) = — хо — 2ер2 — — — ле — — < О. 14 6 Отсюда следует, что 2е2 = 14/27.
Функция ф2(ле) = 1"91х + лер ) с учетом симметричности матрицы 1,1 имеет вид 2 ф2(ле) = †5~(р , р ) + ле(фх , р ) + (с, р )) + 291 2 11 125 + — (Ях .,х )+(с,х ) = — ле — — ле — —. 2 ' ' 98 14 18 77 На отрезке [О, лт2] точкой ее минимума будет 2е2 = —. Поэтому 582 хя = х" + ле2р2 = ~ —, .' ) и 791х~) = — 7,0850 (см. рис. 8.16).
/281 935 1 1,291' 11б4) Т р е т ь я и т е р а ц и я . Используя (8.74), вычисляем / 1015 1373 1 дгабД(х ) = 11 — — — ) 582 291 ) Так как в точке х нет активных ограничений, то Хз = О, и переменное 9 следует минимизировать на множестве И23, заданном неравенствами 1015 1373 Р1 Р2 < 41~ ~Р!~ < 1~ ~Р2~ < 1 Иначе говоря, нужно найти минимальное значение левой части первого неравонства при условии, что выполнены два других неравенства. Ясно, что минимальное значение достигается при т Р1 = р2 = 1, т.е. Рз = (1 1), и минимальным значением 17 будет 9 = — — — — 6,4622.
37б1 582 При движении точки х = х2+ лтрз в направлении вектора р ограничения дз(х) < 0 и д1(х) < О, означающие неотрицательность переменных х1 и х2, выполняются при любом ле. 402 8. ЧИСЛЕЕШЫЕ МЕХОДЪ| Выполнение ограничений д1(х) < 0 и д2(х) < 0 означает., что д1(х) =х +хр +х +хр, — 2 =2х — —. <О., 00 ~з> ОО 00 269 1164 д2(х) =х +нр' +от. +5нр' — 5=Он — — <О. 00 (3> 00 ~з~ 21 1 ! ''2 2 1164 Отсюда устанавливаем, что хз = — 0,0030. 7 2328 Функция рз(н) = Яхз + нр~) на отрезке [О, нз) достигает наименыпего значения при хз = нз. Поэтому хз = хз+, сзрз = ( — ', — ') = (0,9686, 0,8063) и ~о(хз) = — 7,0975. Рассматриваемая задача с квадратичной функцией не является сложной, и ее решение нетрудно найти аналитическими методами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
