|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О новых модификациях обобщенного седлового варианта метода уровнейстатья
- Автор: Соколов Н.А.
- Журнал: Обозрение прикладной и промышленной математики
- Том: 14
- Номер: 3
- Год издания: 2007
- Издательство: Научное издательство «ТВП»
- Местоположение издательства: Москва
- Первая страница: 563
- Последняя страница: 567
- Аннотация: В докладе предложены новые модификации обобщенного седлового варианта метода уровней [1], [2] для отыскания седловой точки выпукло-вогнутой функции if(x, у), /iэффективное множество G которой содержится в декартовом произведении многогранников G = iG/isubix/i/subi /iX iG/isubiy/i/subi /iи, вообще говоря, не совпадает с G, т. е. функция / определена конечными значениями не во всех точках G. «Классический» седловой вариант метода уровней (G i~ /iG) описан в [3], [4]. Рассмотренные модификации метода близки к описанным в [5]; установлена оценка сходимости этих модификаций. 1. Постановка задачи, описание оракула. Пусть iG/isubix/i/subi /iи iG/isubiy/i/subi /i- выпуклые компакты с непустыми внутренностями, расположенные в конечномерных евклидовых пространствах iЕ/isubiх/i/subi /iи iЕ/isubiу/i/subi, /iи пусть iG/isubix/i/subi /iС iЕ/isubiх/i/subi /iи Gsuby/sub С iЕ/isubiу/i/subi /i- выпуклые многогранники, содержащие, соответственно, Gsubz/sub и iG/isubiy/i/subi. /iОбозначим G = iG/isubix/i/subi /iх iG/isubiy/i/subi, G = G/isubix/i/subi /ix iG/isubiy/i/subi, E = E/isubix/i/subi /ix iE/isubiy/i/subi./i Рассмотрим функцию /(г) = if(x,y), z /i= i(x,y), /iопределенную конечными значениями на множестве G. Относительно / примем следующие допущения: A)) функция / выпукло-вогнута на G, т. е. при любом фиксированном iх° /i6 iG/isubix /i/subi/iB)функция if(x°,y) /iвогнута по iу /iЈ iG/isubiy/i/subi /iи при любом фиксированном iу° /iЈ iG/isubiy/i/subi /iфункция iC)f(x,y/isupia/i/supi) /iвыпукла по х Ј iG/isubix/i/subi;/i D)функция / удовлетворяет условию Липшица с постоянной iL, /iт.е. при любых iE)(х, у), (х/isupi1/i/supi, у/isupi1/i/supi), (х", у") /iЈ G имеют место неравенства !/(*,»') - /(*,»")! ill»sup1/sup - Л1, !/(*',») -/(*",»)! ill*sup1/sup i- х"\\, /i(1) Сделанные предположения относительно G и if(z) /iобеспечивают непустоту множества iZ* - X* /iX iY* /iседловых точек функции /(г) на G, т. е. для любых точек г = i(х,у) /iЈ G, г* = i(х*,у*) /iЈ iZ* /iвыполнены неравенства if(x*,y) /i^ if(x*,y*) /i if(x,y*)./i Кроме того, из А), В) вытекает субдифференцируемость функции / по iх /iи супер-дифференцируемость функции / по iу /iв каждой точке i(х,у) /iЈ G. Для произвольной точки iу /iЈ iGy, /iесли iх /iЈ hit iG/isubix/i/subi /iи i1/isubiХ/i/subi /i- произвольный элемент множества idf/isubix/i/subi(x,y), /iто ||/subz/sub|| ^ iL; /iдля точек iх /iЈ idG/isubix/i/subi /iсубдифференциал idf/isubix/i/subi(x,y) /iнеограничен, но существует 564 iVIII Всероссийский симпозиум по прикладной и промышленной математике/i субградиент i1/isubiХ/i/subi /i6 idf/isubix/i/subi(x,y), /iдля которого ||fsubz/sub|| ^ iL. /iАналогично, для произвольной точки iх Ј G/isubix/i/subi, /iесли iу /iЈ int Gsuby/sub и il/isubiy/i/subi /i- произвольный элемент множества idf/isubiy/i/subi(x,y), /iто i\\ly\\ /i^ iL; /iдля граничных точек i(у /i6 i9G/isubiy/i/subi) /iсупердифференциал idf/isubiy/i/subi(x,y) /iнеограничен, но существует суперградиент i1/isubiУ/i/subi /i6 idf/isubiy/i/subi(x,y), /iдля которого ||fsuby/sub|| ^ iL./i Далее предполагается, что многогранники iG/isubix/i/subi /iи iGy /iзаданы двумя системами линейных неравенств. Что же касается выпуклого компакта G - iG/isubix/i/subi /ix iG/isubiy/i/subi /iС G и функции /, определенной на нем, то они задаются не аналитически, а алгоритмически, т. е. с помощью некоторого алгоритма, называемого iоракулом. /iОтветы оракула подчиняются следующим правилам. 1)Если iz° Е /iint iG, /iто оракул вычисляет if(z°) /iи находит некоторые субградиент 'z(zsup0/sup) 6 id/isubix/i/subif(z°) /iи суперградиент il/isubiy/i/subi(z°) /i6 id/isubiy/i/subif(z°), /iт.е. ответом оракула (типа 1) является набор /(г°)Л(sub2/sub°)Л(А(2) 2)Если г° = (z°, iу°) /iG, т.е. если iх° /iЈ iG/isubix/i/subi /i\ iG/isubix/i/subi /iи/или iу° e~G/isubiy/i/subi\G/isubiy/i/subi, /iто оракул находит гиперплоскость (одну или несколько), разделяющую точку iz° /iи множество G, т.е. вычисляет такие вектор ia/isubiz/i/subi(z°) /i€ iЕ /iединичной длины и скаляр ia(z°) /i^ О (отклик типа 2), что для всех iz /iЈ G (a,(*V-*°) + a.(*°KO.(3) 3)Остался случай, когда точка z° принадлежит границе множества G. В [1] для всех точек из idG /iоракул выдает информацию типа (2). В [2] оракул обрабатывает граничные точки 9G так же, как точки множества G \ G, т.е. выдает одну или две гиперплоскости вида (3). В общем случае оракул в граничной точке множества G может использовать любой из предложенных способов (либо оба сразу). 2. Описание новых модификаций обобщенного седлового варианта метода уровней. В предложенных ранее седловых вариантах метода уровней [1], [2] отдельная итерация алгоритма, связанная с вычислением очередной точки iz/isubik/i/subi+i /i€ G, заключается в решении одной задачи линейного программирования и одной задачи квадратичного программирования; получены оценки скорости сходимости этих методов (порядка О (it"sup1/sup/sup2/sup)) при условии, что множества iG/isubix/i/subi /iи iG/isubiy/i/subi /iзамкнуты и имеют непустые внутренности. Рассмотрим новые модификации обобщенного варианта метода уровней для нахождения на выпуклом компакте G седловых точек выпукло-вогнутой функции if(z). /iОбобщение производится в нескольких направлениях: новый метод является «гибридом» седловых методов [1], [2]; можно произвольным образом нормировать векторы /(г;) = (/subг/sub(г;), i-l/isubiy/i/subi(zi)) /iи аsubг/sub(г,-) = (asubz/sub(zi), asubv/sub(z,-)); вместо одного, постоянного для всех итераций алгоритма числа А используется набор, вообще говоря, различных чисел А,-, iг - /i1,2,...; разрешено добавлять на каждой итерации несколько линейных ограничений любого типа; вместо единичной матрицы в задаче квадратичного программирования используется произвольная симметричная положительно определенная матрица; вспомогательные задачи линейного и квадратичного программирования решаются приближенно. Зададим множества sq = 0, ао = 0 и число по = 0, также выберем числа ао Ј (0,1) и ifo /i0 (например, ао = 1/2, ifo - /i1) и произвольную точку iz\ /i€ G. Введем положительно определенную матрицу симметричную iН /i(с собственными числами О ih/isubim/i/subi\/isubin/i/subi /i^ /Imax И ЧИСЛОМ обуСЛОВЛеННОСТИ iЦ = /i/Imax/Umin)- Пусть уже построено ik (k /i^ 1) точек г,- Ј G, iг - /i1, 2,..., fc, определены множества Afc_i, Sfc_i, |Sjt_i| = irik-i. /iС точкой iZk /iсвяжем ть (т ^ 1) откликов оракула Jfc = {njt_i +1,..., п^}, njt = ink-i /i+mjt (типы откликов оракула описаны ранее). Отклики типа 1 обозначим iJ'/isubik/i/subi, /iони порождают три подтипа неравенств. К подтипу Jgj., IJgj.1 = im'/isubiQk/i/subi, /iотнесем неравенства вида iР,(г^\\^(г/isubiь/i/subi)\\-/isupi1/i/supi g[(l/isubixi/i/subi(z/isubik/i/subi),x-x/isubik/i/subi) - (l/isubiy/i/subij(z/isubik/i/subi),y-y/isubik/i/subi)] + ty ~ tx /i^ 0, к подтипам iJ'/isubixk/i/subi /iи iJ/isubiyk/i/subi, \J'/isubixk/i/subi\ = \J'/isubiyk/i/subi\ - m'/isubilk/i/subi, /iотнесем, соответственно, iVIII Всероссийский симпозиум по прикладной и промышленной математике /i565 неравенства вида iF/isubi0/i/subi[(l/isubixj/i/subi(z/isubik/i/subi),x-x/isubik/i/subi} + f(z/isubik/i/subi)]-t/isubix/i/subi /i О, i-F/isubi0/i/subi[(l/isubiyj/i/subi(z/isubik/i/subi),y-y/isubik/i/subi)+f(z/isubik/i/subi)]+t/isubiy/i/subi /i 0. Здесь iFj(z/isubik/i/subi) (j /i6 jqj.) - положительные числа (задаваемые пользователем), if(z/isubik/i/subi), lj(/isupiz/i/supik) /i= dj i(/isupiz/i/supik}i ~lyj /i(supz/supfc)) ?Ј (0 ! 0) - информация, выдаваемая оракулом (см. (2)). Итак, множество iJ'/isubik/i/subi /iразбито на три взаимно непересекающиеся подмножества iJ'/isubiQk/i/subi,/i supiJ/i/supixk /i"^*, i\J'k\=/isupim/i/supi'k=/isupim/i/supiOk+^/isupim/i/supi'lk-/i Оставшиеся отклики оракула (типа 2) обозначим Jjj.' = iJ/isubik/i/subi /i\ Jjj., i\J'/isubik/i/subi'\ - m'/isubik/i/subi. /iОни определяют неравенства вида iAj(z/isubik/i/subi)[(a/isubixj/i/subi(x/isubik/i/subi),x - x/isubik/i/subi) + (a/isubiy/i/subij(y/isubik/i/subi),y - yj) + atj(z/isubik/i/subi)] + t/isubiy/i/subi - t/isubix/i/subi /i^ 0, где числа iAj(z/isubik/i/subi) /i0, ij /iЈ Jjj.', задаются пользователем, аsub;/sub-(г*;) = (агД^А;), iyj (j/fc)), ||i;(supz/sup*;)ll = 1 J € Jjj.'. В итоге имеем im/isubik/i/subi = m'/isubik/i/subi + m'/isubik/i/subi. /iПоложим iS/isubik/i/subi = /iSt.! iUJ/isubik/i/subi,S'/isubik/i/subi= S(_/isubil/i/subi /iU 4, 5^' = 5^_j U Jjj'. Поиск точки 2jt sub+/sub i € G начинается с решения задачи iA/isubik/i/subi /iи задачи iA/isubik/i/subi, /iей двойственной. Задача линейного программирования iA/isubik/i/subi /iимеет вид: - it/isubix/i/subi /i-+ max, (i, j) 6 G, fo [/„(*.-), i* /i- *.- + /(*.-)] ~ » ^ 0, J 6 Ji,-, -Fo[{/suby/sub,-(«0, »-».- + /(*.-)]+ *»0, J6J;., !*, (4) ^(«.ОН'Л'ОГЧОС*.-),*-*.- + *» -*» о, J 6 ^.-,. ^(z.-)[{asub;/sub-(^), ^ - г,-) + «,-(*,)] + j, - it/isubix/i/subi /i 0, j e J/', переменными которой являются точка iz = (х, у) /iи два числа it/isubix/i/subi /iи ity. /iОбозначим Д^ - максимальное значение линейной формы задачи iA/isubik/i/subi. /iПо построению Д^ ^ 0 для всех ik ~?Ј /i1 и последовательность {Д/t} монотонно невозрастает. Если множество Jjj. iф /i0, то вычисляется ik-e /iприближение zjj к множеству iZ*:/i -:=Е[Еч+ЕЧ"/1:[Е^+Е« »* где «j ^ 0, j G J^.,-, «j ^ 0, j e J^,-, ш,- ^ 0, j Ј Jg,., 1 ^ » ^ ik /i- компоненты оптималь- ного плана задачи iA/isubik/i/subi, /iсоответствующие первым трем первым группам неравенств в задаче iA/isubik/i/subi. /iМожно показать, что, начиная с некоторого номера ik, /iпри fe ^ ik /iмножество Jjj iф 0 /iи оба знаменателя положительны. Итерационный процесс оканчивается, если точка iz/isubik/i/subi /i«близка» к множеству седловых точек Z*, в противном случае доопределяется множество Afc = Ajt_i U {Aj-: Ay iЈ /i(0,1), ij /i6 iJ'/isubiok/i/subi, /iA,- = ао, ij Ј /iJjj. \ jqj.}, вводятся масштабные множители iFj(z/isubik/i/subi) /i 0, j 6 Jjj. \ iJ'/isubiQk/i/subi, Aj(z/isubik/i/subi) /i 0, ij ' Ј /iJjj.', и для нахождения точки iz/isubik/i/subi + i /iрешается задача квадратичного программирования iB/isubik/i/subi /iвида непустой при фиксированном it /i6 [О, Д*] выпуклый многогранник iG/isubik/i/subi(t;A/isubik/i/subi) /iС iЕ /iявляется проекцией на iЕ /iмногогранника, определяемого при помощи условий задачи iA/isubik /i/subi/iи дополнительного условия it/isubiy/i/subi - t/isubix/i/subi /i^ aq!. Далее итерационный процесс повторяется ДЛЯ НОВОЙ ТОЧКИ 566 iVIII Всероссийский симпозиум по прикладной и промышленной математике/i 3. Обоснование сходимости седловых вариантов обобщенного метода уровней. В качестве меры близости точки iz = (х, у) /iк множеству iZ* /iестественно (см. [1]-[4]) взять сумму уклонений точек iх /iи iу /iот множеств iX* /iи У*, т.е. Д(г) = i(р(х) /i- р*) + i(ф* - /isupi//i/supiф(у)) = р(х) - 1р(у), /iгде Ј* i- ф* = f(x*,y*) /i- оптимальное значение пары задач i(р(х) = /imaxsuby6/sub^ if(x,y) /i- min^^, iф(у) = /imin^^ if(x,y) /i-+ тах^^. Функция A(z) неотрицательна для всех точек iz /i€ G и обращается в нуль лишь при iz /iЈ iZ*. /iБудем использовать метод до тех пор, пока не получим неравенство Д(**)е,(8) где iЈ /i 0 - наперед заданное число. Точку iz/isubik/i/subi, /iвычисленную по формулам (5) и удовлетворяющую (8), назовем iс-седловой точкой функции f(z) на G. /iПоложим fl/Fo, iS'/isubik/i/subi\S'/isubik/i/subi*0,/i °~supil/i/supi-/i°' Ft = тах{?sub0/sub,?И, * = 1,2,..., iF = /isup{Fsubfc/sub}. fc^i Теорема. iПусть f /i- iвыпукло-вогнутая функция, определенная конечными значениями на выпуклом компакте G = G/isubix/i/subi /ix Gj, iи удовлетворяющая на нем условию Липшица /i(1), a G = Gsubx/sub x iG/isubiy/i/subi /i- iмногогранник, содержащий G, каждый из многогранников G/isubix/i/subi и G/isubiy/i/subi имеет диаметр d, каждый из компактов G/isubix/i/subi и G/isubiy/i/subi содержит шар радиуса г /i 0. iПусть седловой вариант метода уровней /i(4)-(7) iзадается с помощью положительно определенной симметричной матрицы Н с числом обусловленности и и трех последовательностей чисел:/i Afc = {А,- : 0 А А; А 1, ij /i6 iJ^, \j /i= Аsub0/sub € (A, A), ij /ie iJ[ \ J^, l^i^ k],/i Ajt = {^j(z,-): 0 A Aj(z,-)3oo, j e iJ", l^i^k], где l/F ^ F/isubi0/i/subi /i F/(i-y/2), если 5Jsubfc/sub Ј SJ. ^ 0, и пусть 5 - тах{Л, F}. iТогда седловой вариант метода уровней вырабатывает при k /i iК(Ат) точку z/isubik/i/subi, мера близости которой к седловому множеству Z* допускает оценку/i A^KCQATsup1/sup/sup2/sup,(9) iгдеС = [2L(d-r)/(Ar) + F], /iQ = i~BdJlji\-/isupi1/i/supi /i(I - Аsup2/sup)-sup1/sup/2sub;/sub iK(z) = (Q/z)/isupi2/i/supi._ В частности, для любого /iе 0 iможно найти е-седловую точку /i/(г) на G iза k/isubie/i/subi итераций, причем k/isubic/i/subi /i^ 1 + тах{Л"(е/С), iК(Аг)}./i В неравенстве (9) обычно константы iL, г, /iа, возможно, и iA, F, В, /iА, А, определяющие iС /iи iQ, /iнеизвестны. Поэтому для получения оценки (9) одновременно с задачей iAk /iвида (4) будем решать, например, некоторую (другую) задачу линейного программирования iA'/isubik/i/subi, /iотличающуюся от задачи iА^ /iотсутствием переменных it/isubix/i/subi /iи it/isubiy/i/subi /iв последней группе ограничений, а также отсутствием всех нормирующих множителей iaj, j /i€ iS/isubik/i/subi, Fa, fj, j /iЈ iS'/isubiok/i/subi /i(точнее, все эти числа равны 1). Пусть A'subfc/sub - максимальное значение линейной формы задачи iA'/isubik/i/subi. /iТогда легко проверяется, что Д^ ^ Ajfe/F. Кроме того, для ik /i iK(Ar) /iмножество iS'/isubik/i/subi ^ 0 /iи можно определить точку iz'/isubik/i/subi /i= i(x'/isubik/i/subi,y'/isubik/i/subi) /iG G с помощью формул, аналогичных формулам (5). Можно показать, что последовательность {Д'д.} стремится к нулю с той же скоростью, что и {Д,ь} (точнее, если Д* i Аг, /iто Д(г]|.*) ^ Д'^ ^ iC/isubik/i/subi)./i Для поиска е-седловой точки в предлагаемом варианте метода уровней можно использовать правило остановки: тт{Д'д., ттsub;/sub-subе/subл^sub0/sub. ifc{ll'j(sup2;/supi)ll/('sup;/sup''v/2)}} ^ iе. /iКонечной точкой можно считать либо точку iz'/isubik/i/subi, /iесли Д'д. ^ Ј, либо точку iгь*, /iесли iVIII Всероссийский симпозиум по прикладной и промышленной математике /i567 наименьшая норма вектора /у(г/ь*), 1 ^ ik* /i^ ik, /iдостаточно мала. Итак, Ј-седловая точка функции /(г) на множестве G находится для любого е 0 за конечное число шагов, равное iО /i(е~sup2/sup). Для уменьшения трудоемкости метода уровней рекомендуется решать задачу iA'/isubik/i/subi /iне на каждой итерации, а, например, через 10 итераций. В докладе рассматриваются также варианты обобщенного седлового варианта метода уровней для случая, когда на каждой итерации одна и/или обе вспомогательные задачи i(A/, /iBjt) решаются приближенно; приводится оценка скорости сходимости и для этих вариантов. Работа выполнена при финансовой поддержке РФФИ, проект № 05-01-00491.