ОГЛАВЛЕНИЕ
Введение........................................................3
Глава 1. Общий стохастический метод внешних аппроксимаций для решения задач пол у бесконечной оптимизации
§1.1.Постановка задачи цолубесконечной оптимизации.............25
§1.2.Матсматичсский аппарат и основные обозначения.............25
§1.3.Схема активизированного поиска критических ограничений....26
§1.4.Квазиоптимальпые функции и квазиоптнмальные множества....29 §1.5.0бпшй стохастический метол внешних аппроксимаций.......31
Глава 2. Алгоритмы стохастического метода внешних аппроксимаций для решения выпуклых задач полубескоиечной оптимизации
§2.1.Постановка выпуклых задач полубескоиечной оптимизации 34
§2.2.Стохастический алгоритм внешних аппроксимаций с учетом
ограничении неравенств............................................35
§2.3.Мехапиэм учета ограничений равенств в задачах полубеско-
нечной оптимизации................................................47
§2.4.Стохастический алгоритм внешних аппроксимаций с учетом ограничений равенств и неравенств.................................49
Глава 3. Численное исследование задачи упруго-пластического кручения стержня
§3.1.Физическая интерпретация и постановка задачи..............54
§3.2.Сведенис экстремальной постановки к выпуклой задаче полу-
бесконечной оптимизации...........................................56
§З.З.Характеристнка программного обеспечения...................57
§3.4.Проблема выбора локального алгоритма для активизированного поиска критических ограничений.................................59
§3.5.Численное решение задачи при различных сечениях стержня................................................................65
§3.6.Численное решение задачи при различных вариантах учета
граничных условий.................................................73
§3.7.0бсуждение результатов....................................81
Заключение.....................................................83
Список литературы..............................................85
Приложение.....................................................93
2
ВВЕДЕНИЕ
Рассмотрим задачу математического программирования
Р° : f(x) -У min
v 7 хсх°
д(г,у)< 0 Vj,еГ\
где функции J(x) и д{х,у) предполагаются непрерывно дифференцируемыми на А'0, Xа X У0 - выпуклых компактах; Х° С 7lk, У0 С 72і. Здесь и далее 71т - m-мерное пространство.
В поставленной задаче множество У0 задает систему ограничений, определяющих допустимое множество задачи Р°. В случае конечного множества У0, задача Р° - ото обычная задача математического программирования с конечным числом ограничений. Во многих реальных случаях множество У0 не является конечным, например, если у играет роль времени или ирострапственных координат. Поэтому если число переменных конечно, а число ограничений бесконечно, то такие задачи называются задачами пол у бесконечной оптимизации (semi-infinite programming).
К задачам такого типа относятся многие задачи аппроксимации, оптимального управления, вариационные неравенства.
Задачи полу бесконечной оптимизации возникают в различных областях приложений [50, 20, 41]. Например, формулируются как по-лубесконечные задачи с ограничениями, зависящими от времени или пространственных координат: контроль загрязнения воздуха [45, 50, 75], инженерный дизайн [66, 65], проблема моментов [14, 52] и другие.
Задача Чебышевской аппроксимации также может быть представлена как линейная задача с бесконечным числом ограничений: заданы непрерывные функции •••>£* на интервале [а,6]. Необходимо
найти линейную комбинацию функций д\лд2, —,9к, которая наилучшим образом аппроксимирует /, подбирая числа a,xj,X2tд*:
а -¥ min
- а < f{t),
-Е*.0»(О - а < -/(0?
3
< € [а,6].
Существуют причины, по которым задачи полубесконечной оптимизации вызывают особый интерес:
- нередко, на практике оказывается удобным, когда допустимая область в модели с ограничениями, зависищими от некоторого параметра у (времени, пространства, и т. п.), задана значением одного перавенства
д(хих< г(у), а не большим числом несвязных ограничений типа
0,(£1, £2» < Г,-
Это лучше и с точки зрения хранения информации, так и простоты анализа проблемы. Лаже в случаях, когда изначально задан второй способ описания, данные могут быть успешно сведены с помощью некоторой аппроксимации к формату описания первого типа;
- одна из причин изначального интереса к исследованию задач Б1Р состоит в стремлении исследователей объединить и расширить численные методы для решения задач Чебышевской аппроксимации.
Методам решения таких задач посвящено значительное число работ [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] численных методов для общих гладких задач 81Р.
Методы для решения задач полубесконечной оптимизации являются естественным продолжением методов для решения задач математического программирования. Разобьем такие методы с точки зрения необходимости проверки достижения решением аппроксимирующей задачи Р(Уп) :
найти х 6 Хор1[Уп], А
AWTJ = {г € X[Yn] I f{x) = JgfyjWh ЛЭД = {*€X°| *(*.*) <0 VyeYn},
некоторой заданной точности на две группы.
Множества задающие систему ограничений в задачах P{Yn), являются конечными
1*^1 < +оо, п = 1,2,...
Методы, в которых такая проверка не требуется относятся к классу прямых стохастических градиентных методов [26, 10, 11, 32, 23]. Задача полубескопечной оптимизации Р° в случае несложного отыскания максимума
$(*> У) “> max
может бить успешно сведена к негладкой задаче оптимизации
min max 19(г, у).
Z0 К» 4 ’
поэтому к ней применимы и градиентные методы минимизации выпуклых негладких функций, основанные на известной процедуре Эрроу-Гурвица [32] для отыскания nun max д(г,у). Итерационный процесс в этих методах строится по формулам:
**+' = г"-в„. <(*",»”)
SЛи=/+а„»^(ЛЛ-
Второй класс алгоритмов характеризуется тем, что необходимо найти решение исходной задачи SIP с определенной степенью точности и проверить ее выполнение. Общая схема таких подходов состоит в их дискретизации. От способа дискретизации существенно зависит как ”качество” аппроксимирующих задач, так и эффективность всего вычислительного процесса.
Исходная задача полубесконечной оптимизации Р° заменяется последовательностью обычных задач оптимизации P(Yn), которые решаются с помощью соответствующих алгоритмов линейного или нелинейного программирования. Такие алгоритмы называются методами последовательной аппроксимации. В них на каждой итерации некоторые из исходных ограничений отсутствуют, и элементы последовательности •г1’, п = 1,2,... будут недопустимыми по отношению к
5
исходному множеству К0. Поэтому такие алгоритмы относятся к методам внешней аппроксимации. Их можно разделить на два класса в зависимости от способа формирования множеств К„.
К первому классу методов последовательной аппроксимации принадлежат методы, для которых на каждой итерации Уп ~j) Yn-\. Таким образом, на каждом шаге находятся новые ограничения и задача решается без учета старых ограничений. К ним можно отнести некоторые методы обмена [41], метод Eaves-Zarigwill [37] и другие методы [26, 10, 11, 23]. Так как на каждой итерации множество Yn не включает критические точки множеств У!,..., l^-i, то обычно множества У„ имеют маленькую размерность. Недостаток этих методов заключается в том, что часто трудно проверить является ли глобальным максимум, полученный при решении внутренних задач.
Данный класс алгоритмов в которых Yn ~f> Yn-j делится на активные и пассивные методы.
В активных методах для поиска критических точек для формирования множества Yn сначала решается внутренняя задача
XV{x): д(х, у) шах.
К таким алгоритмам относятся, например, алгоритмы, основанные на методе квазиградиентов [26, 23], которые в то же время являются прямыми градиентными методами. Если задачу Р° переписать в виде
fix) —> min
Ф) = тахд(х,у) < 0, у£г 11
то итерационный процесс в этом случае задастся формулами:
*n+1 = + а„ * С
Уп €
СП _ | /'(*"), если v?(xn) = 9(хп,уп) < 0
\ g'z(xn,yn) = в противном случае
В пассивных методах для формирования множеств Yn нет необходимости каждый раз проверять достигается ли максимум функции д(•, •). Элементы для множеств Yn обычно находятся с использованием случайных величин.
6
Ко второму классу отнесем такие методы, в которых У„ Э Уп-1-В этом случае все или некоторые из критических точек мпожеств Уъ..У„-1 войдут в множество У„. В этой группе находится большинство методов, ориентированных на задачи полубесконечной оптимизации, такие как методы дискретизации [41, 47. 46, 68, 69, 48], полунепрерывные [46, 69], методы, основанные на локальной редукции [41, 69, 46]. Остановимся па их основных чертах.
Первый из вышеуказанных подходов к решению задач SIP заключается в минимизации целевой функции на конечном подмножестве бесконечного множества ограничений, и повторении этой процедуры для расширенного множества ограничений, когда требуется более высокая точность или, в случае, когда необходимо цолучить оценку точности полученной последовательности решений. Более подробно, идея заключается в последовательном вычислении ”приближенного решения” дискретизированной задачи полубесконечной оптимизации P(Yn) для п — 1,2,... ио одному из алгоритмов конечномерной оптимизации. Процедуры такого типа относят к методам дискретизации. Используемая в них последовательность узлов {У„} обычно описывается a priori. Иногда бывает, что таках последовательность определяется a posteriori (или ’’адаптивно”), когда информация, полученная на п-м шаге дискретизации используется для одределення Yn+\. Такой вариант метода наиболее эффективен и последовательно уточняет дискретизацию с учетом результатов предыдущей итерации.
Методы дискретизации состоят не просто в замене бесконечного множества ограничений конечным подмножеством несвязных ограничений, но и в ’’запоминании” результатов в выбранной стратегической сетке. Пусть У С Y будет конечным подмножеством и
р(Г, У) - шах min ||у - у\\7.
Тогда на практике для достаточно малого р, решение на множестве Y вместо У будет достаточно хорошей апнроксимапией для исходной задачи.
Для доказательства сходимости методов дискретизации, необходимо чтобы каждая предельная точка последовательности "решений” зР* задач P{Yn) была решением задачи SIP Р°, где ’’решение” Р(Уп) - это такая точка, к которой в соответствии с доказательством его сходимости, сходится соответствующий алгоритм P{Yn). Что каса-
7
ется решения аппроксимирующей задачи P{Yn), то здесь подходят не все методы математического программирования, так как часто во многих из них требуется решение подзадач, которые имеют такое же число ограничений как и исходная задача.
Для улучшения эффективности метода дискретизации важно, чтобы информация о решении задачи, полученная на одном уровне передавалась па следующий уровень, что означает, что приближенное решение хп* задачи Р(УП) может быть использовано в качестве начальной точки для решения P(y,+i). Такая начальная точка может быть недопустимой для P(Yn+1), так как задача P{Yn~\) включает дополнительные или различные с P{Yn) ограничения. Поэтому многие методы, которые нуждаются в допустимой стартовой точке и. следовательно, в двух-фазовой процедуре решения P{Y„+\), слишком дороги для этих целей.
Методы дискретизации могут быть использованы для получения первого приближения к решению, которое может быть улучшено на следующем шаге методом, обладающим хорошей локальной сходимостью.
Методы, в которых бесконечное множество ограничений
< 0, у € У0
задачи Р° локально заменено в точке Хо конечным множеством ограничений
д*{х) := д(х,у>(х)) < О, j = 1,..., п(х0),
где у;(х) - локальные максимумы #(х, •) относительно У0, называются методами, основанными на локальной редукции (в [46] их называют непрерывными методами).
Их основная идея заключается в следующем: нусть задана допустимая точка хо € Р для задачи конечной оптимизации, тогда существует окрестность этой точки, где допустимое множество может быть описано активными в точке хо ограничениями (обычно их > Л). Тогда если хо это (локальное) решение задачи, то оно также является (локальным) решением задачи в которой все ограничения, неактивные в хо, уничтожены и наоборот. На самом деле, в случае задач полубескопечиой оптимизации обычно это не выполняется, т. е. допустимое множество задачи SIP не может быть локально представлено
8
- Київ+380960830922