Содержание к диссертации
Введение
1 Оценки расстояния до решения и идентификация активных индексов 18
1.1 Смешанные комплементарные задачи 18
1.2 Связь с другими задачами 22
1.3 Переформулировки МСР в виде систем уравнений 25
1.4 Оценки расстояния до решения и условия регулярности -. 42
1.5 Идентификация активных индексов 52
2 Ньютоновские методы 56
2.1 Локальные методы активного множества 56
2.2 Глобализация сходимости 65
2.3 Сравнение с другими методами ньютоновского типа 71
3 Системы Каруша-Купа—Таккера 75
3.1 Постановка задачи 75
3.2 Оценки расстояния до решения 76
3.3 Идентификация активных индексов и ньютоновские методы 81
3.4 Сравнение с. другими методами
А Вычислительные эксперименты с идентификацией 92
Б Вычислительные эксперименты с ньютоновскими методами 97
Б.1. Локальные численные эксперименты 97
Б.2 Численные эксперименты с глобальной схемой 101
Заключение 107
Литература 108
- Переформулировки МСР в виде систем уравнений
- Локальные методы активного множества
- Сравнение с другими методами ньютоновского типа
- Идентификация активных индексов и ньютоновские методы
Введение к работе
В работе рассматривается новая постановка задачи, лишь недавно получившая распространение в оптимизационной литературе, а именно, смешанная комплементарная задача (Mixed Complementarity Problem, МСР), которая представляет из себя вариационное неравенство на параллелепипеде. А именно, пусть задан параллелепн-
пед [Є7и] С R71, гдеl = (tu*я (n)tи = (иъ^,,...,^),^ є Ми{-сю},^єКи{+со},
і < itf, г = 1,2,..., п, и отображение F : R" — Жп} которое в дальнейшем будет предполагаться достаточно гладким. Требуется
найти я Є [Є,и] такой, что (.Р{а;),х-я) ^0 Уд; Є [Є,и]. (1)
Эквивалентным образом МСР формулируется в виде
найти х Є [,и] такой, что Fi{x)
(2)
Многие задачи, связанные с отысканием разного рода равновесий, могут быть записаны в формате МСР (см. [40, 32, 29]). Кроме того, этот формат объединяет в себе целый ряд важнейших постановок, возникающих в теории оптимизации, вариационном исчислении и других областях математики. Перечислим некоторые из таких постановок.
1. Система нелинейных уравнений
F{x) = 0, (3)
где F : R11 —* R" — заданное отображение.
2. Комплементарная задача (Nonlinear Complementarity Problem, NCP), состо
ящая в отыскании элемента iGl" такогоа что
х 0, F(x) 0, {xt F{x)) = 0, (4)
Введешіе
где F : R" —* IK" — заданное отображение.
3. Система Каруша-Куна—їаккера (ККТ)
9(х)-(С'(х))тц = П, (5)
/^0, G(z)^0, =0,
относительно (я, /л) Є Rp x R где # : Rp -+ № и G : Ш -* R7" — заданные отображения. Переменную х Є W принято называть прямой, a fi Є Km — двойственной. Если для некоторой функции f : Rp —* R выполнено
то при выполнении определенных условий регулярности ограничений система ККТ даст необходимые условия первого порядка локальной оптимальности в задаче оптимизации
f(z) -+ min, z є D = {z 6 W | G(z) ^ 0}.
Приведем обзор основных известных подходов к построению ньютоновских методов для решения задач вышеперечисленных классов.
Различным методам решения гладких систем уравнений посвящены монографии [12, 9], причем особое внимание там уделено методу Ньютона и квазипыотоповским методам. Роль ньютоновских методов в современном численном нелинейном анализе и оптимизации трудно переоценить. Согласно теореме Дешшса-Морэ, в соответствующих предположениях ньютоновский характер итерационного процесса является не только достаточным, но и необходимым для высокой скорости его сходимости. Именно поэтому наиболее эффективные и практически востребованные алгоритмы для различных классов нелинейных задач имеют в своей основе соответствующим образом понимаемую и адаптированную ньютоновскую итерацию.
Что касается NCP, то можно выделить следующие известные подходы к численному решению таких задач. В начале 90-х большое внимание уделялось сведению NCP к гладким задачам оптимизации с последующим применением к послед-ним традиционных численных методов оптимизации [2, 36, 59, 60, 76], например, метода последовательного квадратичного программирования (Sequential Quadratic Programming, SQP) [65]. В последнее время все более популярным становится другой подход, основанный на переформулировках NCP в виде негладких систем нелинейных уравнений, которые можно решать с помощью специальных неглаких (так
Введение
называемых полугладких) модификаций метода Ньютона и их практических версий (см, [57, 56, 67, 19, 38, 41, 46, 52, 30, 20, 65, 24]).
В настоящей работе совершенно не обсуждаются методы внутренней точки, поскольку идеология используемого здесь подхода радикально отличается от идеологии этих методов (например, в данной работе не используются никакие предположения типа монотонности или выпуклости). Тем не менее, важность методов внутренней точки несомненна, особенно в контексте задач большой размерности. Для NCP такие методы обсуждались, например, в [37, 78].
Аналогичные подходы применяются и для решения систем ККТ: методы SQP [11, 13]; методы, связанные с переформулировкой в виде систем негладких уравнений [11, GS, 47, 28].
Оценкам расстояния до решения для задач обсуждаемых классов посвящены статьи [44, 53, 64, 47].
Известные методы решения МСР основаны на тех же идеях, что и обсуждавшиеся выше методы решения NCP и систем ККТ. Для МСР известны полугладкие методы Ньютона [Ы, 31, 53], метод Джозефи-Ньютона [51,16], который с одной стороны, представляет из себя результат распространения идеи метода Ньютона на вариационные неравенства, а с другой стороны, в случае оптимизационных систем ККТ сводится к SQP.
Одной из первых работ специально посвященных МСР является [14], где па этот контекст распространяются известные ранее алгоритмы для NCP такие, как SQP [65, 24] и метод внутренних точек [78]. Кроме того, для решения МСР предлагается полугладкий метод Ньютона, для обоснования которого требуется предположение о так называемой ^^-регулярности.
Б [31] рассматриваются алгоритмы, генерирующие допустимые траектории, и локально сверхлинейио сходящиеся к сильно регулярным решениям МСР. Этим требованиям удовлетворяют алгоритмы из [51] и из [70]. Кроме того, в [53] представлены строго допустимые методы Ньютона для МСР. Используется идея метода активного множества, предложенная в [27]. Сначала идентифицируются активные множества. Далее с помошью так называемых функций дополнительности и с учетом полученных множеств МСР переписывается в виде системы уравнений, к которой применяется метод ньютоновского типа.
Для получения практических версий рассматриваемых алгоритмов чрезвычайно
Введение
важным является вопрос о глобализации сходимости рассматриваемых локальных методов- Б (49, 24] сходимость полугладкого метода Ньютона для NCP глобализуется с помощью выбора параметра длины шага посредством соответствующих процедур одномерного поиска. Для МСР аналогичный подход развивается в [31, 25, 53]. Также глобализация сходимости рассматривалась в [48, 63].
Для глобализации сходимости алгоритмов в [14] используется стратегия проксимального возмущения, основанная на методах спуска для монотонных МСР, и позволяющая избежать сходимости траектории к точкам локального минимума функции качества, не являющимися глобальными решениями. Эта стратегия применима практически ко всем методам ньютоновского тина л слабых требованиях к задаче, что существенно повышает робастпоеть комбинированного алгоритма по сравнению с исходным.
Глобализация сходимости алгоритма в [31] происходит следующим образом. Сначала запускается локальный алгоритм. Если в точке, сгенерированной локальным алгоритмом, значение гладкой функции качества достаточно мало по сравнению с предыдущим, то такая точка принимается и алгоритм запускается снова. Иначе осуществляется шаг метода проекции градиента для функции качества. В этом случае получаемые точки гарантированно останутся в допустимом множестве.
Для глобализации сходимости алгоритма в [53] используется следующий метод. Сначала происходит идентификация множеств индексов, потом вычисляется ньютоновское направление! которое проверяется тестом на линейное убывание. Если направление принимается, то оно проектируется на допустимое множество. Иначе осуществляется шаг метода проекции градиента.
В [77] рассматривается немонотонный метод доверительной области для негладких уравнений с ограничениями на параллелепипеде, для которого остаются верны все результаты о глобальной сходимости для монотонных методов. Алгоритм основан на полугладкой переформулировке МСР. Чтобы получить глобальный алгоритм и локальный быстро сходящийся алгоритм, метод ньютоновского типа с проектированием на допустимое множество используется для вычисления побных шагов в методе доверительной области. Показано, что при выполнении условий Денписа-Морэ вблизи сильно регулярного решения метод доверительной области превращается в алгоритм ньютоновского типа.
Для тестирования алгоритмов решения МСР используется специально разработан-
Введение
пая библиотека задач MCPLIB [26], включающая ряд представляющих практический интерес задач — от поиска равновесия по Нэшу в экономических приложениях до задач математической физики большой размерности. Библиотека написана на языке алгебраического моделирования GAMS и позволяет реализациям алгоритмов обращаться к постановкам задач но унифицированному интерфейсу.
Целью работы являются построение ньютоновских методов решения смешанных комплементарных задач, для обоснования сходимости и высокой скорости сходимости которых требуются более слабые предположения, чем для существующих методов; глобализация сходимости новых локальных методов и получение эффективных практически реализуемых алгоритмов.
В первой главе диссертации вводится постановка МСР как вариационного неравенства на параллелепипеде (1).
Приводится эквивалентная формулировка МСР (2). В постановке (2), в отличие от (1), присутствует конечное число соотношений, и в этом смысле она может быть удобнее.
В разд. 1.2 приведены примеры задач, укладывающихся в формат МСР- Многие задачи, связанные с отысканием разного рода равновесий, могут быть записаны в этом формате (см, [40, 32, 29]). Например, необходимое условие первого порядка оптимальности для задач минимизации с гладкой целевой функцией на параллелепипеде имеет вид МСР.
Если ti — —со, щ — +оот і = 1, 2,... j її, то МСР есть система уравнений (3).
При і\ = 0, щ = Ч-оОі і = 1,2,... ,ті, МСР превращается в NCP (4).
Систему ККТ (5) можно записать в виде МСР. Для этого следует положить и = Р + т,
^ = -co, і — 1,2, ...,p, ^ = 0, ї =p+ l,p + 2,,,.,7i, u* =+co, г = 1,2,,.,, n.
Методы, о которых пойдет речь в гл. 2, относятся к классу методов активного множества. Для реализации таких методов нужно классифицировать индексы в искомом решении, используя информацию, доступную в точке, близкой к решению. Для последнего предлагаются процедуры идентификации, которые основываются на вычислимых оценках расстояния до решения.
Пусть х — решение МСР, Каждую координату г = 1,2,..,,п можно отнести к
Введение
одному и только одному из следующих пяти множеств индексов:
Ne = Nt{x) - {і І Хі = u Ft{x) > 0}, Au = Ам{х) = {і \ х, = 4 ВД = 0}, Nu = Nu(x) = {г І xi = «і, ^1(Д) < 0), Л* - Л^(х) = {г | , = uh Л(х) - 0}ї
Удобно будет также ввести следующие множества индексов:
N = N(x) = NUNu={i\ Fi(x) ф 0},
А0 = Д)(ж) = ^иЛ0ті = {% | *(х) = 0, Xi = ii или u*},
A = A{x) = A» U A+ = {і І Д(ё) = 0}.
По аналогии с задачами условной оптимизации! будем называть индексы і А аттие-пылт, индексы Ї&Л+ строго актшпъими, индексы і Є Aq вырО01сденными> индексы і Є N неактивными.
Так называемое условие строгой дополнительности имеет вид А0 = 0. В современной оптимизационной литературе условие строгой дополнительности принято считать слишком обременительным. Нигде в диссертации строгая дополнительность не пред по л агается.
Расстояние до решения должно оцениваться через ту или иную вычислимую невязку MGP. Такие невязки вводятся с помощью (смешанных) функций дополнительности, т.е. таких функций ф : Е х R —* R, для которых множество решений уравнения ^((t,6) = 0 совпадает со множеством решений системы
а ^ 0, Ь 0, ab = 0
и кроме того выполняются импликации
а > 0, Ь< 0 => $(atb) < 0,
а >0Т Ь> 0 => ^(а,Ь) > 0.
Можно предложить множество функций дополнительности, однако наиболее часто используются следующие три:
1) функция естественной невязки (Natural Residual)
ipNR{atb) = min{asb}
теряет гладкость при а = Ь;
Впсдсіїис
2) функция Фишера-Бурмєйстєра
фЕВ{а,Ь) = а + Ь- Va2±h2 обладает большей гладкостью, но все же теряет ее при а = 0 и Ь = 0;
3) всюду гладкая функция дополнительности:
ф3(а, Ь) = 2аЬ - (min {0, а + Ь})2.
Теперь можно записать МСР в виде системы нелинейных уравнений. Если ф — смешанная функция дополнительности, то множество решений МСР совпадает со множеством решений уравнения
Ф{я) = 0,
где отображение Ф : R71 —* R" задается формулой
Fj(x)} если і Є Ifi
(6)
W*W _^Ц( _ ^гвд)( если t Є /ш
VC^i - 4, —^(«» - *і. -^(^))), если і Є 7/и, а множества индексов определяются следующим образом:
Соответствующие выбору ф = V'JVfl» 0 = ^fbj Ф = Фб варианты отображения Ф обозначаются через Фдгд, Фгб и Ф^т соотпетствентто. Подчеркнем, что отображения ^nr и Ф^аі вообще говоря, негладкие, каким бы гладким ни было F.
Систему ^fu(x) = 0 можно решать так называемым полу гладким методом Ньютона, итерация которого имеет вид: для к = 0,1,...
где Ak — элемент В-дифференциала [72, 11] отображения Ф/гд- Условие локальной сверхлинейной сходимости этого метода — ВД-регулярность Ф^-д в решении (т,е, невырожденность элементов І7-дифференциала). Целью данной работы является получение методов со сверхлинейной сходимостью в более слабых предположениях.
Введение
При нарушении л точке 5 условия строгой дополнительности матрица Ф$(ё) неизбежно вырождена, поэтому получение оценки расстояния до решения при Ф = Ф# ссылкой на стандартные результаты гладкого нелинейного анализа невозможно. Это обстоятельство является основной причиной, по которой до последнего времени предпочтение отдавалось главным образом негладким функциям дополнительности. Однако, особенность *s в точке х имеет вполне определенную структуру, которая может быть эффективно использована в рамках теории 2-регулярносги отображений с лип-шицевымн производными, развитой в [44, 45].
Разд. 1.3.2 посвящен вычислению производных по направлению отображений Ф = ФіУЯі Ф — Ф^в» первой производной отображения Ф = Фя и производной по направлению отображения Ф'5.
В разд. 1,4 изучаются оценки расстояния до решения вида
||*-х|| = 0(|1Ф(*)П,
где v — заданный параметр, а Ф — отображение, заданное в (б).
Для Ф = Фдг/; и Ф = ф^д такая оценка при v = 1 равносильна Дгсвойству соответствующего отображения в решении х, которое состоит Б том, что
{ЄМ"|Ч'Ш) = 0} = {0}.
Использование Ф = Фя позволяет получить такую оценку при v = 1/2 при более слабом предположении 2-регулярности этого отображения, которое заключается в том, что
Т = Т(х) = { єкегФЧя)|(Ф7(;0?ЄІтФ'()} = { є кегФ'(я) j W(*;0 = 0) = И»
где Р — ортогональный проектор на (іпіФ'(х))1.
Далее приводятся другие условия регулярности, часто используемые в контексте МСР: условия ВD-регулярности, рсгулярітости максимального В-диффсретщиала и условие сильной регулярности (по Робинсону) [71]. Изучена связь этих условий с вышеперечисленными н
В разд. L5 предложен один из возможных способов идентификации введенных выше множеств индексов, основанный на идее из [27].
Введение
Пусть задана и-идентифицирующая функция pt т.е. непрерывная в нуле справа функция такая, что р(0) = 0 и p{t)/tv —* +со при t -+ 0-h Для произвольного х є Rn положим
A(x) = {i=l,...tn\\Fi(z)\*p{\\V(x)\\)}t
N{x) = {1,..-, n}\A{x)t
Ne(x) = [і Є JV(x) І ^і - і < иі - ц}, Nu{x) = ЛГ(х) \ /ОД,
А0(^) = и^Л(х)\шт{\хі-Єі\>\щ-хі\} ^ р[\]Ф(х)\\)},
А+(х)^А(х)\А0(х)}
Ам(х) = {ієА0(х) | Ti-ti ^щ-Хі), А^{х) = А0[х) \ Аие(х).
Наличие оценки расстояния до решения гарантирует правильную идентификацию вблизи этого решения. Соответственно, при использовании б процедуре идентификации Ф = ^nr или Ф = Фрд нужно предполагать их і?о-свойство в решении, а при использовании Ф — Ч'з — более слабое свойство 2-регулярности этого отображения в решении.
Переформулировки МСР в виде систем уравнений
В настоящей работе совершенно не обсуждаются методы внутренней точки, поскольку идеология используемого здесь подхода радикально отличается от идеологии этих методов (например, в данной работе не используются никакие предположения типа монотонности или выпуклости). Тем не менее, важность методов внутренней точки несомненна, особенно в контексте задач большой размерности. Для NCP такие методы обсуждались, например, в [37, 78].
Аналогичные подходы применяются и для решения систем ККТ: методы SQP [11, 13]; методы, связанные с переформулировкой в виде систем негладких уравнений [11, GS, 47, 28]. Оценкам расстояния до решения для задач обсуждаемых классов посвящены статьи [44, 53, 64, 47].
Известные методы решения МСР основаны на тех же идеях, что и обсуждавшиеся выше методы решения NCP и систем ККТ. Для МСР известны полугладкие методы Ньютона [Ы, 31, 53], метод Джозефи-Ньютона [51,16], который с одной стороны, представляет из себя результат распространения идеи метода Ньютона на вариационные неравенства, а с другой стороны, в случае оптимизационных систем ККТ сводится к SQP.
Одной из первых работ специально посвященных МСР является [14], где па этот контекст распространяются известные ранее алгоритмы для NCP такие, как SQP [65, 24] и метод внутренних точек [78]. Кроме того, для решения МСР предлагается полугладкий метод Ньютона, для обоснования которого требуется предположение о так называемой -регулярности.
Б [31] рассматриваются алгоритмы, генерирующие допустимые траектории, и локально сверхлинейио сходящиеся к сильно регулярным решениям МСР. Этим требованиям удовлетворяют алгоритмы из [51] и из [70]. Кроме того, в [53] представлены строго допустимые методы Ньютона для МСР. Используется идея метода активного множества, предложенная в [27]. Сначала идентифицируются активные множества. Далее с помошью так называемых функций дополнительности и с учетом полученных множеств МСР переписывается в виде системы уравнений, к которой применяется метод ньютоновского типа.
Для получения практических версий рассматриваемых алгоритмов чрезвычайно важным является вопрос о глобализации сходимости рассматриваемых локальных методов- Б (49, 24] сходимость полугладкого метода Ньютона для NCP глобализуется с помощью выбора параметра длины шага посредством соответствующих процедур одномерного поиска. Для МСР аналогичный подход развивается в [31, 25, 53]. Также глобализация сходимости рассматривалась в [48, 63].
Для глобализации сходимости алгоритмов в [14] используется стратегия проксимального возмущения, основанная на методах спуска для монотонных МСР, и позволяющая избежать сходимости траектории к точкам локального минимума функции качества, не являющимися глобальными решениями. Эта стратегия применима практически ко всем методам ньютоновского тина л слабых требованиях к задаче, что существенно повышает робастпоеть комбинированного алгоритма по сравнению с исходным.
Глобализация сходимости алгоритма в [31] происходит следующим образом. Сначала запускается локальный алгоритм. Если в точке, сгенерированной локальным алгоритмом, значение гладкой функции качества достаточно мало по сравнению с предыдущим, то такая точка принимается и алгоритм запускается снова. Иначе осуществляется шаг метода проекции градиента для функции качества. В этом случае получаемые точки гарантированно останутся в допустимом множестве.
Для глобализации сходимости алгоритма в [53] используется следующий метод. Сначала происходит идентификация множеств индексов, потом вычисляется ньютоновское направление! которое проверяется тестом на линейное убывание. Если направление принимается, то оно проектируется на допустимое множество. Иначе осуществляется шаг метода проекции градиента.
В [77] рассматривается немонотонный метод доверительной области для негладких уравнений с ограничениями на параллелепипеде, для которого остаются верны все результаты о глобальной сходимости для монотонных методов. Алгоритм основан на полугладкой переформулировке МСР. Чтобы получить глобальный алгоритм и локальный быстро сходящийся алгоритм, метод ньютоновского типа с проектированием на допустимое множество используется для вычисления побных шагов в методе доверительной области. Показано, что при выполнении условий Денписа-Морэ вблизи сильно регулярного решения метод доверительной области превращается в алгоритм ньютоновского типа.
Для тестирования алгоритмов решения МСР используется специально разработанпая библиотека задач MCPLIB [26], включающая ряд представляющих практический интерес задач — от поиска равновесия по Нэшу в экономических приложениях до задач математической физики большой размерности. Библиотека написана на языке алгебраического моделирования GAMS и позволяет реализациям алгоритмов обращаться к постановкам задач но унифицированному интерфейсу.
Целью работы являются построение ньютоновских методов решения смешанных комплементарных задач, для обоснования сходимости и высокой скорости сходимости которых требуются более слабые предположения, чем для существующих методов; глобализация сходимости новых локальных методов и получение эффективных практически реализуемых алгоритмов. В первой главе диссертации вводится постановка МСР как вариационного неравенства на параллелепипеде (1). Приводится эквивалентная формулировка МСР (2). В постановке (2), в отличие от (1), присутствует конечное число соотношений, и в этом смысле она может быть удобнее.
В разд. 1.2 приведены примеры задач, укладывающихся в формат МСР- Многие задачи, связанные с отысканием разного рода равновесий, могут быть записаны в этом формате (см, [40, 32, 29]). Например, необходимое условие первого порядка оптимальности для задач минимизации с гладкой целевой функцией на параллелепипеде имеет вид МСР.
Локальные методы активного множества
Наличие оценки расстояния до решения гарантирует правильную идентификацию вблизи этого решения. Соответственно, при использовании Б процедуре идентификации Ф = NR или Ф = Фрд нужно предполагать их і?о-свойство в решении, а при использовании Ф — Ч з — более слабое свойство 2-регулярности этого отображения в решении.
Глава 2 посвящена ньютоновским методам решения смешанных комплементарных задач. Б разд. 2Л предложен алгоритм, обладающий локальной сходимостью со сверхлииейпой скоростью. Обсуждаются условия, которые требуются для обоснования нужных свойств алгоритма и связь этих условий с условиями регулярности, рассмотренными в гп. 1. Б разд. 2.2 рассматриваются вопросы глобализации сходимости локального алгоритма, Т.ЄН возможность его совмещения с глобально сходящимися схемами без потери сверхлинейной скорости сходимости локального алгоритма. В разд. 2.3 проводится сравнение локального алгоритма с известными ньютоновскими методами для МСР и обсуждаются условия сходимости рассматриваемых методов.
Если идентифицировать множества А+] АыУ А } Ne и Nu то используя явные выражения хды — Лае Ааи = 4 можно получить полный список известных в результате идентификации уравнений относительно х Є R", которые заведомо удовлетворяются в точке х: Чтобы упростить обозначения, предположим, что компоненты х G R" перенумерованы так, что х = {xA+,xAi)euNr A0uuNj- Тогда система (7) дает
При отсутствии строгой дополнительности (когда AQ ф 0, т.е., \А\ А+), система (8) Судет переопределенной {число уравнений больше числа неизвестных). Для определения хд методами ньютоновского типа нужно оставить в системе лишь Л+ уравнений, а это можно сделать многими способами, в том числе допускающими перемешиванием уравнений. Например, можно рассматривать систему нелинейных уравнений где а С(хл+) — \А+\ х Л-матрица, гладко зависящая от жд+.
Условие слабой регулярности решения, состоящее в том, что является необходимым условием невырожденности Ф С(ХА+) при любом выборе (-) Метод Гаусса-Ныотона для переопределенной системы (8) можно интерпретировать как усеченный метод Ньютона для системы (9) при соответствующем выборе С(-). При этом условие слабой регулярности является и достаточным для невырожденности Ф ( л+)- Соответственно, локальная сверхлипе л пая сходимость обосновывается при выполнении условия 2-регулнрности Ф в искомом решении (что обосновывает правильную идентификацию индексов) и слабой регулярности этого решения. Комбинация этих условий для общих МСР слабее До-свойства Фдгя/ в Б решении {а для систем ККТ равносильна ему).
Можно выбирать С(-) и другими способами. Например, можно взять С(-) С, где С є щИ+1 М1 _ фиксированная матрица. Слабая регулярность гарантирует невырожденность Ф С(ЁА+) ДЛЯ почти любой С, и в этом смысле С можно выбирать произвольным (например, случайным) образом. Это находит отражение в теореме о локальной сверх линейной сходимости, которая модифицируется соответствующим образом. Существует ряд причин, по которым не стоит ограничиваться каким-либо детерминированным правилом выбора Во-первых, можно предложить множество разумных детерминированных правил такого рода, причем при отсутствии серьезного вычислительного опыта весьма трудно утверждать, что какое-то из них предпочтительнее других. Во-вторых, реализация детерминированных правил может быть связана с дополнителытыми вычислительными затратами. В-третьих, возможность выбора постоянной матрицы С общего положения имеет принципиальное идеологическое значение. Кроме того, на практике можно выбирать С ис совсем произвольно, а в более специальных классах матриц, например, пытаясь использовать на итерациях разреженную структуру задачи, либо сохранить прямо-двойственную структуру ее переменных (в случае систем ККТ). Кроме того, представляется, что такой подход дает более гибкие возможности для построения к вази ньютоновских методов.
В разд. 2.2 рассматриваются вопросы глобализации сходимости локального алгоритма с сохранением сверхлинейной скорости локальной сходимости, т.е. совмещение последнего с некоторой глобальной схемой, которая обеспечивала бы попадание траектории метода в достаточно малую окрестность решения с автоматическим переключением на быстрый локальный алгоритм. Здесь для этой цели предлагается использовать гибридную схему, которая уже неоднократно применялась в контексте NCP и МСР (см. [31, 25, 53). Идея состоит п прямой замене ньютоновской итерации итерацией некоторого глобально сходящегося метода в тех случаях, когда первая не обеспечивает достаточного убывания значения оценивающей функции. В противном случае результат ньютоновской итерации принимается. В принципе, эта схема может быть использована для глобализации сходимости любого локально сверхлинейно сходящегося алгоритма, если предполагать выполненной соответствующую оценку расстояния до решения: никакое согласование ньютоновского направления и используемой оценивающей функции по требуется.
Разумеется, такой подход имеет свои недостатки. Основным недостатком является необходимость вычисления на каждой итерации ньютоновского шага с перспективой его последующего отбрасывания (во всяком случае, на начальных итерациях, удаленных от решения). Однако, к сожалению, построение более изощренных схем глобализации сходимости здесь весьма проблематично (см. обсуждение вопросов глобализации сходимости ньютоновских методов в [73]). Кроме того, опыт вычислений, в частности, в упомянутых выше работах, свидетельствует о том, что число итераций, на которых используется не ныотогювекос направление, обычно оказывается сравнительно небольшим (т.е. алгоритм не превращается по существу в медленный глобально сходящийся метод).
Сравнение с другими методами ньютоновского типа
Если предположить, что векторы Fl(x)i і A±t є1, і Є А?", линейно независимы, то из того, что в формуле (1.31) все а; и 0І отличны от нуля, вытекает явная формула для Р: Б частности, включение (1.32), а значит и (1.30), выполняется как равенство, т.е. в этом случае 2-регулярность и полуустойчивость равносильны. Без этого дополнительного условия 2-регуляриость, вообще говоря, слабее полуустойчивости.
Предложение 1-8- Пусть выполнены условия предложения 1.7. Пусть х — полуустойчивое решение МСР (или, что то же самое, пусть выполнена оценка расстояния (1-25) для Ф — Ф д или Ф = FB)- Тогда отобраоюениє Фд2-регулярио в точке х (эквивалентно; выполнена оценка, расстояния [1/28)), но не наоборот.
Доказательство. Тог факт, что из полуустойчивостн решения х слезет 2-регуляр-ность Ф , вытекает из предложения 1.7. То, что 2-регулярность Ф в точке х может иметь место когда оценка расстояния (1.25) не выполняется, уже было показано для двух частных случаев МСР, а именно, КСР [44, пример lj и ККТ [47, пример 2], D
Перейдем к рассмотрению других условий регулярности. Определение 1.7. Отображение Ф : Rn R" называется BD-регулярнъш в точке х, если detA О VA є ЭвФ(х). Для любого локально липшицева отображения .BD-регулярность влечет полуустойчивость (11, утверждение б) задачи 8]- Обратное, вообще г о поря, неверно даже для негладких переформулировок оптимизационных систем ККТ (см. [47, пример 1). Известно, что BD-регулярпость Фд-я не влечет BD-регулярность Фря (см. [25, пример 2.1]). Следующий пример показывает, что обратная импликация также не имеет места, т.е. эти два условия между собой не связаны. Пример 1.5, Рассмотрим NCP при п = 2: F(x) = (-%i + #2)1 $\ О, щ = Н-со, і = 1т2. Тогда х = 0 — решение NCP, и можтто показать, что все матрицы в Д-дифференциале Ф в в я невырождены, в то время как ІЇ-дифференциал Ф /е в х состоит из вырожденной матрицы Подчеркнем, что обсуждавшиеся выше понятия (Яо-свойсгво, полуустойчивость, ВD-регулярность) находят применения не только в теоретических вопросах, но и, например, при анализе сходимости численных методов; см, главу 2. Для if-дпффирснциалов отображений Ф л и Ф в известны вычислимые оценки сверху [31], [54]. Любая матрица Л Є OS R{X) имеет (см, вычисления в раздели 1,3,2) строки вида Множество, образованное всеми матрицами такого вида, будем называть максимальным В-дифференциалом отображения Ф д точке х. Условие регулярности максимального В-дифференциала состоит в невырожденности всех составляющих его матриц. В случае NCP условие регулярности максимального 5-диффсрснциала Ф я в решении х совпадает с известным условием Ь-резулярности этого решения (см, [65)), а в случае систем ККТ — с другим традиционным условием, называемым квазирегулярностью (см, [31]). Известно [8], то для систем ККТ максимальный -дифференциал отображения Фдгя совпадает с Я-дифференциал ом отображения Ф я- Однако, для отображения Ф -н такое утверждение неверно, что показывает следующий пример. Пример 1.6. Рассмотрим систему ККТ при g(z) = z и G(z) — (z,z). Максимальный U-диффсрспциал содержит матрицы вида в то время как невозможно получить элементы -дифференциала такого вида. Это связано с тем, что значения unv, соответствующие второй и третьей строке матрицы, не могут яыбираться независимо. Разумеется, регулярность максимального Я-дпфференциала влечет БО-регулярность соответствующего отображения; обратное, вообще говоря, неверно, что иллюстрирует следующий пример. Пример 1.7. Рассмотрим NCP при п — % F(x) = ((xi + x2)/2,(xi + x2)f2). Точка x = 0 является решением этой задачи, причем, как нетрудно видеть, максимальные -дифференциалы Ф л и Ф я в точке х содержат единственную вырожденную матрицу но эта матрица не принадлежит ни дв н(х), ни дв кв(х) В [25, пример 2Л] показано, что регулярность максимального В-дифференциала ФДТЕ не влечет не только аналогичное свойство для ФҐВЇ но даже BD-регулярность Ф в - Вместе с тем, очевидно, что регулярность максимального В-дифференциала Фрв влечет аналогичное свойство для Ф л Напомним еще одно важнейшее понятие регулярности, введенное в [71]: решение х МСР сильно регулярно (по Робинсону), если для всякого у Є RnT достаточно близкого к пулю, возмущенная линеаризованная МСР: имеет в некоторой окрестности точки х единственное решение, причем это решение зависит or у липшнцевым образом. Сильная регулярность влечет регулярность максимального В-дифференциала Ф я и Ф д. ДЛЯ NR В случае ККТ это установлено в [55), а в случае NCP — в [25, теорема 2.5], причем приводимое там доказательство без изменений проходит и для МСР. Отсутствие обратной импликации для ФдгЯ демонстрируется в [25, пример 2.1]. Для Ф в нужная импликация установлена в [31, теорема 1J, отсутствие обратной импликации демонстрируется следующим примером.
Идентификация активных индексов и ньютоновские методы
Разумеется, такой подход имеет свои недостатки. Основным недостатком является необходимость вычисления на каждой итерации ньютоновского шага с перспективой его последующего отбрасывания (во всяком случае, на начальных итерациях, удаленных от решения), Однако, к сожалению, построение более изовдренных схем глобализации сходимости здесь весьма проблематично (см. обсуждение вопросов глобализации сходимости ньютоновских методов в [73]). Кроме того, опыт вычислений, в частности, в упомянутых выше работах, свидетельствует о том, что число итераций, на которых используется не ньютоновское направление, обычно оказывается сравнительно небольшим (т.с, алгоритм пс превращается по существу в медленный глобально сходящийся метод).
Опишем теперь базовую гибридную схєліу глобализации и свойства ее сходимости. Данная схема использует тест на линейное убывание для некоторой (вычислимой) функции качества tp : Еп - М+. Возможный выбор глобального алгоритма и р происходит при следующих предположениях: (Ш) tf(x) = 0 тогда и только тогда, когда xGl14- решение МСР. (П2) р монотонно убывает вдоль траекторий глобального алгоритма. (ПЗ) р сверхлинейно убывает вдоль траекторий локального метода вблизи квалифицированных решений, то есть решений, удовлетворяющих условиям теоремы о локальной сходимости (в случае алгоритма 2.1 это теорема 2.1). Фиксируем число q (0,1). На каждой итерации к глобального алгоритма, сначала идентифицируются необходимые множества индексов. Если можно считать, что множества идентифицированы правильно (например, если они не изменились по сравнению с предыдущей итерации), тогда вычисляем пробную точку хк 1 шагом GNM/AS в точке хк. Если я -1-1 корректно определена и то полагаем xfr+1 = xki lt и переходим к следующей итерации. В противном случае вычисляем xft_bl шагом глобального алгоритма, и переходим к следующей итерации. Если тест на линейное убывание (2.13) выполняется только для конечного числа итераций, гибридная схема глобализации ведет себя в точности как глобальный алгоритм, и свойства глобальной сходимости последнего остаются верными. Иначе, принимая во внимание предположение (П2), заключаем, что и, в частности, в соответствии с предположением (П1), каждая предельная точка последовательности {xfc} является решением МСР. Это и означает глобальную сходимость гибридной схемы. Предположим, что квалифицированное решение х МСР является предельной точкой последовательности {%к}- Тогда по предположению (ПЗ), тест па линейное убывание (2.13) выполняется для всех достаточно больших индексов к} и как легко видеть гибридная схема в конечном счете переключается па GNM/AS (с «начальной» точкой, достаточно близкой к х). Следовательно, по теореме 2.1, последовательность {xh} сходится к х сверхлинейно. Для оценки расстояния до решения будем использовать функцию качества Очевидно, безусловными глобальными минимумами этой функции являются решения МСР, в каждом из которых она принимает нулевое значение. Очень важное свойство функции ФРВ определяющее ее чрезвычайную популярность в последнее время, состоит в том, что она непрерывно дифференцируема, причем для ее градиента в любой точке х Є К" справедлива формула /FD(x) = AT FB(x) VA Є ЭФ в(я) (см. (Зі], [53]). Предположения (Ш) и (П2) очевидно выполняются для такого выбора (р. Чтобы гар анти ропать выполнение предположения (П3) нужно предположить выполнение оценки расстояния Напомним, что эта оценка эквивалентна полуустойчивости решения х. При этом предположении для х Є IR71 достаточно близкого к квалифицированному решению Ё, и соответствующей траектории {хк} локального метода, имеем где второе равенство следует из непрерывности и Липшивости FB (см- предложение 1.3) в окрестности ху третье равенство следует из георемы 2.1, а четвертое — из (2.15). Таким образом, предположение (ПЗ) выполнено.
При численных экспериментах, результаты которых представлены и приложении Б, рассматривались два варианта алгоритма. Для выбора между этими вариантами используется переменная "Alg". Alg = 1 означает, что возможность переключения на шаг GNM/AS заблокирована, и поэтому алгоритм работает как обычный полугладкий метод Ньютона (SNM/FB) с одномерным поиском для функции Фрп [25], который известен как достаточно эффективный и надежный, и легко реализуемый алгоритм. Alg = 2 соответствует возможности использования GNM/AS. Заметим, однако, что переключение на метод активного множества запрещено на первой итерации, а также в случае, когда идентифицированные множества индексов отличается от множеств индексов, определенных на предыдущей итерации. Это сделано для того, чтобы предотвратить слишком раннее переключение на GNM/AS, когда множества еще не установились, что может являться признаком возможной неправильной идентификации.
