[ «НЬЮТОНОВСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ С ЛИПШИЦЕВЫМИ ПРОИЗВОДНЫМИ ...»
Московский государственный университет им. М. В. Ломоносова
Факультет вычислительной математики и кибернетики
Кафедра исследования операций
На правах рукописи
Куренной Алексей Святославович
НЬЮТОНОВСКИЕ МЕТОДЫ
РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ
С ЛИПШИЦЕВЫМИ ПРОИЗВОДНЫМИ
Специальность 01.01.09 — дискретная математика и математическая кибернетика Диссертация на соискание учёной степени кандидата физико-математических наук
Научный руководитель:
профессор, д.ф.-м.н.
Измаилов Алексей Феридович Москва Оглавление Введение Список основных обозначений Глава 1. Элементы вариационного и негладкого анализа 1.1. Условия регулярности для смешанных комплементарных задач......... 1.1.1. Смешанные комплементарные задачи.................... 1.1.2. Системы Каруша–Куна–Таккера...................... 1.2. Обобщенные дифференциалы............................ 1.2.1. Общий случай................................. 1.2.2. Отображения специального вида...................... 1.3. Оценки расстояния до решений........................... Глава 2. Итерационные схемы для решения обобщенных уравнений 2.1. Абстрактные ньютоновские схемы.......................... 2.1.1. Сходимость к сильно метрически регулярным решениям......... 2.1.2. Сходимость к полуустойчивым решениям................. 2.1.3. Случай возможно неизолированных решений............... 2.2. Полугладкий метод Джозефи–Ньютона....................... Глава 3. Методы оптимизации для задач с липшицевыми производными 3.1. Метод модифицированных функций Лагранжа.................. 3.1.1. Сходимость при достаточном условии второго порядка оптимальности 3.1.2. Сходимость при некритичности множителя................ 3.2. Метод множителей с линеаризованными ограничениями............. 3.3. Полугладкий метод последовательного квадратичного программирования.. Заключение Введение Имеющийся в литературе локальный анализ наиболее эффективных численных методов оптимизации традиционно предполагает двукратную непрерывную дифференцируемость целевой функции и ограничений задачи. Настоящая работа посвящена распространению результатов о локальной сходимости этих методов на задачи с более слабыми свойствами гладкости и одновременно построению единой теории их локальной сходимости. Кроме того, целью работы является изучение свойств локальной сходимости этих алгоритмов в различных предположениях о регулярности задачи, и, в частности, ослабление требований регулярности, на которые опираются существующие результаты об их локальной сходимости.
В работе рассматриваются задачи с липшицевыми производными, т. е. задачи оптимизации, производные целевой функции и ограничений которых являются локально липшицевыми. Напомним, что отображение : IR IR называется локально липшицевым в точке IR, если оно удовлетворяет условию Липшица в некоторой окрестности этой точки, т. е.
если существует число > 0 и окрестность IR точки такие, что (1 ) (2 ) 1 2 1, 2.
При этом отображение называется локально липшицевым, если оно локально липшицево в каждой точке своей области определения.
Приведем типичный пример возникновения задачи оптимизации с липшицевыми производными. Предположим, что фирма может производить типов товаров, и ее выпуск задается вектором IR, -я компонента которого равна производимому количеству -го товара. Пусть при производстве товаров может выделяться различных вредных веществ.
Объем -го вредного вещества, выделяемый при производстве единицы -го товара равен.
Если выделенное количество -го вредного вещества превышает установленный государством допустимый уровень, то фирма должна понести затраты по утилизации излишка, равные его квадрату. Тогда, если IR — вектор цен, а : IR IR — функция издержек, то функция прибыли фирмы : IR IR имеет вид Как легко проверить, функция является дифференцируемой, и ее производная локально липшицева, но при этом функция, вообще говоря, не является дважды дифференцируемой.
Фирма может поставить перед собой задачу максимизации функции при тех или иных ограничениях на выпуск. Если эти ограничения обладают соответствующими свойствами гладкости, то в результате возникает задача с липшицевыми производными.
Другим важным примером задач оптимизации с липшицевыми производными являются так называемые поднятые переформулировки задач оптимизации с комплементарными ограничениями. Задачей оптимизации с комплементарными ограничениями (см. [64, 71]) называется задача вида где : IR IR — заданная функция, а, : IR IR — заданные отображения. Один из подходов к решению таких задач оптимизации состоит в их переформулировке в виде задач с ограничениями равенствами (см. [49, 88]):
где IR — дополнительная переменная, и операции взятия максимума/минимума и возведения в степень осуществляются покомпонентно. Такая переформулировка называется поднятой. Какими бы гладкими ни были отображения и, ограничения поднятой переформулировки не являются дважды дифференцируемыми. В то же время, если функция и отображения и дифференцируемы, и их производные локально липшицевы, то переформулированная задача представляет собой задачу с липшицевыми производными.
Еще одним источником возникновения задач оптимизации с липшицевыми производными являются методы поиска обобщенного равновесия Нэша. Пусть имеется агентов (игроков), и пусть стратегия -го игрока представляет собой вектор размерности. Требуется найти набор стратегий = (1, 2,..., ) IR, = 1 +... +, IR, такой, что для каждого = 1,..., точка является решением задачи оптимизации где : IR IR — функция потерь -го игрока, непрерывная по совокупности переменных и выпуклая по переменной, а IR — непустое замкнутое и выпуклое множество.
Оказывается, что поиск обобщенного равновесия Нэша (см. [90, теорема 3.3]) может быть основан на решении задачи оптимизации целевая функция : IR IR которой задается формулой () = max (, ), где : IR IR IR — регуляризованная функция Никайдо–Изода, ( > 0 — фиксированный параметр). Функция корректно определена, поскольку при любом > 0 и любом IR функция (, ·) сильно вогнута, а множество непусто и замкнуто. Более того, поскольку выпукло, существует единственный вектор () такой, что (, ()) = (). Предположим дополнительно, что функции дважды непрерывно дифференцируемое отображение c выпуклыми компонентами. Тогда, как показано в [89], если IR — обобщенное равновесие Нэша, и градиенты ( ()), { = 1,..., | ( ()) = 0}, линейно независимы, то функция дифференцируема, и ее производная локально липшицева в точке, а значит, задача оптимизации локально (вблизи ) представляет собой задачу оптимизации с липшицевыми производными.
Наконец, помимо указанных приложений, задачи оптимизации с липшицевыми производными возникают в оптимальном управлении (речь идет о так называемых обобщенных линейно-квадратичных задачах) [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], в том числе 6 статей опубликовано в журналах из списка ВАК [5, 43, 45, 46, 47, 48].
Апробация результатов. Результаты, полученные в диссертации, были представлены на XXI международном симпозиуме по математическому программированию «ISMP2012»
(Берлин, Германия), на международной конференции по непрерывной оптимизации «ICC OPT2013» (Лиссабон, Португалия), на X всемирном конгрессе по структурной и междисциплинарной оптимизации «WCSMO-10» (Орландо, США, 2013), на ежегодных международных научных конференциях студентов и молодых ученых «Ломоносов-2011», «ЛомоносовМосква), на ежегодной научной конференции «Тихоновские чтения» (Москва, 2012), на ежегодной научной конференции «Ломоносовские чтения» (Москва, 2011), а также на VII Московской международной конференции по исследованию операций «ORM2013».
Общепринятые обозначения специально не оговариваются, их пояснение вынесено в список обозначений. В работе используется следующая система нумерации ее частей. Номер раздела состоит из двух цифр, первая из которых обозначает номер главы, в которой расположен раздел. Аналогично, номер пункта состоит из трех цифр, первые две из которых составляют номер раздела, в котором находится этот пункт. Нумерация объектов (формул, теорем и т. д.) в каждой главе независимая. При ссылке на объект извне главы, в которой он находится, используется номер, состоящий из двух цифр, первая из которых является номером главы, а вторая номером объекта в главе. Под «условиями утверждения» (теоремы, предложения, леммы) всегда понимается все то, что сказано в этом утверждении до слова «Тогда».
Автор выражает огромную благодарность своему научному руководителю Алексею Феридовичу Измаилову, а также своим родителям.
Список основных обозначений IR — множество вещественных чисел;
IR+ — множество неотрицательных вещественных чисел;
IR — -мерное арифметическое пространство, снабженное евклидовым скалярным произведением и соответствующей нормой;
·, · — евклидово скалярное произведение;
· — евклидова норма вектора (если не оговорено иначе);
conv — выпуклая оболочка множества (минимальное выпуклое множество, содержащее ker — ядро (множество нулей) матрицы (линейного оператора) ;
T — матрица, транспонированная к матрице ;
rank — ранг матрицы (линейного оператора) ;
() — проекция точки на замкнутое выпуклое множество ;
dist(, ) = inf — расстояние от точки до множества ;
diag() — диагональная -матрица с диагональю, где IR ;
1 2 — подматрица матрицы, отвечающая номерам строк 1 и номерам столбцов (, ) — замкнутый шар радиуса с центром в точке;
— знак окончания доказательства.
Глава Элементы вариационного и негладкого анализа Данная глава посвящена ряду вспомогательных вопросов и состоит из трех разделов. Первый раздел существенно отличается от двух других. В то время как материал второго и третьего раздела непосредственно относится к задачам оптимизации с липшицевыми производными, в первом разделе рассматриваются гладкие комплементарные задачи. Появление этого раздела объясняется следующими обстоятельствами. Один из подходов к решению задач оптимизации состоит в численном решении соответствующей системы Каруша–Куна– Таккера, которая представляет собой частный случай смешанной комплементарной задачи.
При этом задачам оптимизации с пониженной гладкостью соответствуют негладкие системы Каруша–Куна–Таккера. Теория таких систем является естественным продолжением теории гладких комплементарных задач. Однако даже в последней, как оказалось, имелся ряд «белых пятен», устранение которых и стало предметом первого раздела данной главы.
1.1. Условия регулярности для смешанных комплементарных задач В настоящем разделе будет рассмотрен ряд широко используемых условий регулярности для (гладких) смешанных комплементарных задач и получена полная картина взаимоотношений между этими условиями.
Напомним, что смешанной комплементарной задачей (СКЗ) называется вариационное неравенство на прямоугольнике:
Здесь : IR IR — заданное отображение, а [, ] есть (обобщенный) прямоугольник, задаваемый числами IR {} и IR {+}, <, = 1,...,. Эквивалентным Важными частными случаями смешанной комплементарной задачи являются нелинейная комплементарная задача (НКЗ) соответствующая случаю, когда = 0, = +, = 1,...,, и система Каруша–Куна– Таккера (ККТ) относительно неизвестных (,, ) IR IR IR. Здесь : IR IR, : IR IR и : IR IR — заданные отображения, причем последние два предполагаются дифференцируемыми. Для того чтобы представить систему ККТ (4) в форме смешанной комплементарной задачи (2), достаточно положить = + +, и определить отображение по правилу где : IR IR IR IR — отображение вида Отметим, что СКЗ (1) с () = (), IR, представляет собой набор условий первого порядка оптимальности в задаче где : IR IR — некоторая гладкая функция.
Другой хорошо известный факт (см., например, [15, 34]) состоит в том, что СКЗ (2) может быть переформулирована в виде системы нелинейных уравнений с использованием так называемой функции дополнительности : IR2 IR, удовлетворяющей условию Предполагая наличие у этой функции дополнительных свойств с учетом эквивалентной переформулировки (2) смешанной комплементарной задачи (1) легко видеть, что множество ее решений совпадает с множеством решений уравнения с оператором : IR IR вида где Двумя наиболее часто используемыми функциями дополнительности (обе они обладают свойствами (5)) является функция естественной невязки (или функция минимума) и функция Фишера–Бурмейстера Отображение, заданное согласно (7) с использованием функции естественной невязки, будет обозначаться через, а с использованием функции Фишера–Бурмейстера — через. Отметим, что решение уравнения (6) с = или = методами ньютоновского типа является одним из наиболее эффективных численных подходов к решению комплементарных задач.
Для заданного решения IR СКЗ (1) (или, что то же самое, (2)) определим множества индексов Заметим, что, вне зависимости от свойств гладкости отображения, при нарушении условия строгой дополнительности 0 = как отображение =, так и = может быть недифференцируемым в точке. Однако, эти отображения являются локально липшицевыми в точке, если отображение локально липшицево в этой точке. В связи с этим, дифференциальными объектами, подходящими для изучения указанных отображений, являются -дифференциал и дифференциал Кларка. Напомним, что -дифференциал отображения : IR IR в точке IR определяется как множество где IR — множество точек дифференцируемости отображения. Дифференциалом Кларка называется выпуклая оболочка -дифференциала:
(см. [21, раздел 2.6.1], [32, раздел 7.1]).
Пусть отображение дифференцируемо вблизи, причем его производная непрерывна в точке (что влечет за собой локальную лишпицевость отображения в точке ). Из определения отображения непосредственно выводится следующая верхняя оценка для множества () (см., например, [55]): строки любой матрицы из () удовлетворяют соотношениям где через обозначена -я строка единичной матрицы размера, = 1,...,. Обозначим множество матриц из IR, строки которых удовлетворяют соотношениям (8), символом (). Таким образом, () ().
Напрямую из определений может быть выведена верхняя оценка и для множества (). А именно, строки любой матрицы из () удовлетворяют соотношениям где пара чисел (, ) IR IR принадлежит окружности для каждого 0. Отметим, что аналогичная оценка для множества () была получена в [15]. Обозначая через () множество матриц, строки которых удовлетворяют соотношениям (9) при некоторых (, ), 0, можем записать: () ().
Ниже будет приведен список наиболее широко используемых условий регулярности для смешанных комплементарных задач, включая условия, основанные на понятиях упомянутых выше обобщенных дифференциальных объектов. В пункте 1.1.1 будет получена полная картина взаимоотношений между условиями регулярности для общего случая СКЗ, а также для специального случая НКЗ. Пункт 1.1.2 посвящен системам ККТ.
Следует отметить, что все рассматриваемые условия регулярности имеют большую важность, поскольку каждое из них является ключевым предположением в анализе локальной сходимости определенных численных методов решения комплементарных задач и задач оптимизации. Полная картина соотношений между условиями регулярности позволяет сравнивать между собой теории этих методов, и этим обусловлено ее большое теоретическое и практическое значение. Понимание того, как соотносятся различные теории численных методов между собой, во-первых, важно с теоретической точки зрения, а во-вторых, может быть полезно при выборе алгоритмов для решения комплементарных задач и задач оптимизации на практике.
Будем говорить, что множество (квадратных) матриц невырождено, если все принадлежащие ему матрицы невырождены. Следующие условия регулярности играют ключевую роль в обосновании локальной сверхлинейной сходимости полугладкого метода Ньютона, применяемого к уравнению (6) с локально липшицевым оператором (см. [60, 61, 75, 78], а также [32, Раздел 7.5]).
Определение 1. Отображение : IR IR называется -регулярным (-регулярным) в точке IR, если множество () (()) не вырождено.
Если IR — решение СКЗ (1), то в силу верхних оценок для множеств () и (), приведенных выше, -регулярность отображения ( ) в точке следует из невырожденности множества () (соответственно, ()), в то время как регулярность отображения ( ) в точке следует из невырожденности conv () (соответственно, conv ()).
Определим множества Из определения множества () следует, что conv () есть совокупность всех матриц IR, строки которых удовлетворяют условию (9) с некоторыми числами (, ), 0. Аналогичным образом, легко установить, что множество conv () совпадает с множеством всех матриц IR, строки которых удовлетворяют соотношению (9) с некоторыми числами (, ), 0.
Отметим, что в случае нелинейной комплементарной задачи (3) невырожденность множества () известна в литературе под названием -регулярности решения [72]. Это условие эквивалентно тому, что матрица является невырожденной для любого подмножества 0.
В случае систем Каруша–Куна–Таккера (4), невырожденность множества () есть то же самое, что и квази-регулярность решения = (,, ) IR IR IR [31]. Предположим, что отображение дифференцируемо вблизи, причем его производная является непрерывной в точке, а отображения и являются дважды дифференцируемыми вблизи, и их вторые производные непрерывны в точке. Определим множества индексов Квази-регулярность эквивалентна тому, что матрица является невырожденной для любого множества индексов 0.
Возвращаясь к общему случаю смешанных комплементарных задач, в дополнение к перечисленным выше условиям регулярности рассмотрим следующие условия.
Определение 2. Решение СКЗ (1) называется сильно регулярным, если для каждого IR, достаточно близкого к 0, возмущенная линеаризованная СКЗ имеет вблизи единственное решение (), и отображение (·) является локально липшицевым в точке 0.
Понятие сильной регулярности было введено в [81] и продолжает играть важную роль в вариационном анализе (см., например, [27, Глава 2], [32, Глава 5], а также библиографические ссылки в этих работах). В частности, оно является ключевым предположением в анализе локальной сходимости различных итерационных схем решения вариационных задач (см. [27, Глава 6]).
В [81] была получена простая алгебраическая характеризация сильной регулярности для НКЗ. Эта характеризация была позднее обобщена на случай СКЗ в [30]. Для того, чтобы сформулировать ее, напомним, что квадратная матрица называется -матрицей, если все ее главные миноры положительны. Решение СКЗ является сильно регулярным тогда и только тогда, когда матрица ( ())+ + невырождена, и ее дополнение Шура является -матрицей.
Следующее более слабое условие регулярности было введено в [17] и является основным ингредиентом ряда тонких результатов о локальной сходимости методов ньютоновского типа для вариационных задач. Другие приложения этого свойства связаны с теорией чувствительности, см. [32, Разделы 5.3, 6.2].
Определение 3. Решение СКЗ (1) называется полуустойчивым, если существует константа > 0 такая, что для любого IR всякое решение () возмущенной комплементарной задачи достаточно близкое к, удовлетворяет оценке 1.1.1. Смешанные комплементарные задачи Известные соотношения Начнем с некоторых соотношений между -регулярностью и -регулярностью. Прежде всего, очевидно, что () (), а значит, справедливо и соответствующее включение для выпуклых оболочек этих множеств: conv () conv (). В частности, невырожденность множества () влечет за собой невырожденность множества ().
Обратное включение, вообще говоря, не имеет места. Более того, из невырожденности множества () не следует ни -регулярность отображения в точке, ни регулярность отображения в точке, что демонстрирует следующий пример, взятый из [24, Пример 2.1].
Пример 1. Пусть = 2. Рассмотрим НКЗ (3) с () = (1 + 2, 2 ). Точка = является единственным решением этой НКЗ.
Непосредственно проверяется, что а значит, множество () не вырождено. С другой стороны, матрица вырождена, а значит, отображение не является -регулярным в точке.
Для каждого = 1, 2,... положим = (1/, 2/). Тогда отображение дифференцируемо в точках, и последовательность { } сходится к. Следовательно, вырожденная матрица в правой части последнего выражения лежит в (), а значит, отображение не является -регулярным в точке.
Следующий пример, позаимствованный из [23, Пример 2], показывает, что множество () может быть собственным подмножеством (). Более того, может случиться, что каждое из отображений и является -регулярным в точке, но при этом множества () и () содержат вырожденные матрицы.
Пример 2. Пусть = 2, и () = ((1 + 2 )/2, (1 + 2 )/2). Тогда точка = 0 является единственным решением НКЗ (3).
Непосредственной проверкой убеждаемся, что Путем непосредственного вычисления получаем, что det = 1/2 для любой матрицы (), откуда следует -регулярность (а значит и -регулярность) отображения в точке. В то же время, является вырожденной.
Далее, множество () состоит из матриц вида для всех (, ), = 1, 2. Путем непосредственного вычисления получаем:
определитель равен нулю тогда и только тогда, когда т. е. 1 = 2 = 1, 1 = 2 = 0, откуда следует, что матрица 0, определенная в (12), является единственной вырожденной матрицей во множестве (). Более того, в свете приведенного выше представления для множества conv () становится ясно, что 0 — единственная вырожденная матрица и в этом множестве. При этом, как легко проверить, эта матрица не принадлежит множеству (). Но тогда эта матрица не принадлежит и множеству (), ведь, как видно из (13), 0 не может не быть крайней точкой множества ().
Таким образом, отображение является -регулярным (а значит, и -регулярным) в точке.
Можно предположить, что -регулярность (или, по крайней мере, -регулярность) отображения в точке влечет за собой -регулярность (или хотя бы -регулярность) отображения в точке, но, как показывает следующий пример, взятый из [1], это не так.
Пример 3. Пусть = 2, () = (2, 1 + 2 ). Тогда = 0 является единственным решением НКЗ (3), причем, как легко видеть, множество () содержит вырожденную в то время как отображение является -регулярным в точке. Действительно, несложно убедиться в том, что указанная матрица является единственной вырожденной матрицей в conv () и при этом не принадлежит множеству (). Кроме того, она не может быть некрайней точкой множества (). Следовательно, эта матрица не лежит в (), и отображение является -регулярным в точке.
Помимо указанных фактов, известно, что -регулярность отображения в точке не влечет за собой -регулярность отображения в. Это демонстрируется следующим простым примером.
Пример 4. Пусть = 1, () =. Тогда точка = 0 является единственным решением НКЗ (3).
Очевидно, что () = 2||, () = { 2, 2}, откуда следует -регулярность отображения в точке. В то же время, множество () = () = [ 2, 2] содержит 0.
Наконец, приведем известные соотношения, касающиеся сильной регулярности и полуустойчивости.
В [23] было показано, что -регулярность любого из отобржений и в решении СКЗ влечет полуустойчивость этого решения. Обратная импликация не имеет места, как видно из примеров 1 и 2.
Что касается сильной регулярности, как следует из доказательства [34, Теорема 1], если является сильно регулярным решением СКЗ (1), то множество conv () (а значит, и conv ()) не вырождено. В частности, сильная регулярность не может следовать из условий, которые не влекут за собой невырожденность множества conv ().
Соотношения между условиями регулярности, о которых шла речь в настоящем пункте, представлены в таблице 1.1. Знак «+» («») в ячейке означает, что свойство, соответствующее строке данной ячейки, влечет (не влечет) за собой свойство, указанное в заголовке ее столбца. Знак вопроса говорит о том, что до настоящего момента вопрос о наличии или отсутствии соответствующей импликации оставался открытым.
Таблица 1.1. Условия регулярности для СКЗ: известные соотношения.
Сильная регулярность Недостающие соотношения Займемся устранением знаков вопроса в таблице 1.1. Начнем с доказательства следующего факта.
Предложение 1. Для решения СКЗ (1) следующие три свойства эквивалентны:
а) множество conv () невырождено;
б) множество () невырождено;
в) множество conv () невырождено.
Доказательство. Ключевое наблюдение, делающее сформулированное утверждение очевидным, состоит в том, что для всякой пары (, ) можно указать число > 0 такое, что (, ), и число > 0 такое, что (, ) (см. рисунок 1.1). Следовательно, любая матрица вида (9) с (, ) для всех 0 путем домножения некоторых ее строк на положительные числа может быть преобразована в матрицу такого же вида, но с (, ) или (, ) для всех 0. Отсюда сразу получаем требуемое.
Далее, любое из эквивалентных свойств а)–в) в утверждении 1 влечет за собой сильную регулярность решения. Доказательству этого факта предпошлем следующую лемму.
Лемма 1. Если матрица IR не является -матрицей, то найдутся наборы чисел, IR такие, что (, ) для всех = 1,...,, где множество определено в (10), и при этом матрица вырождена.
Доказательство. Проведем индукцию по. Если = 1, предположение о том, что матрица не является -матрицей, означает, что есть неположительное число. Приравняв правую часть формулы (14) к нулю, получим уравнение прямой в плоскости (, ), которая имеет непустое пересечение с окружностью. Любая из точек в этом пересечении является искомой парой (, ).
Предположим теперь, что утверждение леммы выполнено для любой матрицы размера ( 1) ( 1), и что матрица IR с элементами,,, = 1,...,, имеет неположительный главный минор. Если единственный такой минор есть det, положим = 1, = 0, = 2,...,, и разложим определитель det (, ) по первой строке:
Поскольку det 0, а det {2,..., }{2,..., } > 0, прямая, задаваемая в плоскости (1, 1 ) уравнением det (, ) = 0, имеет непустое пересечение с окружностью, и, взяв в качестве 1 и 1 компоненты произвольной точки из этого пересечения, получим искомые векторы Остается рассмотреть случай существования подмножества {1,..., } такого, что номером, получим матрицу IR(1)(1) с неположительным главным минором. По предположению индукции, существуют векторы = (1,..., 1, +1,..., ) IR1, матрица diag( ) + diag() вырождена. Полагая = 0, = 1, получаем векторы и с требуемыми свойствами.
Предложение 2. Если точка является решением СКЗ (1), и при этом множество () невырождено, то решение сильно регулярно.
Доказательство. Невырожденность всех матриц в множестве () эквивалентна тому, что матрица Полагая = 0, = 1, 0, отсюда сразу получаем, что матрица ( ())+ + невырождена.
Предположим теперь, что решение СКЗ не является сильно регулярным. Тогда из невырожденности матрицы ( ())+ + следует, что матрица не является -матрицей. Тогда, по лемме 1, существуют наборы чисел = (, 0 ) и вырождена. Но эта матрица представляет собой дополнение Шура невырожденной матрицы ( ())+ + в (, ), и следовательно, матрица (, ) также вырождена (см., к примеру, [8, Теорема 1.3.1.1]), что не возможно.
Объединяя предложения 1 и 2 и тот факт, что сильная регулярность решения влечет за собой невырожденность множества conv (), заключаем, что свойства а)–в) из предложения 1 эквиваленты сильной регулярности.
Теперь остается лишь выяснить, следует ли из -регулярности отображения в точке, что отображение является -регулярным (или хотя бы -регулярным) в точке. Следующий пример показывает, что это не так. Более того, даже комбинация регулярности отображения в точке и невырожденности множества () не дает -регулярность (а уж тем более -регулярность) отображения в точке.
Пример 5. Пусть = 2, () = (1 + 32 /(2 2), 21 + (1 3/(2 2))2 ). Тогда точка = 0 является единственным решением соответствующей НКЗ.
Рассмотрим произвольную последовательность { } IR2 такую, что 1 < 0, 2 = 0 для всех, и 1 стремится к 0 при. Тогда для всех отображение дифференцируемо в точке, и а значит, вырожденная матрица в правой части последнего равенства лежит в ().
В то же время, непосредственной проверкой можно установить, что и следовательно, Для любой матрицы () в правой части последнего соотношения имеем откуда следует -регулярность отображения в точке.
Наконец, заметим, что и значит, множество () невырождено, т. е. точка является -регулярным решением рассматриваемой НКЗ.
Пример 5 показывает, что предполагая невырожденность всех матриц из выпуклой оболочки множества () и невырожденность всех матриц из другого расширения этого множества — (), нельзя гарантировать даже -регулярность отображения в точке. В то же время, как показывают утверждения 1 и 2, используя оба вида расширения множества () вместе (т. е. предполагая невырожденность матриц из множества conv ()), мы приходим к сильной регулярности решения.
1.1.2. Системы Каруша–Куна–Таккера Некоторые импликации, неверные в общем случае СКЗ, оказываются справедливыми в специальном случае систем ККТ.
Дело в том, что в отличие от случая НКЗ, для систем ККТ формула (8) дает не просто верхнюю оценку -дифференциала отображения, а точную характеризацию этого множества: для всякого решения = (,, ) системы ККТ (4) справедливо равенство () = (), которое влечет за собой равенство () = conv (). Данный факт объясняется тем, что прямая переменная и двойственная переменная «разделяются» по разным аргументам функции естественной невязки, и для любой матрицы () легко построить последовательность { } такую, что { } и { ( )}.
Как следствие, для систем ККТ -регулярность отображения в решении эквивалентна невырожденности множества () (т. е. квази-регулярности решения), а регулярность отображения в решении эквивалентна невырожденности множества conv ().
Обратимся теперь к отображению. Легко видеть, что формула (9) дает точную характеризацию -дифференциала этого отображения в решении системы ККТ, если градиенты (), 0, линейно независимы. Покажем, что последнее условие автоматически выполняется в решении, если отображение является -регулярным в этом решении.
Предложение 3. Пусть отображение : IR IR дифференцируемо в окрестности точки IR, причем его производная непрерывна в этой точке, и пусть отображения : IR IR и : IR IR дважды дифференцируемы в окрестности точки, причем их вторые производные непрерывны в этой точке. Пусть вектор = (,, ), где (, ) IR IR, является решением системы ККТ (4).
Тогда, если отображение является -регулярным в точке, то в точке выполнено условие линейной независимости: градиенты (), = 1,...,, (),, линейно независимы.
Доказательство. Зафиксируем последовательность { } IR такую, что и { }. Тогда последовательность {(,, )} сходится к (,, ), и, как легко видеть, для каждого номера отображение дифференцируемо в точке (,, ), причем соответствующая последовательность матриц Якоби этого отображения сходится к матрице (с точностью до перестановки строк и столбцов), где символом обозначена единичная матрица соответствующего размера. Отсюда получаем требуемое.
Из этого предложения и предшествующих обсуждений следует, то для систем ККТ регулярность отображения в решении влечет за собой невырожденность множества (), а значит, в силу предложения 1, невырожденность множества conv () (из которой в свою очередь следует -регулярность отображения в точке ). Кроме того, ясно, что -регулярность отображения в решении системы ККТ влечет невырожденность множества ().
Таким образом, для решения системы ККТ можно выделить три группы эквивалентных свойств. Первая группа состоит из -регулярности отображения в точке, регулярности отображения в точке, -регулярности отображения в точке, невырожденности множества (), невырожденности множества conv (), невырожденности множества conv () и сильной регулярности решения. Вторая группа объединяет в себе -регулярность отображения в точке и невырожденность множества (). Наконец, последняя группа образована полуустойчивостью. Условия первой группы влекут за собой условия второй, а из условий второй группы следует полуустойчивость.
Обратные импликации не имеют места. Действительно, НКЗ из примера 4 соответствует прямым условиям первого порядка оптимальности в задаче Единственным решением соответствующей системы Каруша–Куна–Таккера является точка = (, ) = (0, 0), и, как легко видеть, это решение является квази-регулярным, но при этом множество () содержит вырожденную матрицу.
Тот факт, что из полуустойчивости решения системы ККТ не следует -регулярность отображения, может быть продемонстрирован примером 1 из [50].
Завершая раздел, представим соотношения между условиями регулярности в виде диаграммы (см. рисунок 1.2). Сплошные линии на этой диаграмме соответствуют импликациям, которые верны для общего случая СКЗ, а штриховыми линиями обозначены дополнительные импликации, справедливые в специальном случае систем ККТ. Приведенная диаграмма является полной: существование пути из одного ее блока в другой эквивалентно тому, что из свойства, соответствующего первому блоку, следует свойство, соответствующее второму блоку. Последнее справедливо как для общего случая СКЗ, так и для НКЗ (в силу того, что во всех контрпримерах, представленных в пункте 1.1.1, фигурируют только НКЗ). С учетом штриховых стрелок, то же самое верно и для систем ККТ.
регулярность Невырожденность Невырожденность Невырожденность Рис. 1.2. Условия регулярности: полная диаграмма взаимосвязей.
1.2. Обобщенные дифференциалы В контексте задач оптимизации, целевая функция и ограничения которых являются дважды непрерывно дифференцируемыми, наибольшую эффективность имеют численные методы, использующие информацию второго порядка, т. е. задействующие матрицу Гессе функции Лагранжа задачи либо ее аппроксимации. В случае задач с липшицевыми производными указанная матрица Гессе может не существовать, и ее роль выполняют обобщенные дифференциальные объекты, определения которых, как правило, основаны на понятиях дифференциала и дифференциала Кларка (см. с. 14).
Пусть : IR IR IR. Частным -дифференциалом отображения по переменной в точке = (, ) IR IR называется множество а частным дифференциалом Кларка — множество Также введем в рассмотрение оператор проектирования пространства IR IR на подпространство IR :
Основной целью настоящего раздела является изучение взаимосвязи между частным дифференциалом Кларка (, ) и проекцией полного дифференциала Кларка (, ).
Множества как первого, так и второго типа используются в ряде численных методов решения задач с липшицевыми производными (см., например, [39, 76]). В связи с этим важно понимать, как они соотносятся друг с другом, и какие последствия имеет замена одного на другое в практических алгоритмах.
Помимо (, ) и (, ) будем использовать следующие обобщенные дифференциалы 1.2.1. Общий случай Начнем со следующего вспомогательного факта.
Лемма 2. Пусть отображение : IR IR IR является липшицевым в некоторой окрестности точки (, ) IR IR.
Доказательство. Начнем с доказательства равенства в (16).
Включение (, ) ( ) (, ) очевидно. Покажем обратное включение.
Принадлежность матрицы множеству ( ) (, ) означает, что найдется последовательность Из липшицевости отображения в окрестности точки (, ) следует, что его производная в любой точке = (, ) из этой окрестности не превосходит по норме константу Липшица > 0 отображения. За неимением адекватной ссылки, приведем доказательство этого (безусловно хорошо известного) факта. Действительно, зафиксируем произвольный элемент IR IR, = 1. При всех достаточно малых > 0 выполняется Разделив левую и правую части на и перейдя к пределу при 0+, получаем неравенство Таким образом, последовательность { (, )} ограничена, а значит, имеет предельную точку. Тогда (, ), причем из (18) следует, что = [ 2 ], где 2 IR — некоторая матрица. Поэтому (, ). Тем самым доказано включение ( ) (, ) (, ), что и завершает доказательство равенства в (16).
Включение в (16) и включение (17) очевидны.
Таким образом, обобщенные дифференциалы отличаются тем, в каком множестве должны лежать последовательности, фигурирующие в определении этих обобщенных дифференциалов. Для (, ) таким «допустимым» множеством является, для ( ) (, ) — множество точек, в которых дифференцируемо по. В случае ( ) (, ) это множество точек вида (, ), в которых дифференцируемо Замечание 1. Из (16) и (17) легко вытекают аналогичные соотношения для множеств Для доказательства достаточно учесть два факта. Первый состоит в том, что для любых множеств 1 IR и 2 IR из 1 2 следует conv 1 conv 2. Второй факт заключается в том, что для любого линейного оператора : IR(+) IR и любого множества IR(+) выполняется равенство (conv ) = conv ().
Для кусочно-линейной функции : IR2 IR, построенной в примере 2.5.2 из [21], выполнено из чего следует, что для нее включения (17) и (20) выполняются строгим образом, и, значит, в приведенных утверждениях они не могут быть заменены на равенства.
1.2.2. Отображения специального вида Перейдем к рассмотрению отображений : IR IR IR вида где : IR IR и : IR IR — заданные отображения.
Оказывается, что для отображений такого вида дифференцируемость по переменной и дифференцируемость по совокупности переменных эквивалентны.
Лемма 3. Пусть отображение : IR IR IR имеет вид (21), причем отображение : IR IR непрерывно в точке. Тогда если (, ) дифференцируемо по в точке (, ), то оно дифференцируемо по совокупности переменных в этой точке. При этом Доказательство. Дифференцируемость по в (, ) означает, что Тогда Но в силу непрерывности в точке имеем ((+)()) = (), что и дает требуемое.
В следующей лемме устанавливается еще одно дифференциальное свойство отображений вида (21).
Лемма 4. Пусть отображение : IR IR IR имеет вид (21), причем отображение : IR IR является липшицевым в некоторой окрестности точки IR с константой > 0.
Тогда если дифференцируемо по в точках (, 1 ) и (, 2 ) при некоторых 1, 2 IR, Доказательство. Дифференцируемость по переменной в точках (, 1 ) и (, 2 ) означает, что для IR Отсюда следует соотношение Зафиксируем произвольный элемент IR, = 1. В силу (23), используя липшицевость отображения в окрестности точки, при > 0 имеем Разделив левую и правую части на и перейдя к пределу при 0+, получаем неравенство что с учетом произвольности и дает требуемую оценку (22).
Основной результат данного раздела содержится в следующей теореме.
Теорема 1. Пусть отображение : IR IR IR имеет вид (21), причем отображения : IR IR и : IR IR являются локально липшицевыми в точке IR.
Тогда для любого IR справедливы равенства Доказательство. Из леммы 3 следует, что для любого IR Это влечет за собой включение Поскольку () и () локально липшицевы в точке, (, ) является локально липшицевым в точке (, ) для любого IR. Поэтому, в силу замечания 1 выполняются соотношения С учетом этих соотношений и (25), для завершения доказательства теоремы достаточно показать, что при любом IR Пусть ( ) (, ). Тогда найдется последовательность {(, )} (, ), в каждой точке которой дифференцируемо по, причем и, кроме того, для любого точка принадлежит окрестности точки, в которой отображения и являются липшицевыми. Заметим, что при всех отображения (·, ) и (·, ) являются липшицевыми на.
Определим как множество точек, в которых отображение (·, ) не дифференцируемо:
= IR (·, ). По теореме Радемахера [9, теорема 3.1.6] мера Лебега множества равна нулю. Теперь заметим, что Как показано в [29], дифференциал Кларка не зависит от множеств нулевой меры Лебега.
Отсюда и из (28) вытекает, что где Отсюда и из теоремы Каратеодори следует, что для всякого найдутся такие, что Из (29), (30) вытекает, что для любого = 1,..., + 1 и любого существует последовательность {, } ((·, ) ) такая что и значит, можно выбрать номер () так, чтобы выполнялось Далее, для любого имеет место цепочка равенств где последнее равенство следует из второго равенства в (31). С учетом первого равенства в (31) и второго неравенства в (32) имеем и поэтому Кроме того, с учетом леммы 4 выводим оценку где > 0 — константа Липшица для на. Отсюда следует, что Из (27) и (33)–(35) вытекает предельное соотношение Учитывая липшицевость (·, ) на, для каждого индекса = 1,..., + 1 последовательность { (,, )} ограничена. Значит, в силу очевидной ограниченности последовательностей { }, переходя при необходимости к подпоследовательностям, можем считать, что при некоторых из (36) и из (37) вытекают равенства При этом, в силу второго предельного соотношения в (37), для всякого = 1,..., + матрица лежит в ( ) (, ), так как по построению причем в силу первого неравенства в (32) справедливо {, } ( ). Но тогда из (38) получаем, что Это доказывает включение из которого, в силу выпуклости множества (, ), вытекает требуемое включение (26).
В завершение пункта приведем еще одно утверждение, справедливое для отображений вида (21), которое понадобится нам в дальнейшем.
Лемма 5. Пусть отображение : IR IR IR имеет вид (21), причем отображения : IR IR и : IR IR локально липшицевы в точке IR. Пусть последовательности {(, 1 )} IR IR и {(, 2 )} IR IR сходятся к (, ), где IR.
Тогда для любой последовательности матриц { } IR такой, что для всех, существует последовательность матриц { } IR, такая что (, 2 ) для всех достаточно больших, и Доказательство. Рассмотрим произвольную окрестность точки, в которой отображения и удовлетворяют условию Липшица. Тогда для всех отображение (·, 2 ) является липшицевым на, поэтому, по теореме Радемахера, оно дифференцируемо всюду в, где — некоторое множество, мера Лебега которого равна нулю. Пусть обозначает множество точек дифференцируемости отображения (·, 1 ). Поскольку дифференциал Кларка не зависит от множества нулевой меры Лебега [29], для всех достаточно больших (таких, чтобы выполнялось ) и любых матриц (, 1 ) существу- ют IN, матрицы, IR и числа, = =1,,, и для всех = 1,..., найдется последовательность { }, Далее, по лемме 4, при всех достаточно больших, для всех, начиная с некоторого номера, справедливо неравенство где — произвольная константа Липшица отображения на. Для всех больших, поскольку (·, 2 ) локально липшицево в точке, для всех = 1,..., последовательность { (,, 2 )} ограничена, и, следовательно, при необходимости переходя к подпоследовательности, можно считать, что при, она сходится к некоторой матрице,. Тогда, переходя к пределу в (39), получаем оценку По определению -дифференциала, имеем, ( ) (, 2 ). Но тогда, по определению дифференциала Кларка, выпуклая комбинация =, принадлежит (, 2 ), и при этом, в силу (40), 1.3. Оценки расстояния до решений При анализе численных методов оптимизации важную роль играют так называемые оценки расстояния до решения системы Каруша–Куна–Таккера (ККТ) задачи оптимизации. Однако, имеющиеся в литературе оценки такого рода (см. [26, 31, 56, 57, 63, 82], а также обзор [50]) устанавливаются либо в предположении регулярности ограничений, либо для систем ККТ, соответствующих задачам оптимизации, целевая функция и ограничения которых являются дважды непрерывно дифференцируемыми. В настоящем разделе будет доказана оценка расстояния до множества решений системы ККТ задачи с липшицевыми производными без требования каких бы то ни было условий регулярности ограничений. Эта оценка станет одним из инструментов получения тонких результатов о сходимости численных методов решения задач с липшицевыми производными в главе 3.
Рассмотрим задачу оптимизации в которой целевая функция : IR IR и отображения : IR IR и : IR IR дифференцируемы. Система Каруша–Куна–Таккера задачи (41) имеет вид где : IR IR IR IR — функция Лагранжа задачи (41), Пусть () IR IR — совокупность множителей Лагранжа, отвечающих точке IR (т. е. множество пар (, ) IR IR таких, что тройка (,, ) удовлетворяет системе (42)). Точка IR называется стационарной точкой задачи (41), если () =.
В случае, когда, и дважды непрерывно дифференцируемы в точке IR, из результатов [36, 38, 51, 52] следует эквивалентность следующих трех свойств.
Свойство 1 (верхняя липшицева устойчивость решений системы ККТ при канонических возмущениях). Существует окрестность точки (,, ) и число > такие, что для любого = (,, ) IR IR IR, достаточно близкого к точке (0, 0, 0), всякое решение ((), (), ()) возмущенной системы KKT удовлетворяет оценке Свойство 2 (оценка расстояния для системы ККТ). Существует окрестность точки (,, ) и число > 0 такие, что для любого вектора (,, ) выполняется неравенство Свойство 3 (некритичность множителя (, )). Не существует тройки (,, ) IR IR IR, с = 0, которая бы удовлетворяла системе где множества индексов, + и 0 введены в (11).
Замечание 2. Эквивалентность свойств 1 и 2 не требует двукратной дифференцируемости функции и отображений и. Тот факт, что из свойства 2 следует свойство 1, доказывается тривиальным образом. Обратная импликация была получена в [36, Теорема 2].
Однако свойство 3, являющееся наиболее конструктивным, для задач с липшицевыми производными вообще говоря не имеет смысла, поскольку в этом случае матрица Гессе, ) может не существовать. В связи с этим возникает вопрос о том, какие конструктивные условия, гарантирующие (без каких-либо дополнительных предположений) выполнение оценки расстояния (т. е. свойства 2), можно предъявить для задач с липшицевыми производными. Нахождение таких условий и составляет цель настоящего раздела.
Напомним, что, согласно [58, (6.6)], контингентной производной отображения : IR IR в точке (в которой это отображение является локально липшицевым) называется точечно-множественное отображение () из IR во множество подмножеств IR, заданное по правилу В частности, если дифференцируемо в точке по направлению, то ()() состоит из единственного элемента — производной отображения в точке по направлению. Заметим, что (см. [58, (6.5), (6.6), (6.16)]).
Кроме того, частной контингентной производной отображения : IR IR IR в точке (, ) IR IR по переменной называется контингентная производная отображения (·, ) в точке. Будем обозначать эту производную через (, ).
Наконец, будем говорить, что отображение : IR IR удовлетворяет условию Липшица относительно точки IR в окрестности этой точки с константой > 0, если Следующее условие является обобщением свойства 3 на случай задач с липшицевыми производными Определение 4. Множитель Лагранжа (, ), отвечающий стационарной точке IR задачи (41), называется некритическим, если не существует тройки (,, ) IR IR IR с = 0, удовлетворяющей системе с некоторым (,, )(). В противном случае множитель (, ) называется критическим.
Замечание 3. Из (50) следует, что множитель (, ) является некритическим, если не существует тройки (,, ) IR IR IR с = 0, удовлетворяющей системе (51)–(52) при =, где — некоторая матрица из множества (,, ). Множитель, удовлетворяющий последнему условию, будет называться строго некритическим.
С учетом замечания 3 становится очевидным, что некритичность множителя (, ) следует из так называемого достаточного условия второго порядка:
где () — критический конус задачи (41) в точке, Отметим, что, как показано в [59], условие (53) в действительности является достаточным для локальной оптимальности точки в задаче (41).
Рассмотрим следующую параметрическую версию системы ККТ (42):
В этой системе IR является параметром, а функция : IR IR IR и отображения : IR IR IR и : IR IR IR дифференцируемы по переменной. Отметим, что система (55) является системой ККТ параметрической задачи относительно неизвестной. Пусть : IR IR IR IR IR — функция Лагранжа этой параметрической задачи:
В контексте оптимизационных задач, следующий результат о чувствительности обобщает [51, Теорема 2.3] (см. также связанный с этим результат в [38]).
Теорема 2. Пусть функция : IR IR IR и отображения : IR IR IR и : IR IR IR дифференцируемы по переменной вблизи точки (, ), и, кроме того, выполнены следующие предположения:
б) существует окрестность точки и число > 0 такие, что для любого фиксированного, достаточно близкого к точке, отображения ) удовлетворяют условию Липшица относительно точки на с константой Пусть IR — стационарная точка задачи (56) при =, а (, ) IR IR — отвечающий ей множитель Лагранжа.
Тогда, если множитель (, ) некритический, то для любого, достаточно близкого к, и любого решения ((), (), ()) системы (55), достаточно близкого к (,, ), выполняется оценка где (, ) есть множество пар (, ) IR IR таких, что тройка (,, ) является решением системы (55) при =.
Доказательство. Сначала докажем, что Предположим, что (57) не выполняется, т. е. найдутся последовательности { } IR и точка (,, ) является решением системы (55) при =, и при этом >, где { } — некоторая последовательность положительных чисел, стремящаяся к бесконечности. Тогда выполняется оценка Определим множества индексов Поскольку существует лишь конечное число способов разбить множество индексов 0 на два непересекающихся подмножества, без ограничения общности можно считать, что для каждого справедливы соотношения где 1 и 2 — фиксированные множества индексов такие, что 1 2 = 0, 1 2 =. Далее, в предположениях теоремы отображение является непрерывным в точке (, ). Следовательно, в силу условия дополняющей нежесткости в (55) и того факта, что последовательность {(,, )} сходится к (,, ), без потери общности можно полагать, что для любого верно, что Кроме того, при необходимости переходя к подпоследовательности, можно считать, что {( )/ } сходится к некоторому вектору IR, = 1. Тогда, полагая = и вновь переходя к подпоследовательности, если требуется, в силу (49) и локальной получаем существование вектора (,,, )() такого, что Первое уравнение в (55) может быть записано в виде Тогда, используя (59)–(61) и предположения а) и б), а также (58), получаем, что Следовательно, где множество в левой части (будучи суммой линейного попространства и полиэдрального конуса) является замкнутым конусом.
Воспользуясь второй строкой в (55), и предположением б), а также (58), заключаем, что Аналогично, применяя (59) и (60), выводим оценки Разделив (62)–(65) на и перейдя к пределу при, получаем, что Включение (66) означает, что существует вектор (, ) IR IR, удовлетворяющий и такой, что Тогда, с учетом (68), тройка (,, ) удовлетворяет системе Поскольку = 0, соотношения (67), (69), (70) противоречат некритичности множителя (, ). Это доказывает (57).
Для завершения доказательства, заметим, что для всякого, достаточно близкого к, и всякого решения ((), (), ()) системы (55), достаточно близкого к (,, ), имеем где последнее равенство справедливо в силу непрерывности отображения в точке (, ).
Так как (, ) есть множество решения линейной системы по лемме Хоффмана (см., например, [32, лемма 3.2.3]) получаем, что dist(((), ()), (, )) = (,, (), ()) + где были также использованы предположения а) и б). Вместе с (57), это дает утверждение теоремы.
Замечание 4. Применительно к каноническим возмущениям, теорема 2 демонстрирует, что некритичность множителя достаточна для выполнения свойства 1. На самом деле, оказывается, что она является также и необходимой для этого. Чтобы убедиться в этом, возьмем произвольную тройку (,, ) IR IR IR, удовлетворяющую системе (51)–(52) с некоторым (,, )(), и зафиксируем последовательность { }, соответствующую этому в определении контингентной производной (49). Тогда, как легко проверить, для всех достаточно больших тройка ( +, +, + ) удовлетворяет системе (44) с некоторыми = ( ), = ( ) и = ( ). Следовательно, если = 0, мы приходим к противоречию с (45).
Замечание 5. В отличие от случая, когда целевая функция и ограничения задачи оптимизации являются дважды непрерывно дифференцируемыми, строгая некритичность множителя, определенная в замечании 3, является строго более сильной, чем некритичность, введенная в определении 4, а значит, строго более сильной, чем свойство 1.
К примеру, положим = = 1, = 0, () = 1 (max{0, })2, () =. Тогда пара (, ) = (0, 0) является единственным решением системы (42). Непосредственно проверяется, что множитель является некритическим, и что свойство 1 для указанной пары (, ) выполняется. В самом деле, система (44) в данном примере имеет вид Отсюда следует, что либо = 0, и в этом случае удовлетворяет по крайней мере одному. Поэтому || + || || + 2||, что дает (45) с = IR IR и некоторой константой > (зависящей от выбора нормы в правой части (45)). Однако, множество ( ) (, ) = {0, 1} содержит ноль, и любой вектор 0 удовлетворяет системе (51)–(52) с = 0 и = 0.
С учетом замечаний 4 и 2 получаем следующий результат.
Следствие 1. Пусть функция : IR IR и отображения : IR IR и : IR IR дифференцируемы вблизи точки IR, причем их производные являются локально липшицевыми в этой точке. Пусть при этом является стационарной точкой задачи (41), а пара (, ) IR IR — отвечающим ей множителем Лагранжа.
Тогда следующие три свойства эквивалентны:
1. Свойство 1 (верхняя липшицева устойчивость решений системы ККТ при канонических возмущениях).
2. Свойство 2 (оценка расстояния для системы ККТ).
3. Некритичность множителя (, ) () (в смысле определения 4).
Глава Итерационные схемы для решения обобщенных уравнений Настоящая глава посвящена разработке и анализу итерационных схем решения обобщенных уравнений, т. е. включений вида где : IR IR — однозначное отображение (именуемое базовым или базой), а : IR 2IR — многозначное (иногда называемое полем). Получаемые здесь теоремы о сходимости этих итерационных схем станут основным средством анализа численных методов решения задач оптимизации с липшицевыми производными в главе 3.
Глава состоит из двух разделов. Итерационные схемы, рассматриваемые в первом разделе, предназначены для решения обобщенных уравнений с произвольной непрерывной базой и носят абстрактный характер. Во втором разделе речь пойдет о более специальной схеме для обобщенных уравнений, база которых удовлетворяет некоторым дополнительным условиям.
2.1. Абстрактные ньютоновские схемы Пусть есть множество произвольной природы. Рассмотрим следующий итерационный процесс. По текущей точке IR и текущему значению параметра будем генерировать очередную точку +1 как решение подзадачи где для любых и IR точечно-множественное отображение (,, ·) из IR в 2IR представляет собой аппроксимацию отображения вблизи. Свойства, которым должна удовлетворять эта аппроксимация, будут сформулированы ниже.
В следующих трех пунктах для представленного процесса будет установлена локальная сходимость к решению обобщенного уравнения (1) при различных наборах предположений.
2.1.1. Сходимость к сильно метрически регулярным решениям В настоящем разделе рассматривается вариант итерационной схемы из [27, раздел 6C], которая берет свое начало в [83].
Для каждого значения параметра и каждой точки IR определим множество то есть множество решения подзадачи (2) при = и =. Как бы близко точка ни лежала к искомому решению обобщенного уравнения (1), множество (3) может содержать далекие от этого решения точки. В связи с этим, для того, чтобы процесс (2) обладал локальной сходимостью, его итерацию приходится снабжать условием отбора решений подзадачи.
Условие такого рода называется условием локализации, и, как правило, состоит в ограничении расстояния между двумя последовательными итерациями. Простейший вариант условия локализации имеет вид где > 0 — фиксированное достаточно малое число.
Дополняя итерацию процесса (2) условием локализации (4), приходим к следующей схеме где { } — некоторая фиксированная последовательность значений параметра.
В сформулированном ниже результате о сходимости предполагается, что отображение является однозначным и аппроксимирует отображение в достаточно сильном смысле:
разность (·) (,, ·) должна быть локально липшицевой в искомом решении с малой константой липшица равномерно по параметру и точкам IR, близким к этому решению.
Теорема 1. Пусть отображение : IR IR непрерывно в окрестности точки IR, и пусть (·) — точечно-множественное отображение из IR в 2IR. Пусть точка IR является решением обобщенного уравнения (1). Пусть также заданы множество Предположим выполнение следующих свойств:
1) (сильная метрическая регулярность решения) Существует константа > 0 такая, что для всякого IR, достаточно близкого к 0, возмущенное обобщенное уравнение имеет вблизи точки единственное решение (), причем отображение (·) является локально липшицевым в точке 0 с константой.
2) (качество аппроксимации) Существует число > 0 такое, что б) существует функция : IR IR IR IR, удовлетворяющая условию Тогда найдутся числа > 0 и 0 > 0 такие, что для любого начального приближения 0 (, 0 ) и любой последовательности { } существует единственная последовательность { } IR, генерируемая схемой (5); эта последовательность сходится к решению, и для всех выполняются оценки В частности, скорость сходимости последовательности { } линейная. Более того, скорость сходимости является сверхлинейной, если (,,, +1 ) 0 при, и квадратичной, если Приведенное утверждение следует из доказываемой ниже теоремы 2 и из теоремы 1.4 в [28], которая по сути говорит об устойчивости свойства сильной метрической регулярности при однозначных возмущениях с малой константой Липшица.
Теорема 1 показывает, что сверхлинейная скорость сходимости достигается, если точность аппроксимации отображения возрастает с ростом. Общность ее постановки позволяет увидеть, что существует два источника увеличения точности аппроксимации: (,,, +1 ) может уменьшаться либо естественным образом по мере приближения и +1 к, либо искусственным, за счет управления параметром. К примеру, если отображение дифференцируемо вблизи, а его производная непрерывна в точке, то можно аппроксимировать его линеаризацией (, ) = () + ()( ), без каких-либо параметров. В этом случаe, по теореме о среднем, предположение 2) теоремы 1 выполняется с функцией (, 1, 2 ) = sup[0, 1] (1 + (1 )2 ) (), которая стремится к нулю при, 1 и 2, стремящихся к. При таком выборе аппроксимации итерационная схема (5) соответствует так называемому методу Джозефи–Ньютона, а теорема 1 включает в себя результат о сходимости этого метода, полученный в [53, 54].
Как будет показано ниже, метод множителей с линеаризованными ограничениями набирает требуемое качество аппроксимации естественным путем, в то время как в методе модифицированных функций Лагранжа сверхлинейная скорость сходимости достигается за счет стремления параметра штрафа к бесконечности.
Как показано в [42], если является локально липшицевым в решении обобщенного уравнения (1), сильная метрическая регулярность этого решения следует из так называемой -регулярности этого решения (см. с. 58).
В следующем пункте предположения 1) и 2) теоремы 1 будут ослаблены, но «не бесплатно»: разрешимость подзадач итерационной схемы придется требовать явно. Кроме того, нельзя будет гарантировать единственность траектории, которую генерирует схема. Условие регулярности решения будет далее ослаблено в пункте 2.1.3. В частности, искомое решение там не будет предполагаться изолированным. Однако это потребует использования более сильного условия локализации, чем (4).
2.1.2. Сходимость к полуустойчивым решениям Следующий результат представляет собой развитие анализа из [17].
Теорема 2. Пусть отображение : IR IR является непрерывным в окрестности точки IR, и пусть (·) — точечно-множественное отображение из IR в 2IR.
Пусть IR является решением обобщенного уравнения (1), и пусть задано точечномножественное отображение из IR IR в 2IR, где — заданное множество.
Предположим выполнение следующих свойств:
1) (полуустойчивость решения) Существует число > 0 такое, что для любого IR всякое решение () возмущенного обобщенного уравнения (6), достаточно близкое к, удовлетворяет оценке 2) (качество аппроксимации) Существуют число > 0 и функция : IR IR IR+ 3) (разрешимость подзадач) Для любого > 0 существует > 0 такое, что Тогда найдутся числа > 0 и 0 > 0 такие, что для любого начального приближения 0 (, 0 ) и любой последовательности значений параметра { } итерационная схема (5) (при произвольном выборе точки, удовлетворяющей (5), на каждой итерации) генерирует траекторию { } IR ; любая такая траектория сходится к, и для всех выполнено:
В частности, скорость сходимости последовательности { } линейная. Кроме того, скорость сходимости является сверхлинейной, если (,, +1 ) 0 при, и квадратичной, если Если же в дополнение к условиям теоремы для всякого достаточно малого > 0 существует > 0 такое, что множество в (10) содержит ровно один элемент, то числа и 0 можно выбрать так, чтобы для любых 0 (, 0 ) и { } последовательность { }, удовлетворяющая (5), была единственной.
Доказательство. Согласно (3), для всякого и всякого IR любая точка (, ) удовлетворяет обобщенному уравнению (6) с некоторым и, кроме того, в силу предположения 2), существует число > 0 такое, что если, (, ). Кроме того, по предположению 1), уменьшая > 0 при необходимости, можно гарантировать, что для всех, (, ) и (, ) (, ) выполняются неравенства С учетом (8), из последней формулы следует оценка Согласно предположению 3), существуют чила, (0, /3] такие, что выполнено (10).
Положим = +. Тогда для всех (, ) и (, ) имеем а значит, (10) влечет за собой соотношение Более того, для любых (, ) и (, ) выполнено а значит, в силу (13), оценки выполняются для любого, любого (, ) и любого (, ) (, ), где, согласно (8), 2/(1 ) < 1.
Соотношения (14) и (15) очевидно влекут за собой требуемое с 0 =. В частности, если и выбрать таким образом, чтобы один элемент для любого и любого (, ), можно дополнительно гарантировать, что множество в (14) содержит ровно один элемент для всех таких и.
Если убрать слагаемое из правой части неравенства (9), в условиях доказанной теоремы можно заменить ограничение < 1/3 на < 1/2 и убрать множитель 2 из правой части формулы (11). С учетом этого, теорема 1 может быть получена как следствие теоремы 2.
Из доказательства теоремы 2 видно, что предположение 2) может быть несколько ослаблено: (8) можно заменить на а вместо (9) достаточно предположить, что оценка учетом этого, теорема 2 покрывает результат из [51, теорема 2.1] о сходимости возмущенного метода Джозефи–Ньютона, который соответствует выбору (, ) = () + ()( ) + (, ), где точечно-множественное отображение из IR IR во множество подмножеств IR описывает неточность подзадачи метода.
Отметим, что в отличие от теоремы 1, более слабые предположения теоремы 2, вообще говоря, не обеспечивают единственности траектории итерационной схемы (5).
2.1.3. Случай возможно неизолированных решений В этом пункте будет получено обобщение итерационной схемы из [36].
В случае, когда искомое решение может быть неизолированным, «параметр локализации» в (4) приходится стремить к нулю по мере увеличения номера итерации, причем со специальной скоростью. А именно, для произвольного, но фиксированного числа > зададим множество где есть множество решений обобщенного уравнения (1), и рассмотрим итерационную схему Теорема 3. Пусть отображение : IR IR непрерывно в окрестности точки IR, и пусть (·) — точечно-множественное отображение из IR в 2IR. Пусть — множество решений обобщенного уравнения (1), и пускай. Предположим также, что множество (, ) является замкнутым для любого достаточно малого > 0.
Пусть — точечно множественное отображение из IR IR в 2IR.
Предположим, что для некоторого числа > 0 выполняются следующие свойства:
1) (верхне-липшицево поведение решения при канонических возмущениях) Существует число > 0 такое, что для любого IR всякое решение () возмущенного обобщенного уравнения (6), достаточно близкое к, удовлетворяет оценке 2) (качество аппроксимации) Существуют число > 0 и функция : IR IR IR+ справедлива для любых и (, ) IR IR, удовлетворяющих условиям 3) (разрешимость подзадач) Для любого и любого IR, достаточно близкого к, множество (, ), опредленное в (3), (16), непусто.
Тогда для любого > 0 найдется 0 > 0 такое, что для любого начального приближения 0 (, 0 ) и любой последовательности { } итерационная схема (17) (при произвольном выборе точки, удовлетворяющей (17), на итерациях) генерирует траекторию { } (, ); любая такая траектория сходится к некоторой точке *, и при всех выполняются следующие оценки:
В частности, скорости сходимости последовательности { } к * и последовательности {dist(, )} к нулю являются сверхлинейными, если (,, +1 ) 0 при. Более того, обе эти скорости являются квадратичными, если (,, +1 ) = (dist(, )).
Доказательство. Согласно (3) и (16), для любых и IR всякая точка (, ) является решением обобщенного уравнения (6) с некоторым IR, удовлетворяющим (12), и, кроме того, если (, ), то в силу предположения 2) справедлива оценка Поскольку для любого > 0 за счет близости к можно обеспечить выполнение неравенства <, из предположений 1) и 3) следует, что для любого > 0 существуют числа (0, min{, }] и > 0 такие, что для всех верны соотношения и при этом множество (, 2) замкнуто. Положим В силу (18) 0 > 0. Теперь докажем по индукции, что если 0 (, 0 ), то для любой последовательности { } итерационная схема (17) генерирует последовательность { } IR вне зависимости от выбора точки +1 (, ) на каждой итерации, и что для любой такой последовательности верно, что (, ) (, ) для всех.
база индукции выполняется: 0 (, ). Предположим теперь, что точки IR, = 1,...,, таковы, что +1 (, ), причем для любой такой точки +1 справедливы соотношения Тогда, принимая во внимание неравенство в (16), получаем Следовательно, где последнее равенство следует из (23). Таким образом, +1 (, ), и шаг индукции доказан.
Далее, в силу (18) и (22), а также только что доказанного утверждения, для любого 0 (, 0 ), любой последовательности { } и любой последовательности { } IR, удовлетворяющей (17), справедливы соотношения В частности, в силу (18) последовательность {dist(, )} сходится к нулю, и выполняется оценка (21).
Аналогично (24), легко установить оценку где правая часть стремится к нулю при. Следовательно, последовательность { } является фундаментальной, а значит, она сходится к некоторой точке * IR. Более того, пользуясь сходимостью последовательности {dist(, )} к нулю, включением { } (, ), а также замкнутостью множества (, 2), заключаем, что *.
Для того, чтобы установить скорость сходимости последовательности { }, задействуя (25) и (26), получаем Переходя к пределу при, имеем то есть выполнена оценка (20).
Из доказательства теоремы 3 видно, что предположение 2) может быть ослаблено: условие (18) можно заменить на а выполнение условия (19) достаточно предполагать лишь для () + ((,, )) 2.2. Полугладкий метод Джозефи–Ньютона В этом разделе будет рассмотрен еще один метод решения обобщенных уравнений. В отличие от итерационных схем, изученных в предыдущем разделе, этот метод является менее абстрактным. При этом он налагает на базу обобщенного уравнения более сильные ограничения гладкости, чем непрерывность вблизи искомого решения. А именно, предполагается, что отображение является полугладким в этом решении.
Определение 1. Отображение : IR IR называется полугладким [32, раздел 7.4] в точке IR, если оно является локально липшицевым в, дифференцируемым в по любому направлению и удовлетворяет условию Если выполняется более сильное условие отображение называют сильно полугладким в точке.
Отображение называется полугладким, если оно полугладко в каждой точке своей области определения.
Напомним, что итерация метода Джозефи–Ньютона для решения уравнения (1) [17, 51, 53, 54] состоит в решении (частично) линеаризованного обобщенного уравнения где IR — текущее приближение к искомому решению уравнения (1), а IR — некоторая матрица. В классическом варианте метода матрица полагается равной ( ), что, конечно же, предполагает дифференцируемость отображения вблизи искомого решения. Заметим, что применительно к обычным нелинейным уравнениям, т. е. если (·) = {0}, такой способ выбора матрицы приводит к классическому методу Ньютона.
Поскольку полугладкость отображения не влечет за собой его дифференцируемость, классический метод Джозефи–Ньютона к обобщенным уравнениям с полугладкой базой не применим. Однако он приводит к мысли выбирать матрицу в (27) из обобщенных дифференциальных объектов, которые служат заменой производной для полугладких отображений. Один из таких вариантов метода Джозефи–Ньютона и будет изучен в настоящем разделе. Его итерация будет определена позже. Пока отметим лишь, что она обобщает, с одной стороны, итерацию классического метода Джозефи–Ньютона [17, 51, 53, 54] на случай негладкой базы, а с другой — итерацию так называемого полугладкого метода Ньютона для нелинейных уравнений [60, 61, 78, 75] на случай обобщенных уравнений.
В теории классического метода Джозефи–Ньютона важную роль играет понятие сильной регулярности решения обобщенного уравнения, введенное в [81] (хотя, как следует отметить, в настоящий момент сходимость классического метода Джозефи–Ньютона установлена в более слабых предположениях [17]). А именно, решение обобщенного уравнения (1) называется сильно регулярным, если для любого IR, достаточно близкого к 0, возмущенное (частично) линеаризованное обобщенное уравнение имеет вблизи единственное решение (), и при этом отображение (·) является локально липшицевым в точке 0. Ясно, что точка является сильно регулярным решением обобщенного уравнения (1) тогда и только тогда, когда она является сильно регулярным решением линеаризации этого обобщенного уравнения Характеризации свойства сильной регулярности для обобщенных уравнений в терминах обобщенных дифференциальных объектов были получены в [66] (см. также [67]).
Введем в рассмотрение обобщение свойства сильной регулярности на случай, когда отображение может быть недифференцируемым.
Определение 2. Решение IR обобщенного уравнения (1) называется сильно регулярным относительно множества матриц IR, если для любой матрицы точка является сильно регулярным решением обобщенного уравнения т. е. для любой матрицы и любого IR, достаточно близкого 0, возмущенное частично линеаризованное уравнение имеет вблизи единственное решение (), и отображение (·) является локально липшицевым в точке 0.
Когда = () ( = ()), будем говорить, что решение является регулярным (-регулярным) решением обобщенного уравнения (1).
Очевидно, что введенное понятие сильной регулярности обобщает следующие широко известные свойства: сильную регулярность в смысле [81], соответствующую случаю, когда отображение дифференцируемо, а = { ()}, и -регулярность [73] и -регулярность [77] решения обычного уравнения, которые соответствуют случаю, когда (·) = {0}, а = () и, соответственно, = ().
Напомним, что, как показано в [42], если отображение является локально липшицевым в решении обобщенного уравнения (1), -регулярность этого решения влечет за собой его сильную метрическую регулярность (см. c. 50).
Следующий результат об устойчивости свойства сильной регулярности при малых липшицевых возмущениях следует, к примеру, из [28, теорема 1.4].
Предложение 1. Пусть для заданного отображения : IR IR, матрицы IR и точечно-множественного отображения из IR в 2IR точка является сильно регулярным решением обобщенного уравнения (28).
Тогда для любой фиксированной окрестности точки и любой достаточно малой константы 0 существуют число > 0 и окрестности точки и точки 0 такие, что для всякого отображения : IR IR, липшицевого на с константой Липшица, и любого () + обобщенное уравнение имеет в единственное решение (), и отображение (·) удовлетворяет условию Липшица на () + с константой.
Пользуясь предложением 1, докажем разрешимость возмущенного линеаризованного уравнения для всех точек, достаточно близких к сильно регулярному решению исходного уравнения (1), и всех матриц, достаточно близких ко множеству, по отношению к которому это решение сильно регулярно.
Предложение 2. Пусть отображение : IR IR является непрерывным в точке IR. Пусть для заданного точечно-множественного отображения из IR в 2IR точка является сильно регулярным решением обобщенного уравнения (1) относительно компактного множества IR.
Тогда существуют число > 0, число > 0 и окрестности и точки, а также окрестность точки 0 такие, что для любого, любой матрицы IR, удовлетворяющей условию и любого обобщенное уравнение имеет в единственное решение (), причем отображение (·) удовлетворяет условию Липшица на с константой.
Доказательство. Зафиксируем произвольную матрицу. Для любых IR и IR определим отображение : IR IR, Заметим, что для всякого фиксированного > 0 отображение удовлетворяет условию Липшица на IR с константой, если матрица лежит достаточно близко к. Кроме того, () = () () ( ) стремится к 0 при. Тогда, применяя предложение с = IR, получаем существование чисел > 0, > 0 и окрестностей и точки, а также окрестности точки 0 таких, что для любого и любой матрицы IR, удовлетворяющей условию <, при каждом обобщенное уравнение имеет в единственное решение (), и при этом отображение (·) удовлетворяет условию Липшица на с константой. Подставляя (31) в (32), видим, что последнее уравнение совпадает с (30).
Рассмотрим теперь для каждой матрицы открытый шар в пространстве IR с центром в радиуса, где число для каждой матрицы определяется в соответствии с проведенным рассуждением. Совокупность указанных шаров образует открытое покрытие компакта, из которого можно выделить конечное подпокрытие. Теперь переопределим > 0 таким образом, чтобы любая матрица IR, удовлетворяющяя (29), принадлежала этому конечному подпокрытию. Далее, пусть > 0 — максимум из констант Липшица, соответствующих шарам подпокрытия, а окрестности, и являются пересечением окрестностей, соответствующих этим шарам. При необходимости сужая окрестности и для того, чтобы гарантировать, что для любого, любой матрицы IR, удовлетворяющей (29), и всякого решение () уравнения (30) принадлежит, получаем требуемое.
Наряду с полугладким методом Джозефи–Ньютона, итерация которого задается формулой (27) с ( ), будем рассматривать его возмущенную версию. Ее итерация заключается в следующем: по текущему приближению к решению уравнения IR следующее приближение +1 ищется как решение обобщенного уравнения с некоторой ( ), где IR есть возмущение итерации исходного метода. Возникновение возмущения, к примеру, может быть вызвано неточным решением подзадачи ( ) + ( ) + () 0. Еще один пример возмущений связан с квазиньютоновскими вариантами полугладкого метода Джозефи–Ньютона, итерация которых может быть записана в общем виде ( ) + ( ) + () 0, где матрица ( ). В этом случае Начнем со следующего апостериорного результата о сверхлинейной сходимости алгоритма (33), т. е. результата в предположении о наличии сходимости как таковой.
Предложение 3. Пусть отображение : IR IR полугладко в точке IR.
Пусть является решением обобщенного уравнения (1), сильно регулярным относительно замкнутого множества (). Пусть последовательность { } IR сходится к, и при этом точка +1 удовлетворяет включению (33) при всех = 0, 1,... с некоторой матрицей ( ) и возмущением IR такими, что Тогда скорость сходимости последовательности { } является сверхлинейной. Более того, скорость сходимости является квадратичной, если отображение сильно полугладко в точке, и Доказательство. Определим > 0, > 0,, и в соответствии с предложением 2 при =. Тогда для любого, любой матрицы ( ), удовлетворяющей условию dist(, ) <, и любого обобщенное уравнение имеет в единственное решение (), которое зависит от на липшицевым образом с константой. Для каждого положим Заметим, что в силу полугладкости отображения в точке Кроме того, с учетом (38) имеем:
Так как последовательность { } сходится к, и выполнены соотношения (34), (35) и (39), для всех достаточно больших верно, что, +1, dist(, ) <,, и. Следовательно, согласно предложению 2, +1 является единственным в решением обобщенного уравнения (37) с =, т. е. +1 = ( ), в то время как в силу (40) является единственным в решением обобщенного уравнения (37) с =, а значит, = ( ). Тогда где последняя оценка следует из (35) и (39).
Тот факт, что из (41) следует сверхлинейная скорость сходимости, доказывается стандартным образом, см., например, [51, предложение 2.1]. Остается заметить, что если отображение является сильно полугладким в точке, то для вектора, определенного согласно (38), выполняется оценка Эта оценка вместе с (36) и с неравенством в (41) влечет за собой квадратичную скорость сходимости.
Из предложения 3 непосредственно следует результат типа Дениса–Морэ для метода Джозефи–Ньютона применительно к обобщенным уравнениям с полугладкой базой. А именно, пусть имеется последовательность матриц { } IR. Пусть по текущему приближению IR к решению обобщенного уравнения (1) следующее приближение +1 вычисляется как решение обобщенного уравнения (27). Кроме того, предположим, что последовательность { } удовлетворяет следующему условию типа Дениса–Морэ:
Имеет место следующий апостериорный результат.
Теорема 4. Пусть отображение : IR IR является полугладким в точке IR.
Пусть — решение обобщенного уравнения (1), сильно регулярное относительно некоторого замкнутого множества (). Пусть имеется последовательность матриц { } IR, и пусть последовательность { } IR сходится к, и при этом для всех достаточно больших точка +1 удовлетворяет включению (27), и существует матрица ( ) такая, что Тогда скорость сходимости последовательности { } сверхлинейная.
Доказательство. Для каждого положим Тогда условие (44) влечет за собой (35). С учетом (43), требуемый результат немедленно следует из предложения 3.
Предположение о том, что для любого достаточно большого найдется матрица ( ), удовлетворяющая (44), эквивалентно условию (42). Если точка является регулярным решением уравнения (1), то теорему 4 можно применить с = (), причем в этом случае (43) выполняется автоматически вне зависимости от выбора ( ), в следствие полунепрерывности дифференциала Кларка сверху. Также теорему 4 можно применять с = (), предполагая -регулярность решения.
Наконец, перейдем к априорному локальному анализу полугладкого метода Джозефи– Ньютона, т. е. к установлению достаточных условий для сходимости этого метода.
Теорема 5. Пусть отображение : IR IR полугладко в точке IR. Пусть является решением уравнения (1), сильно регулярным относительно замкнутого множества (). Пусть — точечно-множественное отображение из IR во множество подмножеств IR такое, что и для любого > 0 существует окрестность точки такая, что Тогда найдется число > 0 такое, что для любого начального приближения 0 IR, достаточно близкого к решению, при всех = 0, 1,... и при произвольном выборе матрицы ( ) существует единственное решение +1 подзадачи полугладкого метода Джозефи–Ньютона (27), удовлетворяющее условию при этом последовательность { } сходится к, и скорость сходимости является сверхлинейной. Более того, скорость сходимости является квадратичной, если отображение сильно полугладко в точке.
Доказательство. Определим > 0, > 0,, и в соответствии с предложением 2 при =. Пусть, кроме того, окрестность такова, что условие (46) выполняется с = и с указанным.
Тогда по предложению 2 для любых и ( ) и всякого обобщенное уравнение имеет в единственное решение (), которое зависит от на липшицевым образом с константой. В частности, обобщенное уравнение (27) имеет в единственное решение +1 = (0).
Определив согласно (38) и используя (45) и полугладкость отображения в точке заключаем, что выполнено (39), и При необходимости сужая окрестность, в силу (39) получаем, что, если, а значит, точка является единственным решением уравнения (48) с =, т. е. = ( ).
Тогда где последняя оценка следует из (39).
Далее, из (49) следует, что для любого (0, 1) существует число > 0 такое, что (, /2), (, 3/2), и для любого (, /2) выполняется неравенство откуда следует, что +1 (, /2). Тогда и значит, +1 является решением (27), удовлетворяющим (47). Более того, для любой точки +1 IR, удовлетворяющей (47), справедливы соотношения и значит, +1, откуда следует, что +1 является решением обобщенного уравнения (27) тогда и только тогда, когда +1 = (0). Таким образом, (0) — единственное решение обобщенного уравнения (27), удовлетворяющее условию (47).
Таким образом, из включения 0 (, /2) следует, что последовательность { } однозначно определена (при условии, что способ выбора матрицы ( ) для всех является фиксированным) и целиком содержится в (, /2). Тогда соотношение (50) влечет за собой сходимость этой последовательности к точке. Оценки скорости сходимости следуют из предложения 3.
Замечание 1. Теорема 5 обобщает результат о сходимости полугладкого метода Ньютона для обычных нелинейных уравнений [75, 78]. В самом деле, в качестве точечномножественного отображения (·) можно взять (·) или (·). В первом случае теорема применима с = () в предположении -регулярности решения, в то время как во втором случае ее можно применить с = (), предполагая -регулярность решения.
Конечно, возможны и другие варианты выбора (·) (к примеру, связанные со специальной структурой конкретной задачи).
Замечание 2. Для классического метода Джозефи–Ньютона в [17] был доказан более тонкий результат о сходимости, в котором предполагается полуустойчивость и хемиустойчивость (англ. hemistability) искомого решения. Комбинация этих двух свойств, вообще говоря, слабее сильной регулярности. Заметим, однако, что в отличие от результатов теоремы локальная единственность решения подзадачи метода не имеет места в этих более слабых предположениях.
Глава Методы оптимизации для задач с липшицевыми производными В данной главе предлагается ряд численных методов для решения задач оптимизации с лишпшицевыми производными. Для этих методов устанавливаются результаты о локальной сходимости и скорости сходимости в различных предположениях. В качестве инструментов анализа при этом выступают итерационные схемы, представленные в предыдущей главе.
Глава состоит из трех разделов. Первый раздел посвящен так называемому методу множителей или методу модифицированных функций Лагранжа. Во втором разделе будет рассмотрен метод множителей с линеаризованными ограничениями. Нужно отметить, что итерации как первого, так и второго из этих методов не используют вторые производные целевой функции и ограничений задачи, в связи с чем указанные методы являются естественными кандидатами на роль методов решения задач с липшицевыми производными.
Однако имеющиеся в литературе теории локальной сходимости этих методов предполагают существование вторых производных у целевой функции и ограничений решаемой задачи. В настоящей главе эти теории будут обобщены на задачи оптимизации с липшицевыми производными. Заметим, что такое обобщение зачастую является весьма нетривиальным.
Наконец, в третьем разделе главы речь пойдет о полугладком методе последовательного квадратичного программирования. В контексте этого метода нас будут интересовать прежде всего условия, характеризующие его прямую сверхлинейную сходимость.
3.1. Метод модифицированных функций Лагранжа Первыми работами по методу модифицированных функций Лагранжа или методу множителей являются [40] и [74]. Впоследствии метод модифицированных функций изучался в [13, 14, 33]. Другими ключевыми работами, посвященными этому методу, являются [11, 14, 22]. Отметим, что метод модифицированных функций Лагранжа лежит в основе таких успешных солверов, как LANCELOT [62] и ALGENCAN [10]. Теория локальной и глобальной сходимости этого метода до сих пор остается предметом активных исследований, см., например, [11, 33] и ссылки на литературу в этих работах. Традиционно локальная сходимость метода модифицированных функций изучалась в предположении о двукратной дифференцируемости целевой функции и ограничений решаемой задачи. В данном разделе существующие результаты о локальной сходимости этого метода распространяются на задачи оптимизации с липшицевыми производными. Кроме того, получаются новые результаты о его локальной сходимости в одном лишь предположении о некртичности множителя.
3.1.1. Сходимость при достаточном условии второго порядка оптимальности Будем рассматривать задачу оптимизации в которой целевая функция : IR IR и отображения : IR IR и : IR IR дифференцируемы. Напомним, что система Каруша–Куна–Таккера задачи (1) имеет вид где : IR IR IR IR — функция Лагранжа задачи (1), Заметим, что система Каруша–Куна–Таккера (2) эквивалентна обобщенному уравнению а в качестве точечно-множественного отображения из IR во множество подмножеств IR используется где () — нормальный конус ко множеству в точке.
Модифицированной функцией Лагранжа : IR IR IR IR задачи (1) называется функция где максимум берется покомпонентно. Параметр в определении модифицированной функции Лагранжа называется обратным параметром штрафа.
Итерация метода модифицированных функций Лагранжа состоит в следующем. По текущему двойственному приближению (, ) IR IR, текущему значению обратного приближение (+1, +1, +1 ) IR IR IR генерируется следующим образом: точка +1 должна удовлетворять условию а пара (+1, +1 ) вычисляется по формулам Первый результат о сходимости метода модифицированных функций из представленных в данном пункте касается точной версии метода, которая соответствует выбору = для всех. Таким образом, точный метод модифицированных функций генерирует прямое приближение +1 как стационарную точку задачи оптимизации без ограничений и имеют место равенства Отсюда следует, что итерация точного метода модифицированных функций может быть записана в виде (2.2) с : (IR+ {0}) IR IR IR, где = ++, = (,, ), а точечно-множественное отображение определено согласно (6). Легко видеть, что (,, ) = (), и а значит, откуда следует выполнение условия (2.7) с (,, 1, 2 ) = и 1 = (1, 1, 1 ), 2 = локальной сходимости и скорости сходимости будет напрямую следовать из теоремы 2.1, если предположить сильную метрическую регулярность решения = (,, ) IR IR IR системы ККТ (2).
Как уже отмечалось, согласно [42], сильная метрическая регулярность решения обобщенного уравнения (4) следует из -регулярности (см. с. 58) этого решения. Займемся получением достаточных условий для -регулярности в контексте систем Каруша–Куна– Таккера.
Прежде всего напомним, что выполнение в точке IR условия линейной независимости состоит в линейной независимости градиентов (), = 1,..., и (), (), где множество () было введено в (1.11) и представляет собой множество индексов активных ограничений-неравенств в точке. Помимо (), ниже будут использоваться множества + (, ) и 0 (, ), которые были введены в (1.11) для любых IR и IR.
Для задач оптимизации, целевая функция и ограничения которых являются дважды непрерывно дифференцируемыми, характеризация -регулярности (которая для таких задач эквивалентна сильной регулярности) была получена в [81] (достаточность) и в [20] (необходимость). Оказывается, что из этих результатов несложно получить условия, гарантирующие -регулярность в случае задач с липшицевыми производными.
Предложение 1. Пусть функция : IR IR и отображения : IR IR и : IR IR дифференцируемы в точке IR. Пусть — стационарная точка задачи (1), и пусть Тогда, если в точке выполнено условие линейной независимости, а множитель (, ) удовлетворяет условию где то тройка = (,, ) является сильно регулярным решением обобщенного уравнения с (·) и (·), определенными согласно (5) и, соответственно, (6).
«