Общий стохастический метод внешних аппроксимаций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Государственный комитет Российской Федерации по высшему образованию Московский Государственный Университет им. М.В.Ломоносова

На правах рукописи

Волков Юрий Валерьевич

ОБЩИЙ СТОХАСТИЧЕСКИЙ МЕТОД ВНЕШНИХ АППРОКСИМАЦИЙ

Специальность 01.01.09 - Математическая киберн .

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

Москва, 1996 г.

Работа выполнена в Московском Государственном Университете

;: -. учный руководитель:

доктор физико-математических наук, профессор

С.К.Завриев

Официальные оппоненты:

доктор физико-математических наук . Н.М.Новикова кандидат физико-математических наук А. З.Иымутаметов

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

Л ВТ А ОИЯИ (г.Дубна)

Защита состоится "¿<5" ____ 1996 г. & в часов

на заседании диссертационного совета К 200.45.01 при Институте высокопроизводительных вычислительных систем РАН по адресу: Москва, ул. Вавилова. 37.

С диссертацией можно ознакомиться в библиотеке ИВВС РАН.

Автореферат разослан п2.Ь" ^лл____ 1996 г.

Ученый секретарь $¿¡1щ _ У

диссертационного совета ^ С.В.Миронов

1.Общая характеристика работы

АКТУАЛЬНОСТЬ ТЕМЫ.

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

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

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

- обобщении ранее созданных методов с целью определения наиболее универсальной схемы;

- введении широко используемого механизма квазиоптимальных функций и множеств;

- построении общего метода, одинаково легко решающего и простые, и сложные задачи (даже такие, решение которых ранее было затруднено);

- легкой адаптации метода к любой задаче с бесконечным числом ограничений;

- возможности использования в методе для решения внутренних задач ранее существующих методов.

ЦЕЛЬ РАБОТЫ состоит в:

- построении общего стохастического метода внешних аппроксимаций для решения задач, включающих бесконечное число ограничений;

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

- доказательстве теоремы сходимости: любая траектория метода почти наверное сходится к квазиоптимальному множеству исходной задачи;

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

- численной реализации метода для частных случаев задачи

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

НАУЧНАЯ НОВИЗНА работы заключается в:

- создании общего стохастического метода внешних аппроксимаций для широкого класса задач, включающих бесконечное число ограничений;

- использовании новой схемы поиска критических ограничений при построении множеств ограничений аппроксимирующих ч.ач - схемы активизированного поиска;

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ работы состоит в создании удобного в понимании и реализации численного алгоритма для решения задач с бесконечным числом ограничений. Численно решена задача Чебышевской аппроксимации с размерностью по у равной 3, по которой ранее практически не проводились исследования. Для решения вспомогательной задачи квадратичного программирования реализован метод сопряженных градиентов, как известно, сходящийся за конечное число шагов. Метод легок в описании, но сложен в практической реализации вследствие его тонкости. Также численно решена задача минимаксного синтеза робототехнических систем, и оптимальная точка задачи после применения метода внешних аппроксимаций оказалась близка к решению детерминированной задачи минимаксного синтеза.

АПРОБАЦИЯ РАБОТЫ И ПУБЛИКАЦИИ.

Материалы диссертации докладывались на семинарах по исследованию операций факультета ВМиК МГУ им .М.В.Ломоносова (19931996), на семинаре в ИВВС РАН (1996), на конференции в Голландии по проблемам стохастической оптимизации (1995).

Цо теме диссертации опубликованы работы [1-5].

СТРУКТУРА И ОБЪЕМ РАБОТЫ.

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

2. Содержание работы

Во введении к диссертации рассматривается в общем виде задача оптимизации, включающая бесконечное число ограничений:

Р° : найти х £ X°pt,

где множество Х®р1 может быть описано различными способами. Естественно, в описании данного- множества должно присутствовать бесконечное число ограничений. Типичными представителями класса задач оптимизации с бесконечным числом ограничений являются задача полубесконечной оптимизации и задача нахождения решения бесконечной системы неравенств.

Рассмотрим, например, задачу полу бесконечной оптимизации:

SIP : f(x) -> mm

д{х,у)< 0 Vs/еУ0,

где функции /(•), д(-, •) предполагаются непрерывно дифференцируемыми на Х° х У0; Х° С У0 С 3?' - выпуклые компактные множества; - k-мерное вещественное пространство. С точки зрения V0 задачу SIP можно записать в следующем виде:

SIP : найти х е Хйоф

X°pt = {xZX°\f(x)=unnJ(x')},

где допустимое множество задачи SIP следующее:

Х° = {х Е Х° \ д(х,у) < 0 Уг/ б У0}.

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

задач Vn, п = 1,2,____ Простота аппроксимирующих задач заключается

в том, что вместо бесконечного множества ограничений используется множество конечной мощности:

Тп : найти х €

| Уп |< +00.

Далее во введении описана эволюция развития теории методов внешних аппроксимаций: от первых методов, в которых обеспечивался монотонный рост мощности множеств ограничений У„, п = 1,2,..., У-! С Уг С ... аппроксимирующих задач, к методам с адаптивным формированием множеств ограничений. При таком формировании множеств Уп, п — 1,2,... применялись правила добавления и отсеивания точек. Например, для задачи полубесконечной оптизимации эти правила выглядят так:

Добавление точек.

При заданной точке хп последовательное получение точек у",-.. € К0 до тех пор, пока перестанут выполняться необходимые условия оптимальности в точке хп следующей задачи:

Б1Р.РП: /(х)-ишп

д{х,у)<0 УуеУ„ и {у?,...,у£,}.

Добавление точек у",...,у$п к множеству Уп для формирования множества У„.

^Отбрасывание точек.

Отсеивание некоторых точек из У„ для получения множества ДУ„ С Уп такого, что ограничения

Ф,У) <0Уу£ АУ„

не нарушаются в точке хп в задаче

Затем отбрасывание некоторых множеств из {ДУ<, г = 1,..., п} для получения

у„+1 = и ДУ,-,Лс{1,...,п}.

уел.

Глава 1 • посвящена построению общего стохастического метода внешних аппроксимаций. В §1.1 рассматриваются схемы активного и

пассивного поиска критических ограничений (нужных точек) и строится новая схема активизированного поиска. Рассмотрим эти схемы на примере задачи SIP.

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

В схеме пассивного поиска используется правило добавления точек, описанное выше. Очевидно, что если размерность множества У0 не мала, то методы внешних аппроксимаций, использующие схему RS, не могут быть эффективными вследствие того, что точки, "выброшенные" в схеме, не обязательно будут нужными. Поэтому предлагается модифицированная схема RS.ACTIV.

Схема RS.ACTIV. Активизированный случайный поиск.

Шаг 1. г := 0.

Шаг 2. г := г + 1.

Шаг 3.' Определяется точка у" с использованием однородного вероятностного распределения на Y°.

Далее применяется метод локального спуска из начальной точки у" для отыскания локального максимума у"'* задачи

<7(яп,з/) —*шах.

yero

Если условия оптимальности задачи /(г) ш

9{х,у) < 0 \/у £ Г„ U {tf.sT,... уГ)

не нарушаются в точке хп, то переход к Шагу 2. Иначе, переход к Шагу 4.

Шаг 4.

Sn := i,

Y»"Yn U {»?,УГ,.-МУ&,УГ}

и выход.

В §1.2 описан необходимый математический аппарат, используемый в диссертации для построения и анализа метода внешних аппроксимаций. Например,

в6{х) = {*' ея*'||| х'-х ||< 6 > о.

Л (У, К') - Хаусдорфово расстояние между множествами У и У.

ни (У0) - множество всех подмножеств К0 С йПс(У°) - множество всех компактных подмножеств множества У0; яя/(У°) - множество всех ограниченных подмножеств множества У0.

В §1.3 вводятся в рассмотрение необходимые для построения метода внешних аппроксимаций квазиоптимальные функция и множество.

Опишем квазиоптимальную функцию: 0(-, •) : Л'° х элс(У°) —> для любого компакта У (ЕУ° их € Х°. Идея введения такой функции-состоит в создании критерия, оценивающего близость х к решению задачи Т>\У]. Для этого предположим, что

¿6 => в(г,У°) = 0. (1)

Таким образом, неравенство

&(х, У) <е (2)

может рассматривается в качестве критерия остановки для алгоритмов решения задачи Т\У].

Используя квазиоптимальиую функцию, определим ©(-, -)-квазиоп-тимальное множество задачи V[У]:

ХччМ ■■= {* е I У) = 0},Уе апС(У°).

Из (1) следует, что

^орг С (3)

где := = {х е | 0(г,У°) = 0}.

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

ПРЕДПОЛОЖЕНИЕ А1. Пусть

^оР<[У] ф Ч УУ € Ш!с(У°).

ПРЕДПОЛОЖЕНИЕ А2. Пусть для любых х £ Х° и У £ тс(У°) выполнены следующие свойства:

1) Если &(х,У) > 0, то существуют 9,8 > 0 такие, что

О(х\Г')>9>0

для любых х' £ В1(зс) и У' £ йпс(К0),' < <5.

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

0(х',У') < £

для любых X1 £ Ве{х) П и У £ алс(Г°), /¡.(К, Г') <5.

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

В §1.4 непосредственно дается описание общего стохастического метода внешних аппроксимаций. В дополнение к активизированной схеме поиска критических ограничений вводится механизм отсеивания некритических ограничений (точек, не относящихся к делу). Для этого используется множество А £ У0, названное множеством активных параметров:

для любых I е 1° и У £ злс(У°) ограниченное множество А, А € У0 является множеством активных параметров, если

&(х, А) = 0(л;, У) = 9(х, У) ЧУ' £ тс(У) : А С У С У

и, более того, не существует множества А' С А, А! ф А, удовлетворяющего данному свойству.

Пусть А(х,У) - множество всех множеств активных параметров в точке {х,У) в соответствии с функцией (-)(■,•). Для ДУ С У определим

АУУЛ(х,У),

если существует множество А £ А(х,У) такое, что ДУ Э А.

Опишем метод внешних аппроксимаций, сходящийся почти наверное к Э(-, •)-квазиоптимальному множеству Д^0р([У°]. Метод используется для нахождения точки х £ Х{), удовлетворяющей при У = У0 и £ \ О неравенству (2). В метод включена специальная процедура активного

-а-

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

Построим процедуру активного случайного поиска.

Процедура БРНОСЛСПУ

Входные параметры, х е X, У £ й«/(У0).

Выходные параметры. 9 е ДУ 6 %(У°), У € Ш!/(У°) и 5 е N. Параметр процедуры, у > 0. Шаг 0. (Инициализация)..

Тх := У; г := 1.

Шаг 1. (Пассивный случайный поиск критического ограничения). Определяем точку у{ € У0, используя однородное вероятностное распределение на У0. Включаем у,- в множество У,-. Шаг 1. АСТ1У (Активный поиск критического ограничения). Используя алгоритм локального поиска по У0 из точки г/,-, получаем точку у* = у* (г, ?/;). Включаем у* в У;. Шаг 2, й = в(х,Г0. Шаг 3. (Контрольный шаг) Если

г < 7 (4)

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

У:=У,;

5 г.

Шаг 5. (Отсеивание некритических ограничений) Анализируя 0(я, У), получим

ДУ X Л(х,7).

Выход.

Сформулируем теперь общий метод внешних аппроксимаций.

МЕТОД БМЕТН.АСТШ Данные, х1 € Х°.

Параметры. Последовательности {еп}, {сгп},

<7п > о, п = 1,2,..., £п, сг„\0. (5)

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

п := 1, У: 0.

Шаг 1. Выполнение процедуры БРЕОС.АСТГУ с входными параметрами хп и У„.

Определяем на выходе процедуры 9П, АУ„, У„, £„.

Шаг 2.

Уп+1-.= АУпи и А У,-. (6)

1<;'<™-1

Шаг 3. Находим хп+1 € Х°, удовлетворяющее

е(гп+1, У„+1) < е„+ь

Шаг 4. .

п=:п + 1.

Переход к Шагу 1. Построенный общий метод обладает следующим свойством: любая траектория {я"} метода вМЕТН.АСТШ с вероятность единица сходится к множеству Л^ор{[У°].

-JG-

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

В §2.1 рассматривается задача нахождения решения системы бесконечного числа неравенств:

ineq.V0 : найти х €

Н* € I </(*.</) < О V2/G У0},

где <?(•, •) предполагается непрерывно дифференцируемой на Х° х У0; 4g(-,y) е L), L > 0; А'0 С К*, У0 С 3?' являются выпуклыми и

замкнутыми множествами.

Определим квазиоптимальную функцию&(■,■): Х°хтС(У°) —♦

е(г,У) := max(0; тахд{х,у')). Предположения Al, А2 выполнены и

Таким образом, критерий Э(-, ) может работать в стохастическом методе внешней аппроксимации SMETH.ACTIV для решения задачи ineq.VДля активизации алгоритма используется следующая задача, решаемая, например, градиентным методом:

ineqSV(x) : g(x,y) —» шах

у € У0.

В §2.2 рассматривается задача полубесконечной оптимизации SIP. Для построения метода решения SIP используется следующая задача квадратичного программирования:

sip.QV(x,Y) : < Vf(x),p > || p ||2—» min

5(x,2/)+ < Vxg(x, y),p ><0 Vy € У, ' i + p G X,

У e anc(y°), x € X. .

Вводится квазиоптимальная функция 0(-, •) : х плс(У°) —> 3?+: 0(х,У) =|| Ро(х,У) II, тех, Y £ nc(Y°) и показывается, что Al, А2 выполняются и

xqopt[Y] = *5<e<[y] vy 6 MY0); X?,pt С = Xqopi\Ya\.

В §2. Л приведена версия общего стохастического метода внешних аппроксимаций для задачи глобальной оптимизации:

glob : F(х) min,

где целевая функция /(•) предполагается непрерывно дифференцируемой на Х° С 9?*; V/(-) G C/;ip(yY0, L), - выпуклый компакт. Определено оптимальное множество задачи glob:

Kt :={xeX°\f(x)=nnnf(x')}.

Квазиоптимальная функция для этой задачи следующая 0(-,Х) : Х° -

©(х,Х) := max(0;F(x) - rnini^)), х € Х°. Легко показать, что

хЧоп[х] := {хеХ°\ е(х,х) = 0} = X^IX], vx е

Xqopt Xq0pt[X°] —

и, более того, Al, А2 выполнены.

Множество активных параметров в точке (х,Х) в соответствии с квазиоптимальной функцией ©(-,•) выглядит следующим образом:

А(х,Х) = {х G | F(x) < mmF(y)}.

уб-Л

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

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

ГЛава 3 посвящена доказательству теоремы сходимости метода. Метод БМЕТН.АСТГУ является стохастическим, так. как зависит от исходов, случайных экспериментов при генерации точек ^ £ У0, г = 1,2,.... Сходимость этого метода необходимо рассматривать на подходящем вероятностном пространстве.

Пусть (У0, в, ц) - вероятностное пространство, где в - а-алгебра Борелевских подмножеств У0, и ц - Борелевская мера на У0, такая, что /л(У°) = 1. Положим

®„ = ® ш, Рп = ё> V, Я = 1,2,...;

»=1 «=1

ОО л со со

О = ® у0 и = ® В, Р = ® И.

¿=1 ¡=1 ¿=1

Определим через ы = (г/1,... ,уп,...) типичный элемент из П.

Любая траектория {х"}, генерируемая методом ЗМЕТН.АСТ1У, зависит от исходов случайных экспериментов у\,..., у„,... и, поэтому, последовательность {х™.} является ш = (уу,..., «/„,•••) - зависимой, {жп = х"(и>), п = 1,2,...}. Рассмотрим последовательность {г" (о;), п = 1,2,...}, ш £ О. Предположим, что £"(■), п = 1,2,... - измеримы. Таким образом, {ас"} - последовательность случайных векторов на вероятностном пространстве (П, а, Р). Далее изучим свойства Р-почти наверное (Р — а.й.) сходимости последовательности {х"}.

Для любого ш = (уиу2, ■ ■ •) 6 О рассмотрим соответствующую траекторию {х"} метода БМЕТН.АСТТУ. Пусть Я„(ш) - число "выброшенных" точек для получения х1(а/),.. ,,хп(ш), т.е.

хп(ш) = хп(у1, у2, ...) = хп{уи у2, ■ ■ •, г/А,), П = 2,3,... ,

(ясно, ЧТО = 0}.

Из описания метода следует, что 5п(о;) - число точек, "выброшенных" на п-ой итерации метода 5МЕТН.АСТ1\Г для получения жп+1(а/). Таким образом, <

Ди-Кы) = Я„(ш) + 5„Н, п = 1,2,....

-Jbr

Если на щ-ой итерации SMETH.ACTIV неравенство (4) в процедуре SPROC.A CTIV выполняется для любого i = 1,2,..., то метод генерирует ограниченную последовательность я1 (и),... В этом случае

положим

S„0(u>) = -foo, S„(w) = 0, n = n0 + 1, n0 + 2,...

и

Nsiop(u) = По

(•/Vsiop(w) - итерация, на которой завершается метод).

Если же неравенство (4) не выполняется для какого-нибудь i ~ 1,2,..., то

Sn(u) < +оо, n = 1,2,..., N,toP{v) = +оо.

Для подмножества I? множества Х° и s 6 N рассмотрим множества {1 < n < s | 6 £>}, я = 1,2,....

Очевидно, что

{п 6 N | хп(ы) €£>}=U{l<"<s| i"(w) € £}.

s=l

Определим

AT(D,s | iS) :=| {1 < n < 8 | xn(u) e D} a = 1,2,...,

ЛГ(£>,оо | u) :=j {n 6 N | i"(w) € D} |, где | К | - мощность множества К, и

m„(D | ш) := mm{s G N | Af(D,s j u) = n}.

Когда {s £ N | Лf{D,s | u) = n} = 0 (т.е., Af(D, oo | ui) < n) положим mn(D | u) := +oo (т.е. меньше n точек из i = 1,2,... принадлежит множеству D).

Тождество m„0(D | и) = n* означает, что включение

х"(ы) G D

выполняется для точно щ первых п* элементов траектория {я"(о;), п = 1,2,...} и, более того, это включение выполнено для п = п*, т.е. существуют I < jl < ■ ■■ < ]По — п* такие, что

х'И 6 О V; 6

я

0 £> у,- 0 Оь • • •, Зпо), 1<3<п*.

Определим

П(£>) := £ А | тпп{0 | ш) < +оо Уп = 1,2,...}. Яз определения тп(£> | ш) следует, что

^ £ х"(и>) £ В для бесконечного числа п £ N.

Положим

Поо = £ П I К1ор(ш) < +оо}, П«, = О\Поо = {ш £ П I = +оо} =

{ш € Г2 1 {х"^)} — содержит бесконечное число элементов}. Заметим, что для любого Б С Xй

С П«,.

При доказательстве теоремы сходимости метода важную роль имеют следующие Леммы.

лемма. Для любого ы £ йоа следующее свойство выполняется:

п1па 5„(ш) = +оо.

ЛЕММА. Для любого х £ Х°ар1 существуют <5, = &*(х) > 0,

В*.(х)ПХ°сХ°\Х?ор(

и П* = Н*(х) С Ох, Р(П") = 0 такие, что следующие свойства выполняются:

П{®"(ь/)} П В6ф(х) — 0 Чш £ Поо \ П*.

-1S-

JlEMMA. Для любого weliOQ\Р(П^) = 0 выполнено:

/"•'He^V

где fit1) С fi.

Теорема сходимости метода формулируется следующим образом: ТЕОРЕМА. Существует С П, Р(П(0>) = 0 такое, что для любого ш € П \ траектория {т"(ш)} метода SMETH.ACTIV удовлетворяет одному из следующих свойств:

i) Nstop < +00 и х^М €

н) Nstop = +00 и {х"(ш)} сходится к X°opt.

Глава 4 посвящеиа численному решению задач с бесконечным числом ограничений. В §4.1 рассмотрена задача Чебышевской аппроксимации:

apprx.V0 : найти х 6

А^ = {* 6 | max | Ф(*,„) - F(y) |= v%t},

v%t = mm max | Ф(х, у) - F{y) |,

где функции Ф(-, •), F(-) предполагаются непрерывными и непрерывно дифференцируемыми на Х° X У0, УФ(-) = (УХФ(-, ■), У„Ф(-, ■)) б CLip(X° х Y\L), VF(-) е CLip(Y°,l), L > 0, 1° С R4 - полиэдр и компакт, Y0 С 3i' - выпуклое компактное множество.

§4.1 посвящен стохастическому алгоритму для решения задачи apprx.VАлгоритм является версией общего метода внешней аппроксимации SMETH.ACTIV, специально адаптированной для apprx.V0. Заметим, что если функция Ф(х, у) - линейная по х для любого у € Ya,

т.е.

Цх,у) =< а(у),х> Щу) Vx G а(у) £ П», Ъ(у) € К1, у € Y0, (7) то целевая функция

задачи apprx.V0 является выпуклой на Х° и

уО _ уО лstat — opt >

где - стационарное множество задачи арргх.Р0.

Аналогично §2.2 определяются внутренняя задача квадратичного программирования для задачи арргх.Р [У]' и квазиоптимальная функция

е(у):

6(*,У) :=|Ы*,У) II, I € У е яЦУ0).

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

Л^орЛ^0! = Более того, если (7) выполняется, то

ХдО1л[У0] =

Для данной задачи верен следующий результат: Любая траектория {£„} метода 5МЕТН.АСТ1\Г. арргхР-п.н. сходится к стационарному множеству задачи арргх.Р

Более того, если выполнено (7), то {ж"} Р-п.н. сходится к оптимальному множеству Х^.

Далее в §4.1 приведены примеры численного решения задачи аппроксимации:

к

тах | - Е ш,

где У0 С Я*.

Функции г = 1,..., к выбираются следующим способом (для случая (ИтУ° = 2):

уЬ?» *1+«2 <<*, (8)

где ^ е N. Пример

Данные: /^(у^ = 5т(27г?/1), Г° = (0,1], как в (8). Параметры: 7 = 0.1,

е = 0.01, к = 0.3, 77 = 0.7,

£„ = тах(е0(1-2)_", Ю-3), п = 1,2,...,

стп = £0(1-2)-п>п = 1,2,.... £-0 = 2.

Пример 2.

Данные: Р{уиу2) = + Уъ)ыъуи У0 = [0,1] х [1,2.5], как в (8).

Параметры: См. Пример 1. Пример 3.

Данные: Р(уиу2) = (1 + У0 = [0,1] х [1,2.5], как в (8).

Параметры: См. Пример 1. Пример 4.

Данные: Г(уг,у2,у3) = сов(уз)(1 + у^, У0 = [0,1] х [1,2.5] х [0,1], как в (8).

Параметры: См. Пример 4.1.

Из результатов решения задач из Примеров 1-4 следует, что метод, использующий схему пассивного случайного поиска, перестает работать уже на простой тестовой задаче из Примера 1. Это ясно демонстрирует преимущества метода БМЕТН.АСТГУ.арргх над неактивизированным методом БМЕТН. А СТ1У. арргх.

Принимая во внимание метод, использующий схему активного поиска критических ограничений, в параграфе сравниваются результаты его работы с результатами вычислений в методе Римтсена. Эффективность работы метода SMETH.ACTTV.appn: выше, чем у метода Римтсена благодаря тому, что решаемые задачи линейного программирования в методе БМЕТИЛСТТУ.арргх (для нахождения точки хп+х) имеют гораздо меньшую размерность, чем в методе Римтсена (| У„ ]«| У„ |, п = 1,2,...

В §4.2.рассматривается задача минимаксного синтеза робото-техиических систем. Создание систем автоматизированного проектирования (САПР) робототехнических систем (РТС) предполагает решение целого ряда технических, системных и математических проблем. По мере развития систем коллективного пользования многие проблемы, которые

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

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

З.Основные результаты.

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

В работе доказана теорема сходимости метода п.н. к квазиоп-

тимальному множеству. Численная реализация метода выполнена для задач полубесконечной оптимизации. В частности, решена задача Чебышевской аппроксимации функции полиномом для функций с размерностью по у от 1 до 3 (задачи размерности 3 ранее практически не исследовались вследствие их сложности).

Важнейшими преимуществами предложенного стохастического метода внешних аппроксимаций являются следующие:

1) Метод построен для общей задачи V0 и может быть легко адаптирован для любого специального класса задач с бесконечным числом ограничений. Более того, для любого специального класса задач некоторые новые эффективные оптимизационные алгоритмы для решения простых или внутренних задач могут работать со схемой ЯМЕТН.А СТГУ.

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

3) При поиске точек хп, п ~ 1,2,... для классов задач, в которых целевая функция и ограничения являются линейными по х, .может быть эффективно применен симплекс-метод.

4) Так как■ предложенный метод является развитием мгголор мульти-старта, то для внутренней задачи локального спуск.! можно применять специально разработанный алгоритм для нпмлмоюлн« ¡; методе мульти-старта.

5) Метод удобен в реализации и обладает пргк^х-к'нымп гной^грямк сходимости.

4.Публикации.

[1] Ю.В.ВОЛКОВ, А.Г.ПЕРЕВ03ЧИК0В (1991), Об одной тестовой задаче минимаксного синтеза робототехнических систем, Матема-

' ¡тическое моделирование, 3, 2, стр. 218-231.

[2] Y.V.VOLKOV, S.K.ZAVRJEV, A General Stochastic Outer Approximations Method (appear in SIAM Journal of Control and Optimization).

[3] Y.V.VOLKOV, S.K.ZAVRIEV (1995), A General Stochastic Outer Approximations Method, Тезисы доклада, Конференция по стохастической оптимизации, Нидерланды.

[4} Ю.В.ВОЛКОВ (1996), Об общей конструкции стохастических методов внешних аппроксимаций, цеп. в ВИНИТИ, N 848-В96.

[5] Ю.В.ВОЛКОВ (1996), Практическая реализация стохастического метода внешних аппроксимаций для решения задачи полубесконечной оптимизации, деп. в ВИНИТИ, N 855-В96.