И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 53
Текст из файла (страница 53)
В работе Х. Майна н М. Фукушимз [5251 для построения штрафных функций используется понятие инфимзльной сходимости последоввтельности функций и доказывается, что некоторые известные методы внутренних и внешних штрафных функций являются частными случаями нх теории. 5.3. Методы внешних штрафнык функций 1. Задачи о огроввчеввямк в ваде вернвевств 3 а д а ч а 1, Найти агд ппп /, (х) для заданной функции к6Х /е '. В" -ь В' и для заданного множества Х= (х)/1(х)(0, 1=1, 2, ..., т, ХЕВ"). [5.20! Предположения 1. (з) — функция /, непрерывно дифференцируема; (В) — функции /и / = 1, 2, ..., т непрерывны; (1й) — существует такая точка х'Е Х, что множество Х' = (х)/е(х)(/е(х')) компактно.
Идея метода внешних штрафных функций заключается в сведе- нии решения задачи с ограничениями к решению последователь- ности задач на безусловный минимум. При этом необходимо стро- ить последовательность внешних штрафных функций для множест- ва Х, которая определяется следующим образом. Определение 1. Последовательность непрерывных функций рь (х), й = О, 1, 2, ..., называется последовательностью внешних штрафных функций для множества Х, если: Рк(х)=0 для всех хсХ, й=О, 1, 2, Рз(х))0 дЛя ВСЕХ Х [С Х, Л =О, 1, 2, ...; Рз(Х)-ьоо дЛя ВСЕХ Х [С Х, [Г-ьоо; рз+~(х))рз(х) для всех х [С Х, й=О, 1, 2, ..., 281 г(алев, используя алгоритмы глав 2 н 3, при каждом я = О, 1, 2, ...
находим х» — решение задачи на безусловный минимум 1,(х) + р»(х) — ~- пп'п. «гп Предельные точки последовательности (х») ~ > являются оптимальным решением задачи 1. Методы внешних штрафных функций обеспечивают приближенное решение задачи 1 вне допустимой области. Приведем пример последовательности внешних штрафных функций для множества Х, определенного согласно (5.20): р»(х) =а» ~„'(шах(0, /~(х)))», 1=0, 1, 2, °, (».221 ~'=! где р в 1, (а»)»=ь — строго возрастающая последовательность положительных чисел, стремящаяся к бесконечности прн я- оо, Алгоритм 1 1. Построить р, (х), й = О, 1, 2, ...,— последовательность внешних штрафных функций для множества Х, определенного согласно (5.20); для этого можно использовать (5.22).
П. При каждом й = О, 1, 2, ..., найти х» — решение задачи на безусловный минимум (».221 Х»= (х(!»(х)+р»(х)я Л), Л(оо, й=О, 1, ... (».24) компактно; в) задача 1 имеет единственное решение х«; г) минимум в !'5.28) при больших й достигается в единственной точке х"; д) в решении х«задачи! градиенты ф,(х«), (~О(х«), линейно независимы, где множество Э (х*) определяется по правилу Р(х«) = (1(~~(х*) = О, 1= 1, ..., т). Тогда для точек (х»)» ь, порожденных алгоритмом 1, в котором р» (х), й = О, 1, ..., определяется согласно (5.22) при (1 2, имеют 2В2 1«(х)+р»(х)-«пп'и «\И (для этого использовать алгоритмы, описанные в гл. 2 и 3).
П1. Найти предельные точки последовательности (х")» ь. Теорема1. Пусть выполнены предположения 1. Тогда любая предельная точка последовательности (х»)».л, порожденной алгоритмом 1, является оптимальным решением задачи 1. Тео рема 1'. Пусть выполнены все предположения 1 и, кроме того: а) функции 1р !' = О, 1, ..., т — непрерывно дифференцируемы; б) множество место предельные соотношения 1ипх" = х', й Ф 1 1ипа„(шах (О, ~г(х ))) = — ин 1=1, ...,т, где ин 1' = 1, ..., т — множители ЛагРанжа задачи 1.
В случае задачи выпуклого программирования оценки приближения х" к искомому решению х' могут быть сделаны более точными. Теорема 1". Пусть функции ~р 1' = О, 1, ..., т, выпуклы и мноасгспмо Хы определяемое согласно 15.24), компактно. Пусть, кроме того, в точке х", являющейся решением задачи 1, выполнены необходимыг условия в форме теоремы Куна — Танкера, т. е. существуют такие числа и;)0,1=1, ..., т, чпю ~ (х*)( ~ и ~ (х) + ~ (х), Чх; /=! иА (х*) = О, 1 = 1, ..., т. Тогда ~~(хь)( —, если ~г(х") вО; ~,(х') ) ~,(х') — — —, где и= ~(и;)е 2. Задача е еграндчеаидма в виде равеветв 3 ада Ч а 2. НайтИ аГН Пните(Х) дпя ЗадаННОй фуНКцИИ «Ех 1е: В"-~ П' и множества Х = (х(д~(х) =О, 1=1, ..., т).
(6.26) Предположения 2. (1) — функция 1е непрерывно дифференцируема; (Й) — функции ар 1 = 1, ..., т, непрерывны; (и) — существует такая точка х', что множество Х' = (х(Де(х)(~е(х')) компактна. Ниже приводится пример последовательности внешних штрафных функций для множества Х, определенного согласно (5.25): 1Ф 1ва рь(х)=аь(д(х)1а=а ~~ (о (х))е), Й=О, 1, ..., (526) / ! 283 где 5 ~ 1 и сс», й = О, 1, 2, ...— строго возрастающая последовательность положительных чисел, стремящаяся к бесконечности при й -ь оо. Алгоритм 2 1. Построить (р» (х))» е — последовательность внешних штрафных функций для множества Х, определенного согласно (5.25); для этого можно использовать (5.26).
П. При каждом й = О, 1, ..., найти х» — решение задачи на безусловный минимум )е (х) + р„(х) -~ ш1 и. «»н" (для этого использовать алгоритмы, описанные в гл. 2 и 3). 1П. Найти предельные точки последовательности (х»)» е. Теорема 2. Пусть вьтолнены предположения 2. Тогда любая предельная точка последовательности (х')» е, порожденной алгоритмом 2, является оптимальным решением задачи 2. а.
Медпфвцвреааввые методы е процедурой прерыааввя Непосредственное использование описанных выше методов внешних штрафных функций не всегда практически осуществимо, так как не всегда возможно за конечное время найти глобальный минимум функции ~е+ р» на всем пространстве. Поэтому опишем модифицированные методы внешних штрафных функций„которые используют процедуру прерывания при приближении к минимуму или стациопарным точкам функции 1+ р„.
Последовательность точек х», й = О, 1, 2, ..., порожденная этйми алгоритмами, обладает свойством ч~,( ")+ чр,(~) о при й-»- ео. При определенных условиях предельные точки этой последовательности удовлетворяют необходимым условиям оптимальности. Алгоритм 3 применяется для решения задачи 2, а алгоритм 3" — для решения задачи 1. Алго ринам 3 Начало. 1.Выбрать числа е О, а5(О,Ч»),~)1,р)О и точку х'~ й". П. Положить зе= е, 1 = О, й = О. Овнов пой ц и кл. 111. Вычислить вектор й(х», е») = — ~ч)е(х») + — чр(х»)~, 1 е» где функция р определяется по правилу ,о (х) = ) к (х) 1'»'2 = 2 л (Д, (х)) . 284 1Ч.
Если 1й(х), е„)1 ) еь, то перейти к шагу Ч; иначе положить еь»» = еь/р, х" = хц й = й+ 1 и перейти к шагу 1П. Ч. Используя алгоритм 3', вычислить такой шаговый множитель Лп что — Л1(1 — а))П(»1, е„)!'(Д„(х1+ Л,)1(»1, е,)) + + — р(х)+ Л)й(х), е„)) — ) (х))— ! еь — — р(х)) ( — Л,а(й(»1, еь)1(!. 1 'Ч1. Положить »1+! = х)+ Л1)1(»1, еь), 1 = 1+ 1 и перейти к шагу П!. Алгоритмд' (алгоритмвычисления множителя Л для алгоритма 3) 1. Положить р = р. П. Вычислить 8(р„») =~,(» + рй(»1, )) + 1 р(.1+ рй(.1, — 1ь(х~) — — Р(х~) + Р(1 — а) 1п(»Ц е!) 1".
15.2?) 1 П1. Если 8 (р, х)) = О, то положить Л! — — р и прекратить вычисления; если 0(р, х1) (О, то положить р = р+ р и перейти к шагу П; если 0 (р, х)) ) О, то перейти к шагу 1Ч. 1Н. Вычислить 0(р, »1) = ~,(»1+ рй(»1, е„)) + — р(х1+ рй(»1, е„))— — ')ьЮ вЂ” —,Р(х')+Р (Ь(»', еь)Р 1 (5.28) Ч.
Если 0 (р, х') ( О, то положить Л! = р и прекратить вычисления; иначе положить и,= р — р, Ь,= р и перейти к шагу Ч1. ' Ч1. Положить 1 = О. ЧП. Положить о, = (а, + Ь,)/2. ЧП1. Вычислить 0 (оо х') и 8 (оо х)), определяемые согласно (5.27) и (5.28), соответственно. 1Х. Если 0 (о„х') ~ О и 0 (о„х') ( О, то положить Л! = о; и прекратить вычисления; иначе перейти к шагу Х. Х. Если 8 (во х)) ) О, то положить а!» ~ = ао Ь|ы = о„ ! = 1+ ! и перейти к шагу ЧП; иначе положить а!+! = оо Ь|»» = = Ьо 1 = 1+ ! и перейти к шагу НП. Теорема 3. Пусть выполнены предположения: (1) — функции 1ь и д1, ! = 1, ..., т, непрерывно дифференцируемы; (й) — матРица ве !») Якоби — „имеет максимальный ранг для всех х, принадлежа- и(их достаточно большому открытому множеству в В"; (И) — множество (х ( 1ю (я) ~ йю) компактно для всех дю Е В'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
