ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 12, с. 1998-2013
УДК 519.626
МНОГОКРИТЕРИАЛЬНОЕ РАВНОВЕСНОЕ ПРОГРАММИРОВАНИЕ: ЭКСТРАПРОКСИМАЛЬНЫЕ МЕТОДЫ1}
© 2007 г. А. С. Антипин
(119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: antipin@ccas.ru, http:ll www.ccas.ru/antipin Поступила в редакцию 10.05.2007 г.
Задача многокритериальной равновесной оптимизации представляет собой эффективный инструмент математического моделирования ситуаций, связанных с исследованием операций, задачами автоматизации проектирования, регулирования и управления и многими другими проблемами. В данной статье дается формальная постановка задачи многокритериального равновесного программирования, рассматривается подход к ее решению. Библ. 22.
Ключевые слова: многокритериальная оптимизация, парето-оптимальность, равновесные решения, функция чувствительности, экстрапроксимальный метод.
1. ПОСТАНОВКА ОБЩЕЙ ЗАДАЧИ
Все задачи оптимизации описывают какой-нибудь выбор: от простейшего выбора элемента из множества альтернатив до сложного группового выбора, когда каждый из участников не зависимо друг от друга делает свой выбор на своем множестве альтернатив, но потом возникает необходимость убедиться, что групповой выбор удовлетворяет некоторым балансам или другим законам, которым подчинена группа участников как единое целое. Каждый из участников в своем выборе следует принципу рациональности (стремится максимизировать свои интересы или выгоду). Формально, интересы - это целевые функции участников, следовательно, ситуация описывается системой задач оптимизации. Решения этих систем обладают качественно новой характеристикой согласовывать частично противоречивые интересы участников ситуации, а сама система может рассматриваться как математическая модель конфликта. Систему задач оптимизации всегда можно скаляризовать и ввести экстремальное отображение (одно или несколько), неподвижная точка которого и есть решение системы задач оптимизации. Задачу вычисления неподвижной точки экстремального отображения естественно рассматривать как обобщение задачи выпуклого программирования и не менее естественно называть ее задачей равновесного программирования. При переходе от выпуклого программирования к равновесному меняется парадигма решения: вместо оптимума мы имеем дело с равновесной или неподвижной точкой.
Одно из главных достоинств равновесных моделей состоит в том, что участник ситуации не размазывается по модели, его интересы не прячутся внутри малосодержательных преобразований, а всегда явно представлены в виде целевой функции на каждом этапе работы с моделью. Это обстоятельство выгодно отличает модели равновесного программирования от теории моделей вариационных неравенств, где предпочтения каждого участника не представлены в явном виде.
Второе обстоятельство, связанное с равновесными моделями, состоит в том, что невязка этой модели порождает векторное поле, неподвижная точка которого и есть решение нашей модели. Сразу же возникает вопрос об устойчивости (точнее - асимптотической устойчивости) решения этой модели. Последнее означает, что если решение в силу различных возмущений отклонилось от своего состояния, то необходимо выяснить, при каких условиях оно вернется в прежнее состояние. Для этого предполагается построить динамику этого возврата, т.е. построить динамические или итеративные процессы, траектории которых сходятся к решению исходной задачи. Область сходимости этих траекторий является областью устойчивости решения модели. Это чрезвычайно важная характеристика для практических приложений модели. В общем случае любая модель имеет две компоненты: статическую и динамическую; именно вторая компонента характеризует область устойчивости модели к различным возмущающим факторам. С другой сторо-
^ Работа выполнена при финансовой поддержке РФФИ (код проекта 05-01-00242) и по Программе поддержки ведущих научных школ (код проекта НШ-2240.2006.1).
1998
ны, динамическую компоненту часто называют (особенно в итеративном формате) методами решения задач и она часто развивается независимо от общей дифференциальной теории. Настоящая работа посвящена развитию методов экстрапроксимального типа для решения равновесных задач, которые можно рассматривать как естественное обобщение выпуклого программирования.
В [1], [2] была введена конструкция равновесного программирования (в смысле разработки методов ее решения). Затем были обоснованы идеи экстрапроксимального [3], экстраградиентного [4], ньютоновского подходов [5] и метода регуляризации [6] для решения этих задач. Показано, что теория игр п лиц с равновесием по Нэшу вложена в эти равновесные конструкции (см. [7],[8]). Для подкласса выпуклых игр (аналог задач выпуклого программирования) доказана сходимость перечисленных выше методов. Отметим, что теоремы существования решений этих задач были установлены существенно ранее в работах [9], [10] и др. Идеи перечисленных методов пришли из оптимизации, и поэтому они параллельно развивались и продолжают развиваться в теории вариационных неравенств (см. [11], [12]).
В настоящей работе продолжается исследование конструкции равновесного программирования применительно к многокритериальной ситуации. Основное отличие этой ситуации от рассмотренной ранее состоит в том, что теперь вместо задачи о вычислении неподвижной точки экстремального отображения рассматривается аналогичная задача относительно седлового отображения. В этой задаче требуется выбрать вектор весов X = X* и вектор-столбец правой части функциональных ограничений р = р* так, чтобы отвечающий им оптимум ц> = w* удовлетво-
рял системе вариационных неравенств
*, f(w*)>e Min{<X*, f(w)>|g(w)<p*, w e П}, (1)
<f(w*) - X*,X - X*>< 0, X> 0, (2)
<g(w *) - p*, p - p*>< 0, p > 0. (3)
Здесь f (w), g(w) - векторные функции, каждая компонента которых - выпуклая скалярная функция, f(w) е Rm, g(w) е R"1, w е Q с Г, К е R", p е R+"1.
Задачу (1) при фиксированном векторе p > 0 можно трактовать как скаляризацию (скалярную линейную свертку) задачи многокритериальной оптимизации, где требуется определить паре-товское многообразие решений векторного критерия f(w) на допустимом множестве D(p) = {w е
е R"|g(w) <p, w е Q}, другими словами, - решить задачу
f(w*) е ParetoMin{f(w)|w е D(p)}. (4)
Каждая точка паретовского многообразия f (w* ) характеризуется тем, что пересечение неположительного конуса (ортанта) K(f (w* )) с вершиной в точкеf (w* ) и множества векторных оценок f (D(p)) содержит единственную точку f (w* ). В этом случае f (w* ) называется оптимальной по Парето или эффективной точкой (см. [13]). Эта же мысль в [14] представлена в следующей форме: точка f (w* ) называется оптимальной по Парето, если не существует вектора vp е D(p) такого, что
f (v p )< f( w*), i = 1, 2, m, f( Vp) ф f( w*), (5)
т.е. неположительный конус K(f (w* )), из которого выброшена вершина, пуст. Вектор f (w* ) в этом случае называют также недоминируемым на множестве векторных оценок.
Будем предполагать, что решение задачи (1)-(3) существует, тогда точка w* , которая является прообразом Парето-оптимальной точки f (w* ), принадлежит не пустому допустимому множеству задачи выпуклого программирования (напоминаем: при любом фиксированномp > 0). Таким образом, если векторы К = К' > 0 и p = p' > 0 зафиксированы, то мы имеем классическую задачу выпуклого программирования, которая порождает множество эффективных решений f(w') е R+" и
множество множителей Лагранжа Y' е R+1, причем если вектор К',p вложен в свой образ f (w'), Y', то такая пара К' = К*, p = p* является решением исходной задачи (1)-(3). Фактически мы имеем точечно-множественное отображение седлового типа, когда каждой паре К', p ставится в соот-
ветствие седловое множество. Неподвижная точка этого многозначного седлового отображения и есть решение задачи (1)-(3).
Заметим, что задача (1)-(3) допускает естественное и очень важное обобщение:
< ^(А*), / (w * )>е Мш{< ^ (А *), / (w )>| g (w )< р *), w еА|,
</(w*)-^(А*),А-А*>< 0, А> 0, (6)
^^ * ) - ^(р*), р - р*>< 0, р > 0,
на случай, когда отображения ^\(А) и ^2(р) - монотонные операторы.
Конструкция (1)—(3) включает два важных случая, каждый из которых представляет самостоятельную задачу и, следовательно, самостоятельную математическую модель для описания, вообще говоря, различных ситуаций. Сначала рассмотрим оба случая по отдельности, а затем в их единстве.
2. РАВНОВЕСНЫЙ ВЫБОР ВЕСОВ В ЗАДАЧАХ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
В этом разделе будем предполагать, что вектор р > 0 фиксирован и тем самым допустимое множество задачи (1) жестко задано. Задача (1)—(3) в этом случае принимает форму
<А *, / (w * )> е Мт{ <А *, / (w )>| g (w )< р, w ей},
(7)
</(w*) - А*,А - А*>< 0, А> 0. (8)
Допустимое множество В = {w|g(w) <р, w е й} задачи (7) будем называть множеством альтернатив, а его образ/е /(В) = {/=/У), w е В} при отображении/V), w е В, как уже сказано выше, — множеством векторных оценок. Расположение множества /(В) в пространстве векторных оценок по отношению к нулевой точке сильно зависит от вектора /, который обычно называют "абсолютным минимумом", или "идеальной точкой": /г = / (^) = тт{/ е В}, г = 1, 2, ..., т. Если векторы г различны, то не существует такой точки w, образ которой/мог бы достичь
абсолютного минимума /. Интуиция нам подсказывает, что если / > 0, то все компоненты вектора А* в (7) не равны нулю, т.е. А* Ф 0, и наоборот: если / < 0, то все компоненты этого вектора
равны нулю. При наличии смеси тех и других компонент у вектора / имеем случай, когда какие-то Аг, г = 1, 2, ..., т, равны нулю, другие — нет. Чтобы исключить вырожденный случай, введем условие регулярности, которое в каком-то смысле аналогично условию регулярности Слейтера в выпуклом программировании.
Условие регулярности. Задачу (7), (8) назовем регулярной, если среди всех / (х), г = 1, 2, ..., т, существует по крайней мере одна функция / (w) такая, что
/г (w )> 0 Vw ей.
(9)
По умолчанию всегда можно полагать, что индекс такой функции г = 1.
Задача (7) представляет собой многокритериальную задачу минимизации вект
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.