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

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

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

УСКОВ ЕВГЕНИЙ ИВАНОВИЧ

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

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

АВТОРЕФЕРАТ

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

з о окт

2014

Москва 2014

005554035

005554035

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

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

профессор

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

Официальные оппоненты: доктор физико-математических наук,

Березнев Валентин Александрович;

кандидат физико-математических наук, Павлова Наталья Геннадиевна.

Ведущая организация: Институт динамики систем и теории

управления Сибирского отделения Российской академии наук.

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

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

Автореферат разослан 17 октября 2014 г.

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

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

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

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

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

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

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

Методы исследования. При выполнении диссертационного исследования использовались средства нелинейного анализа, линейной алгебры,

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

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

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

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

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

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

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

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

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

Апробация результатов. Результаты, полученные в диссертации, были представлены на XXI международном симпозиуме по математиче-

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

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

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

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

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

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

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

f(x) min, h(x) — 0, д(х) < 0, (1)

где /: ГО™ —>• И — гладкая функция, a h: IR" IR1 и д: IRn IRm — гладкие отображения. Система Каруша-Куна-Таккера (ККТ) задачи (1) имеет вид dL

—(х, Л, ß) = 0, h{x) = 0, 0, s(i)<0, <Д, д(х» = 0, (2)

где L: П1" х Ш,' х IRm —> IR — функция Лагранжа задачи (1). Если тройка (х, Л, Д) е IR" х 1R1 х IRm удовлетворяет системе (2), то х называется стационарной точкой задачи (1), а (Ä, ß) — отвечающим ей множителем Лагранжа. Обозначим через М{х) множество всех множителей Лагранжа, отвечающих х. Введем также множества индексов

А{х) = {г = 1, ..., т | 9i{x) = 0}, N(x) = {1, ..., m} \ А{х), А+{х, ß) = {г £ А(х) | ßi > 0}, А0(х, ß) = {г е А(х) | ßi = 0}.

Множитель Лагранжа (Л, ß) € М{х) называется критическим, если существует набор (£, г), С) € IR" х IR1 х IRm такой, что £ ^ 0, и выполнены соотношения

Я2 г

Л, fl)t + (А'(2))т„ + (</(*))ТС = 0, АШ = 0, Сл„(х,р) > о, Зл0(г,д)(*К < 0, 0 = 0, i G А0(х, ß),

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

демонстрирующих, что двойственные траектории метода последовательного квадратичного программирования (БС^Р) имеют сильнейшую тенденцию притяжения к критическим множителям, причем данный эффект является причиной медленной прямой сходимости. Напомним, что на каждой итерации метода БС^Р для текущего приближения (х, А, 6 Н" х Ж' х Лт вычисляется направление £ е К" как стационарная точка задачи квадратичного программирования

и следующее приближение полагается равным (х + у, г), где у е Н' и г € Н™ — множители Лагранжа, отвечающие стационарной точке £ подзадачи (3).

В разделе 1.2 впервые доказываются априорные результаты о сходимости двойственных траекторий метода БС^Р к критическим множителям Лагранжа. Обоснование данного эффекта представляет собой трудную теоретическую проблему. В частности, все известные до последнего времени результаты были «негативными»: они показывали, что двойственные траектории не могут сходиться к некритическому множителю, либо такая сходимость маловероятна.

Сначала рассматриваются задачи оптимизации с одной скалярной переменной и одним ограничением-равенством:

где /, Л: И —Щ — гладкие функции. Для таких задач доказывается результат о том, что если х — стационарная точка, а А — отвечающий х критический множитель Лагранжа, причем выполнено к"(х) ^ 0, то для любого а;0, достаточно близкого к ж, и для любого А0 существует единственная траектория {(я*, А*)} с И х Л1 метода БС^Р, и эта траектория сходится к (О, А), причем выполнено

(3)

Н(х) + Л'(х)( = 0, д(х) + ¿(х)£ ^ О,

/(х) тш, И{х) — О,

т. е. скорость прямой сходимости является линейной.

Далее эффект притяжения к критическим множителям полностью обосновывается для чисто квадратичных задач, имеющих вид

^{Ах, х) min, х] = О,

где А € IRnxn — симметричная матрица, а В: IRn х IRn —У ГО,' — симметричное билинейное отображение. Полученный результат имеет ключевое значение для понимания эффекта притяжения, поскольку чисто квадратичные задачи несут в себе все основные проблемы связанные с нерегулярностью ограничений.

Наконец, в разделе 1.3 рассматриваются существующие методы, обладающие свойством локальной двойственной стабилизации, т. е. способностью подавлять эффект притяжения: стабилизированный метод последовательного квадратичного программирования (sSQP) и метод модифицированных функций Лагранжа (МФЛ). На каждой итерации метода sSQP для текущего приближения (х, А, ß) G ГО." х IR1 х ]Rm вычисляется направление (£, г], О 6 ]R" xIR'x ]Rm как стационарная точка задачи квадратичного программирования

</'(*), (0{х, А, лК, i) + f (||А + „II2 + Им + СИ2) min

h(x) + ft'(a)i - 0-77 = 0, д{х) + д'(х)£ -а С < О,

где er — параметр стабилизации, и следующее приближение полагается равным (а; + f, А + 77, ц + (). В базовом варианте МФЛ на каждой итерации для текущего двойственного приближения (А*, //) 6 ГО.' х IRm и текущего значения параметра штрафа с* > 0 вычисляется хк+1 6 Ш," как стационарная точка задачи безусловной оптимизации

LCk(x, Хк, ßk) -> min, х £ IR",

где Lc: IR" xE'x IRm -> ]R — модифицированная функция Лагранжа для задачи (1):

Lc(x, А, ß) = f{x) + ± (||А + ch(x)И2 + II max{0, p + с5(х)}||2),

после чего двойственное приближение пересчитывается по формулам А**1 = Хк + ckh{xk+1), ßk+1 = max{0, ßk + ckg(xk+1)},

где максимум берется покомпонентно, и выбирается 1 ^ с^.

Оба метода обладают сильной теорией локальной сходимости: если любой их них инициализируется в достаточно малой окрестности точки (х, X, Д), где х — стационарная точка задачи (1), а множитель (Ä, Д) е Л4(х), удовлетворяет достаточному условию второго порядка оптимальности (SOSC)

(0(Х, Л, д)£, ^ > 0 У,£еС(г)\{0}, (4)

где

С(х) = {£ е IR" | ВД£ = 0, a j(í)(®)C < 0, </'(*), 0 ^ 0},

то траектории метода будут сверхлинейно сходиться к некоторой точке (х, Л*, fi*), где множитель (А*, ц*) € М(х) также удовлетворяет SOSC (для МФЛ сверхлинейная сходимость имеет место только при c¡¡ -> оо). Однако, свойство двойственной стабилизации является лишь локальным, и для обоих методов эффект притяжения к критическим множителям присутствует, хотя и значительно менее выражен. А именно, во многих задачах есть широкие прямо-двойственные области, при старте из которых двойственные траектории методов будут сходиться к критическим множителям.

Вторая глава посвящена исследованию поведения МФЛ для задач оптимизации с нерегулярными ограничениями. В данной главе рассматривается алгоритм, на каждой итерации которого выполняются следующие действия. Выбирается вектор (Xk,ßk) е IR' х IRm из некоторого фиксированного параллелепипеда, и для текущего значения параметра штрафа et вычисляется как стационарная точка задачи оптимизации

LCk(x, Xh, ßk) min, x € IR".

Новое двойственное приближение вычисляется по формулам А*+1 = А* + скЦхк+1) и цк+1 = тах{0, Д* + скд(хк+1)}. Если

\Шхк+1), шш^1, -з(хА+1)})|| < тт{М\ -50гк)})||,

где в 6 (0, 1), то выбирается любое значение Ск+1 > од в противном случае выбирается са+1 > рек, где р > 1.

В разделе 2.1 исследуются свойства глобальной сходимости МФЛ. Раздел 2.1.1 посвящен глобальной сходимости МФЛ для задачи (1). Сначала кратко обсуждаются существующие результаты о глобальной сходимости метода, после чего доказывается результат о глобальной сходимости, не требующий традиционных условий регулярности ограничений. Вместо этого делается два предположения, которые не являются стандартными, но при этом весьма обоснованы и должны выполняться во многих случаях. Пусть траектория {(х*, Хк, цк)} с Ел х Е1 х Л1т сгенерирована описанным выше алгоритмом, и для некоторого бесконечного множества индексов К С {1, 2, ...} подпоследовательность {хк | к е К} сходится к г е Д где Б — допустимое множество задачи (1). Первое предположение состоит в том, что справедлива липшицева оценка расстояния

¿Щхк, Б) = 0(||А(**)|| + || тах{0, д(хк)}\\)

для к 6 К при к —► оо. Данная оценка слабее многих традиционных условий регулярности ограничений (например, ИСРЬБ или МРСС^). Второе предположение состоит в том, что для всех к 6 К, некоторого /3 > О, в е (0, 1/2) и некоторой проекции хк точки хк на множество Ю выполнено

Ь^х", А*"1, Д*-1) < ЬСк_г(хк, А*"1, Д*-1) +

+ /3(11/^)11 + || тах{0, д(хк)}\\) + .

('К—1

Данное требование не выглядит обременительным с учетом того, что приближения хк ищутся посредством минимизации Хк~1, рк~1)-

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

выполнены оба предположения, то последовательность {(А*, цк) | к е К} ограничена, х является стационарной точкой задачи (1), и любая предельная точка подпоследовательности {(Afc, fik) | к 6 К} является множителем Лагранжа, отвечающим х.

В разделе 2.1.2 свойства глобальной сходимости МФЛ исследуются для задач оптимизации с комплементарными ограничениями (МРСС) следующего вида:

/С®) -> min, G(x) > 0, Н{х) > 0, <G(x), Н(х)) < 0. (5)

В МРСС могут также присутствовать «обычные» ограничения-равенства и ограничения-неравенства, однако все сложности проводимого анализа связаны именно с комплементарными ограничениями. Легко показать, что все полученные результаты распространяются и на общий случай.

Определим так называемую МРСС-функцию Лагранжа С.: IR" х (IRS х ]RS) -> Ж:

С(х, А) = f{x) - (АG, G(x)) - (Ая, Н(х)), где А = (Ад, Ая). Для произвольной точки х е И", допустимой в задаче (5), определим множества индексов

IG(x) = {г = 1, ..., а | Gi(x) = 0}, IB{ß) = {г = 1, ..., s | Щ{х) = 0}, h{x) = Iciß) ПIH(x).

МРСС-условие линейной независимости (MPCC-LICQ) состоит в том, что векторы

GJ(®), г е 1а(х), Щ(х), i е IB{x) линейно независимы. Допустимая точка х задачи (5) называется слабо стационарной, если существует вектор Ä = (Äq, Ая) е Н" х Ж®, удовлетворяющий

ÖjC

-jfaix, Ä) = 0, (Ас)/д(г)\/с(г) = 0, (АЯ)/с(±)\/„(2) = 0.

Если дополнительно (Äc)j(Äff)j ^ 0 для всех г £ /0(ж), то х называется С-стационарной точкой. Если же (Äg)/0(j) ^ 0, (Xh)i0(x) ^ 0, то х называется сильно стационарной точкой.

Для задачи (5) доказывается результат о том, что допустимые предельные точки МФЛ являются по крайней мере С-стационарными при условии, что в них выполнено MPCC-LICQ. Более того, они являются сильно стационарными, если определенная двойственная последовательность ограничена. В совокупности с примерами, показывающими, что в общем случае сильная стационарность может не иметь места, доказанный результат дает полную картину глобальной сходимости для МФЛ, применяемого к МРСС.

В разделе 2.2 исследуется возможность ускорения финальной фазы МФЛ с помощью sSQP. Основной результат состоит в том, что если ускоритель инициализируется в окрестности точки (х, А, Д), где х — стационарная точка задачи (1), а (А, р) — некритический множитель Лагран-жа, удовлетворяющий условию строгой дополнительности Дл(г) > 0, то траектория ускорителя будет сверхлинейно сходиться к некоторой точке (х, А*, /X*), где (А*, ц') € М(х).

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

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

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

рировать с обычным БС^Р даже на задачах с нерегулярными ограничениями.

В разделе 3.1 исследуются гибридные подходы к глобализации сходимости на основе некоторого метода внешней фазы. Для задачи (1) предлагаются два способа гибридной глобализации сходимости 8Б(ЗР: алгоритм с возвратами и алгоритм с рекордами.

Идея алгоритма с возвратами заключается в том, что на каждой итерации из текущей точки делается шаг вБС^Р, который принимается, если он приводит к линейному убыванию невязки системы ККТ. Если на какой-то из последующих итераций шаг вБСЭР не принимается, то происходит возврат к той точке, откуда был сделан первый в данной серии шаг зЭСЗР, и из этой точки делается шаг метода внешней фазы.

Стратегия гибридной глобализации сходимости с рекордами состоит в следующем. Вместо того, чтобы сравнивать невязку системы ККТ в пробной точке с невязкой, полученной на предыдущей итерации, будем сравнивать ее с наименьшим достигнутым значением невязки по всем предыдущим итерациям (т.е. с рекордом), и принимать шаг вБСЗР только в том случае, если наблюдается линейное убывание рекорда.

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

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

В разделе 3.2 для задачи (1) предлагается алгоритм, комбинирующий свойства зЭСЭР и МФЛ. Основная идея состоит в том, что направления

вБС^Р можно использовать для приближенного решения подзадач МФЛ. На каждой итерации алгоритма сначала вычисляется направление (£к, т]к, (к) метода sSQP. Если шаг вБСЗР приводит к существенному улучшению невязки системы ККТ по сравнению с рекордным значением, то этот шаг принимается (осуществляется итерация вБСЗР). В противном случае осуществляется одномерный поиск вдоль направления для модифицированной функции Лагранжа при текущих значениях двойственных переменных. Если в результате одномерного поиска получен приближенный минимум этой функции, то осуществляется итерация МФЛ. В противном случае осуществляется внутренняя итерация (двойственное приближение и параметр штрафа не меняются).

Для данного алгоритма доказывается следующий результат о глобальной сходимости: любая предельная точка (х, А, Д) траектории алгоритма либо является решением системы ККТ (2), либо удовлетворяет соотношениям

А, Д) = О, Д ^ О, (/ф))тЛ(г) + (<?'(я))т тах{0, д{х)} = О,

причем в последнем случае все итерации, начиная с некоторого номера, являются итерациями МФЛ. Также доказывается результат о сверхлинейной скорости сходимости. В частности, если траектория алгоритма сходится к точке, удовлетворяющей БОБС (4), то в естественных предположениях скорость сходимости будет сверхлинейной.

В разделе 3.2.2 показано, что данный алгоритм тесно связан с прямо-двойственным алгоритмом БС^Р, но в то же время обладает рядом преимуществ.

В приложении Б.2 приводятся результаты вычислительного эксперимента, которые показывают, что предложенный алгоритм оказывается более эффективным, чем некоторые другие методы (включая прямо-двойственный алгоритм БС^Р), однако проигрывает по эффективности обычному 8<2Р.

В разделе 3.3 для задачи оптимизации с ограничениями-равенствами

f{x) -» min, h(x) = 0, (6)

где /: И" IR — гладкая функция, а h: ]Rn -> В,' — гладкое отображение, разрабатывается подход к глобализации сходимости с помощью точных гладких штрафных функций. Основное отличие данного подхода от других способов глобализации сходимости, предложенных в главе 3, состоит в том, что он не является гибридным. А именно, на каждой итерации вычисляется прямо-двойственное направление поиска sSQP, вдоль которого затем осуществляется одномерный поиск для точной гладкой штрафной функции ¡рСи С2 •' IR" х JR,' -> И:

^(х, А) = L(x, А) + 1Ц/Ф0Ц2+ |

где С\ > 0 и С2 > 0 — параметры штрафа.

В разделе 3.3.1 приводится глобализованный алгоритм, и для него доказывается следующий результат о глобальной сходимости. Если последовательность параметров штрафа ограничена, то любая предельная точка (х, X) траектории алгоритма {(хк, А*)} удовлетворяет <р'СиСз(х, X) = О, откуда в естественных предположениях следует, что (5, Ä) является решением системы Лагранжа задачи (6). Если же любой из параметров увеличивается бесконечное число раз, то любая предельная точка соответствующей подпоследовательности траектории Хк)} в естественных предположениях является решением системы Лагранжа задачи (6).

В разделе 3.3.2 доказывается результат о сверхлинейной скорости сходимости: если траектория алгоритма сходится к точке (х, X), где х — стационарная точка задачи (6), а Ä — отвечающий ей некритический множитель Лагранжа, то скорость сходимости является сверхлинейной.

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

dL( лч

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

В четвертой главе для задачи (6) разрабатывается метод последовательного квадратичного программирования, стабилизированный вдоль подпространства (в-вЗС^Р). Он представляет собой модификацию метода вБОР, в которой двойственная траектория стабилизируется только вдоль подпространства вырожденности матрицы Якоби ограничений. Целью модификации является устранение описанной выше проблемы коротких шагов. Пусть заданы отображение Р: И" хЕ'-+ Ш,'х' и функция а: К" х Ш,' —Ж, где линейный оператор Р(х, А) аппроксимирует проектор на подпространство вырожденности при (х, А) —»■ (х, А). На каждой итерации в-бБС^Р для текущего приближения (х, А) е Ж" х Н' вычисляется направление поиска (£, т)) е К" х Ш,' как решение линейной системы

= А),

Л'(*)£ - а(х, А)Р{х, А)и = -А(®),

и следующее приближение определяется как (х + А + т]).

Раздел 4.1 посвящен обоснованию локальной сверхлинейной сходимости метода вблизи квалифицированного решения. Отдельно рассматриваются два различных набора предположений на Р и сг. Ключевое различие состоит в том, что в первом случае <т(х, А) —»■ 0 при (х, А) —> (х, А) (асимптотически исчезающая стабилизация), а во втором случае сг(х, А) —а ^ 0 при (х, А) —> (х, А) (асимптотически неисчезающая стабилизация). Для каждого набора предположений доказывается теорема о локальной сверхлинейной сходимости, полностью аналогичная соответствующей теореме для зБС^Р.

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

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

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

В приложении В приводятся результаты вычислительного эксперимента, свидетельствующие о том, что стабилизация вдоль нужного подпространства крайне важна для высокой эффективности методов с двойственной стабилизацией: метод в-вЗС^Р существенно опережает по эффективности и робастности как обычный, так и стабилизированный БС^Р. Предложенная процедура идентификации подпространства вырожденности весьма эффективна с вычислительной точки зрения (в частности, она значительно экономичнее известных альтернатив), и при этом демонстрирует высокую надежность.

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

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

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

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

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

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

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

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

1. Измаилов А.Ф., Крылова A.M., Усков Е.И. Гибридная глобализация стабилизированного метода последовательного квадратичного программирования // Теоретические и прикладные задачи нелинейного анализа. - М.: ВЦ РАН, 2011. - С. 47-36.

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

ни М.В. Ломоносова, 14-23 ноября 2011 г.: Тезисы докладов.— М.: МАКС Пресс, 2011. - С. 23-24.

3. Измаилов А.Ф., Солодов М.В., Усков Е.И. Метод множителей как средство глобализации сходимости стабилизированного метода последовательного квадратичного программирования для задач оптимизации с ограничениями-равенствами // Теоретические и прикладные задачи нелинейного анализа. — М.: ВЦ РАН, 2014. — С. 46-64.

4. Измаилов А.Ф., Усков Е.И. О применении ньютоновских методов к системе условий оптимальности Ф. Джона // Журнал вычислительной математики и математической физики. — 2011. — Т. 51, № 7. — С. 1194^1208.

5. Измаилов А.Ф., Усков Е.И. О применении ньютоновских методов к системе условий оптимальности Ф. Джона // Тихоновские чтения: Научная конференция, Москва, МГУ имени М.В. Ломоносова, 14 июня 2011 г.: Тезисы докладов. - М.: МАКС Пресс, 2011. - С. 40.

6. Измаилов А.Ф., Усков Е.И. О влиянии критических множителей Лагранжа на скорость сходимости метода множителей // Журнал вычислительной математики и математической физики. — 2012. — Т. 52, № П.-С. 1959-1975.

7. Измаилов А.Ф., Усков Е.И. О притяжении метода Ньютона к критическим множителям Лагранжа // Тихоновские чтения: Научная конференция, Москва, МГУ имени М.В. Ломоносова, 29-31 октября 2012 г.: Тезисы докладов. — М.: МАКС Пресс, 2012. — С. 41-42.

8. Измаилов А.Ф., Усков Е.И. Эффект притяжения метода Ныотона-Лагранжа к критическим множителям Лагранжа: полный анализ в одномерном случае // Теоретические и прикладные задачи нелинейного анализа. — М.: ВЦ РАН, 2012. — С. 53-71.

9. Измаилов А.Ф., Усков Е.И. Стабилизированный метод Ньютона-Лагранжа для минимизации модифицированной функции Лагран-жа // Теоретические и прикладные задачи нелинейного анализа.— М.: ВЦ РАН, 2013. - С. 39-54.

10. Измаилов А.Ф., Усков Е.И. Эффективная численная аппроксимация подпространства вырожденности нелинейного отображения // Теоретические и прикладные задачи нелинейного анализа. — М.: ВЦ РАН, 2014.- С. 74-87.

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

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

13. Усков Е.И. Численное сравнение оптимизационных алгоритмов // Теоретические и прикладные задачи нелинейного анализа. — М.: ВЦ РАН, 2012. - С. 118-131.

14. Усков Е.И. О притяжении метода Ньютона к критическим множителям Лагранжа // Журнал вычислительной математики и математической физики. - 2013. - Т. 53, № 8. - С. 1272-1286.

15. Izmailov A.F., Solodov M.V., Uskov E.I. Global convergence of augmented Lagrangian methods applied to optimization problems with

degenerate constraints, including problems with complementarity constraints // SIAM Journal on Optimization. — 2012. — Vol. 22, no. 4,— P. 1579-1606.

16. Izmailov A.F., Solodov M.V., Uskov E.I. Combining stabilized SQP with the augmented Lagrangian algorithm // IMPA Preprint A754. — 2014.

17. Izmailov A.F., Solodov M.V., Uskov E.I. Globalizing stabilized SQP by smooth primal-dual exact penalty function // IMPA Preprint A752. — 2014.

18. Izmailov A.F., Uskov E.I. Attraction of Newton method to critical Lagrange multipliers // VII Московская международная конференция по исследованию операций (ORM2013): Москва, 15-19 октября 2013 г.: Труды. - Т. 1. - М.: МАКС Пресс, 2013. - С. 67-69.

19. Izmailov A.F., Uskov E.I. Attraction of Newton method to critical Lagrange multipliers: fully quadratic case // Mathematical Programming. - 2014. - DOI: 10.1007/sl0107-014-0777-x.

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

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

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