[ «НЬЮТОНОВСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ С НЕРЕГУЛЯРНЫМИ ОГРАНИЧЕНИЯМИ ...»
Московский государственный университет им. М. В. Ломоносова
Факультет вычислительной математики и кибернетики
Кафедра исследования операций
На правах рукописи
Усков Евгений Иванович
НЬЮТОНОВСКИЕ МЕТОДЫ
РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ
С НЕРЕГУЛЯРНЫМИ ОГРАНИЧЕНИЯМИ
Специальность 01.01.09 — дискретная математика и математическая кибернетика Диссертация на соискание учёной степени кандидата физико-математических наук
Научный руководитель:
профессор, д.ф.-м.н.
Измаилов Алексей Феридович Москва Оглавление Введение Список основных обозначений Глава 1. Эффект притяжения к критическим множителям Лагранжа 1.1. Критические множители Лагранжа......................... 1.2. Обоснование эффекта притяжения для метода Ньютона–Лагранжа...... 1.2.1. Одномерные задачи.............................. 1.2.2. Чисто квадратичные задачи......................... 1.3. Локальная двойственная стабилизация....................... 1.3.1. Стабилизированный метод последовательного квадратичного программирования................................... 1.3.2. Метод модифицированных функций Лагранжа.............. Глава 2. Метод модифицированных функций Лагранжа 2.1. Результаты о глобальной сходимости........................ 2.1.1. Общая теория глобальной сходимости................... 2.1.2. Глобальная сходимость для задач оптимизации с комплементарными ограничениями................................. 2.2. Ускорение финальной фазы............................. Глава 3. Глобализация сходимости стабилизированного метода последовательного квадратичного программирования 3.1. Гибридные подходы к глобализации сходимости.................. 3.2. Глобализация сходимости с помощью модифицированных функций Лагранжа 3.2.1. Алгоритм и его теоретические свойства.................. 3.2.2. Связь с прямо-двойственным алгоритмом последовательного квадратичного программирования.......................... 3.3. Глобализация сходимости с помощью точных гладких штрафных функций.. 3.3.1. Глобализованный алгоритм.......................... 3.3.2. Анализ скорости сходимости......................... Глава 4. Метод последовательного квадратичного программирования, стабилизированный вдоль подпространства 4.1. Описание метода и результаты о локальной сходимости............. 4.1.1. Асимптотически исчезающая стабилизация................ 4.1.2. Неисчезающая стабилизация......................... 4.2. Аппроксимация подпространства вырожденности................. 4.3. Глобализованный алгоритм.............................. Приложение А. Численные результаты для метода модифицированных функций Лагранжа А.1. Сравнение с другими алгоритмами......................... А.2. Эксперимент с правилами для параметра штрафа: критические множители и скорость сходимости.................................. А.3. Эксперимент с правилами для параметра штрафа: общая эффективность... А.4. Эксперимент с ускорителями............................. Приложение Б. Численные результаты для стабилизированного метода последовательного квадратичного программирования Б.1. Гибридная глобализация сходимости........................ Б.2. Глобализация сходимости с помощью модифицированных функций Лагранжа Б.3. Глобализация сходимости с помощью точных гладких штрафных функций.. Приложение В. Численные результаты для метода последовательного квадратичного программирования, стабилизированного вдоль подпространства Введение В существующей литературе по теории и численным методам оптимизации основное внимание традиционно уделяется задачам, в решениях которых выполнены так называемые условия регулярности ограничений. Такие задачи достаточно подробно изучены, в частности, разработаны эффективные численные методы отыскания их решений, для которых обоснована глобальная сходимость и сверхлинейная скорость сходимости.
Вместе с тем, большой интерес представляют задачи, в решениях которых условия регулярности ограничений могут нарушаться, и их изучению посвящена данная работа. С такими задачами связан ряд серьезных теоретических трудностей (например, не гарантируется устойчивость решения по отношению к малым возмущениям входных данных). Более того, численное отыскание решений в таких задачах весьма проблематично и требует специальных подходов. В частности, многие традиционные методы оптимизации обычно демонстрируют невысокую эффективность на таких задачах.
Недавно было показано, что основной причиной низкой эффективности ньютоновских методов на нерегулярных задачах является эффект притяжения двойственных траекторий к так называемым критическим множителям Лагранжа. Эти множители обычно образуют тощее подмножество множества всех множителей Лагранжа, однако именно к ним обычно сходятся двойственные траектории ньютоновских методов, причем скорость сходимости прямой траектории в таких случаях оказывается в лучшем случае линейной. На сегодняшний день описанный эффект изучен весьма мало, и поэтому ему будет уделено значительное внимание в данной работе.
Отметим, что в недавнем прошлом активно разрабатывались эффективные и устойчивые методы поиска особых решений общих систем нелинейных уравнений (см. [14], а также более поздние работы [3, 5–7]). К сожалению, эффективное использование таких методов для решения нерегулярных задач оптимизации (например, путем применения их к системе Лагранжа или системе Ф. Джона) возможно только в очень обременительных предположениях, в связи с чем такой подход имеет весьма ограниченную область применения [15].
Еще одна причина интереса к нерегулярным задачам, помимо связанных с ними теоретических и практических трудностей, заключается в наличии важных практических приложений. Одним из таких приложений являются задачи оптимизации с распадающимися ограничениями. Такое название связано с тем, что допустимое множество задач этого класса состоит из частей (кусков или ветвей), каждая из которых задается «обычными» ограничениями. В большинстве случаев такие задачи являются нерегулярными, несмотря на то, что ограничения, задающие каждую ветвь, обычно являются регулярными.
Среди задач оптимизации с распадающимися ограничениями наиболее важны задачи оптимизации с комплементарными ограничениями (MPCC, от англ. Mathematical program with complementarity constraints). Задачи этого класса в общей форме имеют следующий вид:
Одним из приложений MPCC являются так называемые двухуровневые задачи оптимизации или задачи двухуровневого программирования, частный случай которых был впервые рассмотрен Штакельбергом в 1934 г. при исследовании иерархических рыночных структур.
В данный класс входят задачи оптимизации, в которых одно из ограничений описывается с помощью другой оптимизационной задачи, называемой задачей нижнего уровня. Таким образом, задачи данного класса имеют двухуровневую иерархическую структуру. Один из способов сведения таких задач к одноуровневым задачам оптимизации заключается в замене задачи нижнего уровня на ее систему Каруша–Куна–Таккера (ККТ). В этом случае получим MPCC, которая в некоторых предположениях будет эквивалентна исходной задаче.
Более подробную информацию о двухуровневых задачах можно найти в [43, 82].
Другим важным приложением MPCC являются задачи нахождения оптимальной формы упругопластичных балочных (стержневых) конструкций [49], относящиеся к так называемой оптимизации форм. В качестве примера рассмотрим следующую задачу. Необходимо спроектировать стержневую структуру таким образом, чтобы она была устойчивой к прилагаемым силам, и чтобы смещения и пластические деформации (если имеются) были в допустимых пределах. При этом геометрическая форма конструкции (т. е. взаимное расположение стержней) задана, а переменными являются площади поперечных сечений стержней. Чем больше площади поперечных сечений, тем прочнее конструкция, но тем больше ее размеры и масса. Возможная постановка задачи звучит следующим образом: необходимо минимизировать некоторую целевую функцию (отражающую размеры или массу) при условии, что конструкция будет удовлетворять указанным выше ограничениям.
При формализации данной задачи оптимизации могут естественным образом возникать комплементарные ограничения. Пластические деформации в таких моделях можно описывать в терминах так называемых пластических множителей IR и значений функции текучести IR, где — количество функций текучести (см., например, [22, 23]). Если наблюдается текучесть (т. е. = 0 для некоторого ), то может произойти пластическая деформация (т. е. 0). Если же выполнено условие упругости (т. е. > 0), то пластические деформации невозможны (т. е. = 0). Таким образом, описанные ограничения можно записать в виде следующего условия комплементарности:
Более подробное исследование задач данного вида можно найти в работе [49].
Существует множество других приложений MPCC. Некоторые из них представлены в [82, 89].
Другой важный подкласс задач оптимизации с распадающимися ограничениями образуют задачи оптимизации с исчезающими ограничениями (MPVC, от англ. Mathematical program with vanishing constraints). Задачи этого класса имеют следующий вид:
Наиболее известным приложением MPVC являются задачи нахождения оптимального дизайна топологий механических конструкций [28, 29]. Целью такого дизайна является нахождение оптимальной геометрической формы структуры, которая включает в себя как взаимное расположение стержней, так и площади их поперечных сечений. Таким образом, задачи данного класса существенно отличаются от задач оптимизации форм, в которых взаимное расположение элементов предполагается заданным, а оптимизируются только площади поперечных сечений стержней.
Рассмотрим пример нахождения оптимального дизайна жесткой (упругой) конструкции с использованием так называемого подхода «базовой конструкции» (см. [29]). Введем множество потенциальных стержней, причем для каждого потенциального стержня параметры материалов будем предполагать заданными. Для обозначения площади поперечного сечения стержня с номером введем переменную 0. Положительное значение означает существование стержня, а значение = 0 — отсутствие. Как и в задачах оптимизации форм, обычно оптимизируется вес или размеры конструкции, а ограничения состоят в том, что структура должна быть устойчива к заданному внешнему воздействию, а деформации должны укладываться в допустимые пределы.
Одним из возможных и естественных способов формализации данной задачи является MPVC. Обозначим через количество незакрепленных узлов стержневой структуры и введем вектор IR узловых смещений структуры под действием приложенной силы. Ограничения на напряжения и на продольный изгиб потенциального стержня с номером можно представить в виде (, ) 0, где — некоторая функция. Очевидно, такие ограничения имеют смысл только в случае, если > 0. Если же = 0, то такие ограничения должны исчезать из задачи. Если функции, задающие эти ограничения, могут быть непрерывно продолжены на случай = 0 (в этом случае они могут не иметь физического смысла), то ограничения для стержня с номером можно представить в виде В результате получаем задачу оптимизации с исчезающими ограничениями.
Существует другой подход к нахождению оптимального дизайна топологий, который также приводит к MPVC (см. [28]). Разобьем область, в которой должна располагаться структура, на конечное число частей. В каждую из получившихся частей можно распределить некоторое количество материала 0. Чем больше материала будет выделено для некоторой области, тем прочнее будет конструкция в этом месте. Однако, выделение дополнительного материала будет приводить к утяжелению конструкции. Так же, как и в предыдущем подходе, ограничения для каждой области имеют смысл только если > 0, в противном случае они должны исчезать. Таким образом, вновь приходим к MPVC. Более подробно данные подходы рассмотрены в работах [28, 29].
Помимо задач оптимизации с распадающимися ограничениями существуют и другие примеры нерегулярных задач. Например, существуют классы задач большой размерности, ограничения которых имеют тенденцию оказываться нерегулярными или «почти» нерегулярными в решении.
ции с нерегулярными ограничениями.
ритмов решения задач оптимизации с нерегулярными ограничениями.
Актуальность диссертационной работы важных приложений задач оптимизации с нерегулярными ограничениями, некоторые из которых были приведены выше. Кроме того, построение эффективных методов решения таких задач связано с существенными теоретическими трудностями. Поэтому такие задачи представляют как теоретический, так и практический интерес.
включает в себя средства нелинейного анализа, линейной алМетодика исследования гебры, теории оптимизации, теории чувствительности для оптимизационных задач, а также современные подходы к численной оптимизации, в том числе и к поиску особых решений.
Структура диссертации.
заключения и списка литературы из 94 источников.
посвящена эффекту притяжения двойственных траекторий ньютоновПервая глава ских методов к так называемым критическим множителям Лагранжа. Данный эффект играет ключевую роль в контексте задач оптимизации с нерегулярными ограничениями, и именно он является причиной медленной сходимости многих традиционных алгоритмов для таких задач. Обоснование данного эффекта представляет собой трудную теоретическую проблему.
В частности, все известные до последнего времени результаты были «негативными»: они показывали, что двойственные траектории не могут сходиться к некритическому множителю, либо такая сходимость маловероятна. В разделе 1.1 обсуждается понятие критического множителя Лагранжа и приводятся примеры влияния таких множителей на поведение метода последовательного квадратичного программирования. В разделе 1.2 впервые доказываются априорные результаты о сходимости двойственных траекторий метода последовательного квадратичного программирования к критическим множителям Лагранжа. Доказательство проводится для двух важных частных случаев, один из которых имеет ключевое значение для понимания эффекта притяжения, поскольку он отражает основные последствия нерегулярности ограничений. Наконец, в разделе 1.3 рассматриваются существующие методы, обладающие свойством локальной двойственной стабилизации, т. е. способностью подавлять эффект притяжения: стабилизированный метод последовательного квадратичного программирования и метод модифицированных функций Лагранжа.
посвящена исследованию метода модифицированных функций Лагранжа Вторая глава в контексте задач оптимизации с нерегулярными ограничениями. В разделе 2.1 исследуются свойства глобальной сходимости метода. Для задач оптимизации общего вида доказывается результат о глобальной сходимости, не требующий традиционных условий регулярности ограничений. Затем для задач оптимизации с комплементарными ограничениями доказывается так называемая C-стационарность предельных точек в естественных для таких задач предположениях. В разделе 2.2 исследуется возможность ускорения финальной фазы метода модифицированных функций с помощью стабилизированного метода Ньютона–Лагранжа. В приложении А приводятся результаты вычислительного эксперимента, показывающие, что метод модифицированных функций обладает хорошими свойствами глобальной сходимости, однако несколько уступает по эффективности другим алгоритмам; ускорители финальной фазы не позволяют существенно повысить эффективность из-за притяжения к критическим множителям.
посвящена глобализации сходимости стабилизированного метода послеТретья глава довательного квадратичного программирования. Построение глобально сходящихся алгоритмов, которые вблизи решения превращаются в стабилизированный метод последовательного квадратичного программирования, является давно стоящей проблемой. В частности, на сегодняшний день отсутствуют алгоритмы такого рода, способные конкурировать с обычным методом последовательного квадратичного программирования даже на задачах с нерегулярными ограничениями. В разделе 3.1 исследуются гибридные подходы к глобализации сходимости на основе некоторого метода внешней фазы. В разделе 3.2 предлагается комбинировать стабилизированный метод последовательного квадратичного программирования с методами модифицированных функций Лагранжа. В разделе 3.3 рассматривается подход к глобализации сходимости с помощью точных гладких штрафных функций. Результаты вычислительного эксперимента, приведенные в приложении Б, показывают, что первые два подхода уступают по общей эффективности обычному методу последовательного квадратичного программирования, однако последний подход имеет более высокую эффективность для некоторых классов задач. Проведенное исследование также показало, что стабилизированный метод последовательного квадратичного программирования обладает серьезным недостатком: для широкого класса задач метод имеет тенденцию генерировать вдали от решения длинные последовательности коротких шагов, существенно замедляющих сходимость.
В четвертой разрабатывается метод последовательного квадратичного програмглаве мирования, стабилизированный вдоль подпространства. Он представляет собой модификацию стабилизированного метода последовательного квадратичного программирования, целью которой является устранение описанной выше проблемы коротких шагов. В разделе 4. обосновывается локальная сверхлинейная сходимость метода вблизи квалифицированного решения. В разделе 4.2 предлагается простая с вычислительной точки зрения процедура идентификации подпространства вырожденности, необходимая для достижения высокой общей эффективности метода. Раздел 4.3 посвящен глобализации сходимости метода с помощью точных гладких штрафных функций. В приложении В приводятся численные результаты, показывающие высокую эффективность метода (в частности, по сравнению с обычным методом последовательного квадратичного программирования).
В заключении сформулированы основные результаты и выводы, полученные в диссертации.
Научная новизна 1. Получены принципиально новые априорные результаты о сходимости двойственных траекторий метода последовательного квадратичного программирования к критическим множителям Лагранжа.
2. Получены новые результаты о глобальной сходимости метода модифицированных функций Лагранжа как для задач оптимизации общего вида, так и для задач оптимизации с комплементарными ограничениями.
3. Предложено несколько новых подходов к глобализации сходимости стабилизированного метода последовательного квадратичного программирования.
4. Разработан принципиально новый метод последовательного квадратичного программирования, стабилизированный вдоль подпространства, а также подход к глобализации его сходимости с помощью точных гладких штрафных функций. Разработана теория локальной и глобальной сходимости метода.
5. Разработана экономичная процедура аппроксимации подпространства вырожденности, которая существенно опережает все известные альтернативы по вычислительной эффективности.
Перечислим научные положения, выносимые на защиту.
1. Доказан эффект притяжения двойственных траекторий метода последовательного квадратичного программирования к критическим множителям в ряде важных частных случаев. Полученные результаты имеют ключевое значения для понимания данного эффекта.
2. Полученные теоретические и численные результаты демонстрируют, что метод модифицированных функций Лагранжа обладает хорошими свойствами глобальной сходимости даже при нарушении условий регулярности ограничений, и поэтому является хорошим выбором для задач оптимизации с нерегулярными ограничениями, если приоритет имеет высокая робастность и качество получаемых решений.
3. Предложен подход к глобализации сходимости стабилизированного метода последовательного квадратичного программирования с использованием точных гладких штрафных функций. Глобализованный таким способом метод существенно опережает по эффективности обычный метод последовательного квадратичного программирования на некоторых классах задач.
4. Разработан новый метод последовательного квадратичного программирования, стабилизированный вдоль подпространства, и получены результаты о его локальной и глобальной сходимости. Разработанный метод существенно опережает по эффективности обычный метод последовательного квадратичного программирования на задачах с нерегулярными ограничениями.
5. Разработана процедура аппроксимации подпространства вырожденности отображения в особом решении, которая, в отличие от существующих альтернатив, целесообразна с практической точки зрения. Данная процедура может быть использована для построения самых разных методов, использующих информацию о структуре подпространства вырожденности.
зательств и использованных научных методов.
Список публикаций.
21, 24–27, 73–77], в том числе 5 статей опубликовано в журналах из списка ВАК [15, 17, 27, 73, 77].
Апробация результатов.
на XXI международном симпозиуме по математическому программированию «ISMP2012»
(Берлин, Германия), на международной конференции по непрерывной оптимизации «ICC OPT2013» (Лиссабон, Португалия), на X всемирном конгрессе по структурной и междисциплинарной оптимизации «WCSMO-10» (Орландо, США, 2013), на ежегодных международных научных конференциях студентов и молодых ученых «Ломоносов-2011», «ЛомоносовМосква), на ежегодной научной конференции «Тихоновские чтения» (Москва, и 2012), на ежегодной научной конференции «Ломоносовские чтения» (Москва, 2011 и 2012), а также на VII Московской международной конференции по исследованию операций «ORM2013».
В работе используется следующая система нумерации ее частей. Номер раздела состоит из двух цифр, первая из которых обозначает номер главы, в которой расположен раздел.
Аналогично, номер пункта состоит из трех цифр, первые две из которых составляют номер раздела, в котором находится этот пункт. Нумерация объектов (формул, теорем и т. д.) в каждой главе независимая. При ссылке на объект извне главы, в которой он находится, используется номер, состоящий из двух цифр, первая из которых является номером главы, а вторая номером объекта в главе.
Автор выражает огромную благодарность своему научному руководителю Алексею Феридовичу Измаилову за постановку задачи, постоянное внимание к работе, ценные советы и поддержку.
Список основных обозначений IR — множество вещественных чисел;
IR+ — множество неотрицательных вещественных чисел;
IR — -мерное арифметическое пространство, снабженное евклидовым скалярным произведением и соответствующей нормой;
·, · — евклидово скалярное произведение;
— евклидова норма вектора (если не оговорено иное);
— спектральная норма матрицы, т. е. порожденная евклидовой нормой (если не оговорено иное);
dist(, ) = inf — расстояние от точки до множества ;
im — образ (множество значений) матрицы (линейного оператора) ;
ker — ядро (множество нулей) матрицы (линейного оператора) ;
T — матрица, транспонированная к матрице ;
det — определитель матрицы ;
rank = dim im — ранг матрицы (линейного оператора) ;
— подвектор вектора с компонентами, ;
— подматрица матрицы, состоящая из строк с индексами ;
, — подматрица матрицы, образуемая пересечением строк с индексами и столбцов с индексами ;
|| — количество элементов в конечном множестве ;
— знак окончания доказательства.
Глава Эффект притяжения к критическим множителям Лагранжа В данной главе исследуется эффект притяжения двойственных траекторий методов ньютоновского типа к так называемым критическим множителям Лагранжа. Раздел 1.1 посвящен обсуждению необходимой терминологии, возможных сценариев двойственного поведения и демонстрации данного эффекта на примерах. Основное внимание уделяется методу последовательного квадратичного программирования, для которого этот эффект является крайне типичным и приводит к потере сверхлинейной скорости сходимости.
В разделе 1.2 для метода последовательного квадратичного программирования доказываются результаты о том, что множество критических множителей действительно является аттрактором для двойственных траекторий, а также характеризуется влияние данного эффекта на скорость прямой и двойственной сходимости. Доказательство проводится для двух частных случаев: задач оптимизации с одной переменной и одним ограничением и для чисто квадратичных задач. Второй частный случай имеет ключевое значение для понимания эффекта притяжения, поскольку он отражает наиболее существенные последствия вырожденности ограничений.
В разделе 1.3 кратко рассматриваются стабилизированный метод последовательного квадратичного программирования и метод модифицированных функций Лагранжа. Эти методы обладают свойством двойственной стабилизации, т. е. способностью подавлять эффект притяжения к критическим множителям. Однако, данное свойство является локальным, и для обоих методов эффект притяжения присутствует, хотя и значительно менее выражен. А именно, во многих задачах есть широкие прямо-двойственные области, при старте из которых двойственные траектории методов будут сходиться к критическим множителям.
1.1. Критические множители Лагранжа Будем рассматривать задачу математического программирования где : IR IR — дважды дифференцируемая функция, а : IR IR и : IR IR — дважды дифференцируемые отображения.
Напомним, что точка IR называется стационарной точкой задачи (1), если существуют такие IR и IR, что тройка (,, ) удовлетворяет системе Каруша–Куна– Таккера (ККТ) этой задачи. Здесь : IR IR IR IR — функция Лагранжа задачи (1):
При этом пара (, ) называется множителем Лагранжа, отвечающим стационарной точке.
Множество таких пар будем обозначать ().
Определим () = { = 1,..., | () = 0} — множество номеров ограниченийнеравенств задачи (1), активных в допустимой точке этой задачи. Введем также разбиение множества () на подмножества Кроме того, положим () = {1,..., } ().
Как хорошо известно, стационарность локального решения задачи (1) можно гарантировать при выполнении в точке тех или иных условий регулярности ограничений. Важнейшим условием регулярности является условие Мангасариана–Фромовица (MFCQ, от англ.
Mangasarian–Fromovitz constraint qualification), которое состоит в следующем:
Выполнение MFCQ в стационарной точке задачи (1) равносильно ограниченности множества (). Требование единственности отвечающего множителя (, ) называется строгим условием регулярности Мангасариана–Фромовица (SMFCQ, от англ. Strict Mangasarian– Fromovitz constraint qualification). Еще более сильным условием, чем SMFCQ, является условие линейной независимости (LICQ, от англ. Linear independence constraint qualification):
Как было сказано во введении, основной интерес в данной работе представляют случаи, когда множество () содержит более одного элемента (т. е. нарушается SMFCQ) или даже является неограниченным (т. е. нарушается MFCQ).
Ключевую роль в данной работе играет следующее понятие критического множителя Лагранжа, введенное в [71]: множитель (, ) () называется критическим, если существует набор (,, ) IR IR IR такой, что = 0, и выполнены соотношения и некритическим иначе. Множество критических множителей обычно является тощим по отношению к множеству всех множителей. Например, при отсутствии ограничений-неравенств, если множество некритических множителей непусто, то оно является относительно открытым и всюду плотным в множестве всех множителей. Вместе с тем, критические множители обладают рядом особых свойств и оказывают значительное влияние на поведение ряда важнейших численных методов оптимизации.
Одно из таких свойств состоит в том, что для критических множителей неизбежно нарушается достаточное условие второго порядка оптимальности (SOSC, от англ. Second-order sufficient condition), которое в стационарной точке задачи (1) для отвечающего ей множителя Лагранжа (, ) () имеет следующий вид:
где есть критический конус задачи (1) в точке. Напомним, что в в случае выполнения (7) точка является строгим локальном решением задачи (1). Более того, если в стационарной точке для множителя (, ) () выполнено необходимое условие второго порядка оптимальности (SONC, от англ. Second-order necessary condition) то множитель (, ) является некритическим тогда и только тогда, когда он удовлетворяет SOSC.
Другое важное свойство критических множителей устанавливается в следующем предложении, взятом из [72]:
Предложение 1.
IR дважды дифференцируемы в точке. Пусть — стационарная точка задачи (1), а (, ) — отвечающий ей множитель Лагранжа.
Тогда следующие свойства являются эквивалентными:
а) множитель (, ) являются некритическим;
б) выполнена оценка расстояния в) для любого = (,, ) IR IR IR, достаточно близкого к нулю, любое решение ((), (), ()) канонически возмущенной системы ККТ достаточно близкое к (,, ), удовлетворяет оценке Таким образом, оценки расстояния (9) и (10) не могут выполняться вблизи критического множителя.
При отсутствии ограничений-неравенств задача (1) принимает вид Стационарные точки и отвечающие им множители Лагранжа задачи (11) характеризуются системой Лагранжа где : IR IR IR — функция Лагранжа задачи (11):
Для задачи (11) условия регулярности MFCQ, SMFCQ и LICQ эквивалентны и имеют следующий вид:
Как следует из первых двух равенств в (6), для задачи с ограничениями-равенствами критичность множителя () означает существование такого элемента ker (){0}, что Для таких задач понятие критического множителя было введено в [8]. В случае полного вырождения (т. е. при () = 0) критичность означает вырожденность матрицы Гессе ). В общем случае, поскольку im( ())T = (ker ()), условие (14) эквивалентно условию где через ker () обозначен оператор ортогонального проектирования на ker (). Симметричную матрицу линейного оператора ker () 2 (, ) : ker () ker () называют суженной матрицей Гессе функции Лагранжа по. Критичность множителя означает вырожденность этой матрицы, а условия SONC и SOSC эквивалентны ее неотрицательной и положительной определенности соответственно. Отсюда, в частности, очевидно, что SOSC является гораздо более сильным условием, чем некритичность.
Как уже упоминалось во введении, скорость сходимости ньютоновских методов к нерегулярным решениям обычно является лишь линейной. Однако, как было замечено в [94, раздел 6] и весьма убедительно продемонстрировано в [8, 67, 68, 70], причина медленной прямой сходимости состоит не в вырожденности ограничений как таковой, а в определенном нежелательном поведении двойственной траектории. А именно, анализ и вычислительный опыт свидетельствуют о том, что двойственные траектории ньютоновских методов имеют сильнейшую тенденцию притяжения к критическим множителям, и именно это обстоятельство является причиной медленной сходимости.
Рассмотрим данный эффект на примере метода последовательного квадратичного программирования (SQP, от англ. Sequential quadratic programming). Итерация метода заключается в следующем. Для текущего приближения (,, ) IR IR IR вычисляется направление IR как стационарная точка задачи квадратичного программирования и следующее приближение полагается равным (+,, ), где IR и IR — множители Лагранжа, отвечающие стационарной точке подзадачи (15). При отсутствии ограниченийнеравенств итерацию можно записать в более простом виде. Для текущего приближения (, ) IR IR вычисляется решение (, ) IR IR системы и следующее приближение полагается равным (+, +). В этом случае метод эквивалентен применению метода Ньютона к системе Лагранжа задачи (11), и поэтому называется методом Ньютона–Лагранжа (МНЛ).
Сначала рассмотрим возможные сценарии поведения МНЛ для задач вида (11), в которых есть критические множители. Первый сценарий, а именно притяжение двойственной траектории к критическим множителям и линейная скорость сходимости прямой траектории, является весьма типичным и наблюдается в большинстве случаев [67, 68]. Такое поведение демонстрируется примерами 1–3, взятыми из [42, 67].
(Пример 2.1 из [67], тест 20203 из коллекции DEGEN [42].) Рассмотрим Пример 1.
задачу Задача имеет единственное решение = 0, () = IR2. Критическими являются множители IR2, для которых 42 + 2 = 4 (эллипс на рис. 1).
На рис. 1 показаны некоторые двойственные траектории МНЛ для двух различных значений 0. Как легко проверить аналитически, в данном примере при фиксированном двойственные траектории всегда сходятся к одному критическому множителю. Однако, как видно из рисунка, при различных 0 предельные критические множители различаются.
(Пример 2.3 из [67], тест 20302 из коллекции DEGEN [42].) Рассмотрим Пример 2.
задачу Она имеет единственное решение = 0, () = IR2. Критическими являются множители IR2, для которых 1 = 1 или (1 3)2 2 = 1 (вертикальная линия и гипербола на рис. 2).
На рис. 2(а) показаны некоторые двойственные траектории МНЛ для начальной точки 0 = (1, 2, 3). На рис. 2(б) показано распределение двойственных приближений на момент остановки МНЛ, который запускался из точек 0 сетки [2, 8] [2, 4] с шагом 1/4. Как видно из рисунка, во всех случаях предельный множитель был критическим.
Следующий простой пример, взятый из [8, 68], позволяет аналитически продемонстрировать эффект притяжения к критическим множителям.
Пример 3.
() = 2. Задача (11) с такими данными имеет единственную допустимую точку (а значит, единственное решение) = 0, причем (0) = IR (поскольку (0) = 0). Это решение удовлетворяет SOSC (7) при > 1, а единственным критическим множителем Лагранжа является = 1.
Согласно (16), любая прямо-двойственная траектория {(, )} МНЛ для данной задачи удовлетворяет равенствам для каждого. Предполагая, что = 0, из второго уравнения получаем и тогда из первого уравнения В частности, Таким образом, если 0 = 0, то = 0 для всех, и последовательность {(, )} корректно определена и сходится к (0, 1) с линейной скоростью. В частности, { } сходится к критическому множителю = 1. Более того, если 0 = 1, то каждая из последовательностей { } и { } сходится с линейной скоростью.
На рис. 3 показаны прямо-двойственные траектории МНЛ. Вертикальная сплошная линия соответствует множеству {} (). Запуски выполнялись из точек (0, 0 ), где равнялось 2 или 2, а 0 принимало различные значения из сегмента [5.5, 0.5]. Как видно из рисунка, все траектории сходятся к (, ) c линейной скоростью.
Другой возможный сценарий состоит в отсутствии сходимости двойственной траектории. В отличие от предыдущего сценария, такое поведение крайне нетипично, но возможно, как показывает следующий (значительно более сложный) пример.
Пример 4.
Систему Лагранжа задачи (17) можно записать в виде Здесь через () обозначена матрица Гессе функции Лагранжа задачи (17).
Согласно (18), задача (17) имеет стационарную точку = 0, а множество множителей Лагранжа, отвечающих, есть все IR. Далее, det () = 2( 5)(2 + 6 + 10), и поэтому существует единственный критический множитель = 5.
Итерация МНЛ для задачи (17) выглядит следующим образом:
Несложно убедиться в том, что если = 5, то матрица в левой части (19) является невырожденной тогда и только тогда, когда Здесь и далее через обозначается присоединенная матрица для матрицы (в частности, = = det ). Далее, если = 5, и выполнено (20) то из (19) получаем Рассмотрим линейное подпространство = ker () в IR. Легко проверить, что является линейной оболочкой векторов 1 = (1, 1, 3) и 2 = (3, 2, 2), и, в частности, dim = 2. Далее, можно проверить, что при любом = 5 выполнено равенство из которого следуют равенства () ()1 = 0 и () ()2 = 0. Используя последние два равенства, получаем (). Наконец, заметим, что если и = 5, то матрица в левой части (58) обязательно является вырожденной.
Приведенные рассуждения позволяют заключить, что если, = 5, и выполнено (20), то равенства в (21) корректно определяют +1 и +1, причем +1. Таким образом, если 0, 0 = 5, и (20) выполнено при = 0, то либо для некоторого будет выполнено = 5 или, ( ) = 0 (и следующая итерация будет не определена), либо для всех справедливо, = 5, и выполнено (20) (откуда, в частности, следует = 0).
Предположим, что имеет место последний случай, и покажем, что сходимость к критическому множителю при этом невозможна. Определим матрицу IR32 со столбцами 1, 2, и рассмотрим (единственную) последовательность { } IR2 {0} такую, что = для всех. Непосредственными вычислениями можно убедиться, что выполнены соотношения Из данных соотношений и из (21) легко получить, что откуда следует Введем вспомогательную последовательность { } такую, что 0 = 0 / 0 и для каждого номера вектор +1 определяется соотношением Заметим, что из соотношений (23), (24) и условия = 0, выполненного для всех, вытекает, что последовательность { } корректно определена, и для каждого вектор совпадает с / с точностью до знака. Поэтому из (22) получаем Предположим, что последовательность { } сходится к некоторому * IR. Как следует из (25), сходимость { } возможна только при условии, что, сходится к 0.
Следовательно, все предельные точки последовательности { } должны удовлетворять, = 0. Однако, как следует из (24), = 1 (* )/1 (* ) также является предельной точкой { }, и поэтому, = 0, откуда следует 1 (* )T 1 (* ), = 0. Далее, несложно проверить, что 1 ()T 1 () = 130( + 3) + (2 10 40), где Следовательно, если * = 3, то вектор также должен удовлетворять, = 0. Однако, данное равенство не может выполняться одновременно с, = 0. Таким образом, последовательность { } не может сходиться к точке, отличной от 3.
Предположим теперь, что * = 3. Из (25) с учетом равенства 2 () = 1 () получаем Кроме того, второе равенство в (25) можно переписать в виде Разделив предпоследнее равенство на последнее, получаем Заметим, что последовательность { } может иметь не более четырех различных предельных точек, поскольку такие точки должны удовлетворять равенству, = 0. Более того, прямой подстановкой можно убедиться, что для каждой такой точки величина, 1 (* )/ 1 (* ), 1 (* )1 (* ) является отрицательной, откуда следует, что (+2 +3)/(+1 +3) > 1+ для некоторого > 0 и для всех достаточно больших. Очевидно, отсюда следует, что +2 будет находиться дальше от 3, чем +1, и поэтому последовательность { } не может сходиться к 3.
Таким образом, если для некоторого, то последовательность { } всегда расходится (и, в частности, не может сходиться к критическому множителю = 5). Более того, как показывает вычислительный эксперимент, у данной последовательности всегда есть некритические предельные точки, и при этом последовательность { } всегда сходится к 0.
Отметим также, что описанное поведение наблюдается в данном примере достаточно часто, и является в некотором смысле устойчивым: оно не разрушается малым шевелением начальной точки. Даже если 0, направления / во многих случаях стремятся к подпространству. Пример такого поведения показан на рис. 4, где 0 = (1, 1, 2), 0 = 1.
Тем не менее, стоит отметить, что сходимость к критическому множителю по-прежнему является типичным сценарием в данном примере, особенно если направление 0 /0 распоо ложено достаточно далеко от, или если 0 достаточно близк к. Конечно, в этом случае для всех выполнено.
Наконец, возможен «смешанный» сценарий поведения, который также является достаточно типичным: двойственная траектория сначала ведет себя «хаотически», но потом попадает в область притяжения одного из критических множителей и далее сходится к этому множителю. Для демонстрации такого поведения вновь рассмотрим пример 2. На Рис. 4. Последовательность { / } для примера 4 при 0 = (1, 1, 2), 0 = 1.
рис. 5 показана двойственная траектория МНЛ для начального приближения 0 = (3, 2, 1), 0 = (3.75, 0.25), которая ведет себя описанным образом. (В [67, пример 2.3], сходимость двойственной траектории не была обнаружена в связи со слишком ранним завершением итерационного процесса.) Отметим, что если в задаче (11) с нерегулярными ограничениями отсутствуют критические множители, то наиболее типичным является сценарий, когда двойственная траектория МНЛ расходится. Это связано с наличием другого эффекта, возникающего при сходимости МНЛ к решениям, которым отвечает более одного множителя Лагранжа — эффекта отталкивания двойственных траекторий от некритических множителей. Более того, данный эффект может возникать даже если в задаче присутствуют критические множители (в частности, именно он лежит в основе поведения, рассмотренного в примере 4), однако в таких случаях он является крайне нетипичным. Исследование данного эффекта можно найти в работах [68] и [77].
Теперь кратко обсудим, как меняются возможные сценарии поведения SQP при добавлении ограничений-неравенств. Для этого потребуются дополнительные определения. Из (2) немедленно следует, что если для множителя (, ) () выполняется () = 0 для некоторого множества индексов (), то является стационарной точкой задачи с ограничениями-равенствами в то время как (, ) является отвечающим этой стационарной точке множителем Лагранжа. Понятие критического множителя Лагранжа дополняется следующим, введенным в [67]:
множитель (, ) () называется критическим относительно множества индексов (), если () = 0 и (, ) — критический множитель Лагранжа, отвечающий стационарной точке задачи (26). В противном случае (, ) называется некритическим относительно.
Как легко видеть из приведенных определений, если множитель (, ) критический, то существует 1 0 (, ) такое, что этот множитель является критическим относительно множества индексов = + (, ) 1. В частности, если выполнено условие строгой дополнительности () > 0 (т. е. 0 (, ) = ), то некритичность эквивалентна некритичности относительно ().
Очевидно, что из выполнения SOSC (7) вытекает выполнение соответствующего достаточного условия второго порядка оптимальности в стационарной точке задачи (26) при = () для отвечающего этой стационарной точке множителя Лагранжа (, () ), и поэтому (, ) не может быть критическим множителем Лагранжа для задачи (1) относительно (). Вместе с тем, критичность такого множителя относительно более узких множеств индексов () может иметь место (см. [67, пример 3.5]).
Рассмотрим произвольную траекторию {(,, )} метода SQP для задачи (1) и для каждого введем множество индексов ограничений-неравенств соответствующей подзадачи SQP, активных в точке.
Весьма естественным является предположение о том, что множества стабилизируются на поздних итерациях, т. е. = для всех достаточно больших. В частности, данное предположение выполнено автоматически, если траектория сходится к точке (,, ), где — стационарная точка, а множитель (, ) () удовлетворяет условию строгой дополнительности. Если = для всех достаточно больших, то метод SQP можно интерпретировать как МНЛ для задачи (26). В связи с этим, возможны следующие сценарии поведения.
Если ограничения задачи (26) регулярны в точке, т. е.
то точке отвечает единственный множитель (, ), который обычно является некритическим. В таких случаях двойственная траектория метода сходится к этому множителю, а скорость прямой и прямо-двойственной сходимости является сверхлинейной.
Если же условие (27) нарушается в точке, то этой точке отвечает бесконечное множество множителей. В этом случае поведение метода зависит от наличия критических множителей относительно. Если такие множители существуют, то двойственная траектория метода в большинстве случаев сходится к одному из них, и при этом скорость прямой сходимости является лишь линейной. Если же все множители являются некритическими относительно, то двойственная траектория обычно расходится.
В завершение данного раздела отметим, что эффект притяжения двойственных траекторий к критическим множителям Лагранжа имеет место и для многих других ньютоновских методов. В частности, в [70] продемонстрировано, что данный эффект имеет место для методов модифицированных функций Лагранжа с линеаризованными ограничениями и квазиньютоновских методов последовательного квадратичного программирования.
В следующем разделе речь пойдет о теоретическом обосновании эффекта притяжения к критическим множителям для МНЛ.
1.2. Обоснование эффекта притяжения для метода Ньютона–Лагранжа Существующие теоретические объяснения эффекта притяжения двойственных траекторий ньютоновских методов к критическим множителям Лагранжа [8, 68, 70] носят в основном «негативный» характер: они показывают, что было бы, если бы двойственная траектория сходилась к некритическому множителю, а также содержат аргументы в пользу того, что такое поведение крайне маловероятно.
В данном разделе разрабатываются первые «позитивные» результаты, показывающие, что множество критических множителей Лагранжа действительно является аттрактором для двойственных траекторий МНЛ. Обоснование проводится для двух частных случаев: задач с одной переменной и одним ограничением и чисто квадратичных задач. Второй частный случай имеет ключевое значение для понимания эффекта притяжения, поскольку он отражает наиболее существенные последствия вырожденности ограничений. Кроме того, возможно, полученные результаты могут быть расширены на общий случай с применением процедуры Ляпунова–Шмидта (см., например, [58, гл. VII]). Вместе с тем, даже в случае чисто квадратичной задачи анализ оказывается крайне нетривиальным.
1.2.1. Одномерные задачи Будем рассматривать задачу оптимизации c одной скалярной переменной и одним ограничением-равенством где функции : IR IR и : IR IR предполагаются дважды дифференцируемыми. Функция Лагранжа : IR IR IR задачи (28) имеет вид Приводимые ниже предложения 2 и 3 полностью объясняет происходящее в примере 3, а также демонстрирует сложности такого анализа даже в таком простейшем специальном случае.
ференцируемы в окрестности точки IR, причем их вторые производные непрерывны в этой точке. Предположим, что () = () = () = 0, () = 0.
Тогда для любого 0 IR{}, достаточно близкого к, и для любого 0 IR существует единственная последовательность {(, )} IR IR такая, что (+1, +1 ) удовлетворяет системе (16) при (, ) = (, ) для всех ; эта последовательность сходится к (, ), где = ()/ (), причем = для всех и Заметим, что из предположения () = () = () = 0 вытекает, что является стационарной точкой задачи (28), причем () = IR. В то же время, из () = 0 следует, что = ()/ () является единственным критическим множителем Лагранжа.
Доказательство.
0, для IR выполняются оценки из которых для = вытекают соотношения Поскольку () = 0, из этих соотношений следует, в частности, что () = 0 для всех достаточно близких к, и Более того, по правилу Лопиталя Пусть (, ) IR IR — текущее приближение; тогда, согласно (16), следующее приближение (+1, +1 ) должно быть решением системы Если достаточно близко к, второе равенство в (34) однозначно определяет и, следовательно, Согласно первому соотношению в (32), отношение в правой части может быть сделано сколь угодно близким к 1/2, если взять достаточно близким к. Отсюда следует, что для всякого 0 IR, достаточно близкого к, существует единственная последовательность { } такая, что для всякого точка +1 удовлетворяет второму равенству в (34), эта последовательность сходится к с линейной скоростью, и, более того, выполняется (30).
Далее, из первого уравнения в (34) и из (35) следует, что +1 должно удовлетворять уравнению однозначно определяющему Следовательно, Используя второе соотношение в (32), а также (33), последнее равенство можно переписать где последовательности { } и { } сходятся к нулю. Применяя, например, [1, лемма 2.6.6], отсюда получаем сходимость { } к.
В предложении 2 установлена скорость сходимости лишь прямой траектории { }. Предлагаемый ниже анализ скорости сходимости двойственной траектории { } существенно сложнее. Для этого анализа потребуются следующие три технические леммы о числовых последовательностях.
Пусть числовая последовательность { } удовлетворяет для каждого условию где числовая последовательность { } сходится к некоторому > 1, а числовая последовательность { } сходится к нулю.
Доказательство.
Предположим, что последовательность { } не сходится к нулю, т. е. существует такое > 0, что найдется сколь угодно большой номер, для которого | | >. Не ограничивая общности, будем считать, что | | < /2, и что > 1 + при некотором > 0. Тогда из (39) следует выполнение для всех номеров. Поэтому для всех, для которых | | >, будет выполнено и, в частности, |+1 | >. Отсюда, очевидно, следует.
Отметим, что в предположениях леммы 1 сходимость последовательности { } к нулю возможна, но крайне нетипична. Действительно, для произвольной последовательности { } с этими свойствами рассмотрим последовательность { }, также удовлетворяющую (38) при тех же { } и { }, но для которой 0 = 0 +, где = 0. Тогда для всякого и если = 0 для всех, то. Таким образом, любое сколь угодно малое возмущение начального элемента последовательности { } разрушает ее сходимость.
Пусть числовая последовательность { } удовлетворяет для каждого условию где числовая последовательность { } сходится к некоторому > 0.
Тогда справедливы следующие утверждения:
в) если > 1, то либо, либо выполнено (41).
Доказательство.
Последнее слагаемое в этом соотношении стремится к нулю. Поэтому, если < 1, то для обоснования (41) достаточно снова применить [1, лемма 2.6.6]. Если же > 1, то требуемое утверждение следует из леммы 1.
Пусть теперь = 1. Предположим, что { } не стремится к бесконечности, т. е. найдется бесконечный набор номеров {0, 1,...} такой, что подпоследовательность { | } сходится к некоторому числу. Тогда для произвольного фиксированного номера из (40) вытекает и поэтому последовательность {+ | } сходится к +. Последнее означает, что найдется неотрицательный элемент со сколь угодно большим индексом. Поскольку, не ограничивая общности, можно считать, что > 0 для всех, последнее означает, что начиная с некоторого номера 1 все элементы последовательности { } будут положительны.
Рассмотрим произвольное число 0 < < 1. Поскольку 1, то найдется номер такой, что для всех 2 выполнено >. Учитывая, что при 2 также выполнено > 0, из (40) получаем для таких. Поэтому для произвольного фиксированного 2 и любого достаточно большого номера будет справедливо Таким образом, начиная с некоторого номера, все элементы последовательности { } будут больше 1/(2(1 )). Учитывая произвольность выбора, получаем противоречие с тем, что { } не стремится к бесконечности.
Как следует из доказательства леммы 2 и комментариев к лемме 1, если > 1, то типичным является случай.
Пусть числовая последовательность { } удовлетворяет для каждого условию (38), где числовая последовательность { } сходится к некоторому (0, 1), а числовая последовательность { } сходится к нулю, причем все элементы последовательности { } с достаточно большими номерами имеют одинаковый знак, и при некотором 0 < < 1.
Тогда все элементы последовательности { } с достаточно большими номерами также имеют одинаковый знак, причем Без ограничения общности будем считать, что все элементы последоваДоказательство.
тельности { } имеют один знак. Перепишем (38) в виде где = 1 /, и, следовательно, /. Таким образом, начиная с некоторого номера будет выполнено > 0, и поэтому последовательность {+1 / }, а значит и { }, может менять знак лишь конечное число раз. Применяя к последовательности {+1 / } лемму 2, получаем, что либо +1 /, либо +1 / /( ), причем если <, то выполнено последнее. Для доказательства (42) остается переписать (38) в виде и перейти к пределу при.
Заметим, что в условиях леммы 3 типичным является выполнение (42) при = max{, }. Если, то это следует из утверждения леммы 3. Если же >, то это следует из доказательства леммы 3 и комментариев к лемме 2, поскольку при этом типичным является случай +1 /.
Перейдем к анализу скорости сходимости последовательности { }. Перепишем равенство (37) следующим образом:
где функции, : IR IR имеют вид Как показано в доказательстве предложения 2, то +1 = ( )( ). Отсюда следует, что если 0 =, то = для всех, и скорость сходимости последовательности { } является линейной:
Условие (45), в частности, выполнено, если ) 0 (как, например, в примере 3). Если же (45) не выполнено, то линейную скорость сходимость { } можно установить при дополнительных предположениях о гладкости функции.
следует предельное соотношение что означает, что функция дважды дифференцируема в точке, причем ее значение и первые две производные в этой точке равны нулю.
Предложение 3.
того, для некоторых 1, 2 > 0 и 1, 2 = 0 выполнены условия где определяется согласно (29).
Тогда для любого 0 IR {}, достаточно близкого к, и для любого 0 IR, для единственной последовательности {(, )} IR IR такой, что (+1, +1 ) удовлетворяет системе (16) при (, ) = (, ) для всех, выполняется следующее: начиная с некоторого номера, имеет место =, где = ()/ (), причем существуют отличные от нуля левая производная -го порядка и правая производная -го порядка функции в точке. Действительно, для минимальных таких и будут справедливы оценки откуда следуют условия (47), (48) при 1 = 2, 2 = 2 и 1 = (1) () ( 0)/!, 2 = () ( + 0)/!.
Кроме того, выполнение (47), (48) гарантировано, если при некоторых > 0, = 1 и = 0, = 1, 2. Действительно, в этом случае, согласно правилу Лопиталя, и поэтому, с учетом (31), Аналогично проверяется (48).
вательность { } удовлетворяет (43). Обозначим Согласно второму соотношению в (44), 0.
Из (36) следует, что если 0 достаточно близко к, то все элементы последовательности { } имеют одинаковый знак. Для определенности будем считать, что < для всех. Тогда из (47) следует, что элементы последовательности { } с достаточно большими номерами имеют один знак. Вновь привлекая второе равенство из (31) и (47), получаем Отсюда и из (30) следует С учетом (43) и (44), применяя лемму 3 к последовательности { }, получаем утверждение теоремы при {1, 1 }.
Если же > при всех, то, повторяя аналогичные рассуждения, также получаем (49), в котором {1, 2 }.
Заметим, что если 0 =, то утверждение предложения 3 остается справедливым, если условие (47) заменить на () = 0 при <, или если заменить (48) на () = 0 при >.
В этом случае доказательство предложения модифицируется очевидным образом, с учетом того, что вся последовательность { } лежит либо слева, либо справа от.
Отметим также, что значение в предельном соотношении (49) зависит от того, с какой стороны { } приближается к. Как следует из комментариев к лемме 3, если < при всех, то типичным является значение = min{1, 1 }, а если >, то = min{1, 2 }.
Приводимый ниже пример, являющийся более общей версией примера 3, демонстрирует возможные сценарии поведения МНЛ, в том числе в ситуациях, когда какие-то из предположений предложения 2 нарушаются.
что в степени и можно возводить отрицательные числа. А именно, будем считать, что оба числа либо являются целыми, либо представляют собой рациональные дроби, в которых знаменатель является нечетным.
Тогда = 0 — единственное решение задачи (28), причем (0) = IR. Далее, если = 2, то (0) = 0, и, следовательно, существует единственный критический множитель Лагранжа, равный при = 2 и нулю при > 2. Если же > 2, то при = 2 критических множителей нет, а при > 2, напротив, все множители Лагранжа являются критическими.
Заметим, что при = 2 выполнены условия предложения 2. Дополнительно, если = 2, то ) 0, а если = 3, то (·) 0, и поэтому в обоих случаях должно выполняться (46). Если же > 2, = 3, то выполнены условия предположения 3 при 1 = 2 = 2, 2 = ( 3) и 1 = (1) 2, вследствие чего должно выполняться (49) при {1, 2}.
Согласно (16), имеем:
для каждого. Предполагая, что = 0, из второго уравнения получаем и тогда из первого уравнения, после несложных преобразований, Таким образом, последовательность { } сходится к 0 с линейной скоростью, но 1/2 в Поведение двойственной траектории зависит от значений обоих параметров и. Если <, то. Действительно, в этом случае уравнения (51) и (52) имеют вид где 0 < < 1, = 0 и > 0. Отсюда следует, что Поскольку 0 < 1+ < 1, то из последнего условия легко получить /(1 1+ ), откуда, в свою очередь, следует.
Если =, то равенство (52) можно переписать в виде Отсюда следует, что { } сходится к =, причем, если 0 =, то = для всех, и Если же >, то, применяя [1, лемма 2.6.6], получаем, что { } сходится к 0. Очевидно, что если при этом = + 1, то (52) принимает вид и поэтому, если 0 = 0, то = 0 для всех, и выполняется (55) при = 0. Для того, чтобы установить скорость сходимости при = + 1, вновь перепишем (51) и (52) в виде (53), где по-прежнему 0 < < 1 и = 0, но теперь < 0 и = 1. Отсюда вновь следует равенство (54), которое можно переписать следующим образом:
где = /(1 1+ ). Предполагая 0 =, из последнего равенства получаем, что при < 1 выполняется, а при 1 < < 0 выполняется. Очевидно, что в обоих случаях = 0 для любого достаточно большого. Для таких из (53) получаем Таким образом, при > выполняется 1.2.2. Чисто квадратичные задачи Будем рассматривать следующую чисто квадратичную задачу оптимизации с ограничениями равенствами:
где IR — симметричная матрица, а : IR IR IR — симметричное билинейное отображение (т. е. [, ] = (1,,...,, ), где 1,..., IR — симметричные матрицы).
Стационарные точки задачи (56) и отвечающие им множители Лагранжа характеризуются системой Лагранжа относительно (, ) IR IR. В данном разделе будем исследовать поведение МНЛ в окрестности точки = 0. Данная точка является стационарной, причем множество отвечающих ей множителей Лагранжа есть IR. Как следует из определения, критическими являются множители, удовлетворяющие det () = 0.
Итерация метода Ньютона для системы (57) определяется следующим образом: для текущего прямо-двойственного приближения (, ) IR IR следующие приближение (+1, +1 ) вычисляется как решение линейной системы где для произвольного IR матрица [] IR определяется соотношением [] = [, ].
Далее будем использовать соглашение, что определитель пустой матрицы равен 1. Отсюда, в частности, следует, что определитель присоединенной матрицы для любой матрицы размера 1 1 также равен 1. Данное соглашение необходимо, чтобы избежать отдельного рассмотрения случая = 1.
Равенство (58) можно переписать в виде Предположим, что матрица ( ) невырождена. В этом случае из первого равенства получаем Подставляя полученное выражение во второе равенство в (59), находим Если матрица [ ](( ))1 ([ ])T невырождена (и, в частности, = 0), то из последнего равенства получаем Введем дополнительные обозначения. Для произвольных IR и IR положим В этом случае условия (60) и (61) можно переписать в следующем виде:
Обозначим через 0 множество всех критических множителей:
где : IR IR, () = det (). В данном разделе будет исследоваться поведение МНЛ (58) в окрестности некоторого критического множителя 0, для которого выполнено Основную идею проводимого ниже анализа можно неформально описать следующим образом. Будет показано, что если лежит достаточно близко к некоторому критическому множителю 0, и при этом достаточно близко к ker (), то величина (, ) близка к, а величина (, ) близка к для некоторого множителя 0. Таким образом, условия (63) означают выполнение следующих приблизительных соотношений:
Неформально говоря, данные соотношения означают, что +1 приблизительно в два раза «ближе» к 0, чем, а +1 приблизительно в два раза «ближе» к множеству 0, чем.
Для начала докажем следующую простую лемму.
Пусть для некоторого критического множителя 0 выполнено (64).
Тогда для произвольного вектора ker () единичной нормы найдется константа > 0 и аналитическое (в частности, дифференцируемое бесконечное число раз) отображение : (, ) IR, обладающее следующим свойствами:
в) множество ker () совпадает с линейной оболочкой вектора () для всех Зафиксируем вектор ker () единичной нормы и рассмотрим параДоказательство.
метрическую линейную систему относительно (, ) IR IR, в которой IR является параметром. Очевидно, что при = система имеет решение (, 0), и при этом матрица системы невырождена. Действительно, если равенства выполнены для некоторого (, ), то, умножая первое из них скалярно на, получаем откуда следует = 0. Таким образом, из первого равенства в (66) следует ker (), что, с учетом (64), означает, что второе равенство в (66) может выполняться только в случае = 0.
Очевидно, для любого IR, достаточно близкого к, матрица системы (65) также будет невырождена, откуда следует, что система имеет единственное решение ((), ()).
Далее, из определения множества 0 следует, что для любого 0, первое уравнение в (65) имеет решение вида (, 0) для некоторого IR {0}. Заметим, что если множитель достаточно близок к, то, = 0. Действительно, предположим, что это не так. В этом случае существуют последовательности { } 0 и { } IR {0}, для которых выполнено { }, а также ker ( ) и, = 0 для всех. Тогда для любой предельной точки IR последовательности { / } выполнено ker (), = 1 и, = 0, что противоречит (64). Таким образом, вектор (/,, 0) удовлетворяет обоим условиям в (65).
Таким образом, для любого 0, достаточно близкого к, для единственного решения ((), ()) системы (65) обязательно выполнено () = 0, откуда следует () ker ().
Наконец, применяя классическую теорему о неявной функции к системе (65) в точке (, ) = (, 0) и при значении параметра, равном, получаем, что отображение ((·), (·)) является аналитическим в некоторой окрестности. В частности, () = 1 при. Таким образом, заменив (·) на (·)/(·), получаем корректно определенное отображение, которое является аналитическим в окрестности и удовлетворяет ()() = 0 для всех 0, достаточно близких к, и при этом () = 1 для всех в окрестности.
Остается заметить, что dim ker () = 1 для всех таких 0 (что следует, например, из непрерывности собственных значений симметричных матриц). Таким образом, построенное отображение (·) обладает всеми необходимыми свойствами.
Очевидно, что из условия (64) следует, что ядро матрицы () содержит ровно два различных вектора единичной нормы. В дальнейшем анализе зафиксируем один из этих векторов, обозначим его через и определим отображение (·) согласно предыдущей лемме.
Подчеркнем, что проводимый анализ не зависит от выбора.
Для произвольной квадратной матрицы обозначим через ее присоединенную матрицу. Напомним, что для любой квадратной матрицы справедливо тождество Пусть условие (64) выполнено для некоторого 0. Тогда найдется > и аналитическая функция : (, ) IR {0}, удовлетворяющая соотношению где отображение (·) определено согласно лемме 4, и () рассматривается как векторстолбец.
Доказательство.
0 выполнено ()() = 0, и поэтому Отсюда, в частности, следует, что rank () 1 при условии, что достаточно близко к, поскольку dim ker () = 1 для таких. Более того, из последнего условия также следует существование ненулевого минора размера ( 1) ( 1) у матрицы (). Поэтому у матрицы () имеется ненулевой элемент, откуда следует rank () = 1. С учетом данного условия, из (69) следует, что для всех 0, достаточно близких к, выполнено С учетом определения (·), отсюда вытекает существование разложения () = ()(())T при некотором () IR. Из последнего равенства, с учетом симметричности матрицы (), получаем также равенство () = ()(())T, из которого, согласно (70), следует () ker (). Таким образом, () = ()() для некоторого действительного числа (), что, в свою очередь, означает, что () = ()()(())T. В частности, что означает выполнение (68) для функции : (, ) IR, определенной согласно последнему соотношению при достаточно малом > 0.
Для завершения доказательства остается заметить, что функция является аналитической в окрестности (, ) (поскольку отображение (·) также аналитично в этой окрестности, а (·) содержит полиномиальные элементы), а также что () = 0 (поскольку в противном случае было бы выполнено () = 0, что противоречит (64)).
Пусть условие (64) выполнено для некоторого 0. Тогда для некоторого > 0 справедливо разложение где отображение (·) определено согласно лемме 4, а функция (·) определена согласно лемме 5.
Доказательство.
(, ) при достаточно малом > 0 и для любого IR справедлива следующая цепочка равенств:
(здесь также использовались определения отображений (·) и (·)). Таким образом, Далее, согласно (68), и поэтому правая часть в (72) есть (), откуда следует (71).
рицы IR выполнено соотношение где представляет собой совокупность всех подмножеств длины множества {1,..., }, и для любого матрица (,, ; ) IR состоит из строк следующего вида:
Доказательство.
и единственным элементом является множество {1,..., }.
Пусть теперь <. Дважды применяя формулу Бине–Коши, находим Далее, применяя формулу для минора обратной матрицы (см., например, [2, пункт 4.70]), получаем где Таким образом, где последнее равенство следует из разложения Лапласа для определителя.
Используя обозначения из леммы 7, определим функцию : IR IR IR IR, Очевидно, эта функция полиномиальна относительно элементов матриц, и. Для следующей леммы понадобится новое предположение:
Легко убедиться, что из данного свойства, в частности, следует Пусть условие (64) выполнено для некоторого 0. Пусть также выЛемма 8.
полнено (74) для некоторого вектора ker () единичной нормы.
Тогда найдется > 0 такое, что матрица [](())1 ([])T невырождена для всех (, ) и всех (, ) 0. Более того, существует аналитическое отображение : (, ) (, ) IR, удовлетворяющее условию Доказательство.
невырожденность матрицы [](())1 ([])T мгновенно следует из леммы 7, предположения (74) и непрерывности функции.
: IR(1) IR(1) IR IR, Очевидно, эта функция также полиномиальна относительно элементов матриц, и.
Обозначим = {1,..., }. Применяя правило Крамера для вычисления обратной матрицы, получаем для произвольной пары индексов, следующую цепочку равенств:
где последнее равенство следует из леммы 7, если применить ее и к числителю, и к знаменателю.
Далее, из предположения (74) и непрерывности следует, что для любого вектора (, ) IR IR, достаточно близкого к (, ), выполнено ([], [], ()) = 0, и поэтому можно определить матрицу (, ) IR следующим образом:
С учетом полиномиальности функций и можно заключить, что построенное отображение является аналитическим в окрестности (, ), и поэтому обладает всеми необходимыми свойствами.
Предположим теперь, что = 1. В этом случае и поэтому, определив : IR IR IR, и проведя аналогичные рассуждения, легко убедиться, что функция является аналитической и обладает всеми необходимыми свойствами.
Пусть условие (64) выполнено для некоторого 0. Пусть также выЛемма 9.
полнено (74) для вектора = (), где отображение (·) определено согласно лемме 4.
Тогда найдется > 0, для которого справедливо где выражение в левой части корректно определено первым соотношением в (62).
Доказательство.
множитель 0 (, ) и введем обозначение = (). Из непрерывности отображения (·) и из леммы 8 следует, что выражение (, ) корректно определено первым соотношением в (62) и является единственным решением линейной системы относительно IR. Заметим, что откуда немедленно следует, что = удовлетворяет системе (77). Это и означает справедливость (, ) =.
Следствие 1.
выполнено (74) для вектора = (), где отображение (·) определено согласно лемме 4.
Тогда найдутся > 0 и > 0, для которых справедливо где (, ) корректно определено первым соотношением в (62).
Доказательство.
корректно определить отображение : (, ) (, ) IR, (, ) = (, )[, ], удовлетворяющее условию Липшица с некоторой константой > 0. При этом из (62) следует, что (, ) = (, ) для всех (, ) (, )((, )0 ). Уменьшая в случае необходимости и применяя лемму 9 для любых таких и и для любого 0 (, ), получаем соотношение > 0 и > 0, для которых справедливо где отображение (·) определено согласно лемме 4.
Предположим, что утверждение неверно: существует последовательность Доказательство.
{ } действительных чисел и последовательности { } IR и { } 0 такие, что 0, { }, { }, и при этом для всех вектор ( ) корректно определен, = 1, и выполнено ( ) < ( ). Таким образом, = ( ) для всех, и справедливо lim ( ) / ( ) = 0, откуда следует Для каждого введем обозначение = ( ( ))/ ( ). Заметим, что справедлива следующая цепочка равенств:
С учетом предельных соотношений { } и {( )} () =, а также условия = 1, получаем Таким образом, для любой предельной точки ограниченной последовательности { } выполнено, () = 0, что, в свою очередь, эквивалентно (ker ()). С другой стороны, из (79) следует ker (), что возможно только при = 0, и поэтому противоречит Для следующего результата об оценке расстояния потребуется еще одно предположение Пусть условие (64) выполнено для некоторого 0. Пусть также Лемма 11.
выполнено (80) для некоторого вектора ker () единичной нормы.
Тогда найдутся > 0 и 1, 2 > 0, для которых справедлива следующая оценка расстояния:
Первая оценка в (81) немедленно следует из липшицевости полиномиДоказательство.
альной функции на ограниченных множествах. Вторая оценка в (81) следует из свойства которое, в свою очередь, следует из предположения (80) и леммы 6.
Определим множество Очевидно, Пусть условие (64) выполнено для некоторого 0. Пусть также Лемма 12.
выполнены условия (74), (80) для вектора = (), где отображение (·) определено согласно лемме 4.
Тогда найдется такое > 0, что для любого 1 > 0 найдется 2 > 0 со следующими свойствами: для любого вектора (, ) (, ) ((, ) 0 ), удовлетворяющего неравенству где (, ) корректно определено первым соотношением в (62), и для любого [0, 1] справедливы соотношения Доказательство.
лемм 4–6, 8 и 11, следствия 1, а также чтобы условие было выполнено для некоторой константы > 0 (возможность выбрать, удовлетворяющее последнему свойству, следует из (80)). Далее, выберем константу (0, ) таким образом, чтобы оценка (, ) была справедлива для всех (, ) (, ) ((, ) 0 ) (возможность выбрать такое вытекает из следствия 1). Рассмотрим произвольный вектор (, ) (, ) ((, ) 0 ) со свойствами, заданными в условии леммы, и произвольную константу [0, 1]. Обозначим через (, ) проекцию вектора (, ) на множество. Очевидно, что, уменьшая в случае необходимости, можно обеспечить выполнение условий (, ) (, ) (, ) и для любого (, ) (, ) ((, ) 0 ).
Обозначим для краткости = (, ), = /() и =. Условие (83) означает, что 1. Из леммы 11 следует и поэтому, согласно (83), для 3 = 1 + 1 /1. Заметим, что из выбора следует (, ).
Очевидно, градиент функции удовлетворяет условию Липшица с некоторой константой 4 > 0 на множестве (, ), и поэтому, используя (88), получаем Аналогично, функция (·) липшицева с некоторой константой 5 > 0 на множестве (, ), и поэтому Наконец, для некоторой константы 6 > 0 выполнены условия Подчеркнем, что для любого > 0 константы 4, 5 и 6 могут быть выбраны независимо от (, ) и (, ).
Далее, используя леммы 5, 6 и соотношение (87), получаем следующую цепочку равенств:
· ( ())T = () · (())T ([()])T = () С учетом оценок (89)–(92), отсюда находим (Напомним, что спектральная норма матрицы совпадает с евклидовой нормой в случае, когда матрица состоит из одного столбца или одной строки; также напомним, что спектральная норма транспонированной матрицы совпадает со спектральной нормой самой матрицы.) Чтобы получить неравенство (84), остается положить 2 = 2 max{6 +2, (3 4 +5 )6 }. Заметим, что константа 2 зависит только от и 1, и не зависит от векторов (, ) и (, ).
Теперь докажем неравенство (85). Из первого соотношения в (62) и из леммы 8 следует, что корректно определяется равенством [](())1 ([])T = [, ], из которого, в свою очередь, следует []()([])T = [, ], и поэтому Применяя оценки (84), (86), а также первое неравенство в (92), получаем цепочку неравенств последнее из которых следует из определения и из оценки (83).
Для завершения доказательства остается переопределить как, а также заменить на 1 2 6 /, если это произведение больше, чем 2.
Пусть условие (64) выполнено для некоторого 0. Пусть также выполнены условия (74), (80) для вектора = (), где отображение (·) определено согласно лемме 4.
Тогда найдется такое > 0, что для любой константы 1 > 0 и произвольных последовательностей { } (, ) и { } (, ) 0, удовлетворяющих предельным соотношениям { } () и { } для некоторого 0, а также для всех неравенству где = (, ) корректно определено первым соотношением в (62), выполнены следующие соотношения:
где = /2. Более того, существует константа 2 > 0 и последовательность { } 0, для которой справедливо предельное соотношение { }, и для всех достаточно больших имеют место следующие оценки:
где причем справедливы неравенства (, ) = 0 и ( ) = 0, первое из которых корректно определено вторым соотношением в (62).
Зафиксируем > 0 таким образом, чтобы были выполнены утверждеДоказательство.
ния лемм 10–12 и следствия 1. Выберем произвольную константу (0, ) и рассмотрим произвольные последовательности { } (, ) и { } (, ) 0 со свойствами, указанными в условии леммы. Условие (93) означает, что последовательность { } ограничена, откуда следует { } 0 и { }.
Действительно, из теоремы о среднем вытекает существование последовательности { } [0, 1], для которой справедлива цепочка равенств Применяя соотношение (85) в лемме 12, получаем требуемое свойство (99) при 3 = 2 /2.
Заметим, что из (99) сразу же следует (94), и, в частности, ( ) = 0 для всех достаточно больших.
Далее, из теоремы о среднем также следует существование последовательности { } [0, 1], для которой выполнено Вновь применяя соотношение (85) в лемме 12, получаем Таким образом, из второй оценки в (81) из леммы 11 следует, что для всех достаточно больших выполнено (поскольку (, ) для таких ), откуда немедленно следует существование последовательности { } 0, удовлетворяющей (96), если переопределить 2 как 2 2 в случае, когда последнее больше чем 2. Поскольку { } и { } 0, из (96) следует { }.
Для краткости введем обозначения = ( ), = ( ), = (, ) для всех.
Покажем, что существует константа 4 > 0, для которой выполнено неравенство Действительно, из второго соотношения в (62), с учетом определения, получаем и поэтому Поскольку последовательности { } и { } ограничены, из леммы 12 сразу же следует оценка (100) при некотором 4 > 0. Отметим, что из (100) также следует (95), и, в частности, = для всех достаточно больших.
Теперь покажем, что оценка (97) выполняется для указанной выше последовательности { }. Заметим, что =, и поэтому где = ( )(= det ). Введем еще одно обозначение = ( ). Тогда, по определению, получаем Поскольку последовательность { } ограничена, из (95) следует существование константы 5 > 0, для которой для всех достаточно больших выполнены неравенства Объединяя (101) с (96) и (100), получаем при 6 = (2 + 4 )5. Наконец, из (95) и сходимости { } к следует, что для достаточно больших выполнено (, ) и (, ), откуда по лемме 10 получаем оценку ( ). Комбинируя ее с неравенством (102), получаем цепочку неравенств которая представляет собой оценку (97), если переопределить 2 как 6 /.
Остается доказать оценку (98). Применяя (96) к тождеству находим Далее, из тождества (103) и условий (93), (96) также следует, что для некоторого > 0 и для всех достаточно больших справедливо /| | 1 /2 +. Кроме того, из (94) легко получить, что для всех достаточно больших выполнено где введено обозначение = ( )(= det ( )). Комбинируя две последние оценки с (99), получаем где 7 = (1 /2 + )(2 + )3. Наконец, согласно следствию 1, для всех достаточно больших выполнено откуда, с учетом определения и свойств (97), (105), легко получить где 8 = 2 (2 + ). Из (104), (106) и (107) теперь выводим для всех достаточно больших. Переопределяя 2 как 22 + 27 + 8, получаем оценку (98).
Для завершения доказательства остается переопределить как.
Вообще говоря, константа 2 в данной лемме не обязательно должна быть одинаковой для различных последовательностей { }, { }. Однако, приводимое ниже следствие показывает, что эту константу можно выбрать независимо от последовательностей.
и 2 > 0, что для всех (, ) (, ) ((, ) 0 ), удовлетворяющих (83), где (, ) корректно определено первым соотношением в (62), выполнены следующие соотношения:
где причем (, ) = 0, где (, ) корректно определено вторым соотношением в (62).
Доказательство.
противного, из соотношений (94), (95) и (98) в лемме 13 легко получить существование таких > 0 и 2 > 0, что условия (108), (109) и неравенство (, ) = 0 будут выполнены для Зафиксируем константы 1 > 0, 2 > 0. Из соотношений (96) и (97) в лемме 13 следует, что, уменьшая > 0 при необходимости, можно для любых (, ) и (, ) 0, удовлетворяющих (83), гарантировать существование множителя 0, для которого выполнено Используя определение и условие (83), отсюда получаем Поэтому из второго неравенства в (113) вытекает которое совпадает с (110), если положить 2 = 1 + 2 + 1 /2.
Наконец, из (83) и первого неравенства в (113) имеем и поэтому (1 + 1 )|()|, откуда, в свою очередь, следует Данная оценка позволяет заключить, что при, и поэтому для любого заданного > 0 с помощью выбора можно гарантировать, что (, ). Поскольку отображение (·) является аналитическим, существует константа 3 > 0, для которой выполнено при условии, что константа > 0 достаточно мала для того, чтобы отображение () было корректно определено. Комбинируя последнее неравенство со вторым неравенством в (113), а также с (114), находим Согласно лемме 11, если > 0 достаточно мало, то и поэтому из (115) следует (111) при 2 = ((1 + 1 )3 + 2 )/1 + 3.
Предложение 4.
любого > 0 найдется такая константа 0 (0, ), что для любой начальной точки ( 0, 0 ) (, 0 ) ((, 0 ) 0 ), удовлетворяющей где ( 0, 0 ) корректно определено первым соотношением в (62), итерационная схема где (, ) и (, ) вводятся согласно (62), генерирует корректно определенную траекторию {(, )} (, ) ((, ) 0 ); данная траектория сходится к ((* ), * ) для некоторого множителя * 0 и для всех удовлетворяет соотношению и выполнено для некоторого IR, удовлетворяющего Доказательство.
> 0. Зафиксируем (0, 1/2) и положим 1 = 1/2, 2 = 1/2 +. Согласно следствию 2, уменьшая при необходимости > 0, можно выбрать 2 > 0 таким образом, что для всех (, ) и (, ) 0, удовлетворяющих (83), будут справедливы соотношения (108)–(111), где и корректно определяются условием (112), и, в частности, (, ) = 0.
Более того, уменьшая при необходимости > 0 и увеличивая 2 > 0, можно гарантировать, что < 1, выполнено утверждение леммы 12, и для всех 0 (, ) справедливо dim ker () = 1, () корректно определено леммой 4 и () < 1. Наконец, выберем константу 0 (0, ) таким образом, чтобы следующие неравенства были выполнены для любого множителя 0 (, 0 ) 0 :
Доказательство проведем по индукции. Предположим, что вектор ( 0, 0 ) (, 0 ) ((, 0 ) 0 ) (, ) ((, ) 0 ) удовлетворяет (116), и для некоторого неотрицательного числа векторы (, ) корректно определены соотношениями Тогда, согласно следствию 2, вектор ( +1, +1 ) (совпадающий с (, ) для = и = ) корректно определен соотношением (117). Более того, с учетом (108)–(111), получаем для всех = 0, 1,...,, где введено обозначение = (, )/( ).
Очевидно, из (126) следует оценка В частности, (+1 ) = 0, откуда следует +1 0. Комбинируя (130) со вторым соотношением в (124) и с неравенством (125) и принимая во внимание (122), получаем для всех = 0, 1,..., + 1, и, в частности, Из предпоследнего неравенства в (131) и из (122), (129) далее находим Наконец, из соотношений (127), (128) и (130) выводим (116), (123) получаем Комбинируя (132)–(134) и используя определение +1, можно заключить, что ( +1, +1 ) (, ) ((, ) 0 ), и соотношение (125) выполнено для = + 1.
Приводимое выше рассуждение показывает, что итерационная схема (117) генерирует корректно определенную траекторию {(, )} (, ) ((, ) 0 ), удовлетворяющую неравенству (118) (для всех ) и неравенствам (126)–(129) (и, следовательно, (130), для всех ). Докажем теперь, что эта траектория сходится к точке ((* ), * ) для некоторого множителя * 0. Действительно, для любых неотрицательных чисел и, используя (122), второе соотношение в (124), а также (125) и (130), получаем Таким образом, последовательность { } (, ) является фундаментальной, и поэтому она сходится к некоторому множителю * (, ).
Далее, согласно первому соотношению в (117), для всех = 1,... выполнено = 1, и поэтому у последовательности { } (, ) есть предельная точка (, ), = 1.
Из свойства (130) следует предельное соотношение lim ( ) = 0, и поэтому, переходя в неравенстве (128) к пределу вдоль соответствующей подпоследовательности, получаем (, * ), откуда следует * 0 и ker (* ). Равенство dim ker (* ) = 1 позволяет заключить, что совпадает либо с (* ), либо с (* ). Однако, из неравенства (* ) < 1 следует и поскольку < 1, то (, ) не может совпадать с (* ). Таким образом, = (* ).
В частности, (* ) является единственной предельной точкой последовательности { }, т. е., Покажем теперь, что последовательность { } сходится. Действительно, из соотношений (127), (128), (130) легко получить, что для любых положительных чисел и справедлива цепочка неравенств где последнее неравенство следует из (123). Таким образом, последовательность { } является фундаментальной, и поэтому она сходится к некоторому вектору IR. Очевидно, из (118) следует 1. Более того, используя оценку (85) в лемме 12, получаем и, в частности, = 0.
Теперь докажем соотношения (119) и (120). Как следует из условия (94) в лемме 13, для любого (0, 1/2) справедливо для достаточно больших. Заново обозначим 1 = 1/2, 2 = 1/2 +. Тогда из (136) следует, что для любых таких и любого неотрицательного числа выполнено Отсюда далее получаем Заметим, что из второго соотношения в (117) следует и поэтому, Таким образом, поскольку для всех достаточно больших, то из (137) и (138) получаем Переходя к пределу при, получаем, что для всех достаточно больших выполнено где также были приняты во внимание определения 1 и 2. Учитывая произвольность выбора, заключаем, что Из этого соотношения, очевидно, следует и поэтому (119) сразу же следует из (136) (напомним, что последнее соотношение справедливо для произвольного > 0 для всех достаточно больших ).
Сформулируем теперь основной результат данного раздела, который легко следует из предложения 4, равенства (которое легко получить из первого соотношения в (63)) и из условия (, ) (которое следует из (95) в лемме 13).
Пусть выполнено условие (64) для некоторого 0, а также условия (74), (80) для некоторого ker( + ).
Тогда для любых 0 > 0 и 1 > 0, 0 < 1, и для любого > 0 найдется такая константа 0 (0, ), что для любой начальной точки (0, 0 ) (IR {0}) ((, 0 ) 0 ), удовлетворяющей 0 /0 (, 0 ) и где (0 /0, 0 ) корректно определено первым соотношением в (62), существует единственная траектория {(, )} (IR {0}) ((, ) 0 ), удовлетворяющая (58) для всех = 0, 1,...; эта траектория сходится к (0, * ) для некоторого множителя * 0, последовательность { / } (, ) сходится к некоторому * ker( + * ), и свойства (119), (120) выполнены для некоторого IR, удовлетворяющего неравенству (121) (из которого, в частности, следует, что вектор не является касательным к в точке * ).
Утверждение данной теоремы, в частности, означает, что ( *, * ) (, ), если (0 /0, Заметим, что поведение, наблюдаемое в примере 4 (например, продемонстрированное на рис. 4) не противоречит теореме 1. Дело в том, что последовательность { / } остается отделенной от = () = ±(10, 5, 3)/ 134, что, в свою очередь, не дает двойственной траектории сходиться к единственному критическому множителю = 5, в котором выполнены предположения (64), (74) и (80). Такое поведение возможно, если 0 /0 не достаточно близко к.
Начальная часть траектории, показанной на рис. 5, также свидетельствует о том, что 0 /0 должно быть достаточно близко к для того, чтобы имело место утверждение теоремы 1. Более того, согласно полученному вычислительному опыту, близость 0 /0 к играет наиболее важную роль для сходимости двойственной траектории к критическому множителю в окрестности.
Следующий пример показывает, что предположение (140), ограничивающее множество начальных точек, также нельзя опустить.
(Пример 2.2 из [67], тест 20301 из коллекции DEGEN [42].) Рассмотрим задачу оптимизации Здесь () = 2(1 1 )(4 42 2 ), и поэтому критическими являются множители IR2, для которых 1 = 1 или 42 + 2 = 4 (вертикальная линия и эллипс на рис. 7).
Несложно убедиться в том, что предположения (64), (74) и (80) выполняются для всех критических множителей IR2, кроме тех, для которых выполнено 1 = 1, и для всех векторов ker () единичной нормы. (Если = (1, 0), то dim ker () = 2. Если же 1 = 1, 2 = 0, то ker () натянуто на вектор = (0, 1, 0), но при этом rank [] = 1, а значит (74) не выполняется.) Рассмотрим, например, множитель = (0, 2) и вектор = (1/ 2, 0, 1/ 2) ker () и возьмем произвольный множитель 0 IR2 из эллипса 4(0 )2 + ( +2) = 16. Заметим, что среди таких существуют сколь угодно близкие к, а также что для любого 0 > 0 неравенство (116) не выполняется для 0 = при условии, что множитель 0 достаточно близок к. Далее, легко проверить, что (, 0 ) = (0, 0 2), и поэтому 1 = критическим, а значит утверждение теоремы не выполнено (см. рис. 7(а)). В частности, выражение (1 /1, 1 ) не является корректно определенным, и представленный выше анализ неприменим.
В то же время, предположение (140) на самом деле не является слишком ограничивающим. Действительно, следующее утверждение показывает, что если 0 достаточно мало, то условие (116) при некотором 0 > 0 выполнено для всех 0 (, 0 ) и для всех 0 из (, 0 ) 0, кроме «узкого» множества вокруг 0.
(0, 1) существует константа 0 > 0, обладающая следующими свойствами: для любого 0 (0, ] условие (116) выполнено для всех ( 0, 0 ) (, 0 ) (, 0 ), для которых dist(0, 0 ) Доказательство.
утверждения леммы 11 и следствия 1. Как следует из (78), для всех (, ) (, )((, ) 0 ) выполнено и поэтому Применяя второе неравенство в (81), далее получаем Таким образом, для любого (0, 1), если ( 0, 0 ) (, 0 ) (, 0 ) и dist(0, 0 ) для некоторого 0 (0, ], то где константа 0 = 2 (1 + )/ не зависит от 0 и ( 0, 0 ).
Из теоремы 1 и предложения 5 следует, что для любого (0, 1) найдется такая константа 0 > 0, что для любой начальной точки (0, 0 ) (IR {0}) (, 0 ), удовлетворяющей 0 /0 (, 0 ) и dist(0, 0 ) 0, рассматриваемый метод сходится к критическому множителю.
Отметим также, что условие (140) в теореме 1 можно опустить, если в рассматриваемой задаче есть только одно ограничение, т. е. если = 1. Действительно, в этом случае из первого равенства в (62) и из (76) следует, что для всех (, ) и ((, ) 0 при условии, что > 0 достаточно мало. Таким образом, из предположения (74) следует существование таких констант 0 > 0 и 0 > 0, что условие (116) выполнено для всех ( 0, 0 ) (, 0 ) ((, 0 ) 0 ).
Другое интересное наблюдение состоит в том, что предположение (74) также можно опустить в случае = 1. Действительно, в этом случае для любых IR и IR {0} выполнено и поэтому свойством, необходимым для доказательства леммы 8, является не (74), а лишь []()([])T = 0. С учетом равенства () = () T (которое следует из леммы 5), требуемое свойство эквивалентно (80).
Однако, предположение (74) нельзя опустить в общем случае: без него нельзя гарантировать невырожденность матрицы в левой части системы (58). Действительно, рассмотрим произвольную задачу оптимизации, в которой одно из ограничений тождественно равно нулю. Ясно, что предположения (64) и (80) вполне могут быть выполнены, однако rank [] <, и поэтому (74) нарушается. В этом примере матрица в левой части системы (58) всегда содержит нулевую строку. Следовательно, решение данной системы определяется не единственным образом, а значит двойственная траектория вовсе не обязана сходиться. В частности, утверждение теоремы 1 в этом случае не выполнено.
Заметим далее, что два предположения (64), (80) на самом деле эквивалентны условию (82). Действительно, если выполнено (64), то из леммы 6 следует, что (82) эквивалентно (80).
Таким образом, достаточно показать, что из (82) следует (64). Для этого, в свою очередь, достаточно показать, что для любых матриц, IR, где dim ker 2, выполнено Если матрица невырождена, то dim ker 1 2, а значит нулевое собственное значение матрицы 1 имеет кратность не меньше 2. Таким образом, det( 1 ) = (2 ), откуда Если же матрица вырождена, рассмотрим произвольную последовательность { } IR невырожденных матриц, сходящуюся к (очевидно, такая последовательность всегда существует). Тогда, согласно сказанному выше, для всех. Переходя к пределу, вновь получаем (141).
Возвращаясь к примеру 6, рассмотрим критические множители, для которых 1 = 1.
Предположения (64) и (80) (или, что то же самое, (82)) выполнены для всех таких множителей за исключением (1, 0). Однако для любого множителя = (1, 2 ), где 2 = 0, выполнено 1 для = (0, 1, 0) ker (), и поэтому предположение (74) нарушается для rank [] таких. Более того, предположение (64) (и, следовательно, (82)) нарушается для = (1, 0), поскольку dim ker () = 2. При этом, если рассматривать начальные точки (0, 0 ), для которых (0 /0, 0 ) достаточно близко к {(0, 1, 0)} ({1} IR), то двойственные траектории во многих случаях будут сходиться к = (1, 0), а не к критическому множителю, близкому к 0. Пример такого поведения показан на рис. 7(б) (где 0 = (0.1, 1.1, 0.1) и 0 = (1.2, 1.8)).
Таким образом, критические множители большей «кратности» (т. е. те, для которых нарушается (64) и, следовательно, (82)) притягивают двойственные траектории даже сильнее, чем другие критические множители.
В завершение отметим, что предположения (64), (75), (80) обычно выполнены «практически для всех» критических множителей. При этом не удалось найти ни одного примера, в котором выполнены предположения (64), (75), (80), но при этом нарушается (74). Поэтому гипотеза состоит в том, что в случае выполнения (64) и (80) условие (74) на самом деле эквивалентно (75).
1.3. Локальная двойственная стабилизация В предыдущих разделах было показано, что эффект притяжения двойственных траекторий к критическим множителям является крайне типичным для метода последовательного квадратичного программирования: двойственные траектории метода двигаются практически параллельно множеству множителей, постепенно приближаясь к критическим множителям.
Данный раздел посвящен обсуждению двух методов, обладающих свойством локальной двойственной стабилизации, т. е. способностью подавлять эффект притяжения к критическим множителям: стабилизированного метода последовательного квадратичного программирования и метода модифицированных функций Лагранжа. Для этих методов эффект притяжения значительно менее выражен: существуют широкие области, из которых метод сходится сверхлинейно, и при этом двойственная траектория сходится к некритическому множителю.
1.3.1. Стабилизированный метод последовательного квадратичного программирования Стабилизированный метод последовательного квадратичного программирования (sSQP, от англ. Stabilized sequential quadratic programming) был изначально введен в [93] для задач с ограничениями-неравенствами и состоял в решении последовательности минимаксных подзадач. Позднее было показано, что такие минимаксные подзадачи эквивалентны задачам квадратичного программирования в прямо-двойственном пространстве (см. [81]), и что метод применим также к задачам с ограничениями-равенствами.
Итерация метода заключается в следующем. Для текущего приближения (,, ) IR IR IR вычисляется направление (,, ) IR IR IR как стационарная точка задачи квадратичного программирования где — параметр стабилизации, и следующее приближение полагается равным ( +, +, +). При отсутствии ограничений-неравенств итерацию можно записать в более простом виде: для текущего приближения (, ) IR IR вычисляется решение (, ) IR IR системы и следующее приближение полагается равным ( +, + ). В этом случае метод также называют стабилизированным методом Ньютона–Лагранжа (СМНЛ), поскольку система (143) отличается от системы (16) метода Ньютона–Лагранжа только наличием стабилизирующего члена во втором уравнении.
Одно из сильных свойств данного метода состоит в том, что для сверхлинейной локальной сходимости не требуется выполнение условий регулярности ограничений. Данное свойство устанавливается приводимой ниже теоремой 2, которая представляет собой результат из [48, теорема 5] с некоторыми улучшениями, которые могут быть получены из доказательства в [50, теорема 1] или [64, теорема 4.1]; см. также [72, глава 7].
в окрестности точки IR, а их вторые производные непрерывны в этой точке. Пусть — стационарная точка задачи (1), и пусть для отвечающего ей множителя Лагранжа (, ) IR IR выполняется SOSC (7). Пусть : IR IR IR IR+ — произвольная функция, для которой справедливы оценки расстояния для некоторых 1, 2 > 0 и для всех (,, ), достаточно близких к (,, ).
«