Ньютоновские методы решения смешанных комплементарных задач тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Дарьина, Анна Николаевна

• Дарьина, Анна Николаевна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Дарьина, Анна Николаевна

Введение

Основные обозначения

1 Оценки расстояния до решения и идентификация активных индексов

1.1 Смешанные комплементарные задачи

1.2 Связь с другими задачами.

1.3 Переформулировки МСР в виде систем уравнений.

1.4 Оценки расстояния до решения и условия регулярности . . . ;.

1.5 Идентификация активных индексов.

2 Ньютоновские методы

2.1 Локальные методы активного множества.

2.2 Глобализация сходимости.

2.3 Сравнение с другими методами ньютоновского типа.

3 Системы Каруша-Куна—Таккера

3.1 Постановка задачи.

3.2 Оценки расстояния до решения.

3.3 Идентификация активных индексов и ньютоновские методы.

3.4 Сравнение другими методами.

А Вычислительные эксперименты с идентификацией

Б Вычислительные эксперименты с ньютоновскими методами

Б.1 Локальные численные эксперименты.

Б.2 Численные эксперименты с глобальной схемой

Введение диссертации (часть автореферата) на тему «Ньютоновские методы решения смешанных комплементарных задач»

В работе рассматривается новая постановка задачи, лишь недавно получившая распространение в оптимизационной литературе, а именно, смешанная комплементарная задача (Mixed Complementarity Problem, МСР), которая представляет из себя вариационное неравенство на параллелепипеде. А именно, пусть задан параллелепипед [£,«] С Rn, где £ = (iu 12,., £п), и = («1, tt2> • • •, u„), li е MU{—оо}, щ е RU{+oo}, ti < щ, i = 1,2,., п, и отображение F : En —► К", которое в дальнейшем будет предполагаться достаточно гладким. Требуется

Эквивалентным образом МСР формулируется в виде

0, если xi = £i, = 0, если Xi G (Ci,Ui), (2) 0, если Xi = щ.

Многие задачи, связанные с отысканием разного рода равновесий, могут быть записаны в формате МСР (см. [40, 32, 29]). Кроме того, этот формат объединяет в себе целый ряд важнейших постановок, возникающих в теории оптимизации, вариационном исчислении и других областях математики. Перечислим некоторые из таких постановок.

1. Система нелинейных уравнений где F :Шп —у Rn — заданное отображение.

2. Комплементарная задача (Nonlinear Complementarity Problem, NCP), состоящая в отыскании элемента i6ln такого, что найти х Е [£, и] такой, что (F(x), % — х) ^ 0 Vx € [t, и].

1)

F{x) = 0,

3) х ^ 0, F(x) ^ 0, {х, F(x)) = 0,

4) где F : Rn Rn — заданное отображение.

3. Система Каруша-Куна-Таккера (ККТ) g(x) - (G'(x))Tfi = 0, (5) ц^О, G{z)> О, </i,G(z)>= О, относительно (х, ц) е Rp х Rm, где 5 : Ер -> Rp и G : Rp Rm - заданные отображения. Переменную хбЕр принято называть прямой, a /i G Rm — двойственной.

Если для некоторой функции / : Rp —> R выполнено g(z) = f(z), 2£Г, то при выполнении определенных условий регулярности ограничений система ККТ дает необходимые условия первого порядка локальной оптимальности в задаче оптимизации f(z) —> min, 2 6 D = {z e Rp | 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, 68, 47, 28].

Оценкам расстояния до решения для задач обсуждаемых классов посвящены статьи [44, 58, 64, 47].

Известные методы решения МСР основаны на тех же идеях, что и обсуждавшиеся выше методы решения NCP и систем ККТ. Для МСР известны полугладкие методы Ньютона [14, 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]). Например, необходимое условие первого порядка оптимальности для задач минимизации с гладкой целевой функцией на параллелепипеде имеет вид МСР.

Если £i = —оо, щ = +оо, г = 1,2,, тг, то МСР есть система уравнений (3).

При li = 0, щ — +00, г = 1,2,., п, МСР превращается в NCP (4).

Систему ККТ (5) можно записать в виде МСР. Для этого следует положить п = р + т,

F(x) = , x=(z,ti)eWx Rm,

U — —oo, i = 1,2,. ,p, £i = 0, i — p + l,p + 2,., n, щ = +oo, i = 1,2,.,n.

Методы, о которых пойдет речь в гл. 2, относятся к классу методов активного множества. Для реализации таких методов нужно классифицировать индексы в искомом решении, используя информацию, доступную в точке, близкой к решению. Для последнего предлагаются процедуры идентификации, которые основываются на вычислимых оценках расстояния до решения.

Пусть х — решение МСР. Каждую координату г — 1,2, .,п можно отнести к одному и только одному из следующих пяти множеств индексов:

Ne = Ne(x) = {г | Xi = 4 Ъ{х) > 0}, Аое = Аы(х) = {»| = ВД = 0}, Nu = Nu(x) = {г | xi = щ, Fi(x) < 0}, Aqu = AQvl(x) = {г | щ = щ, Г{(х) = 0}, А+ = А+(х) = {г | Xi е щ), Fi(x) = 0}.

Удобно будет также ввести следующие множества индексов:

N = N(x) = NeUNu = {i\ Fi(x) ф 0}, Aq = Л0(х) = Aqi U AQu = {г | Fi(x) = 0, x, = ti или Uj}, A = A(x) = A0 U A+ = {i | Fi(x) = 0}.

По аналогии с задачами условной оптимизации, будем называть индексы г Е А активными, индексы i Е А+ строго активными, индексы i Е Aq вырожденными, индексы i Е N неактивными.

Так называемое условие строгой дополнительности имеет вид А0 — 0. В современной оптимизационной литературе условие строгой дополнительности принято считать слишком обременительным. Нигде в диссертации строгая дополнительность не предполагается.

Расстояние до решения должно оцениваться через ту или иную вычислимую невязку МСР. Такие невязки вводятся с помощью (смешанных) функций дополнительности, т.е. таких функций ф : R х R —М, для которых множество решений уравнения ф(а, Ь) = 0 совпадает со множеством решений системы

О 0, Ъ^О, аЬ = 0 и кроме того выполняются импликации а > 0, b < 0 Ф(а,Ь) < 0, а > 0, Ъ > 0 ф(а,Ь) > 0.

Можно предложить множество функций дополнительности, однако наиболее часто используются следующие три:

1) функция естественной невязки (Natural Residual) b) = min {a, b} теряет гладкость при а = Ь;

2) функция Фшмера-Бурмейстера b) = а + b — Va? + b2 обладает большей гладкостью, но все же теряет ее при а = 0 и Ъ = 0;

3) всюду гладкая функция дополнительности: ф3(а, Ь) = 2аЪ - (min {0, а + Ь})2.

Теперь можно записать МСР в виде системы нелинейных уравнений. Если ф — смешанная функция дополнительности, то множество решений МСР совпадает со множеством решений уравнения

Ф(ж) = 0, где отображение Ф : Rn —» Rn задается формулой

Fi(x), если i € If, ф(х1 - £и Fi(x)), если i e h,

-ф{щ - -Fi(x)), если i € Iu, ^ ' ip{xi - £u -ф(щ - xi} -Fi(x))), если i € Ieu, а множества индексов определяются следующим образом:

I/ = {г = 1,. | —оо = £i,щ = +оо}, h = {i = 1,.,п | -оо < £{,щ — +oo}, /u = {г = 1,. | —оо = £{,щ < +oo}, hu = {г = 1, • • •, n | -oo < £i} щ < +oo}.

Соответствующие выбору ф = фмя, ф = V'FBi Ф = Фб варианты отображения Ф обозначаются через Ф;уя> Фfb и соответственно. Подчеркнем, что отображения Ф^д и Фрв, вообще говоря, негладкие, каким бы гладким ни было F.

Систему Ф^д(ж) = 0 можно решать так называемым полугладким методом Ньютона, итерация которого имеет вид: для к = 0,1,. xfc+1 = х* где Л к — элемент Б-дифференциала [72, 11] отображения Ф рв- Условие локальной сверхлинейной сходимости этого метода — BD-регулярность Ф^в в решении (т.е. невырожденность элементов Б-дифференциала). Целью данной работы является получение методов со сверхлинейной сходимостью в более слабых предположениях.

При нарушении в точке х условия строгой дополнительности матрица Ф^я) неизбежно вырождена, поэтому получение оценки расстояния до решения при Ф = Ф5 ссылкой на стандартные результаты гладкого нелинейного анализа невозможно. Это обстоятельство является основной причиной, по которой до последнего времени предпочтение отдавалось главным образом негладким функциям дополнительности. Однако, особенность Фs в точке х имеет вполне определенную структуру, которая может быть эффективно использована в рамках теории 2-регулярности отображений с лип-шицевыми производными, развитой в [44, 45].

Разд. 1.3.2 посвящен вычислению производных по направлению отображений Ф = Фnr, Ф = ФFB, первой производной отображения Ф = Ф5 и производной по направлению отображения Ф'5.

В разд. 1.4 изучаются оценки расстояния до решения вида

-*||=О(||Ф(а0Г), где v — заданный параметр, а Ф — отображение, заданное в (6).

Для Ф = ФтуяиФ = Ф FB такая оценка при u = 1 равносильна R0-cbo йству соответствующего отображения в решении х, которое состоит в том, что tt€Rn|®'(i;O = 0} = {0}.

Использование Ф = Ф5 позволяет получить такую оценку при v = 1/2 при более слабом предположении 2-регулярности этого отображения, которое заключается в том, что

Т = Т(х) = {£ е кегФ'(х) | (Ф')'(®;0С € ипФ'(ж)} = U € кегФ'(х) | Рт'(х-,Ж = 0} = {0}, где Р — ортогональный проектор на (тФ'^))1.

Далее приводятся другие условия регулярности, часто используемые в контексте МСР: условия 5£)-регулярности, регулярности максимального В-дифференциала и условие сильной регулярности (по Робинсону) [71]. Изучена связь этих условий с вышеперечисленными .

В разд. 1.5 предложен один из возможных способов идентификации введенных выше множеств индексов, основанный на идее из [27].

Пусть задана ^-идентифицирующая функция р, т.е. непрерывная в нуле справа функция такая, что р(0) = 0 и p(t)/tv —> +00 при t —> 0+. Для произвольного положим

А{х) = {г = 1, ., п | p(№)ll)},

N(x) = {!,., п}\А(х), Nt{x) = {ie N(x) I Xi-Ci^Ui- Xi}, Nu(x) = N(x) \ Ne(x), Ло(аг) = {г € A(x) | тт{|а* - , |u; - яг<|} ^ р(||Ф(х)||)}, Л+(ж) = А(®)\Ло(х), Лое(х) = {г e Ло(аг) | яг,- - ^ мг - жг-}, Л0и(а;) = \ Аы{х).

Наличие оценки расстояния до решения гарантирует правильную идентификацию вблизи этого решения. Соответственно, при использовании в процедуре идентификации Ф = Ф^д или Ф = ФFB нужно предполагать их Яо-свойство в решении, а при использовании Ф = Ф5 — более слабое свойство 2-регулярности этого отображения в решении.

Глава 2 посвящена ньютоновским методам решения смешанных комплементарных задач. В разд. 2.1 предложен алгоритм, обладающий локальной сходимостью со сверхлинейной скоростью. Обсуждаются условия, которые требуются для обоснования нужных свойств алгоритма и связь этих условий с условиями регулярности, рассмотренными в гл. 1. В разд. 2.2 рассматриваются вопросы глобализации сходимости локального алгоритма, т.е. возможность его совмещения с глобально сходящимися схемами без потери сверхлинейной скорости сходимости локального алгоритма. В разд. 2.3 проводится сравнение локального алгоритма с известными ньютоновскими методами для МСР и обсуждаются условия сходимости рассматриваемых методов.

Если идентифицировать множества А+, Аое, Aqu, А^ и Nu то используя явные выражения XAot = hot, xa0u = «д0и, можно получить полный список известных в результате идентификации уравнений относительно iGR", которые заведомо удовлетворяются в точке х: fa(x) = 0, xaoeun( = £aoeune, xaouunu — ua0uunu- (7)

Чтобы упростить обозначения, предположим, что компоненты гбМ" перенумерованы так, что х = (хА+, xAoe[jNt, xAouUNu). Тогда система (7) дает

FA , ^AotuNi, UA0uUNu ) = 0. (8)

При отсутствии строгой дополнительности (когда Aq Ф 0, т.е., |Л| > |А+|), система (8) будет переопределенной (число уравнений больше числа неизвестных). Для определения хА методами ньютоновского типа нужно оставить в системе лишь |Л+| уравнений, а это можно сделать многими способами, в том числе допускающими «перемешивание» уравнений. Например, можно рассматривать систему нелинейных уравнений ф с(хА+) = о, (9) где

Фс : К|л+| М|л+|, Фс(хА+) = C(xA+)FA(xA+,eAotUNt,uAouUNu), а С(хА+) — |Л+| х |А|-матрица, гладко зависящая от хА+.

Условие слабой регулярности решения, состоящее в том, что rank-^Цж) = |Л+|. дхА+ является необходимым условием невырожденности Ф'с(хл+) при любом выборе С(-).

Метод Гаусса-Ньютона для переопределенной системы (8) можно интерпретировать как усеченный метод Ньютона для системы (9) при соответствующем выборе С(-). При этом условие слабой регулярности является и достаточным для невырожденности Ф'с(хА+). Соответственно, локальная сверхлинейная сходимость обосновывается при выполнении условия 2-регулярности Фs в искомом решении (что обосновывает правильную идентификацию индексов) и слабой регулярности этого решения. Комбинация этих условий для общих МСР слабее /?о-свойства в решении а для систем ККТ равносильна ему).

Можно выбирать С(-) и другими способами. Например, можно взять С(-) = С, где С € М1А+|Х|Л| — фиксированная матрица. Слабая регулярность гарантирует невырожденность для почти любой С, и в этом смысле С можно выбирать произвольным (например, случайным) образом. Это находит отражение в теореме о локальной сверхлинейной сходимости, которая модифицируется соответствующим образом. Существует ряд причин, по которым не стоит ограничиваться каким-либо детерминированным правилом выбора С(-). Во-первых, можно предложить множество разумных детерминированных правил такого рода, причем при отсутствии серьезного вычислительного опыта весьма трудно утверждать, что какое-то из них предпочтительнее других. Во-вторых, реализация детерминированных правил может быть связана с дополнительными вычислительными затратами. В-третьих, возможность выбора постоянной матрицы С общего положения имеет принципиальное идеологическое значение. Кроме того, на практике можно выбирать С не совсем произвольно, а в более специальных классах матриц, например, пытаясь использовать на итерациях разреженную структуру задачи, либо сохранить прямо-двойственную структуру ее переменных (в случае систем ККТ). Кроме того, представляется, что такой подход дает более гибкие возможности для построения квазиньютоновских методов.

В разд. 2.2 рассматриваются вопросы глобализации сходимости локального алгоритма с сохранением сверхлинейной скорости локальной сходимости, т.е. совмещение последнего с некоторой глобальной схемой, которая обеспечивала бы попадание траектории метода в достаточно малую окрестность решения с автоматическим переключением на быстрый локальный алгоритм. Здесь для этой цели предлагается использовать гибридную схему, которая уже неоднократно применялась в контексте NCP и МСР (см. [31, 25, 53]). Идея состоит в прямой замене ньютоновской итерации итерацией некоторого глобально сходящегося метода в тех случаях, когда первая не обеспечивает достаточного убывания значения оценивающей функции. В противном случае результат ньютоновской итерации принимается. В принципе, эта схема может быть использована для глобализации сходимости любого локально сверхлинейно сходящегося алгоритма, если предполагать выполненной соответствующую оценку расстояния до решения: никакое согласование ньютоновского направления и используемой оценивающей функции не требуется.

Разумеется, такой подход имеет свои недостатки. Основным недостатком является необходимость вычисления на каждой итерации ньютоновского шага с перспективой его последующего отбрасывания (во всяком случае, на начальных итерациях, удаленных от решения). Однако, к сожалению, построение более изощренных схем глобализации сходимости здесь весьма проблематично (см. обсуждение вопросов глобализации сходимости ньютоновских методов в [73]). Кроме того, опыт вычислений, в частности, в упомянутых выше работах, свидетельствует о том, что число итераций, на которых используется не ньютоновское направление, обычно оказывается сравнительно небольшим (т.е. алгоритм не превращается по существу в медленный глобально сходящийся метод).

Опишем теперь базовую гибридную схему глобализации и свойства ее сходимости. Данная схема использует тест на линейное убывание для некоторой (вычислимой) функции качества tp : Rn —> R+. Возможный выбор глобального алгоритма и ip происходит при следующих предположениях:

П1) <р(х) = 0 тогда и только тогда, когда xGRn- решение МСР;

П2) <р монотонно убывает вдоль траекторий глобального алгоритма;

ПЗ) <р сверхлинейно убывает вдоль траекторий локального метода вблизи квалифицированных решений, то есть решений, удовлетворяющих условиям теоремы о локальной сходимости.

Фиксируем число q G (0,1). На каждой итерации к глобального алгоритма, сначала идентифицируются необходимые множества индексов. Если можно считать, что множества идентифицированы правильно (например, если они не изменились по сравнению с предыдущей итерации), тогда вычисляем пробную точку хк+1 шагом GNM/AS в точке хк. Если корректно определена и фк+1) ^ чфк), (Ю) то полагаем xk+l = хк+1, и переходим к следующей итерации. В противном случае вычисляем хк+1 шагом глобального алгоритма, и переходим к следующей итерации.

Если тест на линейное убывание (10) выполняется только для конечного числа итераций, гибридная схема глобализации ведет себя в точности как глобальный алгоритм, и свойства глобальной сходимости последнего остаются верными. Иначе, принимая во внимание предположение (П2), заключаем, что ip(xk+1) —* 0 при к —► оо, и, в частности, в соответствии с предположением (П1), каждая предельная точка последовательности {хк} является решением МСР. Это и означает глобальную сходимость гибридной схемы.

Предположим, что квалифицированное решение х МСР является предельной точкой последовательности Тогда по предположению (ПЗ), тест на линейное убывание (10) выполняется для всех достаточно больших индексов к, и как легко видеть гибридная схема в конечном счете переключается на GNM/AS (с «начальной» точкой, достаточно близкой к ж). Следовательно, последовательность {xfc} сходится к х сверхлинейно.

При реализации глобального алгоритма в качестве <р предлагается использовать функцию

4>fb{x) = ^ II^fbWH2.

Очевидно, безусловными глобальными минимумами этой функции являются решения МСР, в каждом из которых она принимает нулевое значение. Очень важное свойство функции 9?fbi определяющее ее чрезвычайную популярность в последнее время, состоит в том, что она непрерывно дифференцируема, причем для ее градиента в любой точке iGR" справедлива формула <p'FB{x) = ЛТФfb(x) VA € (cm. [31], [53]).

В роли глобальной схемы использовался вышеупомянутый полугладкий метод Ньютона с линейным поиском. Доказана глобальная сходимость и сверхлинейная скорость сходимости при выполнении Д0-свойства отображения Ф^в в решении, являющемся точкой притяжения алгоритма.

В главе 3 рассматриваются системы ККТ. Так как системы ККТ являются частным случаем смешанных комплементарных задач, то все условия регулярности, которые встречаются в контексте МСР, могут быть переписаны и для систем ККТ. Однако в контексте систем ККТ используются специальные понятия такие как условия регулярности ограничений и условия второго порядка оптимальности. В разд. 3.2 изучаются соотношения условий, перечисленных типов.

Итерация метода Гаусса-Ньютона в некотором смысле разрушает прямодвойствен-ную структуру, свойственную системам ККТ. Например, представляется невозможным анализ сверхлинейной сходимости в прямых переменных отдельно от сходимости прямодвойственной пары. Тем не менее это удается сделать в случае выбора постоянной матрицы С определенной структуры.

Предполагая, что активные ограничения упорядочены так, что для первых |/+| активных ограничений соответствующие им множители положительны, положим

Г(С1 0 0\ °-\о с2 оJ> где С\ и С/2 — произвольные невырожденные рхр и |/+| х |/+|-матрицы соответственно.

Метод SQP можно распространить на формат МСР, таким методом является метод Джозефи-Ньютона. Как известно, локальная сверхлинейная сходимость метода SQP для систем ККТ доказывается при выполнении До-свойства Фnr/^fb в решении [16]. Локальная сверхлинейная сходимость предложенные в диссертации методов доказывается при аналогичных условиях. Однако, метод SQP состоит в последовательном решении задачи квадратичного программирования, непосредственно аппроксимирующей исходную задачу, в то время как итерация предложенных в диссертации локальных методов состоит в решении одной системы линейных уравнений, что дешевле.

В приложении А приведены результаты экспериментов с идентификацией: их целью был выбор оптимального способа идентификации. А именно, изучалось влияние на качество идентификации выбора функции дополнительности (т.е. выбора Ф равным ФлгЯ) ФрВ) либо Фs)> а. также выбора идентифицирующей функции.

В приложении Б представлены результаты вычислительных экспериментов с локальным алгоритмом на некоторых примерах, специально разработанных для того, чтобы проиллюстрировать случай нарушения различных стандартных условий регулярности. Именно в этом случае использование предложенного локального алгоритма может быть полезным. И результаты с глобализованным алгоритмом на примерах из коллекции тестовых задач MCPLIB (новая версия [26]). Подчеркнем, что возможность использования шага локального алгоритма, введенного в этой работе, направлена не на улучшение свойств полугладкого метода Ньютона с одномерным поиском в тех случаях, когда последний работает хорошо, а на распространение области эффективного применения алгоритма на случаи, в которых полугладкий метода Ньютона с одномерным поиском работает плохо (случаи отсутствия В-О-регулярности в искомом решении). За это приходится платить удорожанием итерации, и важно, чтобы это удорожание не было критическим. Эксперименты подтверждают, что глобализованный алгоритм удовлетворяет этим требованиям.

В заключении сформулированы основные результаты, полученные в диссертации.

Автор выражает искреннюю благодарность своему научному руководителю Алексею Феридовичу Измайлову за постановку задачи, постоянное внимание к работе, ценные советы и поддержку.

Основные обозначения ътпхп множество вещественных чисел. n-мерное арифметическое пространство. пространство вещественных матриц размера m х п. е1, е2,., еп — векторы стандартного базиса в Rn.

Е — единичная матрица, размерность которой всегда ясна из контекста. х, у) — скалярное произведение векторов х я у. х|| — евклидова норма вектора х, равная (х, х)1^2.

Ат — транспонированная матрица А. мощность конечного множества I. xi — вектор с компонентами Xi, i G I, где x G Rn и I С {1,., n}.

F : Rn —v Rm — отображение, действующее из пространства Rn в пространство матрица частных производных F по переменным х„ i Е I. dF dxi

Ф'(x;d) — производная отображения Ф : направлению d G Rn. дв^(х) — В-дифференциал отображения Ф в точке х € R".

ЗФ(ж) — дифференциал Кларка отображения Ф в точке х. im А — образ линейного оператора А. ker А — ядро линейного оператора А.

X х У — декартово произведение множеств X и У.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Дарьина, Анна Николаевна

Общие выводы состоят в следующем. Возможность переключения на шаг GNM/AS никогда не дает слишком большого проигрыша, хотя приходится дополнительно платить за вычисление этого шага на некоторых итерациях (на тех, на которых множества индексов не изменились), даже если этот шаг в последствие отвергается. Но это согласуется с основной целью предлагаемого подхода. Цель состоит не в улучшении SNM/FB (или какого-либо другого алгоритма) когда он работает эффективно. Цель в том, чтобы не слишком много навредить в таких случаях, и, вместе с тем, распространить алгоритм на нерегулярные случаи, когда SNM/FB работает плохо.

Подчеркнем, что для представленных методов очень важна эффективность процедуры идентификации. В соответствии с результатами численных экспериментов, переключение на шаг GNM/AS обычно происходит сразу после правильной идентификации. Дополнительная настройка процедуры идентификации (т.е. использование масштабирования или других идентифицирующих функций) может значительно изменить ситуацию (см. приложение А). В действительности, может использоваться техника идентификации, отличная от описанной выше. Также заметим, что в описанном алгоритме не используется никаких эвристических приемов для того, чтобы решить, вычислять ли шаг GNM/AS. Разработка подобных приемов также могло бы сэкономить некоторое количество вычислений. Например, даже если множества индексов не изменились с предыдущей итерации, можно не делать шаг метода активного множества, если невязка задачи достаточно велика. Другой важный круг вопросов — это допустимые версии метода, а также различные схемы глобализации, которые бы лучше соответствовали структуре локального метода. Это будет предметом дальнейших исследований.

Заключение

В заключение кратко сформулируем основные результаты работы.

1. Получены оценки расстояния до решения смешанных комплементарных задач в терминах некоторой вычислимой невязки, определяемой с помощью так называемых функций дополнительности. Разработан способ идентификации множеств активных индексов, основанный на оценках расстояния до решения.

2. Изучены соотношения между различными условиями регулярности, возникающими в контексте МСР.

3. Предложен локальный алгоритм ньютоновского типа для решения смешанных комплементарных задач, обладающий сверхлинейной скоростью сходимости в слабых предположениях регулярности. Предложены способы глобализации локального алгоритма.

4. Теоретические результаты подтверждены численными экспериментами.

Список литературы диссертационного исследования кандидат физико-математических наук Дарьина, Анна Николаевна, 2005 год

1. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. М.: Радио • и связь, 1987.

2. Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.

3. Дарьина А. Н. Смешанные комплементарные задачи: регулярность, оценки расстояния до решения и ньютоновские методы // Материалы «Ломоносов-2003». С. 5. ВМиК МГУ, МАК С Пресс, М., 2003.

4. Дарьина А. Н. Об идентификации активных индексов в смешанных комплементарных задачах // Материалы «Ломоносов-2004». С. 7. ВМиК МГУ, МАКС Пресс, М., 2004.

5. Дарьина А. Н. Методы ньютоновского типа для задач математического программирования // Вестник РУДН. Сер. матем. 2004. Т. 11. № 1. С. 39-54.

6. Дарьина А. Н., Измаилов А. Ф. Об идентификации активных индексов в смешанных комплементарных задачах // Вопросы моделирования и анализа в задачах принятия решений. М.: ВЦ РАН, 2004. С. 72-87.

7. Дарьина А. Н., Измаилов А. Ф. Об одном классе методов ньютоновского типа для задач математического программирования // Тезисы докладов XL Всероссийской конференции по проблемам математики, информатики, физики и химии. С. 32-33. Изд-во РУДН, М., 2004.

8. Дарьина А. Н., Измаилов А. Ф., Солодов М. В. Смешанные комплементарные задачи: регулярность, оценки расстояния до решения и ньютоновские методы // ЖВМ и МФ. 2004. Т. 44. № 1. С. 51-69.

9. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.

10. Евтушенко Ю. Г., Пуртов В. А. Достаточные условия для минимума в задачах нелинейного программирования // Доклады АН СССР. 1984. Т. 278. № 1. С. 24-26.

11. И. Измаилов А. Ф., Солодов М. В. Численные методы оптимизации. М.: Физматлит, 2003.

12. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975.

13. Bertsekas D. P. Nonlinear Programming. Belmont, MA: Athena Scientific, 1995.

14. Billups S. C. Algorithms for complementarity problems and generalized equations. PhD thesis, University of Wisconsin, Madison, August 1995.

15. Bonnans J. F. Asymptotic admissibility of the unit stepsize in exact penalty methods // SIAM Journal on Control an Optimization. 1989. V. 27. N. 3. P. 631-641.

16. Bonnans J. F. Local analysis of Newton-type methods for variational inequalities and nonlinear programming // Applied Mathematics and Optimization. 1994. V. 29. P. 161-186.

17. Bonnans J. F., Sulem A. Pseudopower expansion of solutions of generalized equations and constrained optimization problems // Math. Program. 1995. V. 70. P. 123-148.

18. Ciarlet P. G. A comparative study on nonlinear programming codes // 1978.

19. Cottle R. W. Nonlinear programs with positevly bounded Jacobians // Journal of the Society for Industrial and Applied Mathematics. 1966. V. 14. P. 147-158.

20. Dan H., Yamashita N., Fukushima M. A superlinearly convergent algorithm for the monotone nonlinear complementarity problem without uniqueness and nondegeneracy conditions // Mathematics of Operations Research. 2002. V. 27. N. 4. P. 743-753.

21. Daryina A. N., Izmailov A. F., Solodov M. V. Numerical results for a globalized active-set newton method for mixed complementarity problems. IMPA Preprint A282/2004.

22. Daryina A. N., Izmailov A. F., Solodov M. V. A class of active-set Newton methods for mixed complementarity problems // Proc. 4th Moscow International Conference on Operations Research (ORM2004). P. 58-63. MAKS-Press, 2004.

23. Daryina A. N., Izmailov A. F., Solodov M. V. A class of active-set Newton methods for mixed complementarity problems // SI AM Journal on Optimization. 2004. V. 15. N. 2. P. 409-429.

24. De Luca Т., Facchinei F., Kanzow C. A semismooth equation approach to the solution of nonlinear complementarity problem // Math. Program. 1996. V. 75. P. 407-439.

25. De Luca Т., Facchinei F., Kanzow C. A theoretical and numerical comparison of some semismooth algorithms for complementarity problems // Computational Optimization and Applications. 2000. V. 16. P. 173-205.

26. Dirkse S. P., Ferris M. C. MCPLIB: A collection of nonlinear mixed complementarity problems // Optimization methods and software. 1995. V. 5. P. 319-345.

27. Facchinei F., Fischer A., Kanzow C. On the accurate identification of active constraints // SIAM Journal on Optimization. 1999. V. 9. P. 14-32.

28. Facchinei F., Lucidi S. Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems // Journal of Optimization Theory and Applications. 1995. V. 85. P. 265-289.

29. Facchinei F., Pang J.-S. Finite-dimensional variational inequalities and complementarity problems. N.Y.: Springer, 2003.

30. Facchinei F., Soares J. A new merit function for nonlinear complementarity problems and a related algorithm // SIAM Journal on Optimization. 1997. V. 7. P. 225-247.

31. Ferris M. C., Kanzow C., Munson T. S. Feasible descent algorithms for mixed complementarity problems // Math. Program. 1999. V. 86. P. 475-497.

32. Ferris M. S., Pang J.-S. Engineering and economic applications of complementarity problems // SIAM Review. 1997. V. 39. P. 669-713.

33. Fischer A. A special Newton-type optimization method // Optimization. 1992. V. 24. P. 269-284.

34. Fischer A. Modified Wilson's method for nonlinear programs with nonunique multipliers // Mathematics of Operations Research. 1999. V. 24. P. 699-727.

35. Fischer A. Local behaviour of an iterative framework for generalized equations with nonisolated solutions // Math. Program. 2002. V. 94. P. 91-124.

36. Fukushima M. Equivelent differentiable optimization problems and descent methods for asymmetric variational problems // Math. Program. 1992. V. 53. P. 99-110.

37. Guler 0. Existence of interior points and interior paths in nonlinear monotone complementarity problems // Mathematics of Operations Research. 1993. V. 18. P. 128-147.

38. Habetler G. J., Kostreva M. M. On a direct algorithm for nonlinear complementarity problems // SIAM Journal on Control an Optimization. 1978. V. 16. P. 504-511.

39. Harker P. T. Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variation inequalities // Math. Program. 1988. V. 41. P. 29-59.

40. Harker P. Т., Pang J.-S. Finite-dimensional variational inequality problems: A survey of theory, algorithm and applications // Math. Program. 1990. V. 48. P. 161-220.

41. Harker P. Т., Xiao B. Newton's method for the nonlinear complementarity problem: A B-differentiable equation approach // Math. Program. 1990. V. 48. P. 339-358.

42. Hintermiiller M., Ito K., Kunisch K. The primal-dual active set strategy as a semismooth newton method // SIAM Journal on Optimization. 2003. V. 13. N. 3. P. 865-888.

43. Hock W., Schittkowski K. Test Examples for Nonlinear Programming Codes. Ser. Lecture Notes in Economis and Meth. Systems 187. Berlin: Springer, 1981.

44. Izmailov A. F., Solodov M. V. Error bounds for 2-regular mappings with lipschitzian derivatives and their applications // Math. Program. 2001. V. 89. P. 413-435.

45. Izmailov A. F., Solodov M. V. The theory of 2-regularity for mappings with Lipschitzian derivatives and its applications to optimality conditions // Mathematics of Operations Research. 2002. V. 27. P. 614-635.

46. Izmailov A. F., Solodov M. V. Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems // SIAM Journal on Optimization. 2002. V. 13. N. 2. P. 386-405.

47. Izmailov A. F., Solodov M. V. Karush-Kuhn-Tucker systems: regularity conditions, error bounds and a class of Newton-type methods // Math. Program. 2003. V. 95. P. 631-650.

48. Jiang H. Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem // Mathematics of Operations Research. 1999. V. 24. P. 529-543.

49. Jiang H., Qi L. A new nonsmooth equations approach to nonlinear complementarity problems // SIAM Journal on Control an Optimization. 1997. V. 35. P. 178-193.

50. Josephy N. H. Newton's Method for Generalized Equations and the PIES Energy Model. PhD thesis, Department of Industrial Engineering, University of Wisconsin, Madison, 1979.

51. Kanzow C. Some equation-based methods for the nonlinear complementarity problem // Optimization Methods and Software. 1994. V. 3. P. 327-340.

52. Kanzow C. Stricly feasible equation-based methods for mixed complementarity problems // Numer. Math. 2001. V. 89. P. 135-160.

53. Kanzow C., Fukushima M. Solving box constrained variational inequality problems by using the natural residual with D-gap function globalization // Operation Research Letters. 1998. V. 23. P. 45-51.

54. Kojima M. Strongly stable stationary solutions in nonlinear programs // Analysis and Computation of Fixed Points / Ed. Robinson S. M. NY: Academic Press, 1979. P. 93-138.

55. Kummer В. Newton's method for nondifferentiable functions // Advances in Math. Optimizat. V. 45. Berlin: Akad. Verlag, 1988. P. 114-125.

56. Kummer B. Newton's method based on generalized derivatives for nonsmooth functions // Advances in Optimization. Berlin: Springer, 1992. P. 227-244.

57. Luo Z.-Q., Pang J.-S. Error bounds for analytic systems and their applications // Math. Program. 1994. V. 67. P. 1-28.

58. Mangasarian O. L. Equivelence of the complementarity problem to a system of nonlinear equations // SIAM Journal on Applied Mathematics. 1976. V. 31. P. 89-92.

59. Mangasarian O. L., Solodov M. Nonlinear complementarity as unconstrained and constrained minimization // Math. Program. 1993. V. 62. P. 277-298.

60. Murphy F. H., Sherali H. D., Soyster A. L. A mathematical programming approach for determining oligopolistic market equilibrium // Math. Program. 1982. V. 24. P. 92-106.

61. Pang J.-S. Inexact newton methods for the nonlinear complementarity problem // Math. Program. 1986. V. 36. P. 54-71.

62. Pang J.-S. A B-differentiable equation based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems // Math. Program. 1991. V. 51. P. 101-132.

63. Pang J.-S. Error bounds in mathematical programming // Math. Program. 1997. V. 79. P. 299-332.

64. Pang J.-S., Gabriel S. A. NE/SQP: A robust algorithm for the nonlinear complementarity problem // Math. Program. 1993. V. 60. P. 295-338.

65. Pang J.-S., Qi L. Nonsmooth equations: Motivation and algorithms // SIAM Journal on Optimization. 1993. V. 3. P. 443-465.

66. Qi L. Convergence analysis of some algorithms for solving nonsmooth equations // Mathematics of Operations Research. 1993. V. 18. P. 227-244.

67. Qi L., Jiang H. Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations // Mathematics of Operations Research. 1997. V. 22. P. 301-325.

68. Qi L., Sun J. A nonsmooth version of Newton's method // Math. Program. 1993. V. 58. P. 353-367.

69. Ralph D. Global convergence of Newton's method for nonsmooth equations via the path search // Mathematics of Operations Research. 1994. V. 19. P. 352-389.

70. Robinson S. M. Strongly regular generalized equations // Mathematics of Operations Research. 1980. V. 5. P. 43-62.

71. Robinson S. M. Local structure of feasible sets in nonlinear programming, part III: stability and sensitivity // Mathematical Programming Study. 1987. V. 30. P. 45-66.

72. Solodov M. V., Svaiter B. F. A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem // SIAM Journal on Optimization. 2000. V. 10. P. 605-625.

73. Sun D., Womersley R. S., Qi H. A feasible semismooth asymptotically Newton method for mixed complementarity problems // Math. Program. 2002. V. 94. P. 167-187.

74. Tseng P. Growth behavior of a class of merit functions for the nonlinear complementarity problem // Journal of Optimization Theory and Applications. 1996. V. 89. P. 17-37.

75. Tseng P., Yamashita N., Fukushima M. Equivalence of complementarity problems to differentiable minimization: a unified approach // SIAM Journal on Optimization. 1996.V. 6. P. 446-460.

76. Ulbrich M. Nonmonotone trust-region methods for bound-constrained semismooth equations with applications to nonlinear mixed complementarity problems // SIAM Journal on Optimization. 2001. V. 11. N. 4. P. 889-917.

77. Wright S. J. An infeasible-interior-point algorithm for linear complementarity problems // Math. Program. 1994. V. 67. P. 29-51.

78. Wright S. J. Superlinear convergence of a stabilized SQP method to a degenerate solution // Computational Optimization and Applications. 1998. V. 11. P. 253-275.