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

Российский Университет дружбы народов

На правах рукописи

Дарьина Анна Николаевна

НЬЮТОНОВСКИЕ МЕТОДЫ РЕШЕНИЯ СМЕШАННЫХ КОМПЛЕМЕНТАРНЫХ ЗАДАЧ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2005 г.

Работа выполнена на кафедре дифференциальных уравнений и функционального анализа факультета физико-математических и естественных наук Российского университета дружбы народов

Научный руководитель - доктор физико-математических наук Измаилов Алексей Феридович

Официальные оппоненты — доктор физико-математических наук, профессор Васильев Федор Павлович, доктор физико-математических наук, профессор Жадан Виталий Григорьевич

Ведущая организация — Московский физико-технический институт (государственный университет)

Защита состоится " "схг^^^е^ 2005 года в 11 часов на заседании диссертационного совета Д 501 001 44 в Московском государственном университете им М В Ломоносова по адресу 119992, Москва, ГСП-2, Ленинские горы, МГУ, 2-й учебный корпус, факучьтет ВМиК, аудитория 685

С диссертацией можно ознакомиться в библиотеке факультета ВМиК Московского государственного университета им М В Ломоносова по адресу 119992, Москва, ГСП-2, Ленинские горы, МГУ, 2-й учебный корпус

Автореферат разослан марта 2005 г

Ученый секретарь диссертационного совета профессор Н

Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В работе рассматривается новая постановка задачи, лишь недавно получившая распространение в оптимизационной литературе, а именно, смешанная комплементарная задача (Mixed Complementarity Problem, MCP) В этом формате могут быть записаны многие известные задачи возникающие в оптимизации, вариационном анализе, исследовании операций, финансовых и инженерных приложениях, включая системы нелинейных уравнений, обычные комплементарные задачи (Nonlinear Complementarity Problem, NCP), системы Каруша-Куна-Таккера (ККТ)

Различным методам решения гладких систем уравнений посвящены монографии [4,2], причем особое внимание там уделено ньютоновским и квазиньютоновским методам Роль ньютоновских методов в современном численном нелинейном анализе и оптимизации трудно переоценить Согласно теореме Денниса-Морэ, в соответствующих предположениях ньютоновский характер итерационного процесса является не только достаточным, но и необходимым для высокой скорости его сходимости Именно поэтому наиболее эффективные и практически востребованные алгоритмы для различных классов нелинейных задач имеют в своей основе соответствующим образом понимаемую и адаптированную ньютоновскую итерацию

В начале 90-х гг большое внимание уделялось сведению NCP к гладким задачам оптимизации с последующим применением к последним традиционных численных методов оптимизации 11, 16, 26] В последнее время все более популярным становится другой подход, основанный на переформулировках NCP в виде негладких систем нелинейных уравнений, которые можно решать с помощью специальных негладких (так называемых полугладких) модификаций метода Ньютона и его практических версий (см [25, 27, 11, 20, 23}) Упомянем также методы проксимальной точки [33] и методы внутренней точки [32] Однако эти подходы обычно связаны с предположением монотонности, которое нигде в данной работе не накладывается

Аналогичные методы применяются и для решения систем ККТ методы (Sequential Quadratic Programming , SQP) [3, 5j, методы, связанные с переформулировкой в виде систем негладких уравнений [3, 28]

Известные методы решения МСР основаны на тех же идеях, что и обсуждавшиеся выше методы решения NCP и систем ККТ Для МСР известны полугладкие методы Ньютона [6, 15, 24], метод Джозефи-Ньютона [22, 7], который с одной стороны, представляет из себя результат распространения идеи метода Ньютона на вариационные неравенства, а с другой стороны, в случае оптимизационных систем ККТ сводится к SQP

Для получения практических версий рассматриваемых алгоритмов чрезвычайно важным является вопрос о глобализации сходимости рассматриваемых локальных методов В [21, 8] сходимость полугладкого метода Ньютона для NCP глобализуется с помощью выбора параметра длины шага посредством соответствующих процедур одномерного поиска Для МСР аналогичный подход развивается в [15, 9, 24]

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

Основные результаты работы.

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

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

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

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

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

Научная новизна работы. Смешанные комплементарные задачи — новая постановка, лишь недавно получившая распространение в оптимизационной литературе В работе получены новые теоретические результаты для задач этого класса, а также разработаны новые высокоэффективные численные методы их решения

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

Методы исследования. Методы алгебры и анализа, в том числе негладкого, а также современные средства численного анализа и оптимизации

Апробация работы. Результаты работы были представлены в виде докладов на семинаре кафедры Исследования операций факультета ВМиК МГУ им М В Ломоносова (рук А Ф Измаилов, Д В Денисов), на семинаре отдела методов нелинейного анализа ВЦ РАН (рук Е А Гребеников), а также на следующих конференциях

1) международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2003», Москва, МГУ, апрель 2003 г,

2) научная конференция «Тихоновские чтения», Москва, МГУ, октябрь 2003 г,

3) международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2004», Москва, МГУ, апрель 2004 г,

4) ХЬ всероссийская конференция по проблемам математики, информатики, физики и химии, Москва, РУДН, апрель 2004 г;

5) 4-я московская международная конференция по исследованию операций (0ЯМ2004), Москва, ВЦ РАН, сентябрь 2004 г

Публикации. По теме диссертации опубликовано 9 работ

Структура и объем диссертации. Диссертация состоит из введения, трех глав, двух приложений, заключения и библиографии Общий объем диссертации 115 страниц Библиография включает 79 наименований

Краткое содержание работы. Во введении раскрываются цели работы, ее актуальность, а также кратко описаны основные результаты, полученные в диссертации

В первой главе диссертации вводится постановка МСР как вариационного неравенства на параллелепипеде. Задача заключается в следующем.

где F Rn -> R" — заданное отображение, [(, u]cR"- параллелепипед, i = (1г, , in), и=(щ,и2, А € RU {-оо}, и, € RU {+оо} и Д < u„ г = 1,2, ,п

Эквивалентная формулировка MCP

0, если х, = = 0, если х, 6 (4,и,), г = 1,2, ,п (2) < 0, если х, = и„

В постановке (2), в отличие от (1), присутствует конечное число соотношений, и в этом смысле она может быть удобнее

В разд 1 2 приведены примеры задач, укладывающихся в формат MCP Многие задачи, связанные с отысканием разного рода равновесий, могут быть записаны в этом формате (см [17, 14, 13)) Например, необходимое условие первого порядка оптимальности для задач минимизации с гладкой целевой функцией на параллелепипеде имеет вид MCP

Если (г = —сю, и, = +оо, г = 1,2, , п, то MCP есть система уравнений

F(x) = О

При I, - 0, и, = +оо г = 1,2, , п, MCP превращается в NCP

х 2 0, F(x) > 0, {х, F(x)) = О (3)

Системы ККТ обладают сильной спецификой по сравнению с общими MCP, так как имеют явную прямо-двойственную структуру Система ККТ имеет вид

g(z)~(G'(z))Tß = О,

/О 0, (?(*)> О, (ß,G(z))=0

относительно (г, //) € Rp х Rm, где д Мр -> Rp и G Rp -> Mm — заданные гладкие отображения

Если для некоторой функции / Rp —» R выполнено

<?(*) = /'(*), z 6 Rp,

то при выполнении определенных условий регулярности ограничений система ККТ дает необходимые условия первого порядка локальной оптимальности в задаче оптимизации

/(г)-»mm, z € D = {z eW \ G(z) 2 0}

Систему ККТ можно записать в виде MCP Для этого следует положить п = р + т,

F(x) = (s(2) ~^z))Tß) ■ * = (*, м) € R" х Rm>

¿, = -oo, г = 1,2, ,p, А = 0, г = р + 1,р + 2, и, = +оо, г = 1,2, ,п

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

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

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

По аналогии с задачами условной оптимизации, будем называть индексы г € Л активными, индексы г 6 А+ строго активными, индексы г € А0 вырожденными, индексы t & N неактивными

Так называемое условие строгой дополнительности имеет вид Aq — 0 Всовременной оптимизационной литературе условие строгой дополнительности принято считать слишком обременительным Нигде в диссертации строгая дополнительность не предполагается Расстояние до решения должно оцениваться через ту или иную вычислимую невязку MCP Такие невязки вводятся с помощью (смешанных) функций дополнительности, те таких функций ф R X R —» R, для которых множество решений уравнения ф(а Ь) = О совпадает со множеством решений системы

и кроме того выполняются импликации

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

1) функция естественной невязки (Natural Residual)

теряет гладкость при a = b,

2) функция Фишера-Бурмейстера

обладает большей гладкостью, но все же теряет ее при а = 0 и b=0,

3) всюду гладкая функция дополнительности

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

Ф(г) = О,

где отображение Ф К" —> К" задается формулой

Ф,(х) =

ОД,

—ф(и, - 1„-Д(х)), Ф(х, ~ -ф{и, -Х„ -

если г € //, если г б и, если г € /„, ■Рг(х))), если г € /г„,

(4)

а множества индексов определяются следующим образом

I/ = {г = 1, ,п| -оо = 4и, = +оо},

/, = {г=1, ,п | -оо < = +оо},

/„ = {» = 1, ,п | -оо = ¿„ и, < +оо},

1ы = {* = 1, ,га | —оо < („и, < +оо}

Соответствующие выбору ф = фцд, ф — Фрв, Ф = Фв варианты отображения Ф обозначаются через Фм, Фрв и Фв. соответственно Подчеркнем, что отображения Фдгя и Фрв, вообще говоря, негладкие, каким бы гладким ни было .Р

Систему ФгВ(х) = 0 можно решать так называемым полугладким методом Ньютона, итерация которого имеет вид для к = 0,1,

хк+1 = хк - А^*РВ(хк),

где Л^ — элемент В-дифференциала [30, 3] отображения Фрв Условие локальной сверхлинейной сходимости этого метода — ВD-регулярность Ф^в в решении (т е невырожденность элементов В-дифференциала) Целью данной работы является получение методов со сверхлинейной сходимостью в более слабых предположениях

При нарушении в точке X условия строгой дополнительности матрица Ф'з(5) неизбежно вырождена, поэтому получение оценки расстояния до решения при ссылкой на стандартные результаты гладкого нелинейного анализа невозможно Это обстоятельство является основной причиной, по которой до последнего времени предпочтение отдавалось главным образом негладким функциям дополнительности Однако, особенность в точке имеет вполне определенную структуру, которая может быть эффективно использована в рамках теории 2-регулярности отображений с липшицевыми производными, развитой в [18, 19]

Разд 13 2 посвящен вычислению производных по направлению отображений Ф = Ф/уя, Ф = Фрв, первой производной отображения Ф = Ф5 и производной по направлению отображения

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

где — заданный параметр, а — отображение, заданное в (4)

Для ф = Фдгд и Ф = Фрв такая оценка при и = 1 равносильна Я0 ствующего отображения в решении х, которое состоит в том, что

свойству соответ-

{|бЕ"|Ф'(х,е) = 0} = {0}

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

где Р — ортогональный проектор на (ип Ф'^))"1"

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

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

Пусть задана V-идентифицирующая функция р, те непрерывная в нуле справа функция такая, что Для произвольного положим

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

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

Если идентифицировать множества А+, Ащ, Лои ЭД и Ии то используя явные выражения Хаы — £л0„ = Ид0„, можно получить полный список известных в результате идентификации уравнений относительно которые заведомо удовлетворяются в

Чтобы упростить обозначения, предположим, что компоненты х € Е" перенумерованы так, что X = (ж/(+, иЛГ^ЖЛоииМ.) Тогда система (5) дает

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

а С(ха+) — |А+| X |Л|-матрица, гладко зависящая отхл+.

Условие слабой регулярности решения, состоящее в том, что

является необходимым условием невырожденности при любом выборе

Метод Гаусса-Ньютона для переопределенной системы (6) можно интерпретировать как усеченный метод Ньютона для системы (7) при соответствующем выборе С() При этом условие слабой регулярности является и достаточным для невырожденности Фд(5д+) Соответственно, локальная сверхлинейная сходимость обосновывается при выполнении условия 2-регулярности в искомом решении (что обосновывает правильную идентификацию индексов) и слабой регулярности этого решения Комбинация этих условий для общих МСР слабее До-свойства Ф^я/Ф^в в решении (а для систем ККТ равносильна ему)

Можно выбирать С() и другими способами Например, можно взять С(') ^ С, где С € — фиксированная матрица Слабая регулярность гарантирует невырожден-

ность Ф'с(5,1+) для почти любой С, и в этом смысле С можно выбирать произвольным (например, случайным) образом Это находит отражение в теореме о локальной сверхлинейной сходимости, которая модифицируется соответствующим образом Существует ряд причин, по которым не стоит ограничиваться каким-либо детерминированным правилом выбора С{) Во-первых, можно предложить множество разумных детерминированных правил такого рода, причем при отсутствии серьезного вычислительного опыта весьма трудно утверждать, что какое-то из них предпочтительнее других Во-вторых, реализация детерминированных правил может быть связана с дополнительными вычислительными затратами. В-третьих, возможность выбора постоянной матрицы С общего положения имеет принципиальное идеологическое значение Кроме того, на практике можно выбирать С не совсем произвольно, а в более специальных классах матриц, например, пытаясь использовать на итерациях разреженную структуру задачи, либо сохранить прямо-двойственную структуру ее переменных (в случае систем ККТ) Кроме того, представляется, что такой подход дает более гибкие возможности для построения квазиньютоновских методов

В разд 2 2 рассматриваются вопросы глобализации сходимости локального алгоритма с сохранением сверхлинейной скорости локальной сходимости, т е. совмещение последнего с некоторой глобальной схемой, которая обеспечивала бы попадание траектории метода в достаточно малую окрестность решения с автоматическим переключением на быстрый локальный алгоритм Здесь для этой цели предлагается использовать гибридную схему, которая уже неоднократно применялась в контексте МСР и МСР (см [15, 9, 24]) Идея

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

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

Опишем теперь базовую гибридную схему глобализации и свойства ее сходимости Данная схема использует тест на линейное убывание для некоторой (вычислимой) функции качества <р Еп —» К+ Возможный выбор глобального алгоритма и ф происходит при следующих предположениях

(П1) >р(х) — 0 тогда и только тогда, когда X € К" — решение МСР,

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

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

Фиксируем число д € (0,1) На каждой итерации к глобального алгоритма, сначала идентифицируются необходимые множества индексов Если можно считать, что множества идентифицированы правильно (например, если они не изменились по сравнению с предыдущей итерации), тогда вычисляем пробную точку х^"1"1 шагом ОММ/Ав в точке корректно определена и

то полагаем хк+1 = хк+1, и переходим к следующей итерации В противном случае вычисляем шагом глобального алгоритма, и переходим к следующей итерации

Если тест на линейное убывание (8) выполняется только для конечного числа итераций, гибридная схема глобализации ведет себя в точности как глобальный алгоритм и свойства глобальной сходимости последнего остаются верными Иначе, принимая во внимание предположение (П2), заключаем, что

и, в частности, в соответствии с предположением (Ш), каждая предельная точка последовательности {я*} является решением МСР Это и означает глобальную сходимость гибридной схемы

Предположим, что квалифицированное решение X МСР является предельной точкой последовательности {я*} Тогда по предположению (ПЗ), тест на линейное убывание (8)

выполняется для всех достаточно больших индексов к, и как легко видеть гибридная схема в конечном счете переключается на ОММ/Ав (с «начальной» точкой, достаточно близкой к х) Следовательно, последовательность {я*} сходится каверхлинейно

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

Очевидно, безусловными глобальными минимумами этой функции являются решения МСР, в каждом из которых она принимает нулевое значение Очень важное свойство функции фрв, определяющее ее чрезвычайную популярность в последнее время, состоит в том, что она непрерывно дифференцируема, причем для ее градиента в любой точке х € К" справедлива формула <р'рв(х) = АтЧрВ(х) УА € дУРВ(х) (см [15], [24])

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

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

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

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

где С1 и С2 произвольные невырожденные рхри |/+| X |/+¡-матрицы соответственно Метод SQP можно распространить на формат МСР, таким методом является метод Джозефи-Ньютона Как известно, локальная сверхлинейная сходимость метода 8С>Р для систем ККТ доказывается при выполнении Яо-свойства Флгд/Фрв в решении [7] Локальная сверхлинейная сходимость предложенные в диссертации методов доказывается при аналогичных условиях Однако, метод SQP состоит в последовательном решении задачи квадратичного программирования, непосредственно аппроксимирующей исходную задачу, в то время как итерация предложенных в диссертации локальных методов состоит в решении одной системы линейных уравнений, что дешевле

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

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

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

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

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант № 04-01-00341).

Литература

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

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

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

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

5 Bertsekas D P Nonlinear Programming Belmont, MA Athena Scientific, 1995

6 Billups S С Algonthmb for complementarity problems and generalized equations PhD thesis, University of Wisconsin, Madison August 1995

7 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

8 De Luca T, Facchmei F, Kanzow С A semismooth equation approach to the solution of nonlinear complementarity problem // Math Program 1996 V 75 P 407-439

9 De Luca T, Facchmei F, Kanzow С A theoretical and numerical comparison of some bemismooth algorithms for complementarity problems // Computational Optimization and Applications 2000 V 16 P 173-205

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

11 Facchmei F, Soares J A new merit function for nonlinear complementarity problems and a related algorithm // SIAM J on Optim 1997 V 7 P 225-247

12 Facchтei F, Fischer A , Kanzow С On the accurate identification of active constraints // SIAM J on Optim 1999 V 9 P 14-32

13 Facchmei F, Pang J -S Finite-dimensional variational inequalities and complementarity problems N Y Springer, 2003

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

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

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

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

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

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

20 Izmailov A F, Solodov M V Superlmearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems // SI AM J on Optim 2002 V 13 N 2 P 386-405

21 Izmailov A F, Solodov M V Superlmearly convergent algorithms for solving smgular equations and smooth reformulations of complementarity problems // SIAM J on Optim 2002 V 13 N 2 P 386-405

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

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

24 Kanzou, С Stncly feasible equation-based methods for mixed complementarity problems // Numer Math 2001 V 89 P 135-160

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

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

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

28 Qi L , Jiang H Scmismooth 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

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

30 Robinson S M Local structure of feasible sets m nonlinear programming part III stabibty and sensitivity // Math Program Study 1987 V 30 P 45-66

31 Solodov M V, Svaiter B F k truly globally convergent Newton-type method for the monotone nonlinear complementarity problem // SIAM J on Optim 2000 V 10 P 605-625

32 Wnght S J An lnfeasible-mtenor-pomt algorithm for linear complementarity problems // Math Program 1994 V 67 P 29-51

33 Yamashita N, Fukushima M The proximal point algorithm with genuine buperlmear convergence for the monotone complementarity problem // SIAM J on Optim 2001 V 11 P 364-379

Публикации по теме диссертации

1 Даръина А Н Смешанные комплементарные задачи регулярность, оценки расстояния до решения и ньютоновские методы // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2003" Секция "Вычислительная математика и кибернетика" М , Издательский отдел факультета ВМиК МГУ, 2003, С 5

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

3 Даръина А Н Об идентификации активных индексов в смешанных комплементарных задачах // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-20041 Секция "Вычислительная математика и кибернетика" М , Издательский отдел факультета ВМиК МГУ 2004, С 7

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

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

6 Даръина А Н, Измаилов А Ф , Солодов М В A class of active-set Newton methods for mixed complementarity problems // Труды 4-ой Московской международной конференции по исследованию операций (0RM2004), Москва, МАКС Пресс, 2004, С 58-63

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

8 Daryina А N, Izmailov A F, Solodov M V A Class Of Active-Set Newton Methods for Mixed Complementarity Problems // SIAM J on Optimization 2004 V 15 № 2 P 409-429

9 Daryma A N, Izmailov A F, Solodov M V Numerical results for a globalized active-set Newton method for mixed complementarity problems // IMPA preprint A256/2004

Заказ №834. Объем 1 п.л. Тираж 100 экз. ^ » Отпечатано в ООО «Петроруш»и I

Г. Москва, ул. Палиха-2а, тел. 250-9^-06 I I I

iww.postator.ru

45*),- 406

2 2 М;, / '13'.

Введение

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

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. Теоретические результаты подтверждены численными экспериментами.

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.