И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 54
Текст из файла (страница 54)
Тогда, если последовательность (х")» ю, порожденная алгоритмом 3, остается в компактном множестве, то И (хю, е«) -«О при И -«ьь, последовательность (хь)Г ю будет иметь предельные точки х«, которые лежат в Х и удовлетворяют необходимым условиям оптимальности для задачи 2. Замечание 8. Из теоремы 3 следует, что для эффективного использования «реализуемого» алгоритма 3 требуется выполнение ряда предположений, н в отличие от чисто принципиальной схемы (алгоритм 2) здесь, по-видимому, нет простых достаточно общих условий, гарантирующих, что последовательность (х")ь" ю будет оставаться в компактном множестве. Алгоритм 8 Шаги 1, 11, 1Ч, Ч, Ч1 такие, как в алгоритме 3.
Шаг 11! алгоритма 3 заменить на 11Г. ИГ. Вычислить вектор И(хц е,) = — ~7~«(х~)+ — Чр(х~~, ! здесь функция р(х) = — ~, '(гпах (О, 1,(х)))', или р (х) = — ~; [~, (х)1', саит где множество Е (х) определяется по правилу Е (х) = (1( 1, (х) ~~ю О, 1Е (1, 2, ..., т) ). Теорема 3'. Пусть выполнены предположения: (1) — функции Гю и ~и 1 = 1, ..., т, непрерывно дифференцируемы; (»1) — множество (х ( 1» (х) ( дь) компактно для всех с[ ~ Л', (11«) — для всех хС Н" векторы ф, (х), 1С С (х), линейно независимы. Тогда для последовательности (х»)» ю, порожденной алгоритмом 3", имеет место предельное соотношение И (х', г«) -«О при й -« Если, кроме того, последовательность (х') ь.ю принадлежит компакту, то ее предельные точки х* лежат в Х и удовлетворяют необходимым условиям оптимальности для задачи 1.
Замечание 3'. Из теоремы 3' следует, что для эффективного использования «реализуемого» алгоритма 3" нет простых достаточно общих условий, гарантирующих сходимость последовательности (хе)е о. Однако иа практике оказывается, что алгоритмы типа 3" работают хорошо, поскольку обычно последовательности (хе)е о сходятся. 4. Метод внешних штрафных функций даа минимиеацив иедифферевцвруеммх функций 3 а д а ч а 4. Найти ага ппп 1е (х), где кех, Х, Х () (х~ух)~~О, 1=1, ..., т).
гз.29) т р(х, а) = ге(х)+ ~ ~()у(х))~)(х), (5.30) где се — некоторое положителыюе число; р Д) (х)) = а, если )) (х) ) 0 и р Д) (х)) О, если )) (х) а" О. Известно, что при а, превышающем абсолютные значения множителей Лагранжа, решение задачи (5.30) в точности совпадает о решением задачи 4. Адгорииеле 4 Н а ч а л а. 1. Выбрать: произвольное начальное приближений хе ~ В"; шаговый множитель ре и нормирующий множитель у„ удовлетворяющие условиям теоремы 4; положительное число а.
11. Положить й = О. Основ ной пи кл. П1. Вычислить числа р) = () ()) (х")), )=1, ...,гл. 1Ч. Вычислить следующее приближение хе+' пх ха — реуе (7~о (ха) + ~, '())Ч~) (хе)), / ! где Ч1,(х') () = 1, ..., лт) — обобщенный градиент функции в точке хе. Ч. Вычислить шаговый множитель рече и нормирующий мно. житель уа+ь удовлетворяющие условиям теоремы 4. Ч1. Положить й = й+ 1 и перейти к шагу 1П. Множество Х ~ В" и функции )): В" -~ В" заданы. Предположения 4. (1) — функции гр / = О, 1, ..., т, выпуклые вниз и непрерывные при х р Х, (В) — ограничения (5.29) удовлетворяют условию Слейтера; (В)) — Х вЂ” выпуклое и замкнутое множество. Приближенное решение данной задачи будем искать как решение вспомогательной (более «простой») задачи: найти агд ппп р (х, а) для «ЯХ Теорема 4. Пусть выполнены предположения 4, а также: (1) — для любого числа 6 ( оо найдется такое конечное число у=т (б), что [)7,р(х, а) [[(Х при )[х[(б; (й)— Уь ~) О, уь [[ т',р (хь, а) 1 ( сопз1; (И)— рь)~ О, ~, рь — — оо, ~„рз~( оо, ь=ь е=о Тогда последовательность [хь) ь ы порожденная алгоритмом 4, сходится к решению задачи 1'5.30), а при достаточно больиюм сс— к решению задача 4.
Замечание 4. Для ускорения сходимости функцию р (х, и) целесообразно минимизировать с помощью методов обобщенного градиентного спуска с растяжением пространства [2231. Чтобы получить гладкую функцию цели р (х, а) при гладких 70 1 = О, 1, ..., т, вместо (5.30) можно взять функцию р(х, а) = 7 (х) + ~„'~(7,(х)) [7 (х)[ь. (з 80 г=! Однако минимизация функции (5.31) дает лишь приближенное решение задачи 4, которое стремится к точному при а -ь оо. Замечания 4'.
Методы внешних штрафных функций имеют следующие преимущества: а) в качестве начального приближения можно выорать любую точку х' ~ В"; б) их можно применять к задачам с ограничениями как типа равенств, так и типа неравенств; в) если штрафная функция имеет вид (5.22) н в процессе решения задачи минимизации без ограничений находим точку х', для которой ~; (хь) ( О, то из суммы (в определении р„(х)) исключается соответствующий член с функцией ~~ и это уменьшает объем вычислений. Недостатки методов внешних штрафных функций следующие: а) генерируют недопустимые, т.
е. не всегда принадлежащие множеству Х, точки; б) если минимизируемая функция 7; (х) или некоторая из функций 70 1 = 1, ..., т — невыпуклы, то при плохом начальном приближении может быть вычислен локальный, а не требуемый глобальный минимум функции /ь+ р„(в таких случаях требуются дополнительные ресурсы для поиска глобального минимума); в) штрафные функции вида (5.22) дифференцируемы небюльшое число раз, что, согласно [3731, может неблагоприятно сказываться на скорости сходимости; г) если вычислительный процесс начинается с внутренней точки х' множества Х, то штрафная функция и все ее производные остаются равными нулю до'тех пор, пока точка хь не пересечет границу множества Х (это делает вычислительный процесс неуправляемым внутри множества Х).
288 Библиографические рлаэалия. Пункты 1, 2 написаны на основании работ [320, 285, 373, 4641, пункт 3 — н«основании работ [285, 5361, пункт 4 — на основании работ [!53, лч4, 4631. В работе [4271 для бе»«плоеной минимиаацнн штрафной функции общей вадачи нелинейного программирования испол»ауетсн модификация метода покоорди. натного спуска.
5.4. Методы внутренних штрафных Функций 1. Общая сиена 3 ад а ч а 1. Найти агяш[п 1» (х) для заданной функции «Ех ге: В"-~. В' и длЯ заданного множества Х=(х(~1(х)(0, 1=1, 2, ..., т, х~В"). Предположения 1. (») — функция [е непрерывно дифференцируема; (В) — функции [р 1 = 1, 2, ..., т — непрерывны; (Вг) существует такая точка х' ЕХ, что множество Х' = ( [1 ( ) (1 (х'И компактно; (Ь) — множество Х имеет внутренние точки и замыкание его внутренности Х' совпадает с Х. Идея метода заключается в сведении решения задачи с ограничениями к решению последовательности задач на безусловный минимум. При атом приходится строить последовательность внутренних штрафных функций для множества Х, которая определяется следующим образом. Определение. Последовательность непрерывных функций р» . Х' -~- В', й = О, 1, 2 ..., называется последовательностью внутренних штрафных функций для множества Х", если: 0(р'+,(х)(р'(х) для всех хЕХ», й= О, 1, 2, ...; р'„(х)-~-0 для всех хЕХ', й-+ оо; Р» (х~) -и оо пРи 1'-м оо ДлЯ любой последовательности (х');"о, принадлежащей Х', для которой х1-и х ~ дХ при 1-+ оо, й = О, 1, 2, ...
(здесь дХ обозначает границу множества Х). Далее при каждом й = О, 1, 2, ..., используя алгоритмы гл. 2 и 3, находят х» — решение задачи 1» (х) [- Р» (х) -~ ппп. [5.32) «их» Предельные точки последовательности (х») ~~ являются оптимальным решением задачи 1. Ниже приведены примеры последовательностей внутренних штрафных функций для множества Х: р' (х) = — а»~ —, й= О, 1, 2..., х~Х», (6.33) 17(х) ' 289 10 где фУнкции 1н ) = 1, 2, ...» т, УдовлетвоРЯют пРедположению 1 и ~а»)» е — строго убывающая последовательностьположительных чисел, стремящаяся к нулю при й-»- оо; р»(х) = — а» 2,' 1од( — 1! (х)) = ! 1 = — а» 1од(( — 1) 1 (х)1 (х) ...
1 (х)), х5Х», й = О, 1, ..., (5.34) где функции 1„1 = 1, 2, ..., т, и последовательность (а»)Г е такие, как в (5.33) и, кроме того, выполняется )» = шах( — ппп 1) (х)) (оо. сх Методы внутренних штрафных функций обеспечивают приближенное решение внутри допустимой области, в пределе стремящееся к решению задачи 1. Алгоритм 1 1. Построить р» (х), й = О, 1, 2, ...— последовательность внутренних штрафных функций к множеству Х (можно использовать (5.33) и (5.34)).
11. При каждом й О, 1, 2, ..., найти х» — решение задачи минимизации функции 1» (х) + р» (х) на множестве Х' (можно использовать алгоритмы, описанные в гл. 2 и 3). 1П. Найти предельные точки последовательности (х»)~ е. Теорема 1. Пуеть еьтолнены предположения 1. Тогда любая яре. дельная точка логледоеательногти (ха)Г е, порожденной алгоритмом 1, яеляеомя оптимальным решением задачи 1. 2. Реаапауеиаа еавма е препвяувей прермааепа Буквальное использование алгоритма 1 практически неосуществимо, так как невозможно за конечное время добиться минимизации функции 1» (х).+ р» (х) по хЕ Х'.
Ниже будет изложен модифицированный метод внутренних штрафных функций, неволь» зующий процедуры прерывания при решении задачи (5.32). Алгоритм 2 Начало. !.Выбратьчислаг~О,аЕ(0 '1») Р)1 Р= 0 н точку х' 5 Хе П. Положить г, = а, 1 = О, й = О. Основной ци кл. П1. Вычислить вектор 1» (х), е») — ((7 (х!) + е„»рр' (х!)), где функция р' (х) такова, что е»р' (х), й = О, 1 ° 2, ...,— последо- вательность внутренних штрафных функций для множества Х 290 (р' (х) можно определить, например, по правилам р'(х) = — ~ —, хЕХ", 1 Ь (х) ' или р' (х) = — ~ 1од ( — ~, (х)), х Е Х').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
