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

• Автор: Федосова, Алина Валерьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 105 с.

ОГЛАВЛЕНИЕ
Введение
Глава 1. Общий стохастический метод внешних аппроксимаций для решения задач полубесконечной оптимизации
§1.1 .Постановка задачи цолубескояечной оптимизации
§1.2.Математический аппарат и основные обозначения
§1.3.Схема активизированного поиска критических ограничений
§1.4.Квазиоптимальныефункции и квазиоптимальные множества
Глава 2. Алгоритмы стохастического метода внешних аппроксимаций для решения выпуклых задач полубесконечной оптимизации
§2.1 .Постановка выпуклых задач полубесконечной оптимизации
§2.2.Стохастический алгоритм внешних аппроксимаций с учетом
ограничений неравенств
§2.3.Механизм учета ограничений равенств в задачах полубесконечной оптимизации
§2,4.Стохастический алгоритм внешних аппроксимаций с учетом ограничений равенств и неравенств
Глава 3. Численное исследование задачи упруго-пластического кручения стержня
§3.1 .Физическая интерпретация и постановка задачи
§3.2.Сведение экстремальной постановки к выпуклой задаче полубесконечной оптимизации
§З.З.Характеристика программного обеспечения
§3.4.Проблема выбора локального алгоритма для активизированного поиска критических ограничений
§3.5.Численное решение задачи при различных сечениях стержня
§3,6,Численное решение задачи при различных вариантах учета
граничных условий
§3.7.0бсуждение результатов
Заключение
Список литературы
Приложение
ВВЕДЕНИЕ
Рассмотрим задачу математического программирования Р° : fix) —> min
V 7 хеХ°
д{х,у) < 0 Vy € П где функции f(x) и д(х, у) предполагаются непрерывно дифференцируемыми на Х°, Х° X У0 - выпуклых компактах; Х° С 7lk, У° С 7Z1. Здесь и далее 7Zm - m-мерное пространство.
В поставленной задаче множество У0 задает систему ограничений, определяющих допустимое множество задачи Р°. В случае конечного множества У0, задача Р° - это обычная задача математического программирования с конечным числом ограничений. Во многих реальных случаях множество У0 не является конечным, например, если у играет роль времени или пространственных координат. Поэтому если число переменных конечно, а число ограничений бесконечно, то такие задачи называются задачами полубесконечной оптимизации (semi-infinite programming).
К задачам такого типа относятся многие задачи аппроксимации, оптимального управления, вариационные неравенства.
Задачи полубесконечной оптимизации возникают в различных областях приложений [50, 20, 41]. Например, формулируются как по-лубесконечные задачи с ограничениями, зависящими от времени или пространственных координат: контроль загрязнения воздуха [45, 50, 75], инженерный дизайн [66, 65], проблема моментов [44, 52] и другие.
Задача Чебышевской аппроксимации также может быть представлена как линейная задача с бесконечным числом ограничений: заданы непрерывные функции /,5i,p2? »n9k на интервале [а, 6]. Необходимо найти линейную комбинацию функций рьрг? —i9hi которая наилучшим образом аппроксимирует /, подбирая числа a,xj,x2,
а —» min
- а < f(t),
-а < - f(t),

t € [а, 6].
Существуют причины, по которым задачи полубесконечной оптимизации вызывают особый интерес:
- нередко, на практике оказывается удобным, когда допустимая область в модели с ограничениями, зависищими от некоторого параметра у (времени, пространства, и т. п.), задана значением одного неравенства
д(х!,х2,-,хк;у) < г(у), а не большим числом несвязных ограничений типа
д1(х1,х2,-,к) < П-
Это лучше и с точки зрения хранения информации, так и простоты анализа проблемы. Даже в случаях, когда изначально задан второй способ описания, данные могут быть успешно сведены с помощью некоторой аппроксимации к формату описания первого типа;
- одна из причин изначального интереса к исследованию задач БГР состоит в стремлении исследователей объединить и расширить численные методы для решения задач Чебышевской аппроксимации.
Методам решения таких задач посвящено значительное число работ [41, 76, 50, 37, 42, 77, 78, 34, 65, 66, 45, 44, 52, 47, 46, 75, 67, 63, 49, 69, 70, 72, 55, 61, 56, 59, 60, 48, 33].
Теоретические основы задач полубесконечной оптимизации развиты достаточно глубоко [41, 52, 48, 33]. В вычислительном аспекте, который менее исследован, известны некоторые конкретные задачи аппроксимации и оптимального управления [45, 50, 75, 66, 65, 44, 52] и другие. Из последних работ следует отметить обзоры Полака [65] и Хеттиша с Кортанеком [50] задач полубесконечной оптимизации с точки зрения недифференцируемой и гладкой оптимизации соответственно, обзор Римтсена и Горнера [69] численных методов для общих гладких задач 31Р.
Методы для решения задач полубесконечной оптимизации являются естественным продолжением методов для решения задач математического программирования. Разобьем такие методы с точки зрения необходимости проверки достижения решением аппроксимирующей задачи Р(Уп) '
Р(Уп) : найти х е ХарАУп],

§2.2.Стохастический алгоритм внешних аппроксимаций с учетом ограничений неравенств.
Предлагаемый алгоритм решения задачи Р(У°) является алгоритмом внешних аппроксимаций, т. е. последовательно находит решения х" задач Р(У„), » = 1,2,
Р(У) : найти х 6 <Уор([У],
е ад I /(*)=йпч/(х-')},
Д-[К] = {х€Х°|з(у)<0 УубУ}.
При этом на п-й итерации алгоритма вначале формируется множество У„ путем добавления в множество Уп- новых точек из множества К0. Очередная аппроксимирующая задача Р(Уп) получается из предыдущей (п — 1)-ой аппроксимирующей задачи Р(Уп-1) путем добавления новых ограничений.
Важной особенностью предлагаемого алгоритма является активизированный ’’двухфазный” поиск критических ограничений при формировании множества У„ на тг-ой итерации, состоящий в следующем: -вначале получаем новое ограничение
У(чу) <
(т. е. точку у € Vго) методом Монте-Карло (с помощью датчика равномерного распределения на У0);
-затем, используя точку у в качестве стартовой, применяем алгоритм локального поиска для решения задачи
д(хп~’,-) -+ шах (2)
4 ' уеГ° 4 '
(где т - решение предыдущей аппроксимирующей задачи Р(У„_])) и находим точку у* - приближенное локальное решение (2), у* 6 У/Ш(д"-1), где У5(0((т) - это с-стационарное множество задачи
д(х, ) шах,
т. е. множество всех точек, удовлетворяющих необходимым условиям оптимальности 1-го порядка с точностью г.