Алгоритм векторной оптимизации на основе конусов доминирования (эффективные решения)

3.2.1. Сравнительный анализ методов векторной оптимизации

Как правило (см. [206] и, например, [32]), основным понятием оптимальности в задачах векторной оптимизации является Парето-оптимальность, определение которой дано в свойствах коалиционного равновесия (опр. 3.6.) и в главе 1.

Следует отметить, что векторная оптимизация с определением области Парето является частным подходом в общем классе кооперативных игр в характеристической форме, например [43, 199], где принципы оптимальности можно подразделить условно на два типа [32]:

1) оптимальность, связанная с устойчивостью поведения игроков (оптимальность по Парето, C-ядро и Н–М-решение);

2) оптимальность, которая явно или неявно предполагает наличие арбитра, формулирующего «разумные» свойства оптимального решения (арбитражная схема, среднеквадратическое решение, вектор дележа Шепли).

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

С учетом параметризации управляющих сил вида u = u(q, x), u = u(q, t), u = u(q) далее материал излагается на основе терминологии сравнительного анализа и результатов, полученных в обсуждаемых работах.

Основная постановка имеет вид

                                ,                             (3.7)

где Q(i) = {qÎQÌE^r | qⁱÎQ_iÌE^r_i;  – фиксированы}; Jⁱ(q) – векторный показатель эффективности i-й коалиции; M_K – множество коалиций коалиционного разбиения P ММС, состоящей из N объектов; Q(i) – множество параметров i-й коалиции; R_i – отношение предпочтения на подмножестве .

Из (3.7) следует, что необходимо определить значение векторного показателя Jⁱ(q) на множестве Парето i-й коалиции K_i, максимальное в смысле отношения предпочтения R_i, варьируя лишь компоненты вектора qⁱ. Остальные компоненты вектора q известны и фиксированы. Если предположить K_i = K = N, ММС составляет единую коалицию и задача (3.7) сводится к определению решений q, оптимальных по Парето (q^П) относительно векторного показателя J(q).

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

Ввиду сложности точного решения задачи (3.7) в связи с проблемой глобальной оптимизации Jⁱ на множестве Q(i) предлагается двухэтапная процедура, первый этап которой – определение

                                                                                            (3.8)

– является дискретной аппроксимацией задачи (3.7).

Здесь  – дискретная аппроксимация множества Парето-оптима-льных в смысле W_i (3.7) значений .

При этом множество  формируется на соответствующем дискретном множестве .

Задача (3.8) дает возможность сформировать начальные приближения для задачи (3.7) или для более сложной задачи из серии задач поиска коалиционного равновесия

                                                                                    (3.9)

относительно набора коалиционных разбиений P и системы отношений предпочтения R_i, iÎM_K в каждой коалиционной структуре РÌ Р.

Если все показатели системы образуют единую коалицию или параметры всех коалиций, кроме одной, фиксированы, то получаем известную задачу Парето-оптимизации. Многокритериальные задачи математического программирования вида (3.7) являются частным случаем задачи многокритериального принятия решений [164]. Решение задачи (3.7) основано на построении компромисса с целью понижения неопределенности выбора на множестве Парето. Наиболее гибкой является диалоговая технология решения оптимизационных задач, особенно многокритериальных [17, 32, 48, 97, 105, 142, 220, 230, 263]. Разнообразие возможных способов получения и формализации информации о предпочтениях функционирующих коалиций или проектировщика в процессе диалога обусловило появление большого количества весьма различных подходов и методов решения многокритериальной задачи (3.7). Содержательные обзоры и библиографии по проблеме многокритериальной оптимизации представлены в работах
[28, 32, 39, 44, 47, 54, 84, 85, 105, 142, 161, 164, 204, 206, 207, 220, 226, 238, 239, 248, 345]. Опираясь на результаты указанных обзоров и на ряд работ, которые будут упомянуты по ходу изложения, можно сделать вывод, что многообразие существующих подходов к решению задачи (3.7) целесообразно разделить на следующие группы (для удобства обозначений далее предполагаем, что все показатели и параметры образуют единые коалиции интересов и действия соответственно).

1. Процедуры, основанные на построении обобщенного скалярного показателя Ф = Ф(J, l) специального вида [5, 39, 83, 84, 120, 164], где l – вектор весовых коэффициентов, характеризующий относительную важность компонент векторного показателя J. Обычно на l накладывается условие нормировки: lÎL, где

                                L = {lÎE^m|l_i >0 "iÎM; }.                          (3.10)

В итоге исходная многокритериальная задача, например с показателем потерь J, сводится к обычной задаче нелинейного программирования:

                                      определить .                                 (3.11)

Легко показать [32, 83, 206], что если компоненты J_i показателя J, а также множество Q – выпуклые, то между множеством J_G(Q) собственно эффективных (оптимальных по Джоффриону) [206] решений задачи (3.7) и множеством L вида (3.10) существует взаимнооднозначное соответствие. Таким образом, при заданной структуре функции Ф(J, l) вектор lÎL полностью определяет решение на множестве Парето. На каждой диалоговой итерации проектировщик производит коррекцию вектора l с тем, чтобы в конечном счете выйти на нужное решение.

Отметим, что в (3.11) могут использоваться нормализованные значения показателей J_i. В этом случае на l, как правило, накладываются условия (3.10). Если же значения J_i не нормализуются, то вектор l играет более сложную роль, и для него условие (3.10) уже не выполняется. Кроме того, компоненты l_i имеют различные размерности, чтобы привести соответствующие J_i в свертке Ф(J, l) к безразмерному виду.

Процедуры построения обобщенного показателя имеют ряд недостатков. Во-первых, сделать обоснованный выбор вектора l достаточно сложно, особенно при нелинейных показателях J_i, что чаще всего и бывает, так как проектировщику затруднительно формулировать свои предпочтения в терминах весовых коэффициентов. То есть неопределенность из области показателей переносится в область весовых коэффициентов (хотя диалоговый подход и уменьшает остроту этого вопроса, так как предоставляет возможность быстрой и многократной коррекции вектора l). Во-вторых, в случае невыпуклости множества Q или хотя бы одного J_i, iÎM, нарушается взаимнооднозначное соответствие между множествами L и J_G(Q) [206].

Точнее говоря, перебор всех lÎL гарантирует построение лишь части множества J_G(Q). В то же время на множестве J_G(Q) можно выделить такие подмножества [83] , которые не являются решением задачи (3.11) ни при каких lÎL. Перечисленные недостатки существенно снижают ценность указанного подхода.

2. Процедуры с применением сообщений проектировщика о желаемых уровнях показателей.В [108, 207] рассматривается метод выделения главного показателя (пороговой оптимизации). В соответствии с этим методом из m показателей один выделяется в качестве главного (например, J_i), на остальные (m – 1) показателей накладываются ограничения. Исходная многокритериальная задача оказывается сведенной к задаче нелинейного программирования:

                                         определить ;                                 (3.12а)

                       ,               (3.12б)

где e_j – максимально допустимое (пороговое) значение показателя J_j, eÎE^m.

Неопределенность в выборе главного показателя в задаче (3.12) преодолевается в [203] , где предлагается строить оптимизационные процедуры на основе принципа сложности [109, 204, 205, 240]. В [25] в качестве главного показателя рекомендуется использовать функционал сложности, а компоненты векторного показателя рассматривать, как m нелинейных ограничений вида (3.12б), сформированных на основе технических требований к системе. При этом изменяется смысл понятия оптимальности, и полученное решение не будет, вообще говоря, Парето-оптимальным относительно векторного показателя J. В [203] принцип минимальной сложности используется для систематического выбора задачи скалярной оптимизации (3.12) из всего набора так называемых сопряженных задач вида (3.12) при . Каждая из сопряженных задач характеризуется некоторым значением W_i, , совокупность которых составляет шкалу сложности. При этом величина W_i определяет вычислительные затраты на решение задачи вида (3.12) с главным показателем J_i. Выбирая по шкале минимальную по сложности задачу, получаем наиболее экономичную вычислительную процедуру построения множества Парето. В [203] отмечается также, что использование принципа сложности не ограничивается только применением метода пороговой оптимизации, но может быть распространено и на другие известные подходы к векторной оптимизации.

В [226, 361] в различных вариантах обсуждаются процедуры, основанные на идее целевого программирования, состоящей в нахождении решения, максимально приближенного к множеству одновременно не достижимых целей g в смысле определенной метрики, при ограничении на максимальные уклонения c_i показателей J_i от целей g_i для некоторых компонент вектора J. Здесь также все сводится к задаче нелинейного программирования. Варьирование параметров e, g, c в сеансах диалога позволяет выходить на различные точки множества Парето.

Применение арбитражной схемы Нэша [32, 245] дает возможность целенаправленно выходить на множество Парето относительно точки J(q^*), получая на нем решение J (q^П), удовлетворяющее неравенству

                                                    J (q^П) £ J (q^*),                                                             

где в качестве q^* принято выбирать минимаксное или равновесное по Нэшу решение.

К недостаткам процедур, использующих информацию о желаемых уровнях показателей, следует отнести следующие:

· введение дополнительных нелинейных ограничений, что усложняет задачу по сравнению с исходной постановкой;

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

3. Лексикографические процедуры многокритериальной оптимизации [144, 180, 206, 207], основная идея которых заключается в введении упорядоченности показателей по важности: J₁ J₂ ... J_m. При этом отношение нестрогого предпочтения вводится в виде лексикографического порядка [206]. Определение Парето-оптимального решения сводится к решению последовательности минимизационных задач со скалярной целевой функцией. Последовательность решения задач определяется упорядоченностью показателей по важности. Причем каждая последующая задача решается на множестве оптимальных решений предыдущей задачи. Однако, как известно, применение данного метода малоэффективно для решения большинства практических задач, так как оптимизация по первому, наиболее важному показателю, уже приводит, как правило, к единственному оптимальному решению, и все сводится к оптимизации лишь по первому показателю.

Обойти эту трудность позволяет метод последовательных уступок [38], в котором после решения очередной, i-й оптимизационной задачи назначается «уступка» D_i на показатель J_i, расширяющая область допустимых решений последующей, (i+1)-й задачи. Окончательное решение зависит от вектора уступок и вида упорядоченности показателей по степени важности.

К недостаткам метода последовательных уступок следует отнести следующие:

· введение нелинейных ограничений;

· сложность назначения обоснованной упорядоченности показателей по важности;

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

Проблема уменьшения размерности вектора показателей с исключением менее важных рассматривается в фундаментальной работе [180].

4. Процедуры, основанные на информации о допустимых взаимных локальных изменениях показателей. Эти методы имеют прикладное значение, так как они [47, 230]:

· формировались в рамках диалогового подхода и принципиально являются машинно-ориентированными;

· используют более содержательную информацию о структуре предпочтений проектировщика без усложнения исходной постановки (3.7);

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

В [97] описывается метод Джоффриона (неявной функции полезности). Основным функциональным элементом метода является процедура построения в критериальном пространстве направления градиента  функции полезности U в текущей точке J(q). При этом, однако, функцию U(J) не требуется задавать в явном виде. Предлагается строить гиперплоскость П(J) = 0, касательную к поверхности равных значений неявной функции полезности U(J) в точке J(q). Компоненты вектора W, нормального к касательной гиперплоскости П, формируются после назначения опорного показателя J_i. Величина W_j характеризует эквивалентные изменения показателей J_i и J_j (при постоянстве значений других показателей), не меняющие значения неявной функции полезности и определяющие относительную важность для проектировщика i-го показателя по сравнению с j-м в текущей точке J(q). Далее полагается .

Векторно-релаксационные методы [220, 265, 363] используют информацию о предпочтениях проектировщика в виде множества индексов M_IÍM, содержащего номера компонент векторного показателя J, значения которых не должны ухудшаться по отношению к текущей ситуации J(q). Выбор направления спуска осуществляется методом, аналогичным методу возможных направлений Зойтендейка [110], используемому при оптимизации скалярных целевых функций и приводящему к задаче линейного или квадратичного программирования. Алгоритмы, приведенные в упомянутых работах, различаются видом условий нормировки искомого направления спуска, способом формирования множества S_a индексов активных ограничений, а также способом учета активных ограничений. В то время как метод Джоффриона описывает «динамику» изменения показателей по отношению лишь к опорному показателю, методы векторной релаксации позволяют учитывать взаимные изменения уже всех показателей, но в количественном отношении более грубо – с точностью до требования уменьшения или безразличия к величине показателя на основе формирования множества M_I.

Формирование точной информации о взаимных локальных изменениях показателей, как это делается, например, в методе Джоффриона при вычислении вектора коэффициентов замещения, предъявляет высокие квалификационные требования к проектировщику. Это естественно повышает трудоемкость решения задачи многокритериальной оптимизации. Для преодоления этого недостатка в ряде работ предлагается диалоговая процедура с лингвистическим моделированием предпочтений. Основная идея этого подхода заключается в том, что проектировщик производит оценку Парето-оптимальных решений, а также оценку необходимых изменений коэффициентов замещения в терминах лингвистической переменной [21].

Интенсивно развивается адаптивный подход к многокритериальным задачам, идейные истоки которого заключены в работах Я.З. Цыпкина. Согласно этому подходу [17, 115] решение задачи многокритериальной оптимизации интерпретируется, как процесс последовательного раскрытия неопределенности специального вида, а именно неопределенности формы компромисса. Адаптивным процедурам присущи все особенности методики случайного поиска [219]. Положительные стороны связаны с тем, что эти методы имеют простую реализацию, не требуют от векторного показателя практически никаких свойств, надежны и иногда оказываются более устойчивыми, чем градиентные методы. Однако процедуры случайного поиска имеют и недостатки, связанные с ограниченностью информации о свойствах компонент векторного показателя. Поэтому они оказываются в целом менее эффективными в тех случаях, когда градиентные процедуры применимы.

5. Процедуры, использующие понятия конуса доминирования и оптимальности по конусу[47, 48, 230, 312, 332, 428, 430] , обобщающие понятие оптимальности по Парето. В [428] поиск W-оптимального решения сводится к решению задачи математического программирования специального вида. При этом оставались открытыми вопросы обоснованного выбора вектора ограничений, вычисления конуса доминирования W.

В [312] предлагается алгоритм построения конуса доминирования, как функции интервалов неопределенности весовых коэффициентов l_i компонент векторного показателя в свертке (3.11). Но указанный алгоритм применим лишь для случая, когда размерность критериального пространства . Таким образом, в существующем виде процедуры W-оптимизации оказываются мало пригодны и с практической точки зрения.

В [312, 428] установлено, что вид конуса доминирования W определяет на множестве Парето J_П(Q) подмножество J_W(Q) Ì J_П(Q) и, следовательно, W-оптимизация может улучшить неопределенность решения на множестве Парето.

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

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

6. Как было отмечено ранее, задача векторной оптимизации является одной из частных задач теории кооперативных игр. Некоторые вопросы исследования задачи управления ММС как кооперативной игры в форме характеристической функции будут рассмотрены в главе 5. В обзорах [28, 248] предлагается краткий неполный перечень работ в направлении кооперативных игр.

Так, в обзоре [248] и в работе [32] в числе других рассматриваются вопросы применения арбитражных схем и среднеквадратичных решений в кооперативной игре. Геометрические свойства и структура Парето-области исследуются в работе [281]. Получение решения кооперативной игры в форме характеристической функции как С-ядра рассматривается в работах [35, 170]. Принципиальные вопросы вступления в коалицию-кооперацию с объединением целей и ресурсов и обеспечением определенной устойчивости коалиций-коопераций рассмотрены в фундаментальных работах
[84, 85, 137], а также в работах [170, 405]. Различные вопросы исследования кооперативных игр рассматриваются в работах [39, 85, 139, 199, 231, 303, 318, 345, 354, 431]. В [139] для ЛКДИ Парето-решения получены на основе принципа максимума, в [303, 318] Парето-решения применяются в мультиобъектном программировании в задаче распределения накоплений и при получении «безопасных» решений в конфликтной ситуации.

3.2.2. Понятие конуса доминирования W. Необходимые условия Парето- и W-оптимизации

Определение 3.14 [47, 428]. Если каждой точке поставить в соответствие множество D(z) доминирующих факторов, такое что для ÎJ(Q) ( ¹ z) и ( – z)ÎD(z)  доминирует решение z, то D(z) может быть рассмотрено в виде выпуклого, острого, многогранного конуса W(z), полярного к конусу B, где

                             B = {zÎE^m | , a_i³0, }                       (3.13)

и где множество { } называется множеством экстремальных векторов конуса B.

Определение 3.15 [428, 477]. Точка z^*ÎJ(Q) называется W-оптималь-ной (оптимальной по конусу W), если не существует zÎ J (Q), z¹ z^*, такого что (z – z^*)ÎW.

Для полной физической картины полезно привести следующие утверждения из [428] и [312] соответственно.

Утверждение 3.3 [428]. Если W₁Ì W₂, то

                                               ,

где  означает множество всех W_i-оптимальных точек в J (Q).

Утверждение 3.4. [312] Пусть W-многогранный конус, определенный матрицей B,

                                             W = {zÎE^m | Bz£ O_P}.

Пусть H(q)ÎE^P и H(q) = BJ(q).

Тогда эффективные (оптимальные по Парето) решения для векторного показателя H(q) точно совпадают с W-оптимальными решениями для векторного показателя J(q) на множестве Q:

                                                      ,                                                 (3.14)

т.е. конус определяет часть множества Парето-решений.

Следствие 3.1. Из утверждения 3.4 следует, что

                                              при B = E,                                       (3.15)

т.е. «прямоугольный» конус доминирования определяет все множество Парето-решений.

Из определения 3.15 следует слабая оптимальность по конусу.

Определение 3.16 [213]. Решение J^* = J(q^*) называется слабо оптимальным по конусу W с матрицей B= [p´m] в критериальном пространстве E^m векторного показателя J, если не существует такого qÎQ, для которого справедлива система неравенств

                                              B(J(q) – J(q^*)) < O _P.                                        (3.16)

Из (3.15) и утверждения 3.4 следует, что слабая оптимальность по конусу W эквивалентна слабой оптимальности по Парето [206] в критериальном пространстве E^P показателя H = BJ.

На основе подхода Куна–Таккера–Мукая [363] и с учетом известной теоремы Да Канхи–Поллака–Джоффриона [206] в [213, 230] сформулированы необходимые условия слабой оптимальности по конусу.

Утверждение 3.5. Пусть q^* – оптимальное решение по конусу доминирования W относительно целевого вектора Jи множества Q, заданного в виде

                                             Q = {qÎE^r | G(q) £ 0},

где G(q) = {g_i(q)£0, ; Cq£ b, C = [s_c, r], b = (s_c´1), q_L £ q£ q_H }.

Функционал  дифференцируем по Фреше в точке q^*, где s – множество индексов ограничений G, активных в точке q^*.

Тогда является совместной система уравнений

                                    (3.17)

Следствие 3.2. Так как множество слабо оптимальных по конусу решений содержит в себе множество оптимальных по конусу решений, то условие (3.17) является также необходимым условием оптимальности по конусу.

Следствие 3.3. Как следует из (3.14), (3.15), при B = E условие (3.17) превращается в необходимое условие Парето-оптимальности q^*.

3.2.3. Об алгоритмах вычисления конусов доминирования

В [47, 213, 230] сформировано несколько вариантов вычисления конусов доминирования в рамках задач векторной оптимизации, в которых учитываются:

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

· равномерное улучшение компонент векторного показателя;

· неопределенность весовых коэффициентов компонент векторного показателя.

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

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

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

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

Данный алгоритм является обобщением известного алгоритма Джоффриона [97], общий смысл которого рассмотрен в 3.2.1 и имеет следующую структуру:

Шаг 1. Формирование множества K = {1 £ k₁ £ k₂£...£ k_p £ m} индексов компонент векторного показателя, изменение величин которых намечено контролировать.

Шаг 2. Построение прямоугольной матрицы A размером [p´m] с элементами a_ij вида:

                                                                  (3.18)

где  – максимально допустимое ухудшение показателя , соответствующее улучшению показателя  на (если значения других показателей при этом не изменяются). На величины , , k_iÎK, jÎM, наложены ограничения, обусловленные постановкой задачи (3.7) в виде задачи минимизации:

                                             0 £ < ¥, < 0.

Шаг 3. Построение конуса доминирования в виде

                                             W = {zÎE^m | Bz£ O_P},                                                             (3.19)

где B = A. То есть конус , где W_A – конус, натянутый на систему векторов

                                         {aⁱ = [a_i1,...,a_im]^T, },                                   (3.20)

составленных из строк матрицы A вида (3.18).

Сформулируем следующее

Утверждение 3.6 [213]. Пусть задана система предпочтений в форме матрицы A вида (3.18). Тогда:

1) конус доминирования W вида (3.19) является выпуклым, острым, многогранным;

2) для любых ;  вектор dÎW, координаты d_l,  которого вычисляются в виде

                                                                              (3.21)

удовлетворяет условию

                                                         .                                                   (3.22)

Замечание 3.1. Геометрический смысл утверждения 3.6 состоит в том, что вектор d, определяемый в виде (3.21), для любых ; , характеризует направление, в котором улучшению  показателя  соответствует изменение  показателя . При этом, если другие показатели остаются неизменными, то ухудшение не может превысить величину a_ij , если только dÎW. То есть конус W, построенный по правилу (3.18), (3.19), удовлетворяет требованиям проектировщика о допустимых взаимных локальных изменениях показателей.

Замечание 3.2. Гиперплоскость П, касательная к поверхности равных значений неявной функции полезности в методе Джоффриона, является частным случаем конуса доминирования, построенного в соответствии с (3.18), (3.19). Касательной гиперплоскости с опорным показателем J_i соответствует матрица A = W^T, где компоненты W_j вектора W представляют собой коэффициенты замещения, вычисленные по алгоритму Джоффриона.

Замечание 3.3. В терминах конуса доминирования W, удовлетворяющего соотношениям (3.18), (3.19), можно интерпретировать информацию о предпочтениях проектировщика в методах векторной релаксации, обсуждавшихся в разделе 3.2.1 [213, 220, 230, 265, 363]. Если в (3.18) для всех iÎK, jÎM, j¹i положить a_ij = 0, то полученный конус доминирования реализует требование одновременного неухудшения компонент векторного показателя Jс номерами из множества K, сформированного на шаге 1 алгоритма. Значения компонент вектора J с номерами из множества (M\K) при этом контролироваться не будут. Условие K = M означает требование одновременного неухудшения всех компонент вектора J. В этом случае конус доминирования W превращается в неположительный ортант  критериального пространства E^m, что означает [213, 312, 428] совпадение понятий W-оптимальности и Парето-оптимальности.

Таким образом, вычисление конуса доминирования в виде (3.18), (3.19) дает возможность количественно учитывать более содержательную информацию о предпочтениях проектировщика по сравнению c методами Джоффриона и векторной релаксации при решении задач (3.7).

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

Третий вариант возникает, если появляется сложность точного назначения вектора весовых коэффициентов lÎL, где L задана в форме (3.10) при свертке векторного показателя, но имеется интервальная информация:

                                                                            (3.23)

где l_L = [l_L1,...,l_Lm]^T, l_H = [l_H1,...,l_Hm]^T.

Информацию вида (3.23) о векторе l можно интерпретировать при  в виде конуса доминирования, где B = B(l_L, l_H).

В работе [213] формируется машинно-ориентированный алгоритм вычисления матрицы B конуса доминирования W, позволяющий решать задачу для любого m.

Очевидно, что практически важным частным случаем (3.23) является формирование матрицы B как пересечения наборов l, удовлетворяющих ограничениям (3.23) и имеющим вид

                                            .                                   (3.23а).

3.2.4. Алгоритмическое обеспечение задачи оптимизации
по конусу (W-оптимизация)

Предполагается, что конус доминирования W задан в виде (3.19) и фиксирован. Для простоты обозначений будем предполагать, что компоненты показателя потерь J и компоненты вектора параметров qобразуют единые коалиции интересов и действия соответственно. Поэтому задачу (3.7) можно записать в виде (J – вектор потерь):

                                   определить ,                             (3.24)

где J(q)ÎE^m, qÎE^r, R = { }. Область Q определяется, например, как

                                    Q = {qÎE^r | q_L£ q£ q_H, Cq£ b},                              (3.25)

                                               C = [s´r], b = [s´1].

Для формирования алгоритма поиска W-оптимального решения в задаче (3.24) в [213] видоизменяется известный алгоритм векторной релаксации [265] с учетом конуса доминирования (3.19). Вычислительная процедура представляется в виде последовательности следующих этапов [213].

Выбор направления спуска внутри конуса доминирования. Как следует из [213, 312, 428], условие доминирования решения  над решением  относительно конуса W с матрицей B записывается в виде

                                                        BDJ £ O,                                                  (3.26)

где D J =  – .

Использование соотношения (3.26) в качестве условия спуска в алгоритме векторной релаксации позволяет сформулировать задачу выбора направления спуска внутри конуса доминирования в виде:

                                      (3.27)

где (3.27б) – условие dÎW; (3.27в) – условие того, что вектор d направлен вовнутрь области допустимых значений параметров Q вида (3.25);
A_a = [s_a´r] – матрица линейных ограничений (как общего вида, так и тривиальных), активных в точке q; ||×||_K – условие нормировки.

Постановка задачи выбора направления вида (3.27) является более общей по сравнению с постановками [265, 363], которые могут быть получены из (3.27) как ее частные случаи. Для этого матрицу B конуса доминирования W необходимо задать с помощью первого алгоритма в виде функции коэффициентов замещения.

Для получения условий останова при решении задачи (3.27) сформулировано утверждение:

Утверждение 3.7 [213]. Пусть в точке q выполнены условия регулярности [220]: существует такая точка q^*ÎE^r, что справедлива система неравенств A_aq^*>O (матрица A_a определена в (3.27)). Тогда:

· точка q удовлетворяет необходимым условиям слабой оптимальности по конусу W тогда и только тогда, когда оптимальное значение целевой функции zв задаче (3.27) равно 0;

· если z> 0, то решение d задачи (3.27) принадлежит конусу доминирования W_Q, построенному в пространстве параметров E^r.

Необходимо отметить, что решение задачи (3.27) зависит от условий нормировки (3.27г). В вычислительной практике, как правило, используются [18, 110] следующие виды нормировки:

при K = ¥                                  |d_i|£1, ,                                            (3.28а)

при K = 2                                        d^Td£ 1.                                                 (3.28б)

В результате получаем задачу линейного программирования вида:

                        (3.29)

где G – вспомогательный вектор, с помощью которого осуществляется переход от переменной d к неотрицательной вспомогательной переменной , необходимой для решения задачи (3.27):

                                                       .                                                 (3.30)

Для решения задачи (3.29) используется симплекс-метод.

Более точное решение задачи (3.27), улучшающее сходимость алгоритма W-опти­ми­за­ции в целом, можно получить, учитывая условия нормировки вида (3.28б). Однако это условие превращает задачу (3.27) в нелинейную и требует иных подходов к ее решению. В работе [47] задача W-оптимизации в нелинейном варианте решается на основе объединения и обобщения результатов [8, 110, 363]. В итоге от задачи (3.27) переходим к линейной задаче дополнительности относительно переменных u, v:

                                                                                        (3.31)

где

                                                       ;                                                               

                                                 ;

                                             .

Решение задачи (3.31) осуществляется с помощью алгоритма дополнительного ведущего преобразования Лемке [8], после чего легко вычисляется вектор d. Как доказывается в [8], алгоритм Лемке сходится к решению задачи (3.31) за конечное число шагов, если матрица H является сильно коположительной. Матрица H в (31) является сильно коположительной. Действительно, во-первых, H – симметричная матрица и, следовательно, коположительная. Во-вторых, . Поэтому из равенства z^THz = 0 следует, что (H + H^T)z = 0.

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

Вычисление шаговой длины в выбранном направлении. Вычисление шаговой длины  в выбранном направлении  на k-й итерации принципиально может производиться с помощью алгоритмов, аналогичных алгоритмам одномерной минимизации, используемым в задачах условной оптимизации скалярных целых функций. Анализ алгоритмов одномерной оптимизации можно найти в [186]. Учет свойства многокритериальности и использование понятие W-оптимальности требуют модификации существующих алгоритмов, так как при этом изменяется вид условия спуска [312, 428]. Рассмотрим алгоритмы вычисления шаговой длины следующих двух типов.

1. Выбор , явно обеспечивающего условие спуска. В задаче
W-оптимизации условие спуска формируется в виде

                                                         DJ^(k)ÎW,                                                   (3.32)

где DJ^(k) = J^{(k +1)} – J^(k); J^{(k +1)} = J(q^(k)+ ^(k)d^(k)); J^(k) = J(q^(k)).

В том случае, когда W – многогранный конус вида (3.19), условие (3.32) представляет собой систему неравенств вида (3.26).

2. Вычисление  по конечным формулам, использующим значения векторного показателя J(q^(k)), а также его производной , вычисляемых на предыдущих итерациях для целевого выбора направления  в задаче (3.27) (так как специально для выбора  это делать нерационально). В соответствии с [312, 428] условие спуска (3.26) означает одновременное уменьшение всех компонент векторного показателя H = BJ. Тогда спуск вдоль выбранного направления d^(k) целесообразно проводить до ближайшего минимума одной из компонент векторного показателя H или до выхода на границу области допустимых значений параметров Q. При решении этой задачи могут быть использованы обычные методы одномерной минимизации (метод Фибоначчи, золотого сечения, параболической интерполяции и др.) [8, 186]. Метод параболической интерполяции обобщается на случай задачи W-оптимизации следующим образом. Легко показать, что вектор  экстремумов интерполирующих парабол вычисляется по формуле

                            ,                      (3.33)

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

Шаговая длина  вычисляется в виде

                                   ,                             (3.34)

где  – расстояние от точки  до границы допустимой области Q в направлении . Необходимо отметить, что другие методы одномерной оптимизации обобщаются на задачу W-оптимизации аналогично.

Таким образом, процедуру поиска оптимального решения в [213] предлагается рассматривать в виде последовательности следующих основных этапов, составляющих в совокупности одну диалоговую итерацию:

· формирование конуса доминирования;

· выбор направления спуска внутри конуса доминирования;

· вычисление шаговой длины в выбранном направлении.

Некоторые виды комплексирования систем управления при решении технических задач приводят к появлению разрывности компонент векторного показателя исследуемой системы. Это обстоятельство требует модификации построенной выше процедуры W-оптимизации с учетом указанного свойства. При этом используется подход к решению задач оптимизации разрывных показателей, изложенный в [16].

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

3.2.5. Выбор начального приближения в задаче многокритериальной оптимизации (постановка (3.8))

Как известно, для векторного показателя J(q) общего вида, когда некоторые его компоненты, вообще говоря, являются невыпуклыми на Q функциями, на множество достижимых векторных оценок J(Q) могут существовать локально эффективные точки, не принадлежащие глобальному множеству Парето J_П(Q). В этих точках также выполняются необходимые условия W-оптимальности (17). Поэтому неудачное расположение начального приближения в задаче (7) может привести к неправильному результату вследствие преждевременного останова алгоритма W-оптимизации в локально эффективной внутренней точке множества J(Q).

С другой стороны, при решении задачи Нэш-оптимизации (глава 2) в случае неединственности равновесия по Нэшу необходимо на множестве равновесных решений определить недоминируемые точки, т.е. ближайшие к множеству Парето [32]. В этом случае начальное приближение целесообразно назначать в окрестности множеств Парето, что повышает возможность определения недоминируемого равновесного решения.

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

Постановку задачи выбора начального приближения на основе (3.8) предлагается формализовать в виде [48, 213]:

                                  определить ,                            (3.35)

где Q(i) = {qÎE^r | qⁱÎQ_i; = const}.

То есть необходимо определить множество  значений показателя , являющееся дискретной аппроксимацией множества W_i-оптималь­ных решений (в частном случае – множества Парето). При этом аналогичное множество определяется в пространстве параметров: . Если положить , то получим , Q(i) = Q. Для конуса доминирования при этом полагаем . Тогда задача (3.35) будет интерпретироваться, как построение дискретной аппроксимации множества Парето относительно векторного показателя JÎE^m и вектора параметров qÎQÌE^r.

Если положить i = M_K\j, то можно оценивать конфликтное взаимодействие коалиции K_j и контркоалиции K_i.

В данном разделе для решения задачи (3.35) предлагается использовать известный метод зондирования пространства параметров, основанный на методике ЛП-поиска [238]. В этом методе условно можно выделить два основных этапа:

1) составления таблицы испытаний;

2) оптимизация таблицы испытаний.

Для определенности полагаем, что  составляет все множество .

Этап 1. Генерируется последовательность точек {p⁽ⁱ⁾}, равномерно распределенная в r-мерном единичном кубе. Как обосновывается в [238], наилучшими характеристиками равномерности обладают так называемые ЛП_t-последовательности. Для генерации ЛП_t-последовательности в [238] предлагается арифметический алгоритм, использующий специальную таблицу направляющих чисел. После этого с помощью линейного преобразования L, сохраняющего равномерность распределения, преобразуем множество сгенерированных точек {p⁽ⁱ⁾, }ÎП_p в множество точек {q⁽ⁱ⁾, }, равномерно заполняющих r-мерный параллелепипед П_q, определяемый верхними и нижними ограничениями на параметры задачи q_L и q_H:

                                                       П_q = L(П_p).                                                 (3.36)

Преобразование L задается [238] в виде

                                       .                                 (3.37)

Так как в описании области Q используются линейные ограничения общего вида, то в каждой точке q⁽ⁱ⁾ необходимо проверять выполнение системы неравенств Cq⁽ⁱ⁾ £ b. Если q⁽ⁱ⁾ является допустимой, то в ней вычисляется значение векторного показателя J(q⁽ⁱ⁾) и заносится в таблицу испытаний.

Этап 2. Предлагается алгоритм оптимизации таблицы испытаний по конусу доминирования W, заданному в виде (19). Для этого из таблицы испытаний выбирается какая-либо точка q⁽ⁱ⁾ и помечается. Просматривая все точки q^(j) таблицы испытаний, отличные от q⁽ⁱ⁾, исключим те из них, для которых

                                             B(J(q^(j)) – J(q⁽ⁱ⁾)) ³ O,                                           (3.38)

причем хотя бы одно из неравенств строгое. То есть проверяется принадлежность точек D_ij конусу (– W); D_ij = J(q^(j)) – J(q⁽ⁱ⁾).

Затем среди оставшихся точек выбирается непомеченная, и вновь повторяется процесс исключения по правилу (3.38). После конечного числа шагов останутся только такие помеченные точки, которые являются дискретной аппроксимацией множества W-оптимальных решений.

Второй этап данного алгоритма [213] отличается от [238] более общей постановкой, основанной на использовании понятия конуса доминирования. В случае B = E оптимизация таблицы испытаний приведет к построению дискретной аппроксимации всего множества Парето, что соответствует максимальной неопределенности весовых коэффициентов O£ l £ 1. В случае B ¹ E, когда O£ l_L £ l £ l_H £ 1, W-оптимизация позволяет построить подмножество  и на этапе экспертного анализа работать с сокращенной таблицей, в которую не будут входить заведомо неприемлемые варианты. Время оптимизации таблицы испытаний уменьшается с сокращением интервалов неопределенности весовых коэффициентов.

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

3.3. Алгоритмы определения векторного равновесия
(стабильные решения)

В соответствии с понятиями коалиционного равновесия, изложенными в разделе 3.1, формулировка вида коалиционного равновесия определяется тремя степенями свободы:

· множество коалиционных разбиений P;

· вид V-решения;

· степенью «охвата» Парето-области коалиции.

На основе определения 3.9 векторное равновесие по Нэшу является частным случаем коалиционного равновесия при единственном коалиционном разбиении, отсутствии угроз (частный случай V-решений) и принадлежности к полной Парето-области коалиции.

В соответствии определением 3.11 W-равновесие является частным случаем векторного равновесия по Нэшу, так как формулируется на части Парето-области коалиции. С другой стороны, при применении единой технологии решения обеих задач, например, на основе конусов доминирования, необходимые условия и алгоритмы определения близки. Поэтому имеет смысл объединить оба определения (3.9), (3.11) в рамках единой схемы поиска векторного равновесия.

3.3.1. Необходимые условия векторного равновесия
(Нэш-равновесия и W-равновесия)

Раскрывая необходимое условие W-оптимальности (3.17), можно получить

                                 ,                            (3.39)

где m, v³0, m ¹ 0; G_a – переобозначение активных ограничений.

Как известно, при B = E данное условие дает необходимое условие Парето-опти­маль­ности.

Формирование постановки (3.7) для каждого iÎM_K и совместных необходимых условий (3.39) для всех i приводит к следующему утверждению:

Утверждение 3.8 [47]. Пусть q^r – векторное равновесное решение. Тогда является совместной система равенств

                                                (3.40)