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

• Автор: Усков, Евгений Иванович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 211 с. : ил.

Оглавление
Введение

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

Глава 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. Эксперимент с правилами для параметра штрафа: критические множители и
скорость сходимости
А.З. Эксперимент с правилами для параметра штрафа: общая эффективность . . .
А.4. Эксперимент с ускорителями
Приложение В. Численные результаты для стабилизированного метода последовательного квадратичного программирования
Б.1. Гибридная глобализация сходимости
Б.2. Глобализация сходимости с помощью модифицированных функций Лагранжа
Б.З. Глобализация сходимости с помощью точных гладких штрафных функций . .
Приложение В. Численные результаты для метода последовательного квадратичного программирования, стабилизированного вдоль подпространства
Заключение
Список литературы

Введение
В существующей литературе по теории и численным методам оптимизации основное внимание традиционно уделяется задачам, в решениях которых выполнены так называемые условия регулярности ограничений. Такие задачи достаточно подробно изучены, в частности, разработаны эффективные численные методы отыскания их решений, для которых обоснована глобальная сходимость и сверхлинейная скорость сходимости.
Вместе с тем, большой интерес представляют задачи, в решениях которых условия регулярности ограничений могут нарушаться, и их изучению посвящена данная работа. С такими задачами связан ряд серьезных теоретических трудностей (например, не гарантируется устойчивость решения по отношению к малым возмущениям входных данных). Более того, численное отыскание решений в таких задачах весьма проблематично и требует специальных подходов. В частности, многие традиционные методы оптимизации обычно демонстрируют невысокую эффективность па таких задачах.
Недавно было показано, что основной причиной низкой эффективности ньютоновских методов на нерегулярных задачах является эффект притяжения двойственных траекторий к так называемым критическим множителям Лагранжа. Эти множители обычно образуют тощее подмножество множества всех множителей Лагранжа, однако именно к ним обычно сходятся двойственные траектории ньютоновских методов, причем скорость сходимости прямой траектории в таких случаях оказывается в лучшем случае линейной. На сегодняшний день описанный эффект изучеп весьма мало, и поэтому ему будет уделено значительное внимание в данной работе.
Отметим, что в недавнем прошлом активно разрабатывались эффективные и устойчивые методы поиска особых решений общих систем нелинейных уравнений (см. [14], а также более поздние работы [3,5-7]). К сожалению, эффективное использование таких методов для решения нерегулярных задач оптимизации (например, путем применения их к системе Лагранжа или системе Ф. Джона) возможно только в очень обременительных предположениях, в связи с чем такой подход имеет весьма ограниченную область применения [15].
Еще одна причина интереса к нерегулярным задачам, помимо связанных с ними теоретических и практических трудностей, заключается в наличии важных практических при-

(46). Если же р > 2, р ф 3, то выполнены условия предположения 3 при ад = «2 = Р ~ 2, 72 = ар(р — 3) и 71 = (—1)р72, вследствие чего должно выполняться (49) при и 6 {1, р — 2). Согласно (16), имеем:
(ар(р - 1)ж£-2 + q(q - 1)Хкх1~г)(хк+1 - хк) + qxgk~1(Xk+1 - к) = -арх^'1 - qxчk~1,
ЯхГ1{хк+1 - хк) = ~х
для каждого к. Предполагая, что хк ф 0, из второго уравнения получаем
%к+1 = Хк' (51)
и тогда из первого уравнения, после несложных преобразований,

Таким образом, последовательность {хк} сходится к 0 с линейной скоростью, но 1/2 в правой части (30) нужно заменить на 1 — l/g ^ 1/2.
Поведение двойственной траектории зависит от значений обоих параметров р и q. Если р < q, то Лі —> оо. Действительно, в этом случае уравнения (51) и (52) имеют вид
хк+і = вхк, Afc+1 = вк + 7хка, (53)
где 0 < в < 1, 7 ф 0 и а > 0. Отсюда следует, что
мхам = в1+акх<£ + 70". (54)
Поскольку 0 < 01+а < 1, то из последнего условия легко получить Хкхк —>■ 70“/(1 — 01+а),
откуда, в свою очередь, следует А*, -> оо.
Если р = q, то равенство (52) можно переписать в виде
Ajfc+i + а — ^1 — —^ (At + а).
Отсюда следует, что {Ац} сходится к Ä = —а, причем, если А0 Ф X, то Хк ф —а для всех к, и
lim = 1 — i. (55)
к-юо А*, — А q
Если же р > q, то, применяя [1, лемма 2.6.6], получаем, что {Ai} сходится к 0. Очевидно, что если при этом р — q + 1, то (52) принимает вид

и поэтому, если А0 ф 0, то Ai / 0 для всех к, и выполняется (55) при А = 0. Для того, чтобы установить скорость сходимости при р ф q + 1, вновь перепишем (51) и (52) в виде (53), где