XIV Аттетков и др. Методы оптимизации (1081420), страница 59
Текст из файла (страница 59)
Процедура дробления еь может и не дать положительного результата вплоть до выполнения неравенства ~в~~ < в„, что Равносильно Условию ~Нь~ < вв пРекРащениЯ послеДУющих итераций. Если множество П задано при помощи не только ограничений типа неравенства, но и а линейных огриниченич", ьаипи равенсгава, т.е. Й = (а Е Е": д,(а) < О, .1 = 1, пц Ав = Ь), где А -- матрица размера д х и, Ь Е Р', то это следует учесть во вспомогательной задаче линейного программирования, добавив в нее ограничение Ар = О. Тогда при спуске в направлении, определяемом вектором р~, удовлетворяющим последнему ограничению, точка т не выйдет за пределы допустимого множества П.
Действительно, учитывая (8.71), для любого значения ж~ находим Аж~ = Ааь ' + к~Ар" = Ь, поскольку Арв = О, а точка ав по условию принадлежит множеству й и поэтому Ах" ' = Ь. При наличии ~ нелинейных ограничений вида 1)(,в) = О, 1 = =1, г, метод возможных направлений можно применить, если на каждой Й-й итерации линеаризовать эти ограничения в окрестности точки в~ . Но тогда спуск в направлении, найденном этим методом, при любом значении кь > 0 может 8.8.
методы последовательной безусловной ииниыиэации 409 выводить точку хь за пределы Й. Это нарушение можно скорректировать, заменяя найденную точку ее проекцией на множество Й. Другой подход состоит в том, чтобы ослабить нелинейные ограничения типа равенства,. для чего полагают ~()(х)~ < ды 1 = 1, т.
По мере приближения к искомой точке х' е Й минимума целевой функции на множестве Й значение да > 0 можно уменьшать*. 8.8. Методы последовательной безусловной минимизации ппп (((х) + дн(х)),. (8.80) где йн(х) -- так называемая индикаторная функция допу- стимого множсстоа Й: Точки минимума функций ((х) в (8.1) и ((х) + дн(х) в (8.80) совпадают, но индикаторная функция имеет точки разрыва второго рода на границе дЙ допустимого множества Й. Это не позволяет применять известные методы безусловной *Сыэ Полак Э.. а также: Реклейтис Г., Рсйваидраи А., Рэесдел К.
Один из подходов к решению обецей задачи (8.1) нелинейного программирования состоит в преобразовании ее в последовательность задач безусловной минимизации для сконструированных специальным образом вспомогательных функций. Алгоритмы, использующие такой подход, принято называть методами последовательной безусловной минимизации. Рассмотрим общую схему построения алгоритмов этих методов на примере решения задачи (8.1) для цс,левой функции 1(х), х Е 1~" . Формально эта задача эквивалентна задаче безусловной минимизации 410 8. НИСЛЕННЪ|Е МЕТОДЫ минимизации к задаче (8.80). Но в случае, когда множество й задано осрвничвниями ксива равенства и неравенство...
используя фигурирующие в них функции, можно построить такие непрерывные функции шгпрафа бс(х), что в каждой фиксированной точке х Е К" 11ш~бь(х)~ = 11пс бь(х) = бо(х). (8.81) Тогда задача, эквивалентная (8.80), принимает вид св1п (|'(х) + 11пс бь(х)) . яви" в — ~ж (8.82) Если при этом операции вычисления минимума и предела явля- ются коммутативными, т.е.
пнп (|" (х) + 1нп бь(х)) = 11ш ( сп1п (|" (х) + бь(хн))), то вместо (8.82) получим Ях) = )'(х) + бс(х) — ~ шш, х Е Й", Й Е И, (8.83) т.е. исходная задача (8.1) нелинейного программирования переходит в последовательность задач безусловной минимизации вспомогательных функций )ь(х), которые называют шгпрафными. Тогда в качестве решения х* Е й задачи (8.1) следует рассматривать предел (если он существует) последовательности (х~) решений х~ задач (8.83).
Можно указать два основных подхода к построению штрафных функций и соответственно два типа методов штрафных функций. Эти типы различают по способу учета ограничений. Если все точки х*, последовательности (х*„) принадлежат допустимому множеству й, то говорят о метподе внутпренних штпрафных функций (иногда о методе внутренней точки). Если же х*„ф й, то говорят о методе внешних штпрафных функций (иногда --- о методе внешней точки).
8.8. Методы поеледопательной беэуелонной нинимионнии 411 Рассмотрим вычислительные конструкции методов штрафных функций, наиболее широко применяемых в приложениях при задании допустимого множества при помощи ограничений типа неравенства в виде й = 1х Е л!' ч д,1х) (~ О, 1 = 1, ш ), (8.84) где д,(х), х Е Р', -- непрерывные функции. ) >О, хай!,дй; ) +со, х ф й !, дй. Ее роль состоит в создании „барьера" с крутыми склонами вдоль границы дй допустимого множества й. ь1аще всего в качестве такой функции принимают п1 4ь(х) = — гь ~, х Ей'1дй, й ЕИ, (8.85) ,, д!1х) 5ь(х) = — гя ~1п ( — д!!х)), х Е й !!дй, й Е И, (8 86) !=! где гь > О -- козффициент, называемый параметром илтрад)а.
Если гь — ++О при й — ! ос, то последовательность Я~.(х)) функций, определенных с помощью !8.85) или (8.86), сходится поточечно к индикаторной функции бп(х), т.е. удовлетворяет равенству (8.81). Метод внутренних штрафных функций. Пусть допустимое множество й вида (8.84) содержит внутренние точки, т.е. точки, в которых все ограничения выполнены как строгие неравенства. е1>ункцию йь(х), определенную во всех внутренних точках допустимого множества й, назовем функцией внутпреннеео илтпраЯа зтого множества, если 412 3.
ЧИСЛЕННЪ|Е ЫЕТОДЪ| Можно показать', что последовательность ~х*„) решений х| Е 11 ~ дй зада |и безусловной минимизации штрафных функций Ях) = |(х) + дь(х)., Й Е И, при использовании представления функций бь(х) внутреннего штрафа в виде (8.85) или (8.86) сходится к точке наименьшего значения целевой функции 1(х) на замкнутом ограниченном множестве й вида (8.84), если каждая точка х*,, к Е Я, является точкой наименьшего значения соответствующей функции |ь(х). Если д|ункиии |'(х) в (8.1) и д|(х) в (8.84) являются выпуклыми, то функции |ь(х) также выпуклы (см. 3.2). Поэтому из приведенного утверждения следует, что для имеющей решение задачи выпдклоео программирования рассматриваомый метод сходится, поскольку в этом случае каждая из функций |ь(х) достигает на множестве Вв лишь наименьшего значения.
Опишем алгоритм метода внутренних штрафных функций решения задачи (8.1) на множестве й (8.84) при использовании представления (8.85). На предварительном этапе выбираем начальную точку хо Е й ~ дй, сходящуюся к нулю последовательность (гь) положительных чисел гь и параметр точности поиска е в условии ~1ь (х*,) — Ях*,, ) ~ ( с прекращения вычислений, а затем, принимая к = 1 и хы — — х, переходим к основной о части алгоритма.
1. Полагая х~~ = х", одним из методов безусловной минимизации (см. 4- 6) находим точку х* Е й '1 дй минимума штрафной функции 1 |ь(х) = |'(х)+бь(х) = |(х) — ть~ ,, д*(х) ' используя в качестве первого приближения точку х~~. Далее переходим к п. 2. 2. Если ~(ь(хь) — ~ь(х*,)~ ( е, то вычисления прекращаем и принимаем х" — х~ и |(х*) — ((х~). В противном случае полагаем Й: = Й+ 1 и возвращаемся к п. 1. Смз Фчвккв А., Мвк-Кормик Г, а также: Гроссман К., Кавяин А.А. 8,8.
Истодм нослодонательной беоуслонной мнниьанаацни 413 Эффективность реализуемого алгоритма в значительной степени зависит от выбора начального значения го параметра штрафа г. Общих рекомендапий здесь не существует. Выбор „подходящего" значения го связан со спецификой решаемой задачи и способом задания функции штрафа. Например, если штрафная функция имеет вид ьа ~(х,г) = 1(х) — г ~ = 1(х) — г6(х), ,,Мх) = т.е. использует функции штрафа вида (8.85), то в качестве начального значения параметра штрафа можно принять* (8тас1 1'(х), бгас1 6(х) ) г ~ягас16(х)~з Возможны и другие способы выбора „подходящего" значения** г.
Если начальное значение го параметра штрафа выбрано, то элементы последовательности ~гь), удовлетворяющей условию 11ш гь = +О, обычно задают рекуррентным соотношением гь = к-аоо = гь 1 ("», Й Е И, где у = сопв1 ) 1. Условие прекращения поиска точки х~ безусловного минимума штрафной функции Ях) зависит от используемого алгоритма безусловной минимизации. Например, в случае применения алгоритмов первого или второго порядков (см. 5) в качестве этого условия обычно используют выполнение неравенства ~8гас11ь(х)~ ( ею где сь ) О -- заданный параметр точности поиска.
Однако применение этого условия может приводить к трудностям вычислительного характера и не всегда практически возможно. В основном эти трудности связаны с тем, что при больших значениях Й значение ~ 8гас1~ь(х) ~ может быть большим даже в малой окрестности точки х*„. Это обстоятельство может оказаться препятствием и при реализации метода внутренних штрафных функций. *Смл Фнакка А., Мак-Кормик Г.
*Смл Гроссман К., Каплан А.А. 414 а '1исденные метОды Эффективность алгоритма рассматриваемого метода может зависеть и от способа задания функции штрафа. Универсальных рекомендаций в этом вопросе также не существует. В одних случаях способ задания этой функции не оказывает существенного влияния, а в других — его влияние оказывается реша»ощим. Покажем это на конкретных примерах. Пример 8.13.
Методом внутренних штрафных функций решим задачу оптимизации с ~(х»,хз) = 10х~» — 4х»хе + 7х~ з— 4Л(5х» — хз) — 16 — » ппп; (х» — 1) + (хэ — 3) — 4 < О. Допустимое множество Й в этой задаче представляет собой замкнутый круг с радиусом 2 и центром в точке (1, 3). Вводя функцию штрафа в соответствии с»8.85) или»8.86), получим два варианта вспомогательных функций: Л»»х) = Пх» з) — ь1»» — Ях» ''). ПаРаметРы штРафа гь опРеДелим соотношениЯми »в = 32, » ь = = гь. »(2, к Е 14.
Па рис. 8.19, а изображены линии уровня вспомогательной функции 1ь(х) при значении параметра штрафа гь = 32, а на рис. 8.19, б — — линии уровня функции ~ь(х) при гь =1. Решение вспомогательных зада» безусловной минимизапии было проведено численно с применением метода Ньютона при выборе в качестве начальной точки х" = »1., 3). Поиск точки минимума х* б Й прекращался при выполнении неравенства ~Я»х,„) — ~ь (х" ») ~ < с или Ць(х*) — ~ь(х*„») ~ < с, где с = 10 з. Результаты проведенных расчетов приведены в табл.
8.4, где Х число вспомогательных задач минимизации штрафных функций, решение которых привело к выполнению условия 8.8. Методы последовательной безусловной минимизации 415 1 0 1 и 3 0 1 2 3 Рис. 8.19 Таблица 8.4 прекращения вычислений. Числа в двух последних колонках таблицы позволяют сравнить значения Х-й штрафной функции в точке х~, — х' и целевой функции 1(х) в этой же точке. Из таблицы видно, что в данном случае способ задания функции штрафа практически не влияет на эффективность реализуемого алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
