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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. М.В. ЛОМОНОСОВА

КУРЕННОЙ АЛЕКСЕЙ СВЯТОСЛАВОВИЧ

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЁНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

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

2 7 ПАР 2014

Москва 2014

005546374

005546374

Работа выполнена на кафедре исследования операций факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

доктор физико-математических наук, профессор

Измаилов Алексей Феридович.

доктор физико-математических наук, Жадан Виталий Григорьевич;

кандидат физико-математических наук, Жуковский Сергей Евгеньевич.

Тамбовский государственный университет им. Г. Р. Державина.

Защита диссертации состоится 16 мая 2014 г. в 11 ч. 00 мин. на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495)9393010 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Научной библиотеке МГУ, а также на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Диссертации».

Автореферат разослан 13 марта 2014 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь диссертационного совета к.т.н., с.н.с.

В. А. Костенко

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

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

Актуальность темы. Задачи оптимизации с липшицевыми производными имеют широкий спектр приложений. К ним относятся кусочно-квадратичные задачи, возникающие, например, в машинном обучении, и обобщенные линейно-квадратичные задачи, находящие применение в оптимальном управлении. Помимо этого, задачи оптимизации с липшицевыми производными возникают в методах поиска обобщенного равновесия Нэша. Также к этому классу задач относятся поднятые переформулировки задач оптимизации с комплементарными ограничениями. Несмотря на многочисленные приложения, задачи оптимизации с липшицевыми производными до недавнего времени оставались малоизученными, особенно в плане обоснования соответствующих численных методов оптимизации, в связи с чем тема работы является актуальной.

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

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

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

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

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

Достоверность научных положений обусловлена строгостью математических доказательств и использованием апробированных научных методов.

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

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

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

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

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

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

Соответствие диссертации паспорту научной специальности. В диссертации проведено исследование локальной сходимости ряда методов минимизации функций. Поэтому в ней решена задача, относящаяся к направлению «математическое программирование», которое входит в содержание специальности 01.01.09.

Апробация результатов. Результаты, полученные в диссертации, были представлены на XXI международном симпозиуме по математическому программированию «13МР2012» (Берлин, Германия), на международной конференции по непрерывной оптимизации «1ССОРТ2013» (Лиссабон, Португалия), на X всемирном конгрессе по структурной и междисциплинарной оптимизации «\VCSMO-IO» (Орландо, США, 2013), на ежегодных международных научных конференциях студентов и молодых ученых «Ломоносов-2011», «Ломоносов-2012» (Москва), на ежегодной научной конференции «Тихоновские чтения» (Москва, 2012), на ежегодной

научной конференции «Ломоносовские чтения» (Москва, 2011), а также на VII Московской международной конференции по исследованию операций «011М2013».

Публикации. Полученные в диссертации результаты опубликованы в 12 работах, список которых приведен в конце автореферата. В их число входит 5 статей, опубликованных в журналах из списка ВАК РФ [4, 7, 9, 10, 11].

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы из 91 источника. Общий объем диссертации — 134 страницы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена вспомогательным вопросам вариационного и негладкого анализа.

В разделе 1.1 рассматривается ряд широко используемых концепций регулярности решения смешанной комплементарной задачи (СКЗ)

«€[*,«], (Ф(г),у-г)&0 У У € [£, и],

где Ф: Ш8 — заданное отображение, а \1, и] есть (обобщенный)

параллелепипед,

[£, и] = {г 6 И* 11{ щ ^ и,, г = 1, ..., в},

задаваемый числами 6 111 {—оо} и щ 6 К и {+оо}, ^ < щ, г — 1, ..., е. В число рассматриваемых условий регулярности входят сильная регулярность, полуустойчивость, ВО и СП-регулярности переформулировок СКЗ с использованием функции естественной невязки и функции Фишера-Бурмейстера и др. Особое внимание уделяется частному случаю

СКЗ — системе Каруша-Куна-Таккера (ККТ). Основным результатом раздела является полная картина взаимоотношений между рассматриваемыми условиями регулярности.

В разделе 1.2 исследуются соотношения между рядом обобщенных дифференциальных объектов, в число которых входит частный дифференциал Кларка и проекция полного дифференциала Кларка. Дифференциалом Кларка отображения Ф: П1® н-»- Иг в точке ге®1 называется множество

дФ{г) = сопу{7 е Нгха | 3{гк} С Т>Ф: {**} 2, (Ф'О*)} -> •/},

где через Т>ф обозначено множество точек дифференцируемости отображения Ф. Пусть в = 81 + 2 = (г1, г2) € И®1 х И®2. Частным дифференциалом Кларка отображения Ф по переменной г\ в точке 2 = (¿ь г2) € х И"2 называется множество

Проекцией полного дифференциала Кларка отображения Ф в точке г — (¿1, г2) £ И- х И82 называется множество

ГЦдФС?!, г2) = {^ € ИТ**1 | 3 32 6 Л1РХ": [Л 32] е 8Ф(гг,

Основной результат раздела состоит в том, что если отображение Ф имеет вид

Ф(г1,гя) = Щх1)г2 + Ь(21), (1)

где К : ГОЛ ГО,7"*®3 и Ь: Щ.®1 н»Ег- заданные отображения, то в любой точке г — (¿ь л2) 6 К"1 х ГО.®2 такой, что отображения К и Ъ локально липшицевы в выполнено равенство

дг,Ф(гъ г2) = Пг19Ф(г1, г2).

Рассмотрение отображений вида (1) вызвано тем, что в таком виде представляется градиент функции Лагранжа задачи оптимизации по прямой переменной.

В разделе 1.3 доказывается оценка расстояния до множества решений системы ККТ задачи оптимизации

/(х) min, h{x) = 0, д(х) 0, (2)

с липшицевыми производными. Напомним, что последнее означает, что функция / :Е"^Еи отображения h\ ЯГ П1! и д: IR" И- IRm дифференцируемы, и что их производные являются локально липшицевыми. Отображение Ф: И8 i-> ]Rr называется локально липшицевым в точке z е ]RS, если оно удовлетворяет условию Липшица в некоторой окрестности этой точки, т. е. если существует число I > 0 и окрестность U с IR5 точки z такие, что

иед - фын < Фх - *2ц v*b zi € и.

При этом отображение называется локально липшицевым, если оно локально липшицево в каждой точке своей области определения. Система ККТ задачи (2) имеет вид

h(x) = О, pfaXO, (jt,g{x))= 0,

где L: К" х El' х IR."1 -> 1R — функция Лагранжа задачи (2),

L(x, А, р) = /(х) + (А, h(x)) + (ß, д{х)). Пусть М{х) С И'

X И™ — совокупность множителей Лагранжа, отвечающих точке х € ПГ (т. е. множество пар (А, /¿) G II1 х lRm таких, что тройка (х, А, ß) удовлетворяет системе (3)). Точка х € IR" называется стационарной точкой задачи (2), если М(х) ф 0. Будем обозначать через

А = А(х) = {г = 1, ..., т \ д{{х) = 0}

множество индексов активных ограничений в точке х € IR™. Кроме того, в том случае, если х — стационарная точка задачи (2), для всякого множителя Лагранжа (А, Д) £ М(х) через

Л+ = Л+(х, Д) = {г е Л (г) | щ > 0}, А0 = А0{х, fi) = {ie А(х) | fii = 0}

будут обозначаться множества индексов сильно и слабо активных ограничений соответственно.

В данном раздаче устанавливается эквивалентность следующих трех свойств.

Свойство 1 (верхняя липшицева устойчивость решений системы ККТ при канонических возмущениях). Существует число £> 0 и окрестность Ы точки (х, А, Д) такие, что для любого а -(а, Ь, с) € И" х Ш.' х Ит, достаточно близкого к точке (0, 0, 0), всякое решение (х(<т), А(<т), р(сг)) € Ы возмущенной системы ККТ дЬ,

дх

(г, А, д) = а, Ь{х) = 6, ц ^ 0, д(х) ^ с, (ц, д{х) - с) = 0

удовлетворяет оценке

||*((т) -3[\ + с^((А(а), м(<Т)), М(£)) ^ ¿\\а\\.

Свойство 2 (оценка расстояния для системы ККТ). Существует число £ > 0 и окрестность Ы точки (х, А, Д) такие, что для любого вектора (х, А, ц) £ Ы выполняется неравенство

||х - х\\ + д), М{х)) < I

Цх)

тш{д, -д{х)} )

Свойство 3 (некритичность множителя (А, ц)). Не существует тройки (£, т), () 6 й" х Е1 х Ит с £ ^ 0, удовлетворяющей системе

¿+(Л'(х))Т7?+(^))ТС = О, А'(г)г = 0, .9^(^ = 0,

Сл0 ^ 0, д'Аа(х)£ ^ 0, <■»(<?№), о = 0, г 6 Л0, С{1.....= 0

с некоторым сI € Сх?}~{х, А, Д)(£)> г&е через Сх^(х, А, Д)(£) обозначена контингентная производная отображения А, Д) в точке х по направлению то есть множество

А, Д)(0 = {ш 6 ЕГ

СК+, {«к}-+0+:

Результаты главы 1 опубликованы в статьях [1, 2, 5, 9, И].

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

Ф(и) + М(и) Э О, (4)

где Ф: Ж" К" — однозначное отображение (именуемое базовым или базой), а И: Ш." 2й* — многозначное (иногда называемое полем). Теоремы о сходимости этих итерационных схем являются основным средством анализа численных методов решения задач оптимизации с липшицевыми производными в главе 3.

Итерационные схемы, рассматриваемые в разделе 2.1, предназначены для решения обобщенных уравнений с произвольной непрерывной базой и имеют абстрактный характер. В первых двух пунктах раздела исследуются свойства локальной сходимости схемы, итерация которой состоит в следующем. По текущей точке ик £ К" и текущему значению параметра тг*, принадлежащему множеству П произвольной природы, очередная точка ик+1 генерируется как решение подзадачи

Л(тгк, ик, и) + Ы(и) Э 0, ||и*+1-г1*|К<5, (5)

где для любых я- е П и й € И" точечно-множественное отображение Л(7г, й, ■) из И" в 2®" представляет собой аппроксимацию отображения Ф вблизи й, а 5 > 0 — фиксированное число. Второе условие в формуле (5) называется условием локализации и служит для исключения из рассмотрения тех решений подзадачи, которые далеки от искомого решения обобщенного уравнения.

В пункте 2.1.1 устанавливается локальная сходимость итерационной схемы (5) в предположении о сильной метрической регулярности искомого решения обобщенного уравнения (4). Решение й обобщенного уравнения (4) называется сильно метрически регулярным, если существует константа £ > 0 такая, что для всякого г е И", достаточно близкого к О, возмущенное обобщенное уравнение

Ф(и) + АГ(и) Э г (6)

имеет вблизи точки й единственное решение и(г), причем отображение и(-) является локально липшицевым в точке 0 с константой Î. В соответствующем результате о локальной сходимости предполагается, что отображение Л является однозначным и аппроксимирует отображение Ф в достаточно сильном смысле: разность Ф(-) — Л(п, й, ■) должна быть локально липшицевой в искомом решении с малой константой Липшица равномерно по параметру -к и точкам й S HR", близким к этому решению. В указанных предположениях гарантируется существование числа 5 > О такого, что из любого начального приближения, достаточно близкого к искомому решению обобщенного уравнения (4), итерационная схема (5) генерирует единственную траекторию, которая сходится к этому решению с линейной скоростью. При этом скорость сходимости является сверхлинейной, если точность аппроксимации отображения Ф возрастает с ростом номера итерации (см. теорему 2.1 диссертации).

В пункте 2.1.2 сильная метрическая регулярность заменяется более слабым условием — полуустойчивостью. Решение й обобщенного уравнения (4) называется полуустойчивым, если существует константа I > О такая, что для любого г в IR" всякое решение и(г) возмущенного обобщенного уравнения (6), достаточно близкое к й, удовлетворяет оценке

1Нг)-й||<ф-||.

Требование на качество аппроксимации отображения Ф также ослабляется. В частности, отображение Л может быть многозначным. В отличие от предположений пункта 2.1.1, эти ослабленные предположения не гарантируют разрешимость подзадач итерационной схемы (5) вблизи искомого решения. Выполнение этого свойства приходится требовать явно. Кроме того, доказываемая в пункте 2.1.2 теорема о локальной сходимости итерационной схемы (5) не гарантирует единственность генерируемой ей траектории.

Итерационная схема, рассматриваемая в пункте 2.1.3, предназначена для поиска неизолированных решений обобщенного уравнения (4). Такие решения не могут обладать ни полуустойчивостью, ни, тем более, сильной метрической регулярностью. По текущей точке uk Е И" и текущему

значению параметра пк € П очередная точка ик+1 генерируется в этой схеме как решение подзадачи

А{тг\ ик, и) + N(u) Э 0, j|Mi+1 - ик\\ < cdist(«fe, í7), (7)

где ¿7 — множество решений обобщенного уравнения (4), а с > 0 — фиксированное число. От схемы (5) схема (7) отличается более сильным условием локализации. Для схемы (7) доказывается теорема о локальной сходимости и скорости сходимости. Ее предположения состоят в требовании разрешимости подзадач схемы, определенных условиях на качество аппроксимации отображения Ф, а также в выполнении свойства, которое носит называние верхне-липшицевого поведения решения при канонических возмущениях. Решение й 6 Ü обладает этим свойством, если существует константа i > 0 такая, что для любого г е IR" всякое решение и{г) возмущенного обобщенного уравнения (6), достаточно близкое к и, удовлетворяет оценке

dist(«(r),

Если решение й изолировано, то верхне-липшицево поведение при канонических возмущениях эквивалентно полуустойчивости. Заметим, что траектория, генерируемая схемой (7), сходится не к й, а к некоторому решение и' обобщенного уравнения (4), которое можно сделать сколь угодно близким к б за счет выбора начального приближения.

Метод решения обобщенных уравнений, исследуемый в разделе 2.2, является менее абстрактным по сравнению с итерационными схемами, рассматриваемыми в разделе 2.1. При этом он накладывает на базу обобщенного уравнения более сильные ограничения гладкости: предполагается, что отображение Ф является полугладким в искомом решении и обобщенного уравнения (4). Отображение Ф: IR" и-)- lRr называется полугладким в точке и 6 IR", если оно является локально липшицевым в и, дифференцируемым вига любому направлению и удовлетворяет условию

sup [|Ф(и + v) - Ф(и) - Jv|| — о(||и||).

Jsd Ф(и+и)

Отображение называется полу гладким, если оно полугладко в каждой точке своей области определения. Метод решения обобщенных уравне-

ний, о котором идет речь, называется полугладким методом Джозефи-Ньютона. Его итерация состоит в решении (частично) линеаризованного обобщенного уравнения

Ф(м*) + ^(и — ик) + И(и) Э О,

где ик € И" — текущее приближение к искомому решению уравнения (4), а Зь — произвольная матрица из множества дФ(ик). Основным результатом раздела является теорема о локальной сверхлинейной сходимости этого метода в предположении о С£) -регулярности искомого решения й. Решение ад обобщенного уравнения (4) называется С Б регулярным, если для любой матрицы J 6 дФ(й) и любого г € И1', достаточно близкого О, возмущенное частично линеаризованное уравнение

Ф(й) + Ди - ы) + ]У(«) Э г

имеет вблизи й единственное решение м,/(г), и отображение «,/(■) является локально липшицевым в точке 0.

Результаты главы 2 опубликованы в работах [3, 6, 7, 10].

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

Раздел 3.1 посвящен методу модифицированных функций Лагранжа. В пункте 3.1.1 исследуется этот метод для задачи (2). Модифицированной функцией Лагранжа Ьа: И" х т' х Кт К задачи (2) называется функция

Ьа(х, А, ц) = /(в) + 2а(\\Х + Кх)/а\\\ + || тах{0, ц + д{х)/а}\Ц),

где максимум берется покомпонентно. Параметр сг в определении модифицированной функции Лагранжа называется обратным параметром

штрафа. Итерация метода модифицированных функций Лагранжа для задачи (2) состоит в следующем. По текущему двойственному приближению (А*, цк) еЕ'хГ и текущему значению обратного параметра штрафа егк > 0 очередное прямое приближение хк+1 ищется как стационарная точка задачи

Ьак{х, Хк, цк) шш, х 6 И", (8)

а очередное двойственное приближение (А*+1, цк+1) вычисляется по формулам

А*+1 = Ак + к{хк+х)/ак, /+1=тах{0, цк + д{хк+1)/ок}. (9)

Для данного метода доказываются теоремы о локальной сходимости и скорости сходимости в различных наборах предположений. В первой из этих теорем предполагается, что в искомой стационарной точке х задачи (2) выполнено условие линейной независимости, и что единственный отвечающий этой точке множитель Лагранжа (А, Д) удовлетворяет сильному достаточному условию второго порядка оптимальности. Первое из этих условий по определению означает, что градиенты ограничений-равенств и активных ограничений-неравенств в точке х линейно независимы. Второе условие заключается в том, что

\/Недх^{х, А,Д) {#£, £) > 0 Д)\{0},

где

с+(г, д) = {£ е ПГ I А'(г)€ = о, = о}.

В указанных предположениях найдутся числа о > 0 и 6 > 0 такие, что для любой последовательности {о>} С (0, <т] из любого начального приближения (а:0, А0, ц°), достаточно близкого к тройке (х, А, Д), метод модифицированных функций Лагранжа (8), (9) генерирует единственную траекторию, удовлетворяющую условию

Хк+\ - (хк, Хк, /)|| ^ 6, к = 0, 1, ...,

и эта траектория сходится к (ж, А, Д) с линейной скоростью. При этом скорость сходимости является сверхлинейной, если {ок} —> 0.

Во второй теореме условие линейной независимости ослабляется до строгого условия Мангасаршна Фромовица, которое заключается в единственности множителя (А, Д), отвечающего стационарной точке х задачи (2). От этого множителя требуется, чтобы он был некритическим. Кроме того, предполагается, что для задачи (2) в точке х выполнено условие квадратичного роста: существуют числа 7 > 0 и р > 0 такие, что

fix) > f{x) + i\\x - х\\2 Vx € Шп: \\х - х\\ si р, h(x) = 0, д{х) < 0.

Отметим, что при выполнении строгого условия Мангасариана-Фромови-ца условие квадратичного роста следует из достаточного условия второго порядка оптимальности, состоящего в том, что

VH€dx^(x, А,Д) (Щ,0> 0 VteCix)\{0}, где С(х) — критический конус задачи (2),

С(х) = {?еГ| ft'(s)i = о,<о, (f'(x), 0 < 0} =

= {$ е к* | h'№ = о, й(2)€ = о, э'а^Ш < о}-

Поскольку последнее условие в свою очередь следует из сильного достаточного условия второго порядка оптимальности, предположения второй теоремы пункта 3.1.1 слабее предположений первой теоремы этого пункта. В части утверждений эти теоремы отличаются тем, что вторая не гарантирует единственность траектории метода.

В третьей теореме пункта 3.1.1 устанавливается локальная сходимость метода модифицированных функций Лагранжа без каких-либо предположений о регулярности ограничений в искомой стационарной точке х £ lRn задачи (2). В ней предполагается только то, что множитель Лагранжа (А, Д) 6 М (х), вблизи которого стартует двойственная траектория, удовлетворяет достаточному условию второго порядка оптимальности. Используемое при этом условие локализации является более сильным, чем в первой и второй теоремах данного пункта. Заметим, что двойственная траектория, генерируемая алгоритмом, сходится не к (А, Д), а к множителю (А*, д*) € Л4(х), который можно сделать сколь угодно близким к (ж, А) за счет выбора начального приближения.

В пункте 3.1.2 рассматривается метод модифицированных функций для задачи оптимизации с липпгацевыми производными, в которой отсутствуют ограничения-неравенства

f(x) min, h{x) = 0. (10)

Итерация этого метода состоит в следующем. По текущему двойственному приближению Л* е ГО.' и текущему значению обратного параметра штрафа ак > 0 очередное прямое приближение xk+l е И™ находится как стационарная точка задачи

/(*) + <Afc, h(x)) + ^~\\h(x)\\l -> min, х 6 ET, а очередное двойственное приближение

\k+1 е JR' полагается равным Лk+h(xk+1)/(Tk- Для этого метода доказываются две теоремы о локальной сходимости и скорости сходимости, не требующие регулярности ограничений в искомой стационарной точке х € Ж" задачи (10) и не предполагающие, что отвечающий точке х множитель А, вблизи которого стартует двойственная траектория метода, удовлетворяет достаточному условию второго порядка оптимальности

чнедх^(х, л) (Щ,0> о Vi€kfirh'(aO\{o},

где L: IR" хЕ'нуЕ - функция Лагранжа задачи (10),

L{х, А) = f(x) + (A, h(x)}.

Вместо достаточного условия второго порядка оптимальности на множитель А в этих теоремах накладывается более слабое условие, состоящее в том, что

Vtf € ЗгЦоё, Ä) Щ £ im(/i'Cr))T V^ е ker h'(x) \ {0}.

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

с к =

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

Раздел 3.2 посвящен методу множителей с линеаризованными ограничениями. Этот метод вводится для задачи вида (2), в которой т = п и д(х) = —х, х € В", то есть для задачи с ограничениями-равенствами и условием неотрицательности переменных. Итерация метода множителей с линеаризованными ограничениями состоит в следующем. По текущему приближению (хк, Хк, цк) € Ж" хК'х И™ и значению параметра штрафа в*; > 0 очередное прямое приближение хк+1 € Ж™ вычисляется как стационарная точка задачи оптимизации

/(*) + <А*, М*)> + §11«->тт, Л(хк) + К'{хк){х - хк) = 0, х > О,

а очередная точка (А*+1, Цк+г) € ГО.' X Ж" двойственной траектории выбирается таким образом, чтобы пара (А^+1 — \к, цк+1) была отвечающим хк+1 множителем Лагранжа. Для этого метода доказывается две теоремы о локальной квадратичной сходимости. Первая теорема требует выполнения условия линейной независимости и сильного достаточного условия второго порядка оптимальности. Во второй теореме аналогичный результат (но без единственности траектории) устанавливается при выполнении строгого условия Мангасариана-Фромовица и достаточного условия второго порядка оптимальности.

Раздел 3.3 посвящен получению необходимых и достаточных условий для прямой сверхлинейной сходимости метода последовательного квадратичного программирования для задачи (2) в случае, когда отображения /', Н и д1 являются полугладкими. Итерация метода последовательного квадратичного программирования состоит в следующем. По текущему приближению (хк, Хк, цк) к решению системы ККТ задачи (2) и текущей симметричной итерационной матрице Нк £ П1пх" очередное прямое

приближение xk+1 6 Л1П вычисляется как стационарная точка задачи

(f'(xk), х-хк} + ¿(Нк(х - хк), х-хк)->- min,

h(xk) + h\xk){x - хк) = 0, д(хк) + д'(хк)(х - хк) s$ О,

а очередное двойственное приближение (А*+1, Цк+1) € И' х IR.™ — как отвечающий ей множитель Лагранжа. Основным результатом раздела является теорема, которая утверждает, что в естественных предположениях прямая сверхлинейная сходимость метода последовательного квадратичного программирования эквивалентна условию

тгсю X, ßk) - §§(**, Afc, ßk) - - **)) =

где х — решение задачи, к которому сходится прямая траектория метода, а тгс(г)(-) — оператор взятия евклидовой проекции на критический конус задачи в точке х. Это условие представляет собой полугладкую версию условия Дениса-Морэ.

Результаты главы 3 опубликованы в статьях [4, 7, 8, 10, 12].

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Измаилов А. Ф., Куренной А. С. Частный дифференциал Кларка и другие обобщенные дифференциалы // Теоретические и прикладные задачи нелинейного анализа. — М. : ВЦ РАН, 2010. — С. 77-90.

2. Измаилов А. Ф., Куренной А. С. Частный дифференциал Кларка и проекция полного дифференциала Кларка // XVIII международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2011», секция «Вычислительная математика и математическая кибернетика»: Сб. тезисов / МГУ им. М. В. Ломоносова. — М.: МАКС Пресс, 2011. -11-15 апреля. - С. 38.

3. Измаилов А. Ф., Куренной А. С. Абстрактная ньютоновская схема для нахождения неизолированных решений негладких обобщенных уравнений // Тихоновские чтения: Научная конференция / МГУ им. М. В. Ломоносова.- Т. 1,- М. : МАКС Пресс, 2012.-23-31 октября.-С. 41.

4. Измаилов А. Ф., Куренной А. С. Методы множителей для задач оптимизации с липшицевыми производными // Журнал вычислительной математики и математической физики. — 2012. — Т. 52, № 12. — С. 2140-2148.

5. Измаилов А. Ф., Куренной А. С. Об условиях регулярности для комплементарных задач // XIX международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2012», секция «Вычислительная математика и математическая кибернетика»: Сб. тезисов / МГУ им. М. В. Ломоносова. - М. : МАКС Пресс, 2012. -9-13 апреля. - С. 61-62.

6. Измаилов А. Ф., Куренной А. С., Солодов М. В. Метод Джозефи-Ньютона для полугладких обобщенных уравнений // Ломоносовские чтения: Научная конференция, посвященная 300-летию со дня рождения М. В. Ломоносова / МГУ им. М. В. Ломоносова. — М. : МАКС Пресс, 2011.-С. 24.

7. Izmailov A. F., Kurennoy A. S. Abstract Newtonian frameworks and their applications // SIAM Journal on Optimization. — 2013. — V. 23, № 4.— P. 2369-2396.

8. Izmailov A. F., Kurennoy A. S. Multiplier methods for optimization problems with Lipschitzian derivatives // VII Московская международная конференция по исследованию операций (ORM2013): Труды. — Т. 1. - М. : МАКС Пресс, 2013. - С. 64-66.

9. Izmailov А. P., Kurennoy A. S. On regularity conditions for complementarity problems // Computational Optimization and Applications. - 2013. - DOI: 10.1007/sl0589-013-9604-l.

10. Izmailov A. F., Kurennoy A. S., Solodov M. V. The Josephy-Newton method for semismooth generalized equations and semismooth SQP for optimization // Set-Valued and Variational Analysis. — 2013. — V. 21.— P. 17-45.

11. Izmailov A. F., Kurennoy A. S., Solodov M. V. A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems // Mathematical Programming.— 2013.— V. 142.— P. 591-604.

12. Izmailov A. F., Kurennoy A. S., Solodov M. V. Local convergence of the method of multipliers for variational and optimization problems under the sole noncriticality assumption // Optimization Online. —2013. http: //www.optimization-online.org/DB_HTML/2013/08/3999.html

Напечатано с готового оригинал-макета

Подписано в печать 06.03.2014 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 70 экз. Заказ 030.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский государственный университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра исследования операций

Куренной Алексей Святославович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика Диссертация на соискание учёной степени

кандидата физико-математических наук

Научный руководитель:

профессор, д.ф.-м.н.

Измаилов Алексей Феридович

Москва 2014

Оглавление

Введение 3

Список основных обозначений 10

Глава 1. Элементы вариационного и негладкого анализа 11

1.1. Условия регулярности для смешанных комплементарных задач..................11

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

1.1.2. Системы Каруша-Куна-Таккера ............................................26

1.2. Обобщенные дифференциалы........................................................28

1.2.1. Общий случай..................................................................30

1.2.2. Отображения специального вида ............................................31

1.3. Оценки расстояния до решений......................................................37

Глава 2. Итерационные схемы для решения обобщенных уравнений 47

2.1. Абстрактные ньютоновские схемы....................................................47

2.1.1. Сходимость к сильно метрически регулярным решениям..................48

2.1.2. Сходимость к полуустойчивым решениям..................................50

2.1.3. Случай возможно неизолированных решений..............................53

2.2. Полугладкий метод Джозефи-Ныотона..............................................56

Глава 3. Методы оптимизации для задач с липшицевыми производными 66

3.1. Метод модифицированных функций Лагранжа....................................67

3.1.1. Сходимость при достаточном условии второго порядка оптимальности 67

3.1.2. Сходимость при некритичности множителя................................85

3.2. Метод множителей с линеаризованными ограничениями..........................106

3.3. Полугладкий метод последовательного квадратичного программирования . . 110

Заключение 126

Введение

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

В работе рассматриваются задачи с липшицевыми производными, т. е. задачи оптимизации, производные целевой функции и ограничений которых являются локально липшицевыми. Напомним, что отображение Ф: Ж5 Жг называется локально липшицевым в точке г € Жя, если оно удовлетворяет условию Липшица в некоторой окрестности этой точки, т.е. если существует число I > 0 и окрестность [/СБ,5 точки г такие, что

ЦФ0?!) - Ф(г2)\\ ^ ф, - г2|| У*!, г2 6 С/.

При этом отображение называется локально липшицевым, если оно локально липшицево в каждой точке своей области определения.

Приведем типичный пример возникновения задачи оптимизации с липшицевыми производными. Предположим, что фирма может производить п типов товаров, и ее выпуск задается вектором х € Ж", ^'-я компонента которого равна производимому количеству ,7-го товара. Пусть при производстве товаров может выделяться N различных вредных веществ. Объем г-го вредного вещества, выделяемый при производстве единицы ^'-го товара равен а^. Если выделенное количество г-го вредного вещества превышает установленный государством допустимый уровень то фирма должна понести затраты но утилизации излишка, равные его квадрату. Тогда, если р £ Ж" — вектор цен, а с: Ж" Ж — функция издержек, то

функция прибыли фирмы /: И" IR имеет вид

f(x) = (р, х) - с(х) ] aVXJ - bi

1=1

N

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

Другим важным примером задач оптимизации с липшицевыми производными являются так называемые поднятые переформулировки задач оптимизации с комплементарными ограничениями. Задачей оптимизации с комплементарными ограничениями (см. [64, 71]) называется задача вида

где /: Нп 1-> И — заданная функция, а С, Я: Н" И"1 — заданные отображения. Один из подходов к решению таких задач оптимизации состоит в их переформулировке в виде задач с ограничениями равенствами (см. [49, 88]):

где у Е Ит — дополнительная переменная, и операции взятия максимума/минимума и возведения в степень осуществляются покомпонентно. Такая переформулировка называется поднятой. Какими бы гладкими ни были отображения G и Я, ограничения поднятой переформулировки не являются дважды дифференцируемыми. В то же время, если функция / и отображения G и Я дифференцируемы, и их производные локально липшицевы, то переформулированная задача представляет собой задачу с липшицевыми производными.

Еще одним источником возникновения задач оптимизации с липшицевыми производными являются методы поиска обобщенного равновесия Нэша. Пусть имеется N агентов (игроков), и пусть стратегия г-го игрока представляет собой вектор размерности щ. Требуется найти набор стратегий х = ж2, ..., xN) Е И", п — П\ +... + nN, хг Е 1R"', такой, что для каждого г = 1, ..., N точка Xi является решением задачи оптимизации

fz(xi, ..., 1, х{, xi+u xN) min, (жь ... , ¿c,_i, xu х'гН, .. . , xN) G X,

где /,: IR" i—IR — функция потерь г-ro игрока, непрерывная по совокупности переменных и выпуклая по переменной хг, а X С IR" — непустое замкнутое и выпуклое множество.

f{x) ->■ min, G{x) ^ 0, Н{х) ^ 0, (G(x), Н(х)) = О

f{x) min, (min{0, у})2 - G(x) = 0, (max{0, у})2 - H(x) = О

Оказывается, что поиск обобщенного равновесия Нэша (см. [90, теорема 3.3|) может быть основан на решении задачи оптимизации

Va(x) —> min, х € X,

целевая функция Va: IR" н> IR которой задается формулой Vn(x) = maxy6A'Фа(а;, у), где : IR™ х IR™ i—у IR — регуляризованная функция Никайдо-Изода,

N

Ф„(х, у) = (/»0еь • • ■ Xi, Xi+U ..., XN)~

i= 1

~ /¡(^1, • ■ • ) Xi— 11 </i, ^'г+li • • • i Xn) — ~~ 2) '

(се > 0 — фиксированный параметр). Функция Va корректно определена, поскольку при любом а > 0 и любом х € IR™ функция Я>а(х, •) сильно вогнута, а множество X непусто и замкнуто. Более того, поскольку X выпукло, существует единственный вектор уа{х) такой, что Фа(х,) уа{х)) = Va(x). Предположим дополнительно, что функции fi дважды непрерывно дифференцируемы, а X = {х G IR" | д(х) < 0}, где д: IR" н-> И"1 — дважды непрерывно дифференцируемое отображение с выпуклыми компонентами. Тогда, как показано в [89], если х € IR" — обобщенное равновесие Нэша, и градиенты <^(у«(.х')), j G {к = 1, ..., т [ Ук(Уа(%)) = 0}, линейно независимы, то функция Va дифференцируема, и ее производная локально липшицева в точке х, а значит, задача оптимизации

Va(x) -4- min, д(х) ^ О

локально (вблизи х) представляет собой задачу оптимизации с липшицевыми производными.

Наконец, помимо указанных приложений, задачи оптимизации с липшицевыми производными возникают в оптимальном управлении (речь идет о так называемых обобщенных линейно-квадратичных задачах) [84, 85], в машинном обучении [65, 91] и др.

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

Итак, объектом исследования в диссертационной работе являются задачи оптимизации с липшицевыми производными, а также численные методы их решения.

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

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

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

Опишем структуру диссертации. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 91 источника.

Первая глава посвящена ряду вспомогательных вопросов вариационного и негладкого анализа.

В разделе 1.1 получена полная картина соотношений между различными условиями регулярности для смешанных комплементарных задач. В разделе 1.2 изучаются соотношения между несколькими обобщенными дифференциальными объектами. В разделе 1.3 доказывается оценка расстояния до решения системы Каруша-Куна-Таккера задачи с липшицевыми производными.

Во второй главе разрабатываются методы решения обобщенных уравнений.

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

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

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

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

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

В разделе 3.3 изучается метод последовательного квадратичного программирования. Для него устанавливаются необходимые и достаточные условия прямой сверхлинейной сходимости.

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

• в диссертации разработаны новые итерационные схемы решения обобщенных уравнений;

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

• результаты о локальной сходимости метода модифицированных функций, полученные для задач с ограничениями-равенствами, являются первыми результатами о его локальной сходимости без требования регулярности ограничений и в предположениях, более слабых, чем достаточное условие второго порядка (они новы даже в дважды дифференцируемом случае);

• результаты о локальной сходимости метода множителей с линеаризованными ограничениями являются новыми в контексте задач с липшицевыми производными;

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

• в работе установлены неизвестные ранее соотношения между важнейшими условиями регулярности для сметанных комплементарных задач;

• доказанная в работе оценка расстояния до решения системы Каруша-Куна-Таккера является новой в контексте задач с липшицевыми производными;

• установленные в разделе 1.2 соотношения между различными обобщенными дифференциальными объектами не были известны ранее и могут быть полезными при их использовании.

Перечислим основные результаты, выносимые на защиту.

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

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

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

Достоверность научных положений обусловлена строгостью математических доказательств и использованных научных методов.

Список публикаций. Полученные в работе результаты опубликованы в [2]-[7], [43]-[48], в том числе 5 статей опубликовано в журналах из списка ВАК [5, 43, 45, 46, 47].

Апробация результатов. Результаты, полученные в диссертации, были представлены на XXI международном симпозиуме по математическому программированию «ISMP2012» (Берлин, Германия), на международной конференции по непрерывной оптимизации «1СС ОРТ2013» (Лиссабон, Португалия), на X всемирном конгрессе по структурной и междисциплинарной оптимизации «WCSMO-Ю» (Орландо, США, 2013), на ежегодных международных научных конференциях студентов и молодых ученых «Ломоносов-2011», «Ломоносов-2012» (Москва), на ежегодной научной конференции «Тихоновские чтения» (Москва, 2012), на ежегодной научной конференции «Ломоносовские чтения» (Москва, 2011), а также на VII Московской международной конференции по исследованию операций «ORM2013».

Общепринятые обозначения специально не оговариваются, их пояснение вынесено в список обозначений. В работе используется следующая система нумерации ее частей. Номер раздела состоит из двух цифр, первая из которых обозначает номер главы, в которой расположен раздел. Аналогично, номер пункта состоит из трех цифр, первые две из которых составляют номер раздела, в котором находится этот пункт. Нумерация объектов (формул, теорем и т.д.) в каждой главе независимая. При ссылке на объект извне главы, в которой он находится, используется номер, состоящий из двух цифр, первая из которых является номером главы, а вторая номером объекта в главе. Под «условиями утверждения» (теоремы, предложения, леммы) всегда понимается все то, что сказано в этом утверждении до слова

«Тогда».

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

Список основных обозначений

1R — множество вещественных чисел;

П{+ — множество неотрицательных вещественных чисел;

IR71 — n-мерное арифметическое пространство, снабженное евклидовым скалярным произведением и соответствующей нормой;

(•, •) — евклидово скалярное произведение;

|| • || — евклидова норма вектора (если не оговорено иначе);

conv S — выпуклая оболочка множества S (минимальное выпуклое множество, содержащее

5);

ker А — ядро (множество нулей) матрицы (линейного оператора) А; Ат — матрица, транспонированная к матрице А\ rank/l — ранг матрицы (линейного оператора) А; 7ts(x-) — проекция точки х на замкнутое выпуклое множество S; dist(x, S) = mf^gs 11re — — расстояние от точки x до множества S; diag(ii) — диагональная s x s-матрица с диагональю и, где и G К6; Di — вектор с компонентами уг, i £ I, где y€lRA, / с{1, ..., s};

Мк1к2 ~ подматрица матрицы М, отвечающая номерам строк г € Ki и номерам столбцов

з е к2]

В (и, 6) — замкнутый шар радиуса S с центром в точке«; ■ — знак окончания доказательства.

Глава 1

Элементы вариационного и негладкого анализа

Данная глава посвящена ряду вспомогательных вопросов и состоит из трех разделов. Первый раздел существенно отличается от двух других. В то время как материал второго и третьего раздела непосредственно относится к задачам оптимизации с липшицевыми производными, в первом разделе рассматриваются гладкие комплементарные задачи. Появление этого раздела объясняется следующими обстоятельствами. Один из подходов к решению задач оптимизации состоит в численном решении соотве�