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

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

ПОГОСЯН АРТУР ЛЕВОНОВИЧ

4857171

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 з ОНТ 2011

Москва - 2011

4857171

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

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

профессор

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

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

Аваков Евгений Рачиевич;

кандидат физико-математических наук, Карамзин Дмитрий Юрьевич.

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

Российский университет дружбы народов (г. Москва).

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

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

Автореферат разослан 25-сентября 2011 г.

/ Ученый секретарь диссертационного совета профессор

Н.П. Трифонов

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

Работа посвящена разработке численных методов ньютоновского типа для задач оптимизации с комплементарными ограничениями (ЗОКО) и для задач оптимизации с исчезающими ограничениями (ЗОИО), которые относятся к объемлющему их классу задач оптимизации с распадающимися ограничениями.

Актуальность темы. ЗОКО — относительно хорошо изученный класс трудных оптимизационных задач, который, является важным частным случаем так называемых задач оптимизации с равновесными ограничениями1'2. Приложения ЗОКО чрезвычайно разнообразны; к ним относятся, например, двухуровневые задачи оптимизации3 (в частности, так называемые игры Штакельберга), задачи нахождения оптимальной формы упругопластических балочных (стержневых) конструкций4, и др. ЗОИО — новый класс трудных оптимизационных задач5, привлекающий в последнее время все большее внимание специалистов. Наиболее известным приложением ЗОИО являются задачи нахождения оптимального дизайна топологий механических структур. Задачи рассматриваемых классов проблематичны для анализа и численного решения из-за неизбежной нерегулярности их ограничений, и поэтому для них требуются специальная теория и специальные численные методы. Существуют численные подтверждения высокой эффективности и робастности традиционных методов последовательного квадратичного программирования (ПКП) применительно к ЗОКО6. Однако, легко привести примеры, удовлетворяю-

щие! Z.-Q., Pang J.-S., Ralph D. Mathematical programs with equilibrium constraints. Cambridge: Cambridge Univ. Press, 1996.

2Outrata J.V., Kocvara M., Zowe J. Nonsmooth approach to optimization problems with equilibrium constraints: Theory, applications and numerical results. Boston: Kluwer Acad. Publ., 1998.

3Dempe S. Foundations of bilevel programming. New York, Boston, Dordrecht, Moscow: Kluwer Academic Publishers, 2002.

4Ferris M.C., Tin-Loi F. On the solution of a minimum weight elastoplastic problem involving displacement and complementarity constraints // Comput. Methods Appl. Mech. Engrg., 1999. V. 174, № 1-2.. P. 108-120.

'Achtziger W., Kanzow C. Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications // Math. Program. 2007. V. 114, № 1. P. 69-99.

6Fletcher R., Leyffer S. Solving mathematical programs with equilibrium constraints as nonlinear programs // Optim. Methods Softw. 2004. V. 19. P. 15-40.

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

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

Целью диссертационной работы является построение эффективных численных методов решения ЗОКО и ЗОИО.

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

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

Научная новизна. В работе уточнены полученные ранее8 необходимые условия первого и второго порядков оптимальности для ЗОИО в плане ослабления используемых условий регулярности. Предложены новые поднятые переформуировки ЗОКО и ЗОИО, которые обладают меньшей гладкостью, чем использовавшаяся ранее подобная переформулировка для ЗОКО9, но при этом обладают лучшими свойствами регулярности. Разработаны новые ньютоновские методы для поднятых задач, а также новые методы активного множества для ЗОИО, использующие структуру рассматриваемых задач и обладающие глобальной сходимостью и сверхлинейной скоростью сходимости.

7Izmailov A.F., Solodov M.V. On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions // Math. Program. 2009. V. 117. P. 271-304.

8Izmailov A.F., Solodov M.V. Mathematical programs with vanishing constraints: optimality conditions, sensitivity, and a relaxation method // J. Optim. Theory Appl. 2009. V. 142, № 3. P. 501-532.

9Stein O. Lifting mathematical programs with complementarity constraints // Math. Program., 2010. DOI 10.1007/sl0107-010-0345-y.

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

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

Соответствие диссертации паспорту научной специальности.

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

Апробация результатов. Результаты, полученные в диссертации, докладывались и обсуждались на VIII всемирном конгрессе по структурной и междисциплинарной оптимизации «WCSMO-8» (Лиссабон, Португалия, 2009), ежегодных научных конференциях «Ломоносовские чтения» (Москва, 2009, 2010), ежегодных научных конференциях «Тихоновские чтения» (Москва, 2009, 2010), 52-ом симпозиуме «Нелинейная оптимизации, вариационные неравенства и равновесные задачи» (Эриче, Италия, 2010), VI Московской международной конференции по исследованию операций «ORM2010» (Москва, 2010), ежегодных международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2010», «Ломоносов-2011» (Москва, 2010, 2011), на VIII конгрессе международного общества анализа, его приложений и вычислений «ISAAC» (Москва, 2011).

Кроме того, результаты обсуждались на семинаре кафедры исследова-

ния операций факультета ВМК МГУ.

Публикации. По материалам диссертации опубликовано 11 работ, список которых приведен в конце автореферата. В число указанных работ входят статьи [1]-[4], опубликованные в журналах из списка ВАК РФ. Кроме того, результаты диссертации содержатся еще в одной статье в журнале из списка ВАК [12] и в одной статье в сборнике ВЦ РАН [13], которые находятся в печати.

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

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

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

Первая глава посвящена теоретическому анализу ЗОКО и ЗОИО.

В разд. 1.1 приводятся необходимые теоретические сведения о ЗОКО

f(x) —> min, G(x) > 0, Н{х)> 0, (G(x), Н(х)) = 0, (1)

где /:Rn R — гладкая функция, a G, H:Rn Es - гладкие отображения. Ограничения задачи (1) могут также включать в себя «обычные» равенства и неравенства. Такое обобщение не вызывает серьезных дополнительных трудностей и в работе не рассматривается. Развивается техника сведения задач указанного типа к так называемым поднятым задачам оптимизации с обычными гладкими ограничениями-равенствами

f(x) min, (min{0, у})2 - G{x) = 0, (max{0, у})2 — Н(х) = 0, (2)

где у € Ra — дополнительная переменная, а также устанавливаются связи поднятых задач с исходными. Заметим, что ограничения задачи (2) дифференцируемы лишь один раз.

В разд. 1.2 приводятся необходимые теоретические сведения о ЗОИО

f(x) ->■ min, h(x) = 0, д{х) < 0, ,

Щх) > О, Gí(x)Hí(x) < 0, » = 1, ..., а,

где /: R" -> R - гладкая функция, a h: Rn 1', д: R" Km, G, Н: Ж" ~> Ra — гладкие отображения. А именно, приводятся условия регулярности, концепции стационарности, а также уточняются некоторые условия первого и второго порядков оптимальности (в плане ослабления используемых условий регулярности). Предлагается способ сведения задач указанного типа к поднятым задачам оптимизации с обычными ограничениями-равенствами и неравенствами

3

fc(x, у) = /(:г) + £ ((max{0, t/;})4 - c(max{0, í/¿})2) min,

h{x) = 0, д(х) < 0, ^

(min{0, у})2 - Н{х) = 0, G(x) - (та*{0, у})2 < О,

где у £ Rs — дополнительная переменная, а с > 0 играет роль параметра штрафа. Устанавливаются связи поднятых задач с исходными.

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

Вторая глава посвящена разработке обобщенных (полугладких) ньютоновских методов для задач оптимизации с распадающимися ограничениями, а именно, разработке полугладкого метода Ньютона для поднятой ЗОКО и разработке полугладких методов ПКП для поднятой ЗОКО и поднятой ЗОИО.

В разд. 2.1 для решения ЗОКО (1) предлагается полугладкий метод Ньютона для следующей системы Лагранжа поднятой ЗОКО (2):

^(х, у, А) = 0, у, А) = 0, (5)

(min{0, у})2 - G{x) = 0, (max{0, у})2 - Н{х) = 0,

где X е R", у 6 Ra, А = (Ас, Ая) 6 ®s х

dLt \\ дС( w -(*, у, А) = -^(х, А),

д L

—(х, у, А) = 2(Ag)¿ min{0, y¡} + 2{XH)i max{0, j/¡}, i = 1, ..., s. oyi

Здесь

С(х, А) - /(s) - (AG, G(x)) - (Лн, Н(х))

— ЗОКО-функция Лагранжа задачи (1) в точке (х, А), а

L(x, у, А) = /(*) + (Ag> (min{0, г/})2 - G(*)) + (АЯ) (max{0, у})2 - Н{х))

— функция Лагранжа поднятой ЗОКО (2) в точке (х, у, А). Полугладкий метод Ньютона для системы (5) заключается в решении на каждой итерации линейной системы

Лк(и - «*) = -Ф(Л Ак 6 двФ(ик),

где в произвольной точке и = (х, у, А) € R" х R* X (Rs х Rs) отображение Ф: Rn х Rs х (Rs х R3) ->ГхГхГ хГ определяется формулой

/

Ф(и) =

дс( и Л)

\

3L

2/. Л)

(6)

\\ А)

ду

(гшп{0, у})2-С(х)

V (тах{0, г/})2 - Я(®) /

а ЭвФ(и) — так называемый В-дифференциал10 отображения Ф в точке и, который состоит из всех матриц вида

О ~(С'(х)Г -(Н'(х))т^ л= 0 2А(у, А) 2Втш(у) 2Втвх{у) -С'(х) 2Вт[а(у) О О

\ -Н\х) 2В^(у) 0 0 /

Здесь А(у, А) = diag(a(2/, А)),

Вть(у) = с^(тт{0, 2/}), Втях(у) = сПа§(тах{0, у}), (7) а вектор а(у, А) € Rs определяется следующим образом:

(Аа){, если ?/,• < О,

аг = (Ас)г или (Ая)ь если У4 = 0, г = 1, ..., з. (8) \ (Ан),-, если у{ > О,

'"Измайлов А.Ф., Солодов М.В. Численные методы оптимизации. 2-е изд., перераб. и доп. М.: Физматлит, 2008.

Под diag(u) понимается диагональная s х s-матрица с диагональю и, где и £ R3.

Для рассматриваемого метода обоснована локальная сверхлинейная сходимость. Проведен сравнительный анализ локальных свойств сходимости разработанного метода с некоторыми альтернативными методами для ЗОКО. Кроме того, осуществлена глобализация сходимости локального полугладкого метода Ньютона, основанная на одномерном поиске для квадрата невязки ¡p: Kn х Rs х (Rs х W) R,

= |||Ф(«)|||,

системы Лагранжа (5) поднятой ЗОКО (2), и обоснованы свойства глобальной сходимости полученного метода.

В разд. 2.2 для решения ЗОКО (1) предлагается полугладкий метод ПКП и его специальная квазиньютоновская версия для поднятой ЗОКО (2), учитывающая структуру этой задачи. Полугладкий метод ПКП для поднятой ЗОКО (2) локально совпадает с полугладким методом Ньютона для этой задачи и состоит в решении на каждом шаге задачи квадратичного программирования

(min{0, ук})2 - G{xk) - G'(xk)(x - хк) + 2Bmin{yk){y - ук) = О, (max{0, ук})2 - Н{хк) - Н'(хк)(х - хк) + 2Втах{ук)(у - ук) = О,

где "Нк — симметричная (п + s) х (п + з)-матрица.

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

где в правой части стоит 5-дифференциал градиентного отображения

г\ у

(я, у) 7Г7-г(®. У, А*) : кп X Г К" X Е". Непосредственными

вычислениями можно показать, что (дв)(х,у)д-,-?Л состоит

"Ч®! У)

из всех матриц вида

0 V (9)

\ 0 2сиа§(а(гДА*)) )

где для у € М" и А = (Ас, Ая) € К' х Е" вектор а(у, А) определен в (8).

Однако, матрицы Нк, вычисленные согласно (9), не обязательно будут положительно определены, и их непосредственное использование при глобализации сходимости вряд ли возможно. Значит, матрицы Нк должны быть соответствующим образом модифицированы. Можно использовать стандартные квазиньютоновские аппроксимации для матриц Нк, однако эти аппроксимации разрушают полезную диагональную структуру в (9). Более того, в негладком случае стандартные квазиньютоновские аппроксимации, вообще говоря, могут разрушать и локальную сверхлинейную скорость сходимости метода ПКП. Поэтому наиболее разумным представляется сохранение и использование специальной структуры поднятой 30-КО (2). Идея состоит в том, чтобы использовать стандартные квазиньютоновские формулы только для Ак) в (9), а элементы а{ук, Хк) при необходимости заменять положительными числами, причем так, чтобы вся матрица Нк была положительно определенной и асимптотически возмущение диагонали а(ук, Хк) исчезало. А именно, будем переопределять Нк следующим образом:

Нк О О 2diag«J

где Нк — некоторая симметричная положительно определенная аппрокси-д2£

мация матрицы Гессе (ж*, Хк) (скажем, по формуле Бройдена-Флет-чера-Голдфарба-Шэнно (БФГШ) с модификацией Пауэлла11), а вектор

"Nocedal J., Wright S.J. Numerical optimization. New York, Berlin, Heidelberg: Springer-Verlag, 2006.

°тах £ определяется следующим образом:

(атах)» = А*), р{а{хк, ук, Аа))>, * = 1, ..., е.

Здесь для произвольной точки (х, у, А) 6 1" х К' х (Ж* х Ж") элементы а)(з/| определены в (8), р : Ж+ —> Ж+ некоторая непрерывная функция такая, что р(0) = 0 и р(^) отделено от 0 при t отделенных от 0, а и : I" X Е' х (К8 х Ж3) -> Ж+ — невязка системы Лагранжа (5):

2/. А) = ||Ф(®, у, А)||,

где отображение Ф определено в (6).

Для полугладкого метода ПКП обосновывается локальная сверхлинейная сходимость в прямых и прямодвойственных переменных. Осуществляется глобализация сходимости данного метода за счет одномерного поиска для негладкой точной штрафной функции <р@ : Ж" х Мт К,

<рЛх> у) = /(к) + РФ{Х> У).

где 0 > 0 — параметр штрафа, а ф : Ж" х Ж* Ж+,

(шш{0, у})2 - С(х) ' (шах{0, у})2 - Н(х)

ф(х, у) =

— ¿1-штраф для ограничений задачи (2). Такая стратегия глобализации может выгодно сравниваться со стратегией глобализации, использующей невязку системы Лагранжа. В частности, глобализация, использующая штрафные функции, является более «оптимизационной» и должна иметь преимущества в смысле качества получаемого результата: эта стратегия имеет более слабую тенденцию притягиваться к неоптимальным стационарным точкам.

В разд. 2.3 для решения ЗОИО (3) предлагается полугладкий метод ПКП и его специальная квазиньютоновская версия для поднятых ЗОИО (4), учитывающая структуру этой задач. Полугладкий метод ПКП для поднятой ЗОИО (4) заключается в решении на каждом шаге задачи

квадратичного программирования

h{xk) + h'{xk){x - xk) = 0, g(xk) + g'{xk){x - xk) < 0, (min{0, yk}f - H(xk) - H'{xk){x - xk) + 2Bmia(y)(y - yk) = 0, G(xk) - (max{0, yk})2 + G'(xk)(x - xk) - 2Bmsx(y)(y - yk) < 0,

где ВШт{у) и Bmax(y) определены в (7),

f'c(xk, yk) = (f(xk), 4(max{0, yk}f - 2cmax{0, yk}).

Поскольку и целевая функция, и ограничения задачи (4) дифференцируемы лишь один раз, а их производные являются полугладкими, то

базовый выбор матрицы Hk состоит в следующем: Нк е ук> хк)>

где для а; е Rn, у G Г и Л = (А\ Л9, Ая, Л°) € Ж1 х Rm х Is х Is

Ьс(х, у, Л) = f(x) + t ((max{0, Vi})4 - c(max{0, y;})2) + K*))+ +(X°, g(x)) + (Xй, (min{0, y}f - H(x)) + (Xе, G{x) - (ma*{0, у})2)

— функция Лагранжа задачи (4). В данном случае Б-дифференциал вычисляется явно и состоит из матриц вида

n-fw«* ° V <10>

\ О 2diag(ac(/,Afc)) /

где

£{х, А) = f(x) + (Xh, h(x)} + (X9, g(x)) - (Хн, H(x)) + (XG, G(x))

— ЗОИО-функция Лагранжа задачи (3) в точке (ж, Л), а для цеВ'и АбЕ'хГ хГ хГ

ас{у, X) = 6(шах{0, у})2 + Ьс{у, А), (11)

!Лf, если у{ < 0,

Af или - Af - с, если yi = 0, t = l,(12)

-Xf - с, если yi > 0,

Заметим, что матрицы вычисляемые согласно (10)—(12), положительно определенными могут не быть. Поэтому будем определять Мк следующим образом:

где Я/с — симметричная положительно определенная п х п-матрица, получаемая с помощью квазиньютоновских аппроксимаций (скажем, по фор-

д2С

муле БФГШ с модификацией Пауэлла) Хк), а вектор 6 Ка

вычисляется по формуле

(<4п)< = тт{шах{(ас(у\ Х%, р{ас{хк, ук, А*))}, М}, г = 1, ..., а.

— р: К+ Е+ — такая функция, что р{$) отделено от нуля положительной константой при t отделенных от нуля, и р(¿) 0 при Ь 0+;

- сТс: Кп х 1" х (К' х X К" X К^) ->■ Е - некоторая невязка системы Каруша-Куна-Таккера (ККТ)

2(тах{0, у;})3 - с(тах{0, у*})+ +Х? тт{0, - Аf тах{0, уг} = 0, г = 1, ..., в, /г(а;) = 0,

А3 > 0, 3(®)<0, (Xя, д{х)) = 0, (тш{0, у})2 - Я(х) = 0, Ас > 0, в{х) - (тах{0, у})2 < 0, (А°, в(х) - (тах{0, у})2) = 0

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

— М > 0 — верхняя граница на элементы а*, в качестве которой разумно брать «большое» число (наличие такой границы требуется при обосновании свойств глобальной сходимости, а для сохранения сверхлинейной скорости сходимости достаточно выполнения условия М > 2с).

Для этих методов обосновываются свойства локальной сверхлинейной сходимости в прямых и прямодвойственных переменных. Кроме того, осу-

Здесь:

«-(*, А) = 0,

дх

ществляется глобализация сходимости локального полугладкого квазиньютоновского метода ПКП посредством одномерного поиска для точной штрафной функции tpc,p : Rn х MM R,

<РеАх> у) = /с(®| у) + у).

где Р > 0 — параметр штрафа, а -ф : К" х Rs -» К,

ф(х, у) = ||Л(®)||г + ||(min{0, у})2 - Н(х)Их +

т я

+ ^шах{0, ffj(a;)} + ^max{0, Gi(x) - (max{0, г/,})2}, j=1 «=1

— /¡-штраф для ограничений задачи (4).

Результаты главы 2 опубликованы в работах [2, 3, 4, 6, 7, 8, 9]. В третьей главе для решения ЗОИО предлагаются ньютоновские методы активного множества. Обосновываются свойства локальной сверхлинейной сходимости этих методов. Кроме того, предлагаются две различные стратегии гибридной глобализации методов активного множества и обосновываются свойства глобальной сходимости полученных концептуальных алгоритмов. Приводятся три конкретные реализации разработанных алгоритмов с соответствующими уточнениями свойств сходимости.

В разд. 3.1 разрабатываются кусочный метод ПКП и методы активного множества. Кусочный метод ПКП для ЗОИО имеет в своей основе ту же общую идею, что и соответствующий метод для ЗОКО12. Идея состоит в том, чтобы идентифицировать любую кусочную задачу

/(¡с) ->• min, h(x) = 0, д{х) < О, -Н1о+иф) = 0, -Н1т_{х)< 0, GI+nVIl{x) <0,

отвечающую искомому решению х ЗОИО (3), и применить к этой задаче

"Ralph D. Sequential quadratic programming for mathematical programs with linear complementarity constraints // Computational Techniques and Applications: CTAC95. Singapore: World Scientific, 1996. P. 663-668.

метод ПКП. Здесь множества индексов определяются по формулам

А- = !+{%) = {t = 1, ..., a I Hi(x) > 0}, /0 = /0(г) = {i = 1,..., в I Hi{x) = о}, 7+0 = 1+0(х) = {г е /+ I Gi{x) = 0}, 7+_ = 1+4х) = {г б 7+ I Gi(x) < 0}, 10+ = 10+{х) = {iel0 I Gi{x) > 0}, Too = Ых) = {г € /01 Gt(x) = 0}, /о_ = /0_(я) = {г € /0 I Gj(®) < 0},

a (7i, I2) — произвольное разбиение множества 7оо, такое, что Ди/2 = Iqq, Ii П h = 0.

Локальная идентификация ветви допустимого множества не требует никаких затрат. А именно, достаточно идентифицировать такое разбиение (Ji, J2) множества {1, ..., s}, что

I0+CJ2, 7+U/o-CJi- (13)

Как только это будет сделано, можно определить кусочную задачу следующим образом:

f{x) -> min, h(x) = 0, д(х) < 0, -HJt{x) = 0, -Нф)< 0, Сф)<0.

Из определения множеств 7+, 7о+ и 7о_ очевидно следует, что для х £ R", близкого к я, разбиение (Ji, J2), удовлетворяющее (13), может быть идентифицировано, например, следующим образом:

Л = Ji(x) = {» = 1, ..., 5 I Gi(x) < Щх)}, h = J2(®) = {» = 1, ..., a I Gi(x) > Hi(x)}.

Кусочный метод ПКП для ЗОИО (3) заключается в решении на каждой итерации задачи квадратичного программирования

if'{xk), х-хк) + ^ ßk){x - хк), х-хк^ ^ min,

h{xk) + h'{xk) (x-xk) = Q, g(xk) + g'(xk) (x-xk)<0, -Нфк) - H'j2(xk)(x - xk) = 0, -Нфк) - HfJx(xk)(x - xk) < 0, Сфк) + С'^(хк)(х-хк) <0,

где для х 6 W1 и ц = (,uh, м3, /Л 6 Мг х Rm X Ма X Rs

С(х, /х) = f(x) + h(x)) + </Л д(х)) - (/Д Н(х)} + (у?, ОД)

— ЗОИО-функция Лагранжа.

Идея предлагаемых в диссертации методов активного множества для ЗОИО состоит в том, чтобы идентифицировать суженную задачу математического программирования (СЗМП)

f{x) -> min, h{x) = 0, g{х) < 0, -Hh+UIoo(x) = 0, -Н1о_{х)< 0, G/+0U/00(a;) < О,

отвечающую искомому решению, и применить к этой задаче метод ПКП, в котором на каждой итерации решается задача квадратичного программирования

(/V), х-х*) + ± /)(* - Л min,

h{xk) + h'{xk){x - хк) = 0, g{xk) + gf{xk){x - хк) < О, -Hh+UIoo(xk)-H>Ia+UIJxk)(x-xk)=0,

-Н1о.(хк)-Н'1о_(хк)(х-хк)< О, Gi+ouiJxk)+G'Wo(xk)(x-xk)<0.

Идентифицировать СЗМП (14) — значит идентифицировать множества индексов 1+о, Io+, ho и Iо-, и при определенных (очень слабых) предположениях такая идентификация локально может быть осуществлена без серьезных вычислительных затрат на основе оценок расстояния до множества прямодвойственных решений.

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

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

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

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

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

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

Результаты главы 3 опубликованы в работах [1, 5, 10, 11], а также содержатся в [12, 13].

В приложениях представлены результаты вычислительного эксперимента с разработанными алгоритмами для ЗОКО на 38 задачах из тестовой коллекции МасМРЕС13, и для ЗОИО на собственной тестовой коллекции из 23 задач, взятых из всех доступных автору публикаций, ка-

13Leyffer S. МасМРЕС: AMPL collection of Mathematical Programs with Equilibrium Constraints. http://wiki.racs.anl.gov/leyfFer/index.php/MacMPEC.

сающихся ЗОИО. Поведение разработанных алгоритмов сравнивалось со стандартными методами и между собой.

Результаты вычислительного эксперимента опубликованы в работах [2, 3, 4], а также содержатся в [12, 13].

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

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

1. Предложенная в работе поднятая переформулировка ЗОКО имеет лучшие свойства регулярности, чем использовавшаяся ранее, хотя и обладает меньшей гладкостью. Разработана поднятая переформулировка ЗОИО. Установлены связи исходных и поднятых задач. Уточнены условия первого и второго порядков оптимальности для ЗОИО.

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

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

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

1. Измаилов А.Ф., Погосян А.Л. Условия оптимальности и ньютоновские методы для задач оптимизации с исчезающими ограничениями // ЖВМиМФ. 2009. Т. 49, № 7. С. 1184-1196.

2. Измаилов А. Ф., Погосян А.Л. Полугладкий метод последовательного квадратичного программирования для поднятых задач оптимизации

с исчезающими ограничениями // ЖВМиМФ. 2011. Т. 51, № 6. С. 9831006.

3. Izmailov A.F., Pogosyan A.L., Solodov M.V. Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints // Comput. Optim. Appl. 2010. DOI 10.1007/sl0589-010-9341-7

4. Izmailov A.F., Pogosyan A.L., Solodov M.V. Semismooth SQP method for equality-constrained optimization problems with an application to the lifted reformulation of mathematical programs with complementarity constraints // Optim. Meth. Software. 2011. DOI 10.1080/10556788.2011.557727.

5. Измаилов А.Ф., Погосян А.Л. О методах активного множества для задач оптимизации с исчезающими ограничениями // Тематический сборник «Теоретические и прикладные задачи нелинейного анализа». М.: ВЦ РАН, 2009. С. 18-49.

6. Измаилов А.Ф., Погосян А.Л. Полугладкий метод последовательного квадратичного программирования для поднятых задач оптимизации с исчезающими ограничениями // Научная конференция «Тихоновские чтения» (Москва, 25-29 октября 2010). М.: МАКС Пресс, 2010. С. 10.

7. Измаилов А.Ф., Погосян А.Л., Солодов М.В. Полугладкие ньютоновские методы для задач оптимизации с комплементарными ограничениям // Труды VI Московской международной конференции по исследованию операций (ORM2010: Москва, 19-23 октября 2010). М.: МАКС Пресс, 2010. 237-239.

8. Погосян А.Л. Ньютоновские методы для задач оптимизации с комплементарными ограничениями '// Сборник тезисов 17-ой Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2010» (Москва, 12-15 апреля 2010). Секция «Вычислительная математика и кибернетика». М.: МАКС Пресс, 2010, С. 148— 149.

9. Погосян A.JI. Ньютоновские методы для поднятых задач оптимизации с исчезающими ограничениями // Сборник тезисов 18-ой Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2011» (Москва, 11-15 апреля 2011). Секция «Вычислительная математика и кибернетика». М.: МАКС Пресс, 2011. С. 43-44.

10. Izmailov A.F., Pogosyan A.L. Newton-type methods for mathematical programs with vanishing constraints // Proceedings of the Eighth World Congress on Structural and Multidisciplinary Optimization (WCSMO-8: June 1-5, 2009, Lisbon, Portugal). Paper 1045. P. 1-9.

11. Izmailov A.F., Pogosyan A.L. Active-set Newton methods for mathematical programs with vanishing constraints // Abstracts of the 8th Congress of the International Society for Analysis, its Applications, and Computation (ISAAC: August 22-27, 2011, Moscow). M.: PFUR, 2011. P. 390.

12. Izmailov A.F., Pogosyan A.L. Active-set Newton methods for mathematical programs with vanishing constraints 11 Comput. Optim. Appl. To appear.

13. Погосян A.JI. Численное сравнение ньютоновских методов для задач оптимизации с исчезающими ограничениями // Тематический сборник «Теоретические и прикладные задачи нелинейного анализа». В печати.

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

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

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

Введение

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

Глава 1. Задачи оптимизации с распадающимися ограничениями: элементы теории

1.1. Задачи оптимизации с комплементарными ограничениями.

1.1.1. Предварительные сведения.

1.1.2. Поднятая задача.

1.2. Задачи оптимизации с исчезающими ограничениями.

1.2.1. Регулярность, стационарность и условия оптимальности.

1.2.2. Поднятая задача.

Глава 2. Обобщенные методы Ньютона для поднятых задач

2.1. Полу гладкий метод Ньютона для поднятых задач оптимизации с комплементарными ограничениями.

2.1.1. Локальный метод.

2.1.2. Глобализация сходимости.

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

2.2.1. Локальный метод.

2.2.2. Глобализация сходимости.

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

2.3.1. Локальный метод.

2.3.2. Глобализация сходимости.

Глава 3. Ньютоновские методы активного множества для задач оптимизации с исчезающими ограничениями

3.1. Локальные методы.

3.1.1. Кусочный метод последовательного квадратичного программирования.

3.1.2. Методы активного множества.

3.2. Гибридная глобализация сходимости методов активного множества

3.2.1. Стратегия глобализации с возвратами.

3.2.2. Стратегия глобализации с рекордами.

3.2.3. Гибридные алгоритмы

Теория и численные методы оптимизации — относительно недавно сформировавшаяся самостоятельная область математической науки, бурный рост которой наблюдается со второй половины XIX века. За это время в оптимизации сформировались свои подобласти, появился свой язык, обнаружилось множество приложений; ей посвящено огромное количество работ (см., например, [1, 9] и цитированную там литературу). Процесс развития данной области знаний интенсивно продолжается и по сей день.

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

Задача оптимизации с комплементарными ограничениями (ЗОКО) в общей форме имеет вид f{x) min, h(x) = 0, g{x) ^ О, G(x) > О, Я (ж) ^ 0, (G(x), Н(х)) = О, а задача оптилшзации с исчезающими ограничениями (ЗОИО) имеет вид f(x) -»■ min, h(x) = 0, g(x) ^ О, Я,(х)^0, Gl(x)IIl(x) ^ 0, г = 1.s, где /:R" -» К - гладкая функция, a h:Wl -> Rl, g:Rn -> Em, G, H:Rn Ks -гладкие отображения.

ЗОКО является относительно хорошо изученным классом задач, для которого все принципиальные трудности связаны именно с комплементарными ограничениями, составляющими вторую строку в (1) [59, 63]. Поэтому в данной работе для простоты изложения задача (1) рассматривается без «обычных» ограничений типа равенств и неравенств (первая строка в (1)), которые легко могут быть добавлены. Вместе с тем, ЗОИО — относительно недавно сформировавшийся класс задач, который изучен сравнительно мало, и поэтому задачи данного класса рассматриваются здесь в самой общей форме (2). Название последнего класса задач, впервые введенного в [17], связано с тем, что если в точке х G 1КП для некоторого индекса г Е {1, ., s} имеет место равенство Нг(х) = 0, то последнее ограничение в задаче (2) выполняется автоматически, т.е. «исчезает»; если же Нг(х) > 0, то последнее ограничение эквивалентно неравенству G\(x) ^ 0.

Два вышеприведенных класса задач тесно связаны между собой. В частности, ЗОИО можно свести к следующей ЗОКО с помощью введения дополнительной переменной и G Rs: f{x) min, h(x) = 0, g(x) ^ 0, G(x) - и ^ 0, H{x) ^ 0, и ^ 0, (H(x), u) = 0.

Однако, помимо повышения размерности задачи, такое сведение имеет следующий серьезный недостаток: для данного (локального) решения х ЗОИО (2) соответствующее оптимальное значение дополнительной переменной и определяется неоднозначно, и соответствующие локальные решения ЗОКО (3) не могут быть строгими. В частности, в этих решениях не могут выполняться достаточные условия второго порядка оптимальности, а значит, основанные на таких условиях теоретические результаты (о чувствительности, о численных методах) неприменимы. Кроме того, ЗОИО являются в определенном смысле «менее нерегулярными», чем ЗОКО [17]. Эти обстоятельства заставляют рассматривать ЗОИО как самостоятельный класс задач, требующий специальных подходов и методов. С другой стороны, нетрудно видеть, что ЗОКО также можно рассматривать как ЗОИО с дополнительными обычными ограничениями —G(x) ^ 0. Однако, такая интерпретация ЗОКО как ЗОИО не дает преимуществ, так как дополнительные ограничения —G(x) ^ 0 ухудшают свойства регулярности полученной таким образом ЗОРЮ.

Важнейшим источником возникновения ЗОКО являются так называемые двухуровневые задачи оптимизации или задачи двухуровневого программирования. Впервые частный случай таких задач был рассмотрен Штакельбергом в 1934 г. при исследовании иерархических рыночных структур. Двухуровневые задачи оптимизации — класс оптимизационных задач, в которых, помимо стандартных ограничений типа равенств и неравенств, присутствует ограничение, описываемое с помощью другой оптимизационной задачи, называемой задачей нижнего уровня. Таким образом, эти задачи имеют двухуровневую иерархическую структуру, что объясняет название данного класса. Переменные в этих задачах разделены на два вектора х и у, где х определяется как решение задачи нижнего уровня, в которой у выступает в качестве параметра. Детали о двухуровневых задачах оптимизации см., например, в [25, 59].

Двухуровневые задачи оптимизации можно сводить к обычным (одноуровневым) задачам оптимизации разными способами (см., например, [25]). Следующий подход приводит к ЗОКО: задачу нижнего уровня можно заменить ее системой Каруша-Куна-Таккера (ККТ). Однако получаемая таким образом ЗОКО, вообще говоря, не эквивалентна исходной двухуровневой задаче оптимизации. Они эквивалентны в том случае, если задача нижнего уровня является выпуклой и регулярной, используется оптимистический подход к понятию решения этой задачи, и в задаче верхнего уровня нет ограничений, связанных с переменными задачи нижнего уровня, кроме ограничения, описываемого оптимизационной подзадачей нижнего уровня.

Другим важным примером приложения ЗОКО являются задачи нахождения оптимальной формы упругопластических балочных (стержневых) конструкций [31], которые относятся к так называемой оптимизации форм. В оптимизации форм геометрическая форма конструкции задана; не заданы только проектные переменные, в данном I случае — площади поперечных сечений стержней. Будем рассматривать стержневую систему, поведение которой определяется поведением ее элементов. Простейшим примером такой системы является ферма. Предполагается, что рассматриваемая система является голономной (т.е. системой, в которой все механические связи можно свести к геометрическим). Основные связи всей системы в духе теории пластичности (см., например, [10, 11]) могут быть записаны следующим образом: = Стх, ц = Си, = е + х = ве, р = Ыг, из =-Ыгх + Кг + г, (4) ги 0, О 0, гитг = 0. (5)

Векторы и матрицы представляют собой наборы некоторых несвязанных величин для отдельных элементов системы. Для системы с й степенями свободы (количество координат, по которым могут свободно перемещаться узловые точки) и п элементами, в первом уравнении (4) посредством матрицы совместимости (или геометрической матрицы) С Е Ш71 х имеющей полный столбцовый ранг, представлено равновесие между узловыми нагрузками / £ Е1* и напряжениями в элементах х € Еп. Второе уравнение в (4) представляет линейную зависимость деформаций с/ Е К" от узловых смещений и 6 Е^. Третье равенство в (4) выражает аддитивность упругой деформации еЕК"и пластической деформации р £ К", т.е. общая деформация получается путем сложения последних. Четвертое равенство в (4) выражает линейную эластичность (упругость), где 5 е К" х 1" - матрица, в которой содержатся жесткости элементов. Пластические деформации р в пятом уравнении (4) определяются ассоциированным законом течения (закон, согласно которому, пластические деформации развиваются по нормали к поверхности текучести [12]) в терминах пластических множителей г Е Шт, где т — количество функций текучести, посредством матрицы внешних нормалей N 6 Мп х Е7'1 к поверхности текучести. В шестом уравнении (4) определена линейная функция текучести т(х(г), г):Мт —> Кт, которая посредством матрицы К £ Кш х определяет модель упрочнения с известными пределами текучести г 6 К™. Наконец, условие комплементарности в (5) означает, что если наблюдается текучесть (т.е. и> = 0), то может произойти пластическая деформация (т.е. г ^ 0); если же выполнено условие упругости (т.е. и> > 0), то пластические деформации невозможны (т.е. z = 0).

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

Пусть I е К" — вектор длин всех стержней. Тогда задачу нахождения минимального объема можно формально записать как следующую ЗОКО: а) —> тт,

-х + 5(а)Си - 5(а)УУг = 0, СТх - / = 0, + К (а) г + г (а) = т, ги^О, г ^ 0, гиТг = 0, —й ^ и ^ й, г ^ г, а/ ^ а ^ аи, Та = 0, где й е — вектор пределов смещений, г € Мт — вектор верхних ограничений на пластические множители, моделирующий ограниченную пластичность элементов, щ, аи £ К" — нижние и верхние ограничения на площади поперечных сечений стержней соответственно, Т 6 Е' х К" - технологическая матрица, налагающая Ь ограничений на проектные переменные (площади поперечных сечений).

Многочисленные другие приложения ЗОКО представлены в [59, 63].

Наиболее известным приложением ЗОИО являются задачи нахождения оптимального дизайна топологий (задачи проектирования оптимальной топологии) механических конструкций [17, 16]. В отличие от традиционной оптимизации форм, такая оптимизация дизайна не предполагает предопределенной форму структуры. Классическим и наиболее цитируемым учебником по оптимизации топологий в настоящее время является [18]. Оптимизация топологий становится все более общепринятым инструментом в промышленных приложениях, например, в производстве автомобилей и самолетов.

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

Рассмотрим пример из [17] нахождения оптимального дизайна жесткой (упругой) конструкции. Будем использовать так называемый подход «базовой конструкции». Для этого рассмотрим множество из М так называемых потенциальных балок, которые определяются координатами своих концов (в К2 или в К3). Более того, параметры материалов (модуль Юнга ограничения на напряжения а[ > 0 и асг < 0 при растяжении и сжатии соответственно) для каждой г-ой потенциальной балки заданы. Эти параметры нужны для формулировки ограничений, предотвращающих разрушение конструкции, когда потенциальная балка становится реальной. Последнее имеет место в случае, когда вычисленная площадь поперечного сечения аг балки положительна. Наконец, граничные (краевые) условия (т.е. фиксированные узловые координаты) и внешние силы (т.е. силы, прилагаемые к некоторым узлам) считаются заданными. Задача («задача проектирования топологии жесткой структуры») состоит в нахождении площадей поперечного сечения аг для каждой потенциальной балки, таких чтобы было предотвращено разрушение всей конструкции, внешние силы удерживались конструкцией и подходящая целевая функция имела минимальное значение. В качестве целевой функции обычно берется общий вес конструкции, или ее объем, или энергия деформации («податливость» — обратная величина жесткости).

Для того, чтобы получилась хорошая результирующая конструкция после оптимизации, базовая конструкция должна состоять из большого числа потенциальных балок. На рис. 1 (взятом из [17]) изображена базовая структура в К2. Конструкция (до проектирования) считается фиксированной слева, что отображено как стена. Справа к конструкции прикладывается внешняя сила (вертикальная стрелка), которая должна удерживаться конструкцией. Пусть дана прямоугольная область, на которую нанесена сетка с 15 х 9 узловыми точками. Все узловые точки попарно соединены между собой потенциальными балками. После исключения длинных потенциальных балок, которые состоят из более мелких потенциальных балок, в такой конструкции остается 5614 потенциальных балок. На рис. 1 черными линиями изображены некоторые из них, так как изображение всех балок привело бы к полностью черной картинке.

Рис. 1: Базовая структура.

Рис. 2: Оптимальная структура.

С практической точки зрения естественно надеяться, что оптимальный дизайн й будет использовать небольшое количество потенциальных балок, т.е. неравенство аг > 0 будет выполняться для малого количества индексов г, в то время как большинство площадей поперечных сечений Щ будут равны нулю. На рис. 2, также заимствованном из [17], изображена полученная численно оптимальная структура, в основе которой лежала базовая структура, приведенная на рис. 1. В самом деле, большинство потенциальных балок не реализовались, и такое поведение является типичным в прикладных задачах проектирования топологий жестких конструкций.

Одним из возможных и естественных способов формулировки задач указанного типа является ЗОИО. Простая формулировка задачи проектирования жесткой конструкции с ограничениями на напряжения и на продольный изгиб имеет следующий вид: f(a,u) —> min, д(а,и) ^ О, а ^ 0, К(а)и = F, ^ и) ^ of7, если ßj > 0, г = 1, ., т, f\nt(a, и) ^ /fucfc(a), если щ > 0, г = 1, ., т. Здесь вектор а G IR7", а ^ 0 является вектором площадей поперечных сечений потенциальных балок, а и € Rd — вектор узловых смещений структуры (конструкции) под действием приложенной силы, где d — количество степеней свободы структуры. Переменная состояния и является дополнительной переменной. Целевая функция / обычно представляет собой вес или податливость конструкции, но также может быть и другой величиной, определяемой дизайном а и соответствующим состоянием и структуры. Нелинейная система уравнений К(а)и = F отображает равновесие сил внешних нагрузок F £ Rd и внутренних сил (вдоль балок) выраженное законом Гука в терминах смещений и площадей поперечных сечений. Матрица К (а) 6 xRd — глобальная матрица жесткости, соответствующая структуре а, которая всегда является симметричной и неотрицательно определенной. Ограничение д(а,и) — ограничение на ресурс, т.е. на общий объем конструкции (например, если / символизирует податливость) или на податливость конструкции (например, если / символизирует объем или вес). Если di > 0, тогда <7j(a> и) G Ш — напряжение вдоль г-ой балки, а erf, crf7 — нижнее и верхнее ограничения на напряжения для г-ой балки соответственно. Аналогично, если a,i > 0, f-nt(a,u) G R означает внутреннюю силу вдоль г-ой балки, а fiUck{a) соответствует допустимой эйлеровой силе или критической силе при продольном изгибе (наибольшее значение сжимающей силы, при которой сжатое упругое тело (длинный стержень и т. п.) еще сохраняет начальную (неизогнутую) форму равновесия). Здесь предполагается, что геометрическая форма поперечных сечений задана, например, круг или квадрат. Тогда критическая сила при продольном изгибе зависит только от щ. Таким образом, ограничения на напряжения и на продольный изгиб имеют смысл только в том случае, если а* > 0. Значит эти ограничения должны исчезать из задачи, если о, = 0. К счастью, функции Uj, /¡nt и f^uck обладают непрерывным продолжением при щ —> 0, и могут быть определены также для щ = 0 (без какого-либо прямого физического смысла). Это позволяет сформулировать эту задачу как ЗОИО; для этого достаточно положить Hi {а, и) — щ, для всех г = 1, ., т и к — 1, 2, 3, а СЦа, и) = of - <п(а,и), С?(а, и) = аг(а,и) - аи{ , &'?(а, и) = /?""*(а) - Дп\а,и), г = 1, ., т, и все остальные ограничения считать «обычными».

В частности, задачу проектирования топологий ферм можно записать и следующим образом [23]:

ТП = Z) Pi^ih -» min, /Cuj = Fj, j = 1.n, 1

Oi ^ 0, aj(of - ajj) ^ 0, аг-(а^ - crf) ^0, г = 1, ., m, где m — общее количество потенциальных балок в базовой структуре, п — количество прилагаемых сил к конструкции, pi и Ii — плотность и длина г-ой балки соответственно. Здесь целевая функция представляет общий вес конструкции.

Пример 1. Рассмотрим простейший пример конструкции, взятый из [23], в которой имеется 4 балки; см. рис. 3(а). К структуре в узловой точке (точке соединения всех балок) прикладывается вертикальная сила F = 1, изображенная в виде стрелки. Предполагается, что модуль Юнга Е — 1, длины всех балок равны 1. Кроме того, предполагается, что площади поперечных сечений балок 1 и 3 одинаковы и равны 1

01, их массовая плотность р\ = 2, допустимое напряжение для них =--р,

5\/2 uf = —две другие балки имеют также одинаковые площади поперечных сечений Ъу2 l 1 u 1

02, массовую ПЛОТНОСТЬ Pi = 1, допустимое напряжение ДЛЯ НИХ Сто = — 0~2 =

5 5

Из структурного анализа имеем: л/2 1 п

0-1 = 03 = —-;-г, = -;-. 04 = и,

2(ßi + а2) ах + а2 где предполагается, что а\ + а2 > 0. При этом, оптимизационная задача может быть сформулирована в следующем виде: = Аа\ + 2а2 —> min, ai ^ 0, а2 ^ 0, aj(5\/2 — ах — а2) ^ 0, а2(5 — ах — а2) < 0.

Соответствующее допустимое множество изображено на рис. 3(6) серым цветом с выделенной границей. Обращаем внимание на отрезок, соединяющий точки (0, 5\/2) и (0,5), все точки которого допустимы. а) Четырехбалочная конструкция (б) Допустимое множество

Рис. 3: Конструкция и допустимое множество.

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

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

ViPi► min, K(p)u = F, (F, и) ^ с, 0 ^ р ^ 1, i=i of(p, и) ^ а2, если pi > 0, г = 1, ., п, где р 6 М", и £ Kd. Здесь предполагается, что область Г2 разбита на п конечных элементов. Так называемая проектная переменная р G К™, pi G [0, 1] для всех i — 1, ., п, символизирует распределение материала по этим элементам, т.е. рг — плотность материала, который находится в элементе г (рг также может быть проинтерпретирована как «толщина» или другая характеристика материала, содержащегося в элементе г; см. [18]). Целевая функция представляет вес структуры, где V\, ., vn — весовые множители или коэффициенты, которые обычно учитывают размеры элементов и веса используемых материалов.

Оптимизация осуществляется при воздействии внешней силы F 6 Md. Для простоты здесь рассматривается случай, когда прикладываемая к структуре сила одна. Предполагается, что внешние силы прикладываются только к узловым точкам дис-кретизированной структуры. Как и в предыдущем приложении, число d означает количество степеней свободы структуры, и € Rd — вектор всех узловых смещений, а так называемое упругое равновесие К(р)и — F выражает связь проектных переменных с узловыми смещениями, где К{р) 6 Kd х Rd — глобальная матрица жесткости, которая может быть вырожденной, если некоторые (или многие) элементы pi равны нулю. Далее, так называемая податливость (F, и) структуры ограничивается определенной пользователем константой с. Это ограничение, необходимое для того, чтобы задача была корректной, может рассматриваться как ограничение на энергию деформации структуры, порожденную внешней силой F. Отметим, что (F, и) ^ 0 для всех допустимых (р, и), так как К(р) неотрицательно определена. Кроме того, of(p, и) означает квадрат нагрузки на г-ый элемент, а ¿г2 — ее предельное допустимое значение.

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

-> min- К(р)и = F, (F, и) ^ с, р ^ 1, 1

Pi ^ 0, pi(af(p, и) - ä2) ^ 0, г = 1, ., п.

На рис. 4, взятом из [16], приводится дискретизированная область Q размера 16x32 элемента, которая фиксирована слева, и к правому нижнему узлу которой прикладывается внешняя сила F, направленная вниз. На рис. 5 приводится полученная в процессе численной оптимизации консольная структура из [16]. Значения pi линейно меняются В серых тонах ОТ белого (Pi = 0) ДО черного (Рг = 1). я fy

Рис. 4: Дискретизированная область.

Рис. 5: Консольная структура.

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

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

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

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

В диссертации для решения задач оптимизации с комплементарными ограничениями предлагается подход, основанный на поднятой переформулировке данных задач. Впервые идея такой переформулировки была предложена в [72]. Предлагаемый подход состоит из двух этапов: сначала осуществляется переформулировка исходной ЗОКО в виде поднятой задачи с обычными ограничениями-равенствами, а затем к поднятой задаче применяются полугладкий метод Ньютона и полугладкий метод последовательного квадратичного программирования (ПКП). При этом, в отличие от работы [72], предлагается использовать поднятую задачу, ограничения которой обладают большей регулярностью, но дифференцируемы лишь один раз, и именно это приводит к необходимости применения полугладких ньютоновских методов. Аналогичный подход предлагается и для решения ЗОИО. Второй предлагаемый подход для решения ЗОИО состоит из двух этапов: сначала строятся локальные методы активного множества для этих задач, а затем осуществляется гибридная глобализация их сходимости.

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

Основные результаты диссертационной работы заключаются в следующем.

1. Осуществлено сведение задач двух указанных классов к поднятым задачам с обычными ограничениями-равенствами и неравенствами. Теоретически обоснованы взаимосвязи поднятых и исходных задач. Кроме того, для задач оптимизации с исчезающими ограничениями уточнены условия оптимальности первого и второго порядков.

2. Для решения поднятых задач предложены полугладкий метод Ньютона и полугладкий метод последовательного квадратичного программирования. Обоснована их локальная сверхлинейная сходимость. Осуществлена глобализация сходимости предложенных методов. Численное сравнение разработанных методов с альтернативными методами для ЗОКО на 38 задачах из тестовой коллекции МасМРЕС [58], а для ЗОИО на собственной коллекции из 23 примеров, взятых из всех известных автору публикаций, касающихся данного класса задач, продемонстрировало их эффективность и конкурентоспособность.

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

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

Заключение

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

1. Васильев Ф.П. Методы оптимизации: в 2-х кн. Новое изд., перераб. и доп. М.: МЦНМО, 2011.

2. Измаилов А.Ф. Зададачи оптимизации с комплементарными ограничениями: регулярность, условия оптимальности и чувствительность // Ж. вычисл. матем. и матем. физ. 2004. Т. 44, № 7. С. 1209-1228.

3. Измаилов А.Ф. Чувствительность в оптимизации. М.: Физматлит, 2006.

4. Измаилов А.Ф., Погосян А.Л. Условия оптимальности и ньютоновские методы для задач оптимизации с исчезающими ограничениями // ЖВМиМФ. 2009. Т. 49, № 7. С. 1184-1196.

5. Измаилов А.Ф., Погосян А.Л. О методах активного множества для задач оптимизации с исчезающими ограничениями // Тематический сборник «Теоретические и прикладные задачи нелинейного анализа». М.: ВЦ РАН, 2009. С. 18-49.

6. Измаилов А.Ф., Погосян А.Л. Полугладкий метод последовательного квадратичного программирования для поднятых задач оптимизации с исчезающими ограничениями // ЖВМиМФ. 2011. Т. 51, № 6. С. 983-1006.

7. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. 2-е изд., перераб. и доп. М.: Физматлит, 2008.

8. Ильюшин А.А. Пластичность. 4.1. Упруго-пластические деформации. М., Ленинград: Государственное издательство технико-теоретической литературы, 1948.

9. Ильюшин А.А., Ленский B.C. Сопротивление материалов. М.: Физматлит, 1959.

10. Качанов Л.М. Основы теории пластичности. М.: Наука, 1969.

11. Погосян А.Л. Численное сравнение ньютоновских методов для задач оптимизации с исчезающими ограничениями // Тематический сборник «Теоретические и прикладные задачи нелинейного анализа». В печати.

12. Achtziger W., Hoheisel Т., Kanzow С. A smoothing-regularization approach to mathematical programs with vanishing constraints // Preprint 284 / Institute of Mathematics, University of Wiirzburg. Wiirzburg, 2008.

13. Achtziger W., Kanzow C. Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications // Math. Program. 2007. V. 114, № 1. P. 69-99.

14. Bendsoe M.P., Sigmund 0. Topology Optimization. Berlin, Heidelberg, New York: Springer, 2003.

15. Billups S. C. Algorithms for complementarity problems and generalized equations. Tech. report 95-14 and Ph.D. thesis. Computer Sciences Department, University of Wisconsin. Madison, 1995.

16. Boggs B.T., Tolle J.W. Sequential quadratic programming // Acta Numerica. 1996. V. 4. P. 1-51.

17. Bonnans J.F. Local analysis of Newton-type methods for variational inequalities and nonlinear programming // Appl. Math. Optim. 1994. V. 29. P. 161-186.

18. Bonnans J.F., Gilbert J.Ch., Lemaréchal C., Sagastizábal C. Numerical optimization. Theoretical and practical aspects. Berlin: Springer-Verlag, 2006.

19. Cheng G.D., Guo X. e-relaxed approach in structural topology optimization // Structural Optimization 13, 1997. P. 258—266.

20. De Luca T., Facchinei F., Kanzow C. A theoretical and numerical comparison of some semismooth algorithms for complementarity problems // Comput. Optim. Appl. 2000. V. 16. P. 173-205.

21. Dempe S. Foundations of bilevel programming. New York, Boston, Dordrecht, Moscow: Kluwer Academic Publishers, 2002.

22. Dolan E., Moré J. Benchmarking optimization software with performance profiles // Math. Program. 2002. V. 91, № 2. P. 201-213.

23. Facchinei F., Fischer A., Kanzow C. On the accurate identification of active constraints // SIAM J. Optimizat. 1999. V. 9. P. 14-32.

24. Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity Problems. New York: Springer-Verlag, 2003.

25. Facchinei F., Soares J. A new merit function for nonlinear complementarity problems and a related algorithm // SIAM J. Optim. 1997. V. 7. P. 225-247.

26. Fernández D., Izmailov A.F., Solodov M.V. Sharp primal superlinear convergence results for some Newtonian methods for constrained optimization // SIAM J. Optim. 2010. V. 20, № 6. P. 3312-3334.

27. Ferris M.C., Tin-Loi F. On the solution of a minimum weight elastoplastic .problem involving displacement and complementarity constraints // Comput. Methods Appl. Mech. Engrg., 1999. V. 174, № 1-2. P. 108-120.

28. Fischer A. Local behaviour of an iterative framework for generalized equations with nonisolated solutions // Math. Program. 2002. V. 94. P. 91-124.

29. Fletcher R., Leyffer S. Solving mathematical programs with equilibrium constraints as nonlinear programs // Optim. Methods Softw. 2004. V. 19. P. 15-40.

30. Fletcher R., Leyffer S., Ralph D., Scholtes S. Local convergence of SQP methods for mathematical programs with equilibrium constraints // SIAM J. Optim. 2006. V. 17, № 1. P. 259-286.

31. Hager W. W., Gowda M.S. Stability in the presence of degeneracy and error estimation // Math. Program. 1999. V. 85. P. 181-192.

32. Han J., Sun D. Superlinear convergence of approximate Newton methods for LC1 optimization problems without strict complementarity 11 Recent Advances in Nonsmooth Optimization. V. 58. Singapur: World Scientific Publishing Co, 1993. P. 353-367.

33. Hoheisel T., Kanzow G. First- and second-order optimality conditions for mathematical programs with vanishing constraints // Appl. of Math. 2007. V. 52. P. 495-514.

34. Hoheisel T., Kanzow C. Stationarity conditions for mathematical programs with vanishing constraints using weak constraint qualifications //J. Math. Anal. Appl. 2008. V. 337. P. 292-310.

35. Hoheisel T., Kanzow C. On the Abadie and Guignard constraint qualifications for mathematical programs with vanishing constraints // Optimization. 2009. VI 58, № 4. P. 431-448.

36. Hoheisel T., Kanzow C., Outrata J. Exact penalty results for mathematical.programs with vanishing constraints. // Nonlinear Analysis. 2010. V. 72. P. 2514-2526.

37. Hoheisel T., Kanzow C., Schwartz A. Convergence of a local regularization approach for mathematical programs with complementarity or vanishing constraints // Optim. Meth. Software. To appear.

38. Ip C.-M. and Kyparisis J. Local convergence of quasi-Newton methods for B-differentiable equations // Mathematical Programming. 1992. V. 56. P. 71-89.

39. Izmailov A.F., Pogosyan A.L. Active-set Newton methods for mathematical programs with vanishing constraints // Comput. Optim. Appl. To appear.

40. Izmailov A.F., Pogosyan A.L., Solodov M.V. Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints // Comput. Optim. Appl. 2010. DOI 10.1007/sl0589-010-9341-7.

41. Izmailov A.F., Solodov M. V. Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems // SIAM J. Optim. 2002. V. 13, № 2. P. 386-405.

42. Izmailov A.F., Solodov M. V. Newton-type methods for optimization problems without constraint qualifications // SIAM J. Optimizat. 2004. V. 15. P. 210-228

43. Izmailov A.F., Solodov M.V. An active-set Newton method for mathematical programs with complementarity constraints // SIAM J. Optim. 2008. V. 19, № 3. P. 1003-1027.

44. Izmailov A.F., Solodov M. V. Mathematical programs with vanishing constraints: optimality conditions, sensitivity, and a relaxation method //J. Optim. Theory Appl. 2009. V. 142, № 3. P. 501-532.

45. Izmailov A.F., Solodov M. V. On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions // Math. Program. 2009. V. 117. P. 271304.

46. Jiang H. Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation of the complementarity problem // Math. Oper. Res. 1999. V. 24. P. 529-543.

47. Kanzow C., Kleinmichel H. A new class of semismooth Newton-type methods for nonlinear complementarity problems // Comput. Optim. Appl. 1998. V. 11. P. 227251.

48. Kojima M., Shindo S. Extensions of Newton and quasi-Newton methods to systems of PC1 equations // J. Oper. Res. Soc. Japan. 1986. V. 29. P. 352-374.

49. Kummer B. Newton's method based on generalized derivatives for nonsmooth functions // Advances in Optimization, W. Oettli and D. Pallaschke, eds. Berlin: Springer-Verlag, 1992. P. 171-194.

50. Leyffer S. MacMPEC: AMPL collection of Mathematical Programs with Equilibrium Constraints. http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC.

51. Luo Z.-Q., Pang J.-S., Ralph D. Mathematical programs with equilibrium constraints. Cambridge: Cambridge Univ. Press, 1996.

52. Martinez J.M., Qi L. Inexact Newton methods for solving nonsmooth equations // J. of Computational and Applied Mathematics. 1995. V. 60. P. 127-145.

53. Mifflin R. Semismooth and semiconvex functions in constrained optimization // SIAM J. Control Optim. 1977. V. 15. P. 959-972.

54. Nocedal J., Wright S.J. Numerical optimization. New York, Berlin, Heidelberg: Springer-Verlag, 2006.

55. Outrata J. V., Kocvara M., Zowe J. Nonsmooth approach to optimization problems with equilibrium constraints: Theory, applications and numerical results. Boston: Kluwer Acad. Publ., 1998.

56. Pang J. S., Qi L. Nonsmooth equations: Motivation and algorithms // SIAM J. Optim. 1993. V. 3. P. 443-465.

57. Qi L. Convergence analysis of some algorithms for solving nonsmooth equations // Math. Oper. Res. 1993. V. 18. P. 227-244.

58. Qi L. Superlinearly convergent approximate Newton methods for LC1 optimization problems // Math. Program. 1994. V. 64. P. 277-294.

59. Qi L., Sun J. A nonsmooth version of Newton's method // Math. Program. 1993. V. 58. P. 353-367.

60. Ralph D. Sequential quadratic programming for mathematical programs with linear complementarity constraints // Computational Techniques and Applications: CTAC95. Singapore: World Scientific, 1996. P. 663-668.

61. Ralph D., Wright S. J. Some properties of regularization and penalization schemes for MPECs // Optim. Methods Softw. 19 (2004), 527-556.

62. Scheel H., Scholtes S. Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity // Math. Oper. Res. 2000. V. 25. P. 1-22.

63. Scholtes S. Convergence properties of a regularization scheme for mathematical programs with complementarity constraints // SIAM J. Optim. 2001. V. 11. P. 918936.

64. Stein 0. Lifting mathematical programs with complementarity constraints // Math. Program. 2010. DOI 10.1007/sl0107-010-0345-y.

65. Tseng P. Growth behavior of a class of merit functions for the nonlinear complementarity problem // JOTA. 1996. V. 89, № 1. P. 17-37.