XIV Аттетков и др. Методы оптимизации (1081420), страница 60
Текст из файла (страница 60)
Пример 8.14. Найдем решение задачи квадратичного программирования < 1(х1, хг) = 10хг1 — 4х1хг + 7хг г— 4и 5(бх1 — хг) — 16 -+ шш; хь — 2 < О, х1+хг — 1 < О. Граница допустимого множества Г1 для этой зада ~и изображена на рис. 8.20.
Используя функции штрафа (8.85) и (8.86), 8. ЧИСЛЕННЫЕ МЕТОДЫ Рис. 8.20 получаем вспомогательные функции (ь(х) = Т(хмхя)— х~ — 2 х1+ хз — 1 Ть(х) = Т(х1)хз) — Гь(1П( — (х1 — 2)) + 1П( — (х1+ хз — 1))). Параметры штрафа гя определим, как и в примере 8.13, соотношениями гв = 32, гь = гь 1(2, й Е К. Па рис.
8.21, а показаны линии уровня вспомогательной функции (я(х) при гь = 32, а на рис. 8.21, б линии уровня вспомогательной функции ~,, (х) при гь = 1. Все расчеты прове дены так же, как и в примере 8.13. их результаты представлены в табл. 8.5 (обозначения в ней те же, что и в табл. 8.4). В данном случае способ задания штрафной функции оказывает существенное влияние на эффективность реализуемого алгоритма. Предпочтительней является штрафная функция Т'(х), применение которой позволяет найти точку х* с той же 8.8.
Методы последовательной безусловной минимизации 417 — 1,5 -2 — 2,5 0 0,5 1 1,5 2 2,5 0,5 1 1,5 2 2,5 0 Рис. 8.21 Таблица 8.5 точностью путем решения значительно меньшего числа вспо- могательных задач минимизации штрафной функции. Метод внешних штрафных функций. Отличие метода внешних штрафных функций от метода внутренних штрафных функций состоит прежде всего в форме задания функции называемой функцией внешнеео штпра0ча. При этом должно быть выполнено условие (8.81).
Как и в методе внутренних штрафных функций, обычно полагают ол(х) = глФ(х), где г1, > 0 — параметр штрафа, но Ф(х) функция, определенная на всем множестве К", равная нулю на допустимом множестве Й и положительная за его пределами. 418 3. ЧИСЛЕЕШЫЕ МЕХОДЪ| Если множество П имеет вид (8.84)., т.е. задано при помощи ограничений типа неравенства, то в качестве функции штрафа обычно используют квадратичную функцию т, бь(а) = тв ~~~ (д,,+(а)), з=-1 (8.87) где д~(ж) — так называемая „срезка" функции д,(х): О, дг в)<О; д,'(*) = д;(а), д;(ж) > О, т.е. д,+(х) = шах10,д,(х) ) = (д,(х) + ~д,(х) ~) /2. Последовательность (бь (ж) 1 функций штрафа, задаваемых в виде (8.87), сходится к индикаторной функции бп(х), т.е.
удовлетворяет равенству (8.81), если ть — >+со при й — ~ оо. Если допустимое множество й задано не только при помощи ограничений типа неравенства д, (х) < О, 1 = 1, т., но и ограничений типа равенства др(ш) = О, г = ив+ 1, .р, то функцию штрафа задают в виде сп бь(а) =ть ~~ (д, (ж)) +ть ~~ (д,(х)) . г=1 Опишем алгоритм метода внешних штрафных функций в случае, когда решается общая задача нелинейного программирования (8.1) на множестве 11 (8.84), а функция штрафа задана в виде (8.87). На предварительном этапе выбираем произвольную начальную точку ш, параметр в точности поиска точки ш' минимума целевой функции 1(т) на множестве й в условии ~~ь(а~) — ~ь(аь )~ < в прекращения вычислений и возрастающую последовательность ать) положительных чисел тя. Принимаем к = 1, х*, = шв и переходим к основной части алгоритма.
8.8. Методы ноеледонательной оеауслоеной мнниьснаацни 419 1. Полагая хо = хо, одним из методов безусловной минимизации (см. 4 — 6) находим точку х~ минимума штрафной функции )я(х) = г" (х) + би(х) = ~(х) + гс, ~~~ (дь(х)), используя в качестве первого приближения точку хы Далее о переходим к п.
2. 2. Если ~1ь(хь) — ~а(хь с)~ < е, то вычисления прекращаем и принимаем х' — х~ и 1(х*) — ~(х~). В противном случае полагаем Й: = Й+ 1 и возвращаемся к п. 1. В рассмотренном алгоритме возмогкпы и другие условия прекращения вычислений. Например, в качестве условия оста- нова можно использовать неравенство ~х~ — х~ с~ < е, где е— заданный параметр точности поиска. Проиллюстрируем работу этого алгоритма на конкретном примере. Пример 8.15. Решим методом внешних штрафных функций задачу из примера 8.13, выбрав в качестве начальной точку хо = (О, — ьс5) и условие останова ~хь — х~ с~ < е с параметром точности поиска е = 10 з. В данном случае штрафные функции имеют вид ~ь(х~,.хз) = ~(хмхя) +та(дь(хмхз)) где д~(хмхз) = — (д(хмх2) + ~д(хм хо)~).
Минимизация этих 1 функций проведена численно с применением того же алгоритма лсетодл Ньютона, что и в примере 8.13. Параметры гн определены рекуррентным соотношением гь = гь с + 2, А е И, го = 2. Результаты расчетов приведены в табл. 8.6, а траектория поиска точки минимума целевой функции изображена на рис. 8.22 сплошной линией. ф Методы штрафных функций выгодно отличаются от рассмотренных выше методов проектирования и спуска простотой 420 В.
ЧИСЛЕННЫЕ МЕТОДЫ Рис. 8.22 Таблица 8.6 У( ь) реализации и „сильными" свойствами сходимости. Поэтому на их разработку и совершенствование и до сих пор затрачиваются значительные усилия. В то же время практическая реализация методов штрафных функций может приводить к трудностям (0,386, — 0,672) (0,652, 0,270) (0,899, 0,755) (1,263, 0,928) (1,694, 1.041) (1,852, 1,150) (1,954, 1,212) -33,568 — 38,698 -40,109 — 46,877 — 53,222 — 53,501 -53,551 8 9 10 11 12 13 14 (1,974, 1,230) (1,976, 1,234) (1,976, 1,236) (1,975, 1,237) (1,975, 1,238) (1,975, 1,239) (1,974, 1,240) — 53,434 — 53,384 — 53,348 — 53,318 — 53,292 — 53,271 — 53,252 д.а.н Некоторые приемы обралцеиия матрицы 421 принципиального характера.
В основном они связаны с топографией поверхностей уровня штрафных функций Яа): при больших Ь (больших значениях параметра штрафа тк) графики этих функций приобретают все более выраженную овражную структуру. Это может приводить к большим вычислительным затратам при решении вспомогательных задач безусловной минимизации и даже к прерыванию процесса вычислений ввиду потери точности.
Для преодоления этих трудностей развиты модификации метода штрафных функций, свободные от указанных недостатков: метод штрафных оценок, метод модифицированных функций Лагранжа, метод штрафов с регуляризацией и др*. Дополнение 8.1. Некоторые приемы обращения матрицы Некоторые алгоритмы численного решения заоач нелинейного программирования включают процедуру замены в невырожденной матрице В одного столбца с последующим обращением вновь полученной матрицы В. Если матрица В ', обратная к В, известна, то процесс обращения матрицы В можно значительно упростить. Пусть В невырожденнвя матрица порядка п. Столбцы этой матрицы обозначим Ь,, л' = 1, пп а строки обратной к ней т матрицы В 1 обозначим с,.
Тогда равенство В 1В = Я можно записать в виде )1, л=у; (Ьыс,) =б, ~0, 1ф1, где Б,. символ Кроненера. Предположим, что матрица В получена из матрицы В в результате замены столбца Ь| столбцом Ь|. Тогда векторы с,, "Смс гроссман К., Каплан А.А. 422 3. ННОленные а|ехОды определяющие строки матрицы В, можно вычислить по формулам с,=с| — ' сы 1=1,и.
(ь,-ьыс,) (8.88) (Ьь, сь) Действительно, (Ьы с,) = (6~., с,) — ' ' (Ьы сь) = (Ьы с;), (Ьы с,) — (Ьы с,) (бь, сь) откуда заключаем, что (Ь~, с,) = бьо Если у у'= Ь, то (Ь, сь) = О и для любого номера г = 1, ц имеем (ь„— ьы с;) (ь„с,) =(ь„с;) — ' ' (ь„с,) =(ь„;). (Ьы сь) Следовательно, (Ь~., с,) = б|г Заметим, что в формуле (8.88) (Ьы сь) ~- 'О. В самом деле, если это скалярное произведение равно нулю, то вектор сь ортогонзлен всем столбцам матрицы В. Но поскольку с+ Ь ~ О, то это возможно ли|пь в случае, когда столбцы матрицы В линейно зависимы, а матрица В вырождена. В этой ситуации матрица В, разумеется, не имеет обратной матрицы.
В алгоритме, реализующем метод проекции внтизрооиенша, при построении проекционной, матрицы используется процедура обращения симметрической матрицы Р = АА, где А прямоугольная матрица размера т х и, соответствующая в задаче ограничениям типа равенства и активным ограничениям типа неравенства.
При переходе от итерации к итерации эта матрица может менятыя, причем в некоторых случаях новая матрица А образуется из уже использовавшейся матрицы А вычеркиванием одной из строк. В этом случае при обращет нии матрицы Р = АА можно использовать известную матрицу Р ', тем самым существенно сокращая объем вычислений. Д.З.Ь Некоторые приемы обрапеения матрицы 423 Из смысла задачи ясно,что порядок строк в матрице А не является существенным*, и мы можем считать, что матрица А получается из матрицы А вычеркиванием последней строки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
