И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 55
Текст из файла (страница 55)
С-1 1Ч. Если 1Ь(х~, еь)()еы то перейти к шагу Ч; иначе положить зь+1=з„1р, х" х/, Ь=Ь+1 и перейти к шагу П1. Ч. Используя алгоритм 3' (см. $ 5.3), вычислить такое число Лп что Ф+Л~Ь(х~, еь)ЕХ вЂ” Л~(1 — а)/!Ь(х!, еь)(«(~ь(хУ+Л~Ь(х', е„))+ + еьр' (х~ + Л;Ь (х1, е„)) — 1р (х1) — зьр' (х') ~ ( — Л,«х'1Ь(х/, е )1«. Ч1. Положить х~+' = х~+ Лг Ь (х', е„), положить 1 = 1+ 1 и перейти к шагу 1П. Теорема 2. Пусть выполнены предположения 1 и, кроме того: («) — функции гь 1 = 1, ..., т — непрерывно дифференцируемы; (И) — для всех х Е В" векторы 71, (х), ! Е 1.
(х), линейно независимы, еде 1. (х) = (1~ 7, (х) ~ О, 1 Р 1, т); (111) точка хл Р Х«и число е ) О выбраны так, что множеппво (х ~ 1«(х) ( 1« (хь) + ер' (хь)) компактно. Тогда предельные точка последовательности (хл)ь-ь. порожденной алгоритмом 2, допустимы и удовлетворяют необходимым условиям оптимальности задачи 1. Замечания 2. Достоинством методов внутренних штрафных функций (по сравнению с методами внешних штрафных функций) является то, что они порождают последовательности только допустимых точек, и, следовательно, могут быть использованы в реальном масштабе времени, имеют обычно производные достаточно высокого порядка и допускают управление вычислптельным процессом во «внутренностиэ множества Х.
Перечислим теперь их некоторые недостатки. Методы внутренних функций можно использовать лишь для ограниченного класса множеств Х (для множеств Х, содержащих внутренние точки). Процесс должен начинаться только из внутренней точки множества Х. Если множество Х имеет вид Х = (х3~~(х)(О, 1'=1, ..., т), то все члены штрафных функций типа (5.33) и (5.34) всегда дают ненулевой вклад в величину градиента штрафной функции. Это значительно увеличивает объем вычислений при отыскании направле1о 291 ния спуска (градиента внутренней штрафной функции).
В этом смысле методы внешних штрафных функций более предпочтитМьны. 3. Алгоритмы ииутреввеа точка и иримевевием О .фувквик 3 а д а ч а 3. Найти агй ппп го (х) для заданной функции кбх Ге: 11"->. Нг и заданного множества Х=(х)~,(х))0, (=1, ..., т, хЕВ"). Предположение 3. Функции 1!, 1 = О, 1, ..., т, непрерывны, а множество Хо!~(х!~,(х))0, 1 1, ..., т! — непустое. Главную роль в данном алгоритме играет характеристическое свойство функции, называемой (4-функцией и определенной следующим образом.
Определения. Пусть г = (г„г„..., г ) обозначает и + 1-мерный положительный вектор. Функция ~ (а) называется Я-функцией если: а) Я (х) непрерывна по г ) 0; б) !пп Я (г') = а ) Я (г), х ) 0 (до! > пускается а = оо), причем нижний предел беретея для такой бесконечной последовательности векторов (х), что г~ ) 0 для всех ! и )пп (г~) =* г, причем г~ = 0 для некоторого !.
В качестве примера Я-функции можно привести функцию Ю(/„(х') — ге(х), ~г(х)... °, Г' (х)) + ~ <„> . Алгоритмы внутренней точки с применением Я-функций составляют особый класа алгоритмов внутренней точки и обладают следующими свойствами: 1) не требуется выбирать строго убывающую последовательность (и,)~ о неотрицательных параметров, используемых в качестве весовых коэффициентов в ялучае обычной внутренней функции штрафа; 2) процеса минимизации на й-й итерации зависит только от значения нелевой функции в начальной точке х" ', т. е.
в точке безусловного минимума на (Й вЂ” 1)-й итерации; 3) членам последовательности внутренних допустимых точек соответствуют значения целевой функции ге (хе)> 1е (х'). " ге (х') образующие, начиная с исходной точки, строго убывающую последовательность. При обычных предположениях эта последовательность локально сходится. Алгоритпм 3 Н а ч а л о. 1.
Найти хе Е Х'. 292 П. Положить й = 1. О с н о в н о й ц и к л. Ш. Определить множество Х»= (х[[е(х)(7»(х» — '), х~Х'). 117. Положить [T(х)=Д( — ~»(х)+~е(х~'), ~,(х), ..., ~„(х)), где Я ( ) — Я-функция. Ч. Найти х» — какой-нибудь локальный минимум функции Я» (х) на множестве Х».
Ч[. Положить й = й + 1 и перейти к шагу П1. Теорема Ю. Пусть выполнены предположения д и: (») множество Х' локальных миниму»юв задачи д — непустое компактное изолированное множество; (»») Хе () Х' ~ 8. Тогда (»') — при Ха» Ф я существует точка х", являющаяся безусловным локальным минимумом 6)ункции (г» на Х»о, и любая предельная точка равномерно ограниченной последовательности (х»)а о есть локальный минимум функции 7";, (Л') — при Х» = 8 »-1 для некоторого конечного значения й точка х — локальный минимум функции )е.
Замечания 3. Алгоритмы с 9-функцией сохраняют для задач выпуклого программирования все преимущества алгоритмов внутренних штрафных функций, например такие, как глобальная схо. димость и возможность получения двойственных допустимых точек, дающих в пределе при я -ь оо решения двойственной выпуклой задачи. В (2601 было показано, что минимизирующей последовательности для Я-функций соответствует минимизирующая последовательность для метода внутренних штрафных функций, отвечающая некоторой специальной последовательности значений козффициентов штрафа.
Библиографические укавп«пя. При написании параграфа использовались работы [285, 536, 373, 464, 522, 5281. В работе [5261 предлагается метод сопряженных внутренних штрафных функций, позволяющий преодолеть трудности, возникающие вблизи границы допустимой области в обычных методах внутренних штрафных функций. б.б. Комбинированные методы штрафных функций 3 а д а ч а 1.
Найти агй ппп 7» (х) для заданной функции «ех 1»: 11" -ь »1» и заданного множества Х. Предположения 1. (») — функция 7» непрерывно дифференцируема; (»а) множество Х имеет вид Х = Х' [) Х", где Х' замкнуто, а Х" замкнуто и замыкание его внутренности Х ' совпадает с Х"; (з»») существует точка х ~ Х такая, что множество Х = (х [ 1» (х) ~( (~е(х)) компактно; (йи) — по крайней мере для одной точки хЯ ~ Х, являющейся оптимальным решением задачи 1, найдется такой открытый шар У, что х ~ У и пересечение внутренности множества Х" с множеством У' = У П Х' непусто. Комбинированные методы штрафных функций представляют собой простую комбинацию методов внешних и внутренних штрафных функций.
На каждой итерации приходится решать задачу минимизации функции без ограничений (минимизируется функция, являющаяся суммой целевой функции 1„внутренней штрафной функции р» и внешней штрафной функции р,). Предельные точки последовательности, состоящей из решений этих задач, при определенных условиях будут решениями задачи 1. В общем случае комбинированные методы дают лучший результат вычисления условного минимума функций по сравнению а каждым методом в отдельности. Алгоритло 1 1. Положить /г = О. П. Построить функцию р» (х), принадлежающую последова тельности внешних штрафных функций для множества Х' (определение последовательности внешних штрафных функций и способы нх построения приведены в $ 5.3). 1П.
Построить функцию р» (х), принадлежащую последовательности внутренних штрафных функций для множества Х' (опреде. ление последовательности внутренних штрафных функций и спасо. бы их построения приведены в й 5А). И. Найти х» — какой-нибудь локальный минимум задачи оптимизации без ограничений: найти ага гп!п (1о (х) + Р, (х) + Р» (х)).
зех" о Ч. Положить й = й + 1 и перейти к шагу П. Творе»»а 1. Прстьвыполненыпредположения1 и суи[еспшует та",о каяточка х" Е Х ', что множество (х ) 1» (х) ~ ~1» (х ) + Ро (х ) + Ро (х )) компактно. Тогда каждая предельная точка последовательноапи (х»)»,.о, порожденной алгоритмом 1, является оптимальным Решением задачи 1. Библиографические указания. Параграф написан на основании работы [286[. В работе [5301 предлагается комбинация метода порождаюших столбцов и метода внешних штрафных функций, в работе [4311 — комбинировапкый метод множителей и штрафных функций.
5.6. Стокастнческий метод штрафов 3 ада ч а 1. Найти агдш)пЕР,(х, а), где «а.ь. 'л'=Х () (х)ЕР/(х, а)(0, 1 1, ..., т). Предположения 1. (1) — значения // (х) «»ЕР/ (х, в), / О, 1, ... ..., т, не вычисляются (или их практйческое вычисление слишком трудоемко), а значения Р/ (х, а), 1 = О, 1, ..., т и градиенты этих функций вычисляются с требуемой точностью; (и) — почти прн каж- дом значении состояния природы в функции Р1 (х, а),1 = О, 1, ... ..., т, непрерывно дифференцируемы по х; (и() — Х вЂ” выпуклое замкнутое ограниченное множество. Решение задачи 1 сводится к решению следующей задачи.
3 а д а ч а Г. Минимизировать по х функцию р(х, с) = 1,(х)+ ~ с/ф/(х))1/(х) 1 при ограничениях х ~ Х, где с = с (р) = (с, (р), ..., с,„0))); с/(р) = а, р)0, = О,р<О, 1=1,...,т, (6.34) здесь а — достаточно большое число. При достаточно большом конечном значении а решение задачи 1' будет решением задачи 1. Алгоритлг 1 Н а ч а л о. 1. Выбрать: произвольные начальные приближения х» ~ В" и гг Е В"; начальные значения шатовых множителей р, (0) и р, (0), удовлетворяющие условиям теоремы 1; выбрать «достаточ- но большое» число а ) О. 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
