Популярное

Мифы о звукоизоляции



Как построить дом из пеноблоков



Как построить лестницы на садовом участке



Подбираем краску для ремонта



Каркасные дома из дерева


Главная » Стохастический метод

1 2

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

С.К.Завриев, А.В.Федосова* МГУ им. Ломоносова, факультет ВМК

November 4, 1999 1. Постановка задачи.

Рассмотрим задачу математического программирования

Р(У°) : найти х £ Х^,

хщл = {х £Х° \ f(x) = min f(x)}

Х° = {х £ Х° д(х, у) < О Уу £ У0},

Х° С 7Zk, У0 С TZ1. Функции f(x) и д(х,у) предполагаются непрерывно дифференцируемыми и выпуклыми по х на выпуклом компакте Х° для любого у £ У0, 1Z - п-мерное пространство. Будем предполагать также регулярность по Слейтеру ограничений задачи Р(У°), т. е. существование точки х* £ Х° такой, что

g(x*,y)<0Vy£Y°.

В поставленной задаче множество У0 задает систему ограничений, определяющих допустимое множество Х° задачи Р(У°). В случае, когда множество У0 бесконечное, т. е. У° = оо (через У| обозначаем мощность множества У), задачу Р(У°) принято называть задачей полубесконечной оптимизации (semi-infinite programming problem). Задачи полубесконечной оптимизации возникают в различных областях приложений (см. [1, 2, 3]), методам их решения посвящены обзоры [3, 1, 4, 5].

*19alina0cmc.msu.ru



Далее мы рассмотрим именно такие задачи Р(У°), приняв следующие дополнительные предположения:

V/(-), Vg(; ) <= Сир(Х° x y°,L), L > 0, где CLtp(X,L) обозначает класс вектор-функций, удовлетворяющих на X условию Липшица с константой L > 0.

Одним из наиболее употребительных подходов к решению задач с бесконечным числом ограничений является метод внешних аппроксимаций. Суть этого метода состоит в сведении исходной задачи Р(У°) к решению последовательности аппроксимирующих задач P(Yn), п = 1, 2,следующего вида

Р(У) : найти х £ Xopt[Y],

Xopt[Y] = {х£ X[Y] I f(x) = min f(x%

X[Y] = {x£X° \g(x,y)<0 Vy£Y},

в которых множества Yn, задающие систему ограничений, являются конечными

\Yn\ < оо, п = 1, 2,....

Очевидно, что аппроксимирующие задачи P(Y ), п = 1,2,... суть стандартные задачи математического программирования, то есть задачи с конечным (равным Уте|) числом ограничений, и для их решения могут быть применены соответствующие эффективные стандартные алгоритмы (см., например, [6, 7]). При определенных условиях, задающих правила формирования множеств Yn, доказывается, что последовательность {хп}, где х - решение n-й аппроксимирующей задачи P(Yn), хп £ Xopt[Yn], п = 1,..., сходится к множеству решений X®pt исходной задачи Р(У°).

Главной сложностью в применении рассматриваемого подхода является конструирование правил формирования множеств

Уь Y2j..., Ym...

Здесь важно избежать быстрого роста числа элементов в множествах Yn, п = 1,2,..., так как при больших У], задача Р(Уте) становится почти столь же сложной для решения, что и исходная задача Р(У°).

В настоящей работе, следуя общему подходу к построению алгоритмов внешней аппроксимации, предложенному в [8], мы сконструируем и обоснуем алгоритм решения выпуклых задач полубесконечной оптимизации Р(У°). Важной особенностью предлагаемого алгоритма является использование активных стратегий фор-



мирования множеств V*i..... V . задающих аппроксимирующие задачи Р(УП), п = 1,2,... Пусть

П1 = {х G П1 х > 0}; Бст(ж) = {х е Кк \\х - х\\ < сг}, сг > 0.

Обозначим через A4(Y°) - множество всех подмножеств У0 С 7Z1, A4C(Y°) и A4f(Y°) - соответственно множество всех компактных подмножеств множества У0 и множество всех конечных подмножеств множества У0.

Для любых У, Y £ M.C(Y°) определим

p(Y, Y) := max min \\у - у'\\,

и Хаусдорфово расстояние между множествами У и У:

h(Y,Y) :=тах{р{У,У'), p(Y,Y)).

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

Предлагаемый метод решения задачи Р(У°) является алгоритмом внешних аппроксимаций, т. е. последовательно находит решения х задач P(Yn), п = 1,2,.... При этом на n-й итерации алгоритма вначале формируется множество Уте, путем добавления в множество Yni новых точек у £ У0. Тем самым, очередная аппроксимирующая задача P(Yn) получается из предыдущей (п - 1)-ой аппроксимирующей задачи P(Yn-i) путем добавления новых ограничений.

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

вначале получаем новое ограничение

9(;У)<0

(то есть точку у £ У0) методом Монте-Карло (с помощью датчика равномерного распределения на У0);

затем, используя точку у в качестве стартовой, применяем эффективный алгоритм локального поиска для решения задачи

0(жп~\-) -> max (1)

(где хп1 - решение предыдущей аппроксимирующей задачи P(Yn-i)) и находим точку у* - приближенное локальное решение (1),



у* £ Ys£tat(xn ). где Ys£tat(x) - это -стационарное множество задачи

q(x. ) -> max,

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

Выпишем соответствующий алгоритм стохастического метода внешних аппроксимаций для решения выпуклых задач Р(У°). Данный алгоритм является версией общего стохастического метода внешних аппроксимаций SMETH.ACTIV [8] и состоит из вспомогательной и основной процедур.

Вспомогательная процедура SPROC.ACTIV.sip призвана формировать множество AYn для добавления к множеству Yn:

Yn+1:=AYnU U

j-.ej>*y/n,

1<?<п-1

Основная процедура метода SMETH.ACTIV.sip с помощью данных, полученных SPROC.ACTIV.sip, на на каждой итерации п решает задачу P{Yn) с конечным числом ограничений.

Метод SMETH.ACTIV.sip

Шаг 0. (Начальный шаг)

Yl := 0.

Шаг 1. Находим х - решение задачи P{Yn).

Шаг 2. Выполнение процедуры SPROC.ACTIV.sip с входными

параметрами хп nYn.

Получаем AYn и вп. Шаг 3. Формируем новое множество ограничений

Yn+1:=AYnU U AYj.

j:Sj->7/n, 1<?<п-1

Шаг 4.

п := п + 1.

Переход к шагу 1.



Процедура SPROC.ACTIV.sip

Входные параметры : х £ Х°, У £ A4f(Y°). Выходные параметры : в £ 7Z\, AY £ A4f(Y°). Параметры процедуры : 7 > 0, е > 0. Шаг 0. (Инициализация).

г := 1.

Шаг 1. (Пассивный случайный поиск критического ограничения).

Найти точку i/i £ У0, используя равномерное

вероятностное распределение на У0.

Шаг 1. ACTIV. (Активный поиск критического ограничения).

Применить алгоритм локального поиска для решения

задачи д(х,у) -> max (метод проекции градиента),

yeY°

стартуя из точки у; для получения точки у* £ У0, такой что :

у* е Ys£tat(x), д(х, yi) < д(х, у*).

Шаг 2. $i = тах(д(х,у$),...,д(х,у?)).

Шаг 3. (Контрольный шаг). Если

г 0i < 7,

то г := г + 1 и переход к Шагу 1. Шаг 4.

в := в;\ := {уиу$, ...,уиу*}.

Выход. 3. Сходимость.

В работе [8] был предложен алгоритм общего стохастического метода внешних аппроксимаций SMETH.ACTIV и доказана его сходимость. В нем были использованы понятия квазиоптимальных функций и множеств.

Квазиоптимальная функция в(а/, Yn) : Х° xA4c(Y°) -> 7Z\ задается для любого компакта Y С У и х' £ Х° и играет роль критерия, показывающего, насколько близка точка х' к решению задачи P{Yn). Было условлено, что х £ / означает, что в(ж,У°) = 0.



Неравенство

S{x,Yn) <е

рассматривалось в качестве критерия останова для решения конечных задач P(Yn).

Квазиоптимальное множество задачи P{Yn) в [8] определялось следующим образом

Xqopt[Y] := {х £ Х° в(х, Y) = 0}, Y £ MC(Y°).

Для алгоритма SMETH.ACTIV в [8] была доказана сходимость для любой квазиоптимальной функции, удовлетворяющей Предположениям А1 и А2:

Предположение А1. Пусть

ХтЛ[У]Ф^ VY£MC(Y°).

Предположение А2. Пусть для любых х £ Х° и Y £ A4C(Y°) выполнены следующие свойства:

1) Если 0(х. Y) > 0, то существуют в. д > 0 такие, что

6(ж',У) > 0 > 0

для любых х' £ В5(х) П Х°, Y £ MC(Y°) и h(Y,Yf) < S.

2) Если в (ж, У) = 0, то для любого е > 0 существует д > 0 такое, что

6(ж',У) < е

для любых х' £ В$(х) Г) Х° и для тех У £ Л^С(У°), для которых h(Y,Yf) < S.

Для наших задач определим квазиоптимальную функцию (-)( . ) по следующему правилу

Six, У) := тах(/(ж) - min fix), max.g(x,y)).

хеХ°: y£Y

g(x,y)<0 Vj/бУ

Заметим, что для данной квазиоптимальной функции

Xqopt[Y] = Xopt[Y] VY£MC(Y°), в частности, если Y := У0, то = .

Для доказательства сходимости траектории предлагаемого алгоритма SMETHACTIV.sip достаточно показать, что он является



версией общего алгоритма SMETH.ACTIV и проверить выполнение Предположений А1 и А2 для нашей квазиоптимальной функции.

Из следующей Леммы вытекает, что алгоритм SMETH.ACTIV.sip является версией общего стохастического метода внешних аппроксимаций из [8]:

Лемма 1. Для любых компактных множеств У С У0, У С У0 и точки х £ Xopt[Y]

0(ж, У U У) = max(0, max д(х, у')) = тах(0, тахд(ж, у')).

yeYUY yeY

Доказательство.

Фиксируем У С У и х £ Xopt[Y]. По определению множества Xopt[Y]

0(ж,У) =0.

Рассмотрим расширенное множество ограничений У U У. Легко видеть, что

fix) = min fix) < min fix),

xeX°: xeX°:

g(x,y)<0 Vy£Y g(x,y)<0 VyeYUY

а также

max. g(x,yf) > max. g(x,yf). y€Y\JY v&

Откуда следует, что для нашей квазиоптимальной функции 0(ж, У) := тах(/(ж) - min fix), тзхд(х,у'))

хех0-. y€Y

g(x,y)<0 Vy£Y

выполняется

в(ж, У U У) = max(0, max д(х, у')) =

yeYuY

тах(0, тахд(ж, у'), тахд(ж, у')) = тах(0, тахд(ж, у')),

У'£¥ y£Y y£Y

так как max #(.7-. у') = ().□

y£Y

Пусть У = {у\.у:\..... у у*}. Тогда из Леммы 1 следует, что Контрольный шаг Процедуры SPROC.ACTIV.sip

г тах(#(ж, у\), ...,д(х, у*)) < 7,

эквивалентен проверке

г в(ж,У U {уъу*ъ уиУ*}) < 7



в силу того, что

д(х,у*) > g(x,yi) Vz.

Обозначив V / = V U {у\.у'1..... у у*}. Контрольный шаг можно записать как

Поэтому Контрольный шаг Процедуры SPROC.ACTIV.sip эквивалентен Контрольному шагу алгоритма SPROC.ACTIV из работы [8].

При доказательстве выполнения Предположений А1 и А2 для квазиоптимальной функции важную роль будет играть следующая Лемма.

Лемма 2.[9] Пусть ограничения д(х,у) выпуклы Уу £ Y0 и удовлетворяют условию Слейтера, т.е. существует точках*, для которой

g(x\y)<0 УуеУ0, тогда Уж и VY С A4f(Y°) из множества

C(x,Y) = {х £ Х° д(х,у) < О Уу £ Y}

выполняется:

max(0; тахд(ж, у)) > Kp(x,C(x,Y)),

[К > 0 - некоторая константа).

Основываясь на Лемме 2, получаем следующее утверждение: Лемма 3. Для любых: точки х £ Х°, множества Y £ A4C(Y°) и последовательностей {хп}, {Yn}, удовлетворяющих условиям

хп £ Х°, п = 1, 2..., lim хп = х, Yn £ MC(Y°), п = 1, 2..., Jim h(Ym Y) = 0,

выполнено

YimQh{C{xmYn),C{x,Y))=Q.

Из Леммы 3 следует, что рассматриваемая квазиоптимальная функция (-)( . ) удовлетворяет Предположениям А1 и А2.

Итак, алгоритм SMETH.ACTIV.sip является версией метода SMETH.-ACTIV из [8], поэтому приведем его в терминах версии SMETH.-ACTIV.

Метод SMETH.ACTIV.sip



Шаг 0. (Начальный шаг)

п : = 1, Yt := 0.

Шаг 1. Находим х - решение задачи P{Yn). Шаг 2. Выполнение процедуры SPROC.ACTIV с входными параметрами хп ж¥п.

Получили на выходе процедуры в„. AY . Yn. Шаг 3.

Yn+1:=AYnU U А^-.

j:9j>7/n,

l<j<n-l

Шаг 4.

п := п + 1. Переход к шагу 1.

Процедура SPROC.ACTIV.sip

Входные параметры : х £ X. Y £ A4f(Y°).

Выходные параметры : в £ 7Z\, AY £ A4f(Y°), Y £ A4f(Y°).

Параметры процедуры : 7 > 0, е > 0.

Шаг 0. (Инициализация).

У :=У; i := 1.

Шаг 1. (Пассивный случайный поиск критического ограничения).

Определяем точку у; £ У , используя равномерное

вероятностное распределение на Y0.

Включаем у; в множество Y

Шаг 1. ACTIV (Активный поиск критического ограничения).

Применить алгоритм локального поиска для решения

задачи д(х,у) -> max (метод проекции градиента),

yeY°

стартуя из точки у; для получения точки у* £ Y0 такой что :

V*i Ys£tatix)i 9{х, Уг) < д(х, У*).

Включаем у* в множество У/. Шаг 2. 0i = e(x,Yi).



Шаг 3. (Контрольный шаг). Если

г 0i < 7,

то г := г + 1 и переход к Шагу 1.

Шаг 4.

0 := в;\ У := У{.

Алгоритм SMETH.ACTIV.sip является версией алгоритма SMETH.ACTIV и Предположения А1 и А2 для предложенной квазиоптимальной функции выполнены. С учетом того, что

Xqopt[Y] = Xopt[Y) VY <= MC(Y°)

верна следующая Теорема:

Теорема. Любая траектория {хп} метода SMETH.ACTIV.sip с вероятностью единица сходится к множеству Xopt\Y{)].

Если при выполнении Шага 2 алгоритма SMETH.ACTIV.sip мы не выходим из Процедуры SPROC.ACTIV.sip за конечное число шагов, то решением исходной задачи Р(У°) считается последнее полученное алгоритмом SMETH.ACTIV.sip на Шаге 1, приближение решения хп <= Xopt[Y%

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

References

[1] Hettich R., Kortanek К. O. Semi-infinite Programming: Theory, Methods, and Applications SIAM Review, 1993, V. 35, N. 3, P. 380-429.

[2] Крабе В. Теория приближений и их приложений. М.. 1978.





1 2
© 2017 РубинГудс.
Копирование запрещено.