И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 62
Текст из файла (страница 62)
Алгоритм 1' Н а ч а л о. 1. Выбрать начальное приближение хч р В". П. Выбрать константы 6, ) 0 и р ) О. П1. Положить й = О. Основной цикл. 1Ч. Положитьх=х". Ч. Положить 6 = 6,. Ч1 Найти множество индексов Оь(х) (шаг Ч1 алгоритма 1). ЧП. Найти вектор й (х) (шаг ЧП алгоритма 1). ЧП1. Если й (х) = О, то положить х*= х и прекратить вычие- ления; иначе перейти к шагу 1Х. 1Х. Вычислить следующее приближение х"+' = х+ рй(х). Х. Положить й = я + ! и перейти к шагу 1Ч. Теорема 1'. Пусть хь — решение задачи 1 и выполняются еле. дующие условия: (!) — для любого доспиипочно малого 6 ) 0 вспомо.
гат ель нал задача квадратичного программирования — найти агкш!п~(Ч1,(х), 6) -(- — '1й(~'~ при ограничениях (Ч1!(х), 6) -(- ~!(х)(0, )ЕОг(х), где аь(х) = Ц~~,(х)~вшах~,(х) — б, )~О), ~ИХ разрешима; (й) — функции ~1 — дважды непрерывно дифференцируе- мы и градиенты Ц~ (х"), 1 ~ аь (х*), где О,(")=(111,(*)=О, Ий), линейно независимы; ((и) — в точке х* выполняются необходимые условия минимума в форме Ч1ь (хФ) + ~ )~ь~7( (х~) = О /яя,ыи и Х1 ) О, 1 Е Иь (хь); (Юо) — выполняется достаточное условие ло- кального минимума, т. е. (й, "т(;„; "' й))О для всех й чь О и удовлетворяющих условию (Ь, Ч~~(х~)) = О, 1ЕИ,(х*), где ~Р(х, ь) = 1ь(х) + ~; Ч,(х); 1ЕХи о вектор У состоит из компонент Х;, 1 Е 21ь (х*). Тогда существуют такая окрестность У точки х* и константы б, ) О, а ) О, что бесконечная последовательность (хь)Г~, порожденная алгоритмом 1', сходится к точке хь с любого начального приближения х' Е У с геометрической скоростью, т.
е. существует такое число О ( о, < 1, юпо (~х" — хь)(()г(д,)", (3,<оь, для всех достаточно больших значений й. Теорема 1". Если выполнены все предположения теоремы 1' и, кроме того, число индексов в множестве Иь (х*) равно и (размерности пространства), то бесконечная последовательность (хь) ь=в, порожденная алгоритмом 1' при р = 1, сходится в некоторой окрестности точки х' с квадратичной скоростью, т, е.
~ хь+' — х*1((1, ~хь — хь(ь, р, < оь. а. Отааяячеиия типа равеяьчв 3 а Д а Ч а 2. НайтИ ата ПЦН 1ь (Х) ДЛЯ ЗаДаННОй ФУНКЦИИ счх 1ь: В" -+ В' и множества Х, задаваемого соотношением Х = [х~),(х) =О, 1=1, ..., т, хЕЛ"). Предположение 2. Функции /ь / = О, 1, ..., т — дважды не- прерывно дифференцируемы. Алгоритм 2 Н а ч а л о. 1. Выбрать начальное приближение х' и числа )!с, ! = 1, ..., т. о П.
Положить й = О. О с н о в н о й ц и к л. Ш. Если выполняются равенства Ч/.(")+ Ей'Р/(")=О' ! 1 /!(х")=О, о=1, ..., т, то положить х'= х» и прекратить вычисления; иначе перейти к шагу 1Ч. П/. Вычислить производную д!р(х', )»»)/дх функции Лагран- жа по формуле »! д<р (х", У)/дх = д/о (х»)/дх + ~; )»; д/! (х')/дх. »=! »/. Вычислить матрицу вторых производных д»!р(х', У)/дх» функции Лагранжа по формуле до<р (х», У)/дх» = д»/о (х»)/дх» + ~ )»!~д»/! (х")/дх'. ! ! 'Ч1. Найти вектор/!» и числа 6»,1 = 1, ..., т, удовлетворяющие рйвенствам "т~(' "1 й»+~6!» Ы.»)+ "~ х) =О, ! ! (ч/! (х"), /»») + /! (х») = О, ! = 1, ..., т.
'»/П. Вычислить следующее приближение х»+' =х»+/!». »/П1. Вычислить )!г+' А!+6!, ! 1, ..., т. 1Х. Положить й = й + 1 и перейти к шагу Ш. Теорема 2. Пусть выполнено предположение 2, а также следующие дополнительные предположения: (!) — вторые производные Функций //, / = О, 1, ..., т, удовлетворяют условию Липшица; (»1) — в точке х*, которая является решением задачи 2, градиенты 1/ /! (х~), / = 1, ..., т — линейно независимы, так что существуют множители Лагранжа Ц, !' = 1, ..., т, удовлетворяющие системе 77, (~*) + ~ Л,'Р/, (х*) = О; !-! /! (х») = О, 1 = 1, ..., т; зз! ٠— выполняются условия локального минимума, т.
е. д»р 1х', Л'1 У дх» У))0, если У~О; Щ,(х*), у)=0, 1=1, ..., т, здесь ~р(х, Л) = ~, (х) + 2', ЛД (х) . / ! Тогда, если начальное приближение х' и числа Ли 1 = 1, ..., т, е достаточно близки к х* и Л~, 1 = 1, ..., т, соответственно, то по- следовательность )х"; Л»п 1 = 1, ..., т)» о, порожденная алго- ритмом 2, сходится к (х', Л~, 1 = 1, ..., т) с квадратичной скоро- стью. 8. Ограиичеиии еиешаииого типа 3 а д а ч а 3. Найти агд ппп го (х) для заданной функции хех 1»: Л"- В' и множества Х =- )х)(~(х)(0, 1~8, хЕУ), где У вЂ” заданное выпуклое замкнутое множество; ~~ . Ь"-~ В' (1 ~ О) — заданные непрерывные функции. ЛРедположение 3.
(1) — фУнкции гн 1 Е Г () (О) — непРеРыв- но дифференцируемы, Алгоритм 3 Все шаги, за исключением 1 и Ч11, такие, как и в алгоритме 1. Шаг 1 в алгоритме 1 заменить на Г. Г. Выбрать начальное приближение х' ~ Г. Шаг Ч11 в алгоритме 1 заменить на Ч1Г. Ч1Г.
Найти решение Ь = Ь (х) задачи квадратичного програм- мирования: найти агй ппп '(Ч)е(х), Ь) + — ))Ь))т) прн ограничениях (Ч)~(х), Ь)+1»(х)~(0, )Ело(х), х+ЬЕК, Теорема 3. Если выполнены предположения 3 и существуют та- кие константы 6 ) 0 и а ~ О, что: (1И) — множество Х„= ) х ) Де (х) + а шах )~ (х) (1» (хе) + а шах ~~ (хе), х с )' ), гйу ИУ ограничено; (4о) — градиенты функций 1н 1 Е О () (0), в Х„удов- лепморяют условию Липшица, т. е. ))Чг»(х) — Ч~~(х))(Ч(х — х)), т(оо, х, хеХ„; (о) — задача квадратичного программирования найти агу пип ~(Ч)".е (х), Ь) + -и- ) Ь)~) 1 л 832 при ограничениях (Ч)(х), й)+1)(х)<0, 1Е~г(х), х+йб)', 1з.зз) разрешима относительно й при любых х Е Х„и существуют такие множители Лагранжа а) (х), 1 с Иь (х), что а)(х)(а; )е.угы) (ь() — среди функцийгп 1 Е О, имеется функция Гн равная тождественно нулю (1) (х) — 0), то любая предельная точка бесконечной последовательности (х"]е" е, порожденной алгоритмом 8, принадлежит множеству Х и в этой точке выполняются необходимые УсловиЯ минимдма фУнкЦии )е на множесп)ве Х и, кРоме то.
го, справедливо шах 1) (хе) — )- 0 при й -е- оо, Иу хе~)', й=О, 1, .... (Множители Лагранжа для задачи (6.62) — (5.63) — это такие неотрицательные числа, которые удовлетворяют неравенству (7)'е(х), й(х))+][й(х)1 + ~' к)(х)Щ)(х), й(х))+)')(х)]< /яуеы) ~((Ч]'е(х), й)+ (й(х), й)+ ~л к)(х) [(%7) (х), й)+))(х)] ) саввы) для всех й, удовлетворяющих условию х + й Е у и равенствам й,(х) [(%7,(х), й(х))+~,(х)] =О, )ЕОь(х)). 4. Метод лввеариаавии, правтичееви реалиауевыа ва ЭВМ 3 а д а ч а 4.
Найти агд ппп 1е (х) для заданной функции еех 1ь: В"-ь В' и множества Х = (х ] ~) (х) (~ О, 1 = 1, ..., т, х с В" ] П [х [) ) (х) = О, )=т+1, ..., т+1, хЕВ ], определенного с помощью заданных непрерывно дифференцируемых функций ]). В" -ь В'. Данный алгоритм не требует априорного знания констант а и 6, обеспечивающих сходимость алгоритма. Эти константы вычисляются в процессе счета. Для реализации данного алгоритма требуется эффективная стандартная подпрограмма решения зздачи квадратичного программирования. .Алгоритм 4 Н а ч а л о.
1. Выбрать произвольное начальное приближение хе ЕВ ° 333 11. Выбрать константы 6,) О, 0 < е ( 1, сс, (а, — достаточно большое число). 1И. Положить й = О. Основной цикл, 1У. Положить 6=6„х=х~, а= = аь. Ч. Вычислить ф(х) = шах (О, у,(х), ..., у„(х), (у»»(х)(, ..., (у +с(х)(). Ч1. Найти множество индексов да (х) = (у(у (х) ~ф(х) — 6, у = 1, ..., т); Оь(х) = (у(уу(х)~ф(х) — 6, у =т+1, ..., т+1).
ЧП. Если задача квадратичного программирования найти агдппп((Чу,(х), И) + — ((Ус((') при ограничениях (ЧУ*у(х), Ус)+У'у(х)(О, УЕВ (х); (Чу,(х),ус)+у,(х) =О, уЕОь(х), совместна, то найти ее решение Ус = й', множители Лагранжа Лу, у Е Ч7 (х) (( Ч1(х) и перейти к шагу 1Х; иначе перейти к шагу ЧП1. Ч111. Положить х"+' = х, аа» с = а, 6~»1 = 6У2 и перейти к шагу ХЧ1. 1Х. Положить з = О. Х. Вычислить р„= (1У,)'. Х1.
Если выполняется неравенство У~(х+ р~Ус~) + а$(х+ рьУсь)(У,(х) + аф(х) — ер„16" ((', то перейти к шагу ХП; иначе положить з = з + 1 н перейти к шагу Х. Х11. Вычислить следующее приближение ха+' = х+ раус". ХП1. Положить ба+1 = 6. Х1Ч. Если выполняется неравенство сс) ~ Лу+ ~", (Лу(, !ЕГд"гл уефа то положить аь»» = а и перейти к шагу ХЧ1; иначе перейти к шагу ХЧ.
ХЧ. Вычислить "~-ч х ~+ х Р~~) ~уята (м у~,т'~~(м ХЧ1. Положить Ус = й + 1 н перейти к шагу 1Ч. Для алгоритма 4 справедливы теоремы сходимостн, аналогичные теоремам пункта 1. Отметим, что начиная с некоторого значения й, величпны аа и 6„ не будут меняться. 334 а. Аналог метода линеариаапвв в детерминированных задачах минимваацив почтв двфферевцируемых функций 3 а д а ч а 5. Найти агй ш!иге (х) для заданной функции «ел ге: В" -~ В' и заданного множества Х с= В". Предположения 5.
(1) — функпия !е — почти дифференцируема; (В) — Х вЂ” выпуклое, ограниченное и замкнутое множество, образованное неравенствами )~(х) < 0. где ~~: В" — ~ Вт — выпуклые функции. Данные методы используют общую идею метода линеаризации и основаны на понятии почти градиента минимизируемой функции. Алгорин».н д Н ачало. 1.
Выбратьи начальное приближение хе ~ Х, начальное значение г' Е В", начальное значение щаговых множителей р„ае и величину смещения Ь„удовлетворяющие условиям теоремы 5. 11. Положить й = О. Основной цикл. 111. Вычислитьхь(=1, ...,а — независимые случайные величины, равномерно распределенные на отрезках х» — — х'+ — ~ 1 1 ... и. [ «»» е»" с з)> 1Ч. Вычислить вектор 0(х", й) — ~~~„[~е (хы ..., х~ + —, ..., х„) 1 ! Г-»» о» -»| где е', ! = 1, ..., а — 1-й орт. Ч. Вычислить вектор у» Е Х, удовлетворяющий условию (г", у») пп'п (г», х).
«ех Ч1.. Вычислить вектор х»+' х» — р, (х» — р»). ЧП. Вычислить вектор г»+' г'+ >х» (О (х", й) — г"). Ч!П. Найти значения щаговых множителей р»+ь а»+1 и значение смещения б»+ь удовлетворяющие условиям теоремы 5. 1Х. Положить'й ° й + 1 и перейти к шагу 111. Теорелси 6. Пусть выполнены предположения 6 и, кроме того, имеют место условия 0<р»(1 и б«)0 при 6 = 0„1, ...; ОО ~о р«= оо, р«/а«б«-» 0 при /с~со; »-о Ю Е (р»/6)'<"., Е и'<ж »-о «=о )6» — 6«+с(/р — О, б«-еО при й- оо, Тогда с вероятностью 1 предельные точки последовательности (х")ь о, порожденной алгоритмом 6, принадлежат множеству Х" решений задачи 6 и последовательность (/о (х"))«=о почти наверное сходится.