Стохастические алгоритмы решения оптимизационных задач на отношениях предпочтений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1ре-воя: к Л/0И69 в««-5.01.1390

Министерство высшего и среднего специального 9

образования УССР /¡У!)

Киевский ордена Ленина и ордена Октябрьской Революции * государственный университет им. Т. Г. Шевченко

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

МИХАЛЕВИЧ Михаил Владимирович

УДК 519.8

СТОХАСТИЧЕСКИЕ АЛГОРИТМЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ НА ОТНОШЕНИЯХ ПРЕДПОЧТЕНИИ

01.01.09 — математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Киев 1990

Работа выполнена в Киевском государственном университете им. Т. Г. Шевченко.

Официальные оппоненты: доктор физико-математических

наук, профессор ИВАНИЛОВ Ю. П.,

доктор физико-математических наук, профессор ГИРКО В. Л.,

доктор физико-математических наук ТРЕТЬЯКОВ А. А.

Ведущая организация: Московский государственный университет имени М. В. Ломоносова.

Защита состоится « »- 19 г. в -

часов на заседании специализированного совета Д 068.18.16 при Киевском государственном университете им. Т. Г. Шевченко по адресу:

252127 Киев 127, проспект Академика Глушкова, 6, факультет кибернетики.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан «-» - 19

Ученый секретарь специализированного совета

АНИСИМОВ В. В,

ВВВДЗМЕ

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

Участие экспертов и лиц, принимающих решение (ЛПР), в процедурах принятия решений позволяет использовать опит и интуицию специалистов для повышения качества принимаемого решения,учесть не только количественную, но и качественную информацию. Если решение принимается при неполной информации, то недостаток данных может быть частично восполнен интуитивными прогнозами экспертов.

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

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

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

Различные подходы к построению диалоговых процедур принятия решений рассматривались в работах В.Л.Волковича, В.А.'Лрико-ва.П.С.Краснощекова, Г.С.Поспелова.

Бинарные отношения и оптимизационные задачи, сформулированные с их помощью, часто использовались для теоретического анализа экономических, технических и других сложных систем. Этому посвящены, в частности, работы Дж.Дебре, Н.П.Бусленко, В.В.Калашникова, Ю.П.Иванилова, И.Н.Коваленко, М.Месаровича. В работах Х.Никайцо, К.Эрроу указанный математический аппарат был использован для исследования поведения потребителей в условиях рыночной экономики. В меньшей степени развиты численные методы решения таких задач. Различные подхода к ним рассматривались, например, А.Вержбицким, Дж.Дайером, Д.В,Юдиным. Особенностью исследуете в данной работе алгоритмов является их повышенная устойчивость к случайным ошибкам ЛПР, достигающаяся за счет увеличения количества обращений к ЛПР и роста общего объема вычислений. В их основу были положены стохастические квазиградиентные методы, развитые в работах Ю.М.Ермольева, А.М.Гупа-ла, В.Т.Поляка и их учеников. Первые из таких алгоритмов были предложены А.Й.Ястремским. В то же время алгоритмы, рассматриваемые в данной работе, имеют существенные отличия от известных методов стохастической оптимизации. Во-первых, случайность в них не только порождается внешними причинами, связанными с постановкой задачи (например, случайными ошибками ЛПР), но также заложена в вычислительную схему. Направление поиска на каждой итерации выбирается случайно, с заданным законом распределения. Поэтому данные алгоритма можно рассматривать и как развитие методов случайного поиска, предложенных в работах В.Г.Карманова и Л.А.Рясстоигина. Во-вторых, они отличаются от сточестичесякх квазиградиентных методов тем, что используеше в них

направления поиска в среднем не совпадают с обобщенным градиентом ( или его аналогом ) целевой функции.

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

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

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

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

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

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

Исследована устойчивость к случайным ошибкам ЛПР рассмотренных в работе алгоритмов при предположениях о том, что вероятность ошибки ЛПР неизвестна. Определены условия, при выполнении которых устойчивость может быть повышена за счет использования приближенных оценок вероятности ошибки ЛПР и применения коллективных процедур принятия решений. Показана возможность построения алгоритмов, обладающих максимально возможной устойчивостью к ошибкам ЛПР.

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

Реализация результатов работы. Данная работа является составной частью исследований, проводившихся на факультете кибернетики Киевского государственного университета им. Т.Г.Шевченко по госбюджетной теме ¡Г» 32 "Разработать оптимизационные человеко-машинные процедуры принятия решений в сложных социально-экономических системах". Разработанные алгоритмы реализованы в составе диалоговых процедур, созданных для прикладных СППР в ходе выполнения данной темы и хоздоговорной темы 407-88 на факультете кибернетики КГУ, а также при выполнении тем "Таможенник", "Аксон" в ВА ПВО СВ. Результаты работы также использовались в учебном процессе при создании программных средств и подготовке новых курсов лекций на факультете кибернетики Киевского государственного университета им. Т.Г.Шевченко.

Апробация работы. Результаты диссертационной работы докладывались на Международном семинаре по проблемам устойчивости стохастических моделей( г.Москва, 1982), 1У Советско-Японском симпозиуме по теории вероятностей и математической статистике(г Тбилиси, 1982), Международной конференции "Стохастическая оптимизация" (г.Киев, 1984), Международном семинаре "Стохастическая динамическая оптимизация: подходы и применения" (ВНР, г.Шапрон, 1988), Международной конференции "Многокритериальная оптимизация" (г.Ялта, 1988), И Международной конференции.по эконометрическим моделям принятия решений (ФРГ, г.Валберт,1989) на Всесоюзных и Республиканских конференциях, семинарах и

симпозиумах.

Публикации. По теме диссертации опубликовано 35 печатных работ, в том числе монография.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Объем работы - 237 страниц машинописного текста, список литературы содержит 135 наименований.

СОДЕРЖАНИЯ РАБОТЫ

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

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

В первой постановке бинарное отношение Я выступает в качестве математической модели предпочтений ЛПР. Полагается, что для двух решений, сс и у , выполняется X Л у , если ЛПР считает, что решение СС не хуже решения у . Пусть задано 2) - множество допустимых решений, требуется найти такое X* € 3) , что для любого ХвЭ выполняется

X."К X. , Эту задачу в дальнейшем будем называть задачей поиска наиболее предпочтительного элемента и обозначим её так:

ОГ-^ргс/. (1)

Задача (I) рассматривается в работе при следующих предположениях: множество Д) - выпуклый компакт из £ ; отношение Я удовлетворяет условиям полноты (А1), рефлексивности (А2), транзитивности (АЗ), непрерывности (А4), монотонности (А5), выпуклости (А6), регулярности (А7), выпуклости по

Каппах (А8), дифференцируемое™ (А9), конечной плот-

ности (АЮ), несущественной овражности (АН).

Во второй постановке считается, что отношение - это объективно существующее, но неизвестное правило предпочтения решений. Информация, поступающая от ЛПР, представляет собой экспертную (стохастическую) реализацию этого правила.

Для двух, решений, Ос и у , таких, что до Ц и , ЛПР с вероятностью скажет, что решение X не хуже ре-

шения у (обозначим . йС. Яе ^ ), а с вероятностью

^(х, у) = 1 (зс, у) Даст противоположный ответ.

Требуется решить задачу (I) при известном , но неизвест-

ном Л . Такую постановку будем называть задачей оптимизации на предпочтениях с помехами. Заметим, что величина £ ) » как правило, неизвестна и поэтому не может быть использована при решении данной задачи.

В главах 2-4 рассматриваются численные алгоритмы решения задачи поиска наиболее предпочтительного элемента, её частных случаев и обобщений. В главе 5 определяются условия, при которых эти алгоритмы могут применяться для решения задачи оптимизации на предпочтениях с помехами, т.е. проводится анализ их устойчивости к случайным ошибкам ЛПР.

В разделе 1.3 проведена классификация задач поиска наиболее предпочтительного элемента. Если отношение А удовлетворяет условиям А1-А4, А6-А7, то задача (I) является аналогом задачи квазивыпуклой оптимизации. Если отношение В удовлетворяет условиям А1-А4, А6-А8, то (I) - задача выпуклой оптимизации. Аналогами задач дифференцируемой (выпуклой и невыпуклой) оптимизации являются задачи, у которых отношение А удовлетворяет условиям А1-А4, А6-А9 и А1-А4, А5, А9 соответственно.

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

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

Пусть ЗС € {сс*} - произвольное допустимое решение задачи (I). Рассмотрим случайное направление

в , если X ,

-е , если (х-£(9)9)Я 02 ,

(2)

где отношение Я удовлетворяет условиям А1-Л4, Л6, А7, А9, 0 - случайный вектор, равномерно распределенный на П. -мерном

единичном шаре, величина }"(&) подобрана так, чтобы выполнялось либо (X 9) Ах .либо (х~у($)9)£эе. В силу свойства А9 отношения Я у,(Э)>0 с вероятностью I. Справедливо следующее утверждение.

Теорема 2.1. Пусть СС. , отношение Я удовлетво-

ряет условиям А1-А4, Аб, А7, А9. Тогда

где

К*) - нормаль опорной гиперплоскости к множеству

, доведенной через точку X ,

Км -

Нормаль опорной гиперплоскости в квазивыпуклых оптимизационных задачах является аналогом квазиградиента, поэтому, согласно теореме 2.1, направление ^ ^^ может быть использовано в методах стохастической оптимизации в качестве стохастического квазиградиента. Используя этот результат, в разделе 2.2 предложены следующие численные алгоритмы решения задачи (I).

I, Метод стохастических квазиградиентов:

а^-^^ДЧх-Л, 4«о,1.... , (3)

где ОС0 - произвольное начальное приближение; ) - опе-

ратор проектирования на множество Э ; ^ > 0 " детер-

минированный скалярный шаговый множитель, &

^ 6СЛИ

^ " (_ - О5 , если (х*-у(в')в*)цх\

(4)

I. независимое наблюдение „ад реализацией случайного вектора б, р(8') определяется так же, как и в (2). Доказано, что при выполнении условий ^ Оц — 00 »

р^ <■ °° все предельные точки последовательности

{.Х5} , построенной согласно (3), с вероятностью I принадлежат множеству X решений задачи (I).

2. Метод проекции стохастического градиента:

1 яЗ^Сх'-г***). <5)

X5+1 = х* + р3 (у*1-^,¿ = 0,4,... ,

где , 2) , определено соглас-

но (4). 1

Условиями сходимости алгоритма (5) будут:

о*р£±1> ^>0,^/8-^0, 2

его ^

Отметим следующуньособенность этого алгоритма. В случае, когда ¿П* (Р) Ф ф , 0.<р5<1 , а на-

чальное приближение СС° - внутренняя точка множества ]) , все текущие приближения эг5 также будут внутренними точками 3 . Это позволяет применять алгоритм (5) для решения задач вида (I), у которых отношение Я не определено вне Ъ

Заметим, что на каждой итерации алгоритмов (3), (5) требуется определять проекцию точки на множество 3) . Такая задача может быть достаточно сложной. Поэтому для решения задачи (I), у которой множество "]) задано линейными уравнениями и неравенствами, в работе предложен аналог метода стохастической линеаризации:

(г*+\хх) = пЬг (г'**,х), х*еЯ, (б)

ее541 г л« Ссс^-ас5),

сходящийся при тех же условиях, что и алгоритм (5).

Для решения задачи вида

* _

осеХ ,

где ^I (х.) , ¿~ - выпуклые функции; X -

выпуклый компакт из ь предлагается алгоритм

/'^^-рлг (в)

г

Л]').

если 0 , ¿*ТуП*

У Г, ..

где I * " ст0хастиг!еск1,й квазиградиент функции £ ¿* ) в точке X. »¿С5 . В качестве ^ ¿-* допускается использование субградиента (п дифференцируемом случае - градиента) функции <? ;-* Г^с) • Условиями сходимости этого алгоритма к .X *

О 1 М во 2

выступают ^ Рх = °° ' 2 Р^

• " IIIIII*'•

и условие Слейтера для нелинейных ограничений задачи (7).

Алгоритм (8) монет применяться и для решения задач поиска наиболее предпочтительного элемента с ограничениями вида

32 & ^ О.1, , где Я с - отношения предпочтения,'

О.1 - заданные решения. В этом случае вместо в (8)

будет использовано случайное направление ~ ?£* »

определенное согласно (4) с использованием отношения Ц. вместо Я .

Алгоритмы (3), (5), (6), (8) представляют собой формальное описание диалоговых процедур принятия решений. Например, алгоритм (3) может быть реализован в режиме диалога СППР и ЛПР следующим образом. Пусть известно - предыдущее приближе-

ние к оптимальному решению X* . СППР генерирует б5 , вычисляет + для некоторого Т"^® и предлагает ЛПР для сравнения решения Х^^в* и . ¿¿ели ЛИР считает, что первое из этих решений не хуке второго, то

, в противном случае СППР вычисляет и предлагает ЛПР сравнить ас5-^"* и ОС*. Если, по мнению ЛПР, первое решение не хуке второго, то

(х£) = , в противном случае уменьшается величина ■V» и повторяется описанная процедура. После того, как определено " ^ (сЕ5) , СППР вычисляет по формуле (3).

Очевидно, что такая проце.дура может потребовать большого числа обращений к ЛПР на одной итерации. Поэтом/ представляет интерес алгоритм, требующий однократного обращения к ЛПР на каждой итерации. Рассмотрим случайное направление

I в противном случае ,

где > 0 - заранее заданная детерминированная величина. Справедливо следующее утверждение.

Теорема 2.5. Пусть отношение Я удовлетворяет условиям А1-А4, А6-А9, X* .Тогда

где Ц^Ц^.^в п'н- •

На основе теоремы 2.5 можно доказать сходимость к X* аналогов алгоритмов (3), (5), (б), (8), использующих направле-

•ов алгоритм

ние (эо) , определенное согласно (9) при дополнительном

условии •

В разделе 2.3 рассмотрены алгоритм решения задачи (I) в случае, когда отношение Я не удовлетворяет условию дифферен-цируемости А9. От рассмотренных ранее они отличаются выбором направления

3 Г в* . если (&+Х<в*№!1

1 , если (8*-Г(&*№А Ш)

где ОС 5 { ЭС^ - последовательность приближе-

ний к X* ; |Ц.5 - реализация случайного вектора с независимыми, равногйрно распределенными на £ — * компонен-

тами

В работе доказано, что для Л с вероятностью I

И (\ - - ^(Уй( ].

Полученное соотношение показывает, что 2 , опре-

деленный согласно (10), не будет аналогом стохастического квазиградиента, однако это направление обладает свойством, используемым при исследовании сходимости стохастических квазиградиентных методов: М (х*)/32 s) будет направлением убывания расстояния от а5 до X* , если 3cs<= X .

Ha этом основывается доказательство сходимости алгоритмов (3), (5), (8), использующих , определенное со-

гласно (10). Алгоритм (6), использующий это направление, будет приближенным, оценки точности для него приведены в главе 5.

В разделе 2.4 даны оценки вычислительной сложности предложенных алгоритмов. Рассмотрена последовательность Í.X5}, S"Oti,..., построенная по формуле

--s.i X5 , если X.3R 2CS+\

Л = S*i

<32 в противном случае,

где последовательность построена согласно одному

из рассмотренных алгоритмов; 0С° = 32° , Сценки вычислительной сложности представляют собой оценки с заданной доверительной вероятностью i~po количества итераций алгоритма, которое достаточно осуществить для достижения последовательностью { XSj множества L (&) приближенных (с заданно^ точностью € ) решений задачи (I). Множество L (b) = {ztxRcC(6)) , <¿(6) выбрано таким, чтобы

{ о:t тля Ксс-х*II^6 \ £ Líe).

Для алгоритма (3) справедливо следующее утверждение.

Теорема 2.8. Пусть построена согласно (И),

где построена с помощью алгоритма (3), использую-

щего направление (xS) , определенное согласно (4).

Пусть для некоторого 30 выполняется неравенство

Тогда для всех S

Р{ L(b)}*í-pa .

Используя теорему 2.8, были получены оценки 50 для

различных регулировок

К*

. Например, для

ех

г

тт +с ~б

х'еХ*

^ Г,

р„£'

¿е^ Мр0<

$+й

Минимальное значение

примет при

* С а

'„Ж.

зг

II

для ру>0 ,^<2ер0к/п) тСп Иас'-аг-'И*-0 6*

х*£Х*_\_1_

1 .

Минимальным 5о будет при ^ — £р01с¿(п) . В случае, когда в алгоритме (3) используется направление

£ (а?*) , определенное согласно (10), справедливо следующее утверждение, _

Теорема 2.9. Пусть { 20 } построена согласно (II), где построена с помощью алгоритма (3), использующего

(эс5) , определенное согласно (10). Пусть отношение 9-удовлетворяет условиям А1-А4, Аб, А7, А10, АН и для некоторого 5 о выполняется -

«р.*' ,

где В *00 . Н* 00 - константы, использующиеся в формулировке свойств АЮ, АН.

Пусть также для любого 5 УЛ ^ 5 . Тогда для

всех £ 5-"»>0

тт цл0-гс*" +

5

для

Оценки величины 50 > следующие из теоремы 2.9:

^ = гтг п?и ,

<

ехр

¿Рак(п) з

¿(р0+В<ВН)

( 9 •> О1

1 тт Их°-х*11-р0а +с2-т

.««.У» I "

зг'ЧгХ

:бр01сл (п.)

В

/

1

Минимальное значение 3 0 примет при

с- «у г у

Для

„ л л п, бро'кМ п—л

при < -- , и ,

6РЛМ

5П =

ЬМрр.ув

1

Минимальное значение Й» примет при 0 = --

25

Полученные оценки показывают, что применение процедуры (10), не требующей выполнения условия АУ дифференцируемости

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

Аналогичные оценки были получены и для алгоритмов (5), (8). Они показывают, что алгоритмы (3), (5), (8) имеют экспоненциальную вычислительную сложность. В разделе 2.5 рассматривается возможность уменьшения'их вычислительной сложности путем применения усредненных направлений спуска ¥ 5 вместо

Исследованы две процедуры усреднения. Согласно первой, на $ -й итерации по формуле (4) вычисляется К независимых направлений спуска ("X*),^'"(сс*) » которые

затем усредняются

Вторая процедура - усреднение направлений спуска, подученных на 3 -й и предыдущих итерациях по рекуррентной формуле ,

(13)

£

где детерминированный множитель ' 0$ выбирается, исходя из условий: ^ В?*«, . <?, »0 .

Для алгоритма (3), использующего вместо направления £ определенный согласно (12) случайный вектор ?

справедливо следующее утверждение.

Теорема 2.13. Пусть { } построена согласно (II),

где построена алгоритмом (3), использующим направ-

ление , определенное согласно (12). Пусть в (3)

}* > И для

некоторого £а выполняется

•4=0 ^ '

пап В*в.«-Г-

, г г

Тогда для всех 3

теорему, были получены ( для регулировок = '

Используя эту теорему, были получены оценки величины , зависящие от К , для регулировок и

"" £*1 • Ддя первой из регулировок величина число обращений к процедуре (4), требуемое для построения приближенного решения из ^ (б) — будет минимальной при

К = тах

гсмр'

Що-у Ш

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

п ъ

У У {+с(п)

В противном случае алгоритм (3), использующий случайное направление \ 5 (З^) , потребует меньшего числа обращений к процедуре (4). Аналогичный результат получен и для второй из рассмотренных регулировок .

Для алгоритма (3), использующего направление ^ 5 , определенное согласно (13), доказано следующее утверждение.

Теооема 2.14. Пусть {. 5с 3 } определена согласно (II),

где {} построена алгоритмом (3), использую::!/!:.« ? 5 , определенное согласно (13). Пусть в (3) П =П '//С (п.)

тте^ят! о-д-? 1

Г-

и для некоторого выполняется

* + таг*

где

- диаметр множества Л . Тогда для всех

Поскольку для применяемых в (13) регулировок ^ величина V 5 ^ 0 ^) , оценки 50 , следующие из теоремы 2.14, превосходят оценки К50(}С) ■ следующие из теоремы 2.13 для оптимального выбора К ПРИ рассмотренных регулировках. Таким образом, применение процедуры (12) более предпочтительно, с точки зрения уменьшения вычислительной сложности алгоритма (3), чем применение процедуры (13).

Для алгоритма (3), использующего процедуру (9) вычисления > доказана теорема 2.15, аналогичная теореме 2.14. Оценки качества обращений к ДПР, требуемого для получения приближенного решения задачи (I) с помощью такого алгоритма,показывают, что при соответствующем выборе параметров процедуры (4) потребуется меньшее количество таких обращений для этой цели.

В разделе 2.6 рассмотрены примеры диалоговых процедур принятия решений, основанных на алгоритме (3).

Полученные оценки вычислительной сложности алгоритмов существенно зависят от выбора начального приближения Xе. В разделе 2.? предлагается выбирать Х° кок решение задачи максимизации на множестве 3) аналитической функции полезности, приближенно отражающей интересы ЛПР. В данном разделе изложен алгоритм построения такой функции.

В третьей главе рассмотрены стохастические постановки задачи (I). Они сводятся к задаче вида

Я

А

рге^

Мд^а:,«))« 0, 1 = 1,т., хьХ >

. Для решения

- произвольное

где - функции управляемых переменных X -л

случайных параметров и) , выпуклые по X почти при каждом од - выпуклый компакт из £ этой задачи предложен следующий алгоритм.

Пусть 2;°= 0, ¿=1,т , Х°

с у---

начальное приближение. Постооение гг. . £. - 1 , О?

5 • ; 5 1 по известным ¿?. , £=2,/71," X ,3=0,1,... осуществляется следующим образом. 4 , , -

1. Вычисляются 2; = 2£ + 05 (£•(:Ж'. и)£) ), 1= 1, т , где и)5 — 3-е независимое наблюдение над реализацией случайных параметров , ^ ¿3 - детерминированный скалярный множитель. 2 / • • --т

2. Определяются множества X— 1 = 1 } и

3. Вычисляется по формуле

П

г.«!3

в противном случае,

¿«1Сх4)

где ^ , В.Т'О» 1= детерминированные параме

ритма." Р- стохастический кваяитяпиент йунтгтгии

'/етры алго-стохастический квазиградиент функции

в точке 32 = X5

✓7 ь

гея =

>

где толь

4. Вычисляет

р$ О - детерминированный скалярный

Предложенный алгоритм представляет собой обобщение алгоритма (8). Зхесто левы частей нелинейных ограничений в нем используются их статистические оценки с • Сходимость предложенного алгоритма при произвольном виде множества X 5 к условиях:

оо оо

гИг: гз-0•

}*.[УьТхО. 1*1,т, ил ({X =Ли,а)ч 0. £=СТ) * 0

доказана в теореме 3.1.

Теооема 3.1. Пусть выполняются перечисленные условия, 2s(jG5) определяется согласно (4) или (10). Тогда все предельные точки последовательности i3!S} , построенной согласно изложенному алгоритму, с вероятностью I принадлежат множеству решений задачи (14).

Для доказательства этой теоремы использовалась модифицированная техника доказательства сходимости с вероятностью I стохастических квазиградиентных методов (лемма 3.1).

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

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

В разделе 4.1 рассмотрена процедура построения случайного направления

П Ул = ( если ) Я а:,

" 1 ~ в противном случае.

где отношение Я удовлетворяет условиям А1-А4, А5, А9,

0 * - 5-е независимое наблюдение над реализацией случайного вектора, равномерно распределенного на П. -мерном единичном . шаре, ^ ^(в5) выбирается так же,

как в (4), а - так же, как в (9).

Теорема 4.1 утверждает, что

где

еы - вектор коэффициентов касательной гиперплоскости к множеству { Ц ' Ц Я X } , проведенной через тоЧ1дг

Полученный результат обосновывает применение алгоритмов (3), (5), (б), использующих такое случайное направление, для решения невыпуклых задач вида (I). Доказано, что любая предельная точка последовательности { X 3 } , построенной согласно любому из этих алгоритмов, с вероятностью I принадлежит множеству точек { ЗС*1 , удовлетворяющих необходимому условию экстремума ||л* (х*-С = 0 .

В разделе 4.2 рассмотрена антагонистическая игра, сформулированная посредством бинарных отношений предпочтения. Пусть X - множество стратегий первого игрока; У - множество стратегий второго игрока; бинарное отношение Я , заданное на

, отражает предпочтения первого игрока. Под решением (седловой точкой) этой игры будем понимать такую пару стратегий (х*У*) . «ТО (л\цШ(л*,и*)& (л,Ц*) при

любых хеХ, °

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

гс = л4 (а:,у*),

где в кечество операторов ^ (••>) и г.-огут

бкть использованы любые из рассмотренных ранее алгоритмов. Доказано, что при соответствующем подборе параметров этих алгоритмов все предельные точки последовательности {.Э!5} с вероятностью I принадлежа? множеству {X *} стратегий первого игрока, входящих в решение игры.

В разделе 4.3 рассмотрена частично-дискретная задача поиска наиболее предпочтительного элемента

СсеЕ , ^еЬГ,

где множество У - конечно. Дня её решения предложен следующий алгоритм.

О — о

Пусть СС ■> у - произвольное начальное приближение к

решению задачи, Ц°. Опишем процедуру построения — 5*1°

.8 + 1

£С"' , У"" п0 известным X »у

1. Осуществляется случайный выбор у' из множества У, так, чтобы с ненулевой вероятностью мог быть выбран любой элемент этого множества.

2. Вычисляется

Ч

¿■и

=

8 + 1

если

где

3. Определяется

ё\ у(в')

4. Вычисляется

I

у ^ в противном случае . 2 ('з? » ^ по формуле

05 , если определяются так же, как и в (4).

Л ={

Л5-.

м

если

Л

в противном случае .

Теорема 4.5 определяет условия сходимости последовательности { ССу & } к множеству решений рассматриваемой задачи.

В пятой главе проведен анализ устойчивости к ошибкам ЖР алгоритмов, исследованных зо второй главе. Дня этого рассматривается задача оптимизации на предпочтениях с помехами при предположении о том, что отношение Я. в (I) удовлетворяет условиям AI-A4, А6-А9. В разделе 5.1 доказано, что замена в

(4), (9) отношения R его экспертной реализацией Re приводит к появления ненулевого среднего отклонения величины

М(2'(х*)/х') от-fc/ft) -¡ifgsjjj- - ненулевой

средней ошибки определения стохастического квазиградиента. В разделе 5.2 рассмотрена следующая задача. Пусть последовательность { СС^ } построена согласно одному из рассматриваемых в работе алгоритмов. Стохастический квазиградиент (или его аналог) в этом алгоритме определяется с точностью до ненулевой средней ошибки JJ . В этом случае могут существовать предельные точки последовательности (.З^} , не принадлежащие множеству X > к которому сходится алгоритм при точном определении стохастического квазиградиента. Требуется определить зависимость от JJ максимально возможного отклонения предельной точки последовательности 13!5 } от множества X . Такие оценки были построены в разделе 5.2 на основе леммы 3.1, доказанной в третьей главе, для алгоритмов (3),

(5), (6), (8). Наряду с оценками, для алгоритмов были сформулированы условия устойчивости - достаточные условия того, что все предельные точки последовательности ^ ^ } принадлежат множеству х*.

На основе построенных оценок и сформулированных условий устойчивости алгоритмов (3), (5), (6), (8) в разделе 5.3 получены следующие результаты. .

Рассмотрим процедуру (9) определения \ (-Х) при условии, что вероятность совпадения ответа ЛПР с отношением Ä. при сравнении км произвольных решений у не зависит от

Л, т.е. £ >i/<2 .Справедливо

следующее утверждение.

Теорема 5.II. Пусть X - множеству решений задачи

(I). Тогда

не Mi!

где величина р & 0

Теорема показывает, что направление (Х) при этом условии остается аналогом стохастического квазиградиента. Алгоритмы (3), (5), (б), (8), использующие это направление, будут сходиться с вероятностью I к множеству X. решений задачи (I). Сохранится порядок оценок их вычислительной сложности, следующих из теоремы 2.15.

Для случая, когда величина § ^ различна при разных Э2,, в работе построен пример сходимости последовательности {эс^ , -построенной согласно (3), к множеству точек, не принадлежащих X . В этом случае для алгоритма (3), использующего определенное согласно (9) направление ^(и)* справедливо следующее утверждение.

Теорема 5.12. Пусть выполняется неравенство

*гссов { ЯКЩ-1) ) *у < т- '

где о —

у>Ы = а.гст ^ ||г(*)||В*»-д|1 ) .

Тогда все предельные точки последовательности построенной согласно (3), (9),с вероятностью I принадлежат множеству X. решений задачи (I).

Из теоремы 5.12 следует,^то если отношение Я удовлетворяет условию АН, то и решение задачи (I) может

быть получено с помощью алгоритма (3), (9) и для случая, когда

. Иными словами, алгоритм (3), (95 устойчив к случайным ошибкам ЛПР, если вероятность такой ошибки р(эс»у) = 4, — ^ достаточно мала.

Если в (I) Э = £ , то справедлив более сильный результат: при для любых Л,у все предельные точки последовательности {.Л5} , построенной согласно (3), (9), с вероятностью I принадлежат множеству X решений

задачи (I).

Аналогичные утверждения доказаны также для алгоритма (3),

(4).

В работе построены зависимости между отклонениями предельных точек {jCs} от X* и величиной ^ (х,^). Для алгоритма (3), (9) доказано следующее утверждение.

Теорема 5.13. Пусть Lié) - множество вида {зМЭСЯв^б)} , где d(¿) подобрано таким, чтобы

l^imio ||«-ае*Ц4б} s Lis) ; d(D- диаметр этого множества. Тогда с вероятностью I все предельные точки последовательности { X $ }

{хгтсп 112-2*1léd(L)l

принадлежат множеству

» где g —

2(ï-i)JndÛ>)

¿(ъ) - диаметр множества .

Аналогичные оценки были построены для алгоритма (3), (4).

Для задачи оптимизации на предпочтениях с помехами, решаемой алгоритмом (3), (10) при условии, что В. удовлетворяет А1-А4, А6-А7, были доказаны утверждения, аналогичные теоремам 5.12,5.13.

В разделе 5.4 рассмотрены пути повышения устойчивости к ошибкам ЛПР: применение приближенных оценок величины ^ и процедур коллективной экспертизы. Как отмечалось, точное значение величины ^ (х.,^) , как правило, неизвестно. Если известны приближенные оценки 0 (Э2,у) этой величины, устойчивость алгоритмов к случайным ошибкам ЛПР может быть повышена при использовании вместо (9) следующего правила опреде-

ления

15М . I

в5 -Ôs

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

Для алгоритма (3), использующего такое ^ (з?) » утверждение, аналогичное теореме 5.12, формулируется следующим образом.

Теорема 5.15. Пусть выполняется неравенство $ тСп.

СЯССйЗ

Щ

то» /

2

о . -

где величина ^ - такая же, как в теореме 5.12,

Тогда все предельные точки последовательности { ЭС й ^ I построенной алгоритмом (3), будут с вероятностью I принадлежать множеству X решений задачи (I).

В работе рассматривается следующая модель коллективной процедуры принятия решений. Пусть решения оценивают И* экспертов, расхождением интересов которых можно пренебречь, поэтому можно считать, что при сравнении решений все эксперты стараются следовать отношению .К , различия в оценках вызваны исключительно их случайшл.м ошибками. Экспертная реализация Я.е отношения .Я строится следующим образом: из двух решений, £С и у , лучшим считается то, за которое высказалось простое большинство экспертов. Предполагается, что п\ - нечетное число и эксперты не могут воздерживаться при оценке решений. Доказано, что если для всех экспертов

то величина ^ - минимальная вероятность получения ответа, совпадающего с 11, при сравнении всевозможных пар решений согласно описанной процедуре - увеличивается с ростом 171 Из теорем 5.12, 5.13 следует, что такая процедура повысит устойчивость алгоритма (3) к случайным ошибкам ЛПР.

В разделе 5.5 проведен анализ устойчивости к ошибкам ЛПР детерминированных алгоритмов решения задачи (I) - метода Дайера-Дкоффриона и аналога метода ЗС. Доказано, что при любой, отличной от 0 вероятности несовпадения ответов ЛПР с отношением Я , возможны существенные отклонения результата работы алгоритмов от множества X решений задачи (I).

В разделе 5.6 доказана разрешимость задачи оптимизации на предпочтениях с помехами для случая, когда для всех ^»У • Согласно теореме 5.1?, эта задача эквивалентна задаче разрывной стохастической спти"и.за|;ии.

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

В заключении сформулированы следующие основные результаты работы:

1. Ряд прикладных задач принятия решений сводится к оптимизационным задачам на отношениях предпочтений. Среди последних можно вьщелить классы аналогов задач квазивыпуклой, выпуклой и дифференцируемой оптимизации.

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

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

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

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

6. Исследована устойчивость к случайным ошибкам ЛПР предложенных алгоритмов. Определены условия, при выполнении которых данными алгоритмами может быть решена задача оптимизации на предпочтениях с помехами. Доказано, что такая задача не может быть решена методами Дайера-Джоффриона и ЗС.

7. Изучены пути повышения устойчивости к ошибкам ЛПР предложенных алгоритмов. Получены условия целесообразности применения процедуры коллективной экспертизы при сравнении решений.

8. Доказана разрешимость задачи оптимизации на предпочтениях с помехами. .

9. Разработанные и исследованные в диссертации численные методы реализованы в составе пакетов прикладных программ для ЭВМ класса СЫ и ПЭВМ,

Основные результаты диссертации опубликованы в следующих работах:

1. Михалевич К.В. Обобщенный стохастический метод центров //Кибернетика. - I960. - !."' 2. - С. 122-125.

2. Михалевич М.В. Об устойчивости методов стохастического программирования к ошибкам вычисления стохастических квазиградиентов //Кибернетика. - I960. - № 3. - С. II7-II9.

3. Ястремский А.И., Михалевич М.В. Стохастические методы поиска наиболее предпочтительного элемента и их диалоговая интерпретация //Кибернетика. - I960. - Г1 б. - С. 119-125.

4. Михалевич М.В., Кошлай JI.Б. Оценки и условия устойчивости методов стохастического программирования и методов поиска наиболее предпочтительного элемента (резюме) /Деория вероятностей и её применения. - 1981. - Вып. 4. - С. 817.

5. Mihalevic M.V,,Koslai L.B. Some questions of stability theory of the stochastic economical во de la //Lecture Notes in Mathematics. - 198?.- 282. - P. 125-136.

6. Михалевич M.B. О возможности применения метода проектирования стохастических квазиградиентов для минимизации ло-кально-лишшцевых функций //Кибернетика. - 1983. - 1Г> 3. - С. 124-125.

7. Ыирзоахмедов ф., Михалевич М.В. Метод проекции стохастического - градиента //Кибернетика, - 1983. - № 4. - С. 103109.

8. Михалевич М.В. Оценки скорости сходимости стохастических методов поиска наиболее предпочтительного элемента //Докл. АН УССР. Сер. А. - 1984. - » 5. - С. 74-76.

9. Михалевич М.В. Анализ устойчивости к ошибкам ЛПР стохастических методов поиска наиболее предпочтительного элемента //Кибернетика. - 1985. - Г» 3. - С. 41-48.

10. Михалевич М.В,, Рымарук В.И. Алгоритмы поиска седло-вых точек в антагонистических играх, заданных посредством бинарных отношений предпочтения //Изв. АН СССР. Техн. кибернетика. - 1985. - № 3. - С. 17-25.

11. Mikhalevicii M.V. Stochastic approaches to Interactive Bulticriteria optimization problems, - Laxenburg, 1986. - 16 p. -(Working paper/ Intern. In St. Applied Systeri3 Analysia; 86 - 10).

12. Михалевич M.B. Оценки скорости сходимости одного метода поиска наиболее предпочтительного элемента //Журн. вычисл. математики и мат. физики. - 1986. - 26. Г3 7. - С. 994-1005.

13. Mikhalevich M.V..ICoshlai Ь.В. Estimates and conditions for stability of atochaetic programming methods and methods

of search, for the most preferable element // J. Soviet

Math. - 1986. - N 2. - P. 1516-1525.

14. Мирзоахмедов Ф., Михалевич M.B. Прикладные аспекты стохастического программирования. - Душанбе: Маориф, 1989. -342 с.

15. Михалевич М.В. Оценки скорости сходимости процедур, использующих усредненные направления спуска /кибернетика. -1989. - № 2. - С. 91-101.