Ньютоновские методы для задач оптимизации с распадающимися ограничениями
Оптимизация осуществляется при воздействии внешней силы F 6 Md. Для простоты здесь рассматривается случай, когда прикладываемая к структуре сила одна. Предполагается, что внешние силы прикладываются только к узловым точкам дис-кретизированной структуры. Как и в предыдущем приложении, число d означает количество степеней свободы структуры, и € Rd — вектор всех узловых смещений, а так называемое… Читать ещё >
Содержание
- Список основных обозначений
- Глава 1. Задачи оптимизации с распадающимися ограничениями: элементы теории
- 1. 1. Задачи оптимизации с комплементарными ограничениями
- 1. 1. 1. Предварительные сведения
- 1. 1. 2. Поднятая задача
- 1. 2. Задачи оптимизации с исчезающими ограничениями
- 1. 2. 1. Регулярность, стационарность и условия оптимальности
- 1. 2. 2. Поднятая задача
- 1. 1. Задачи оптимизации с комплементарными ограничениями
- 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. 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 К&trade-. Наконец, условие комплементарности в (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, ., т, fnt (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 К&trade-, 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, и) — a2) ^ 0, г = 1, ., п.
На рис. 4, взятом из [16], приводится дискретизированная область Q размера 16×32 элемента, которая фиксирована слева, и к правому нижнему узлу которой прикладывается внешняя сила F, направленная вниз. На рис. 5 приводится полученная в процессе численной оптимизации консольная структура из [16]. Значения pi линейно меняются В серых тонах ОТ белого (Pi = 0) ДО черного (Рг = 1). я fy.
Рис. 4: Дискретизированная область.
Рис. 5: Консольная структура.
Объектом исследования в диссертационной работе являются задачи оптимизации с комплементарными ограничениями и задачи оптимизации с исчезающими ограничениям, которые относятся к объемлющему их классу задач оптимизации с распадающимися ограничениями.
Основной целью диссертационного исследования является построение эффективных численных методов решения задач оптимизации с комплементарными и с исчезающими ограничениями.
Актуальность темы
диссертационной работы обусловлена широким полем практических приложений задач оптимизации с комплементарными ограничениями и важными приложениями задач оптимизации с исчезающими ограничениями в области оптимального дизайна топологий механических структур. Некоторые из этих приложений были приведены выше. Кроме того, задачи оптимизации с комплементарными и с исчезающими ограничениями трудны для анализа и численного решения из-за неизбежной вырожденности их ограничений. Таким образом, указанные задачи представляют как практический, так и теоретический интерес.
Методика исследования. При выполнении работы использовались средства нелинейного анализа, современного негладкого анализа, теории оптимизации, а также методы и подходы современной численной оптимизации.
В диссертации для решения задач оптимизации с комплементарными ограничениями предлагается подход, основанный на поднятой переформулировке данных задач. Впервые идея такой переформулировки была предложена в [72]. Предлагаемый подход состоит из двух этапов: сначала осуществляется переформулировка исходной ЗОКО в виде поднятой задачи с обычными ограничениями-равенствами, а затем к поднятой задаче применяются полугладкий метод Ньютона и полугладкий метод последовательного квадратичного программирования (ПКП). При этом, в отличие от работы [72], предлагается использовать поднятую задачу, ограничения которой обладают большей регулярностью, но дифференцируемы лишь один раз, и именно это приводит к необходимости применения полугладких ньютоновских методов. Аналогичный подход предлагается и для решения ЗОИО. Второй предлагаемый подход для решения ЗОИО состоит из двух этапов: сначала строятся локальные методы активного множества для этих задач, а затем осуществляется гибридная глобализация их сходимости.
Далее опишем структуру диссертации. Диссертационная работа состоит из введения, трех глав, заключения, двух приложений и списка литературы из 73 наименований.
Основные результаты диссертационной работы заключаются в следующем.
1. Осуществлено сведение задач двух указанных классов к поднятым задачам с обычными ограничениями-равенствами и неравенствами. Теоретически обоснованы взаимосвязи поднятых и исходных задач. Кроме того, для задач оптимизации с исчезающими ограничениями уточнены условия оптимальности первого и второго порядков.
2. Для решения поднятых задач предложены полугладкий метод Ньютона и полугладкий метод последовательного квадратичного программирования. Обоснована их локальная сверхлинейная сходимость. Осуществлена глобализация сходимости предложенных методов. Численное сравнение разработанных методов с альтернативными методами для ЗОКО на 38 задачах из тестовой коллекции МасМРЕС [58], а для ЗОИО на собственной коллекции из 23 примеров, взятых из всех известных автору публикаций, касающихся данного класса задач, продемонстрировало их эффективность и конкурентоспособность.
3. Для решения ЗОИО предложены кусочный метод последовательного квадратичного программирования и методы активного множества. При весьма слабых предположениях обоснована их локальная сверхлинейная сходимость. Осуществлена глобализация сходимости методов активного множества. Численное сравнение разработанных методов с альтернативными методами продемонстрировало их эффективность и конкурентоспособность.
4. Заключительное сравнение разработанных методов для поднятых ЗОИО и методов активного множества между собой с целью выявления наилучшего среди них дало неоднозначную картину. Это свидетельствует о том, что у каждого из разработанных методов есть свои относительные преимущества и недостатки, и каждый из них может быть полезен в определенных ситуациях.
Заключение
.
В работе исследовались два трудных и актуальных класса задач математического программирования, относящиеся к так называемым задачам оптимизации с распадающимися ограничениями: задачи оптимизации с комплементарными ограничениями и задачи оптимизации с исчезающими ограничениями. Разработаны и обоснованы различные методики их численного решения, эффективность которых подтверждена вычислительным экспериментом.
Список литературы
- Васильев Ф.П. Методы оптимизации: в 2-х кн. Новое изд., перераб. и доп. М.: МЦНМО, 2011.
- Измаилов А.Ф. Зададачи оптимизации с комплементарными ограничениями: регулярность, условия оптимальности и чувствительность // Ж. вычисл. матем. и матем. физ. 2004. Т. 44, № 7. С. 1209−1228.
- Измаилов А.Ф. Чувствительность в оптимизации. М.: Физматлит, 2006.
- Измаилов А.Ф., Погосян А. Л. Условия оптимальности и ньютоновские методы для задач оптимизации с исчезающими ограничениями // ЖВМиМФ. 2009. Т. 49, № 7. С. 1184−1196.
- Измаилов А.Ф., Погосян А. Л. О методах активного множества для задач оптимизации с исчезающими ограничениями // Тематический сборник «Теоретические и прикладные задачи нелинейного анализа». М.: ВЦ РАН, 2009. С. 18−49.
- Измаилов А.Ф., Погосян А. Л. Полугладкий метод последовательного квадратичного программирования для поднятых задач оптимизации с исчезающими ограничениями // ЖВМиМФ. 2011. Т. 51, № 6. С. 983−1006.
- Измаилов А.Ф., Солодов М. В. Численные методы оптимизации. 2-е изд., перераб. и доп. М.: Физматлит, 2008.
- Ильюшин А.А., Ленский B.C. Сопротивление материалов. М.: Физматлит, 1959.
- Качанов Л.М. Основы теории пластичности. М.: Наука, 1969.
- Погосян А.Л. Численное сравнение ньютоновских методов для задач оптимизации с исчезающими ограничениями // Тематический сборник «Теоретические и прикладные задачи нелинейного анализа». В печати.
- Achtziger W., Hoheisel Т., Kanzow С. A smoothing-regularization approach to mathematical programs with vanishing constraints // Preprint 284 / Institute of Mathematics, University of Wiirzburg. Wiirzburg, 2008.
- Achtziger W., Kanzow C. Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications // Math. Program. 2007. V. 114, № 1. P. 69−99.
- Bendsoe M.P., Sigmund 0. Topology Optimization. Berlin, Heidelberg, New York: Springer, 2003.
- 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.
- Boggs B.T., Tolle J.W. Sequential quadratic programming // Acta Numerica. 1996. V. 4. P. 1−51.
- Bonnans J.F. Local analysis of Newton-type methods for variational inequalities and nonlinear programming // Appl. Math. Optim. 1994. V. 29. P. 161−186.
- Bonnans J.F., Gilbert J.Ch., Lemarechal C., Sagastizabal C. Numerical optimization. Theoretical and practical aspects. Berlin: Springer-Verlag, 2006.
- Cheng G.D., Guo X. e-relaxed approach in structural topology optimization // Structural Optimization 13, 1997. P. 258—266.
- 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.
- Dempe S. Foundations of bilevel programming. New York, Boston, Dordrecht, Moscow: Kluwer Academic Publishers, 2002.
- Dolan E., More J. Benchmarking optimization software with performance profiles // Math. Program. 2002. V. 91, № 2. P. 201−213.
- Facchinei F., Fischer A., Kanzow C. On the accurate identification of active constraints // SIAM J. Optimizat. 1999. V. 9. P. 14−32.
- Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity Problems. New York: Springer-Verlag, 2003.
- 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.
- Fernandez 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.
- 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.
- Fischer A. Local behaviour of an iterative framework for generalized equations with nonisolated solutions // Math. Program. 2002. V. 94. P. 91−124.
- Fletcher R., Leyffer S. Solving mathematical programs with equilibrium constraints as nonlinear programs // Optim. Methods Softw. 2004. V. 19. P. 15−40.
- 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.
- Hager W. W., Gowda M.S. Stability in the presence of degeneracy and error estimation // Math. Program. 1999. V. 85. P. 181−192.
- 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.
- 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.
- 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.
- 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.
- Hoheisel T., Kanzow C., Outrata J. Exact penalty results for mathematical. programs with vanishing constraints. // Nonlinear Analysis. 2010. V. 72. P. 2514−2526.
- 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.
- Ip C.-M. and Kyparisis J. Local convergence of quasi-Newton methods for B-differentiable equations // Mathematical Programming. 1992. V. 56. P. 71−89.
- Izmailov A.F., Pogosyan A.L. Active-set Newton methods for mathematical programs with vanishing constraints // Comput. Optim. Appl. To appear.
- 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.
- 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.
- Izmailov A.F., Solodov M. V. Newton-type methods for optimization problems without constraint qualifications // SIAM J. Optimizat. 2004. V. 15. P. 210−228
- 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.
- 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.
- 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. 271 304.
- 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.
- Kanzow C., Kleinmichel H. A new class of semismooth Newton-type methods for nonlinear complementarity problems // Comput. Optim. Appl. 1998. V. 11. P. 227 251.
- 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.
- 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.
- Leyffer S. MacMPEC: AMPL collection of Mathematical Programs with Equilibrium Constraints. http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC.
- Luo Z.-Q., Pang J.-S., Ralph D. Mathematical programs with equilibrium constraints. Cambridge: Cambridge Univ. Press, 1996.
- Martinez J.M., Qi L. Inexact Newton methods for solving nonsmooth equations // J. of Computational and Applied Mathematics. 1995. V. 60. P. 127−145.
- Mifflin R. Semismooth and semiconvex functions in constrained optimization // SIAM J. Control Optim. 1977. V. 15. P. 959−972.
- Nocedal J., Wright S.J. Numerical optimization. New York, Berlin, Heidelberg: Springer-Verlag, 2006.
- 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.
- Pang J. S., Qi L. Nonsmooth equations: Motivation and algorithms // SIAM J. Optim. 1993. V. 3. P. 443−465.
- Qi L. Convergence analysis of some algorithms for solving nonsmooth equations // Math. Oper. Res. 1993. V. 18. P. 227−244.
- Qi L. Superlinearly convergent approximate Newton methods for LC1 optimization problems // Math. Program. 1994. V. 64. P. 277−294.
- Qi L., Sun J. A nonsmooth version of Newton’s method // Math. Program. 1993. V. 58. P. 353−367.
- Ralph D. Sequential quadratic programming for mathematical programs with linear complementarity constraints // Computational Techniques and Applications: CTAC95. Singapore: World Scientific, 1996. P. 663−668.
- Ralph D., Wright S. J. Some properties of regularization and penalization schemes for MPECs // Optim. Methods Softw. 19 (2004), 527−556.
- Scheel H., Scholtes S. Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity // Math. Oper. Res. 2000. V. 25. P. 1−22.
- Scholtes S. Convergence properties of a regularization scheme for mathematical programs with complementarity constraints // SIAM J. Optim. 2001. V. 11. P. 918 936.
- Stein 0. Lifting mathematical programs with complementarity constraints // Math. Program. 2010. DOI 10.1007/sl0107−010−0345-y.
- Tseng P. Growth behavior of a class of merit functions for the nonlinear complementarity problem // JOTA. 1996. V. 89, № 1. P. 17−37.