Парето — 07 — Список вопросов

Многокритериальная задача (основные объекты и постановка)

Многокритериальная задача является прямым обобщением обычной экстремальной задачи и включает следующие два объекта:

$X$ — непустое множество, содержащее по крайней мере два элемента. Это множество называют множеством возможных (допустимых) вариантов (решений, альтернатив) .
$f(\cdot) = \paren{ f_1(\cdot), \dots, f_m(\cdot) }$ — числовую векторную функцию, заданную на множестве $X$ и именуемую векторным критерием.

Будем считать, что возможные решения являются векторами арифметического $n$-мерного пространства: \[ X \subset \R^n, \] причём в общем случае множество $X$ не совпадает со всем пространством $\R^n$.

Векторная функция $y = f(x)$ принимает значения в арифметическом векторном пространстве $\R^m$, которое называют критериальным пространством.

Введём образ множества $X$ при отображении $f$: \[ Y = f(X) = \set{ y \in \R^m: y = f(x) \quad \text{при некотором} \quad x \in X }. \] Множество $Y$ будем называть множеством возможных векторов.

Определение: основные бинарные отношения. Свойства бинарных отношений

На критериальном пространстве $\R^m$ вводятся следующие бинарные отношения: \[ \begin{aligned} a \geqq b &\iff & a_i &\geqslant b_i, & i &= 1, \dots, m \\ a \gt b &\iff & a_i &\gt b_i, & i &= 1, \dots, m, \\ a \geq b &\iff & a &\geqq b \quad \text{и} \quad a \neq b, \\ a \eqslantgtr b &\iff & b &\not\geq a. \end{aligned} \]

Отношение $\geq$ называют отношением Парето.

Взаимосвязь введённых отношений можно выразить следующим образом: \[ \gt \implies \geq \implies \geqq \implies \eqslantgtr. \]

Оптимальность по Парето

(оптимальность по Парето, в негативной форме).
Точка $x^* \in X$ называется оптимальной по Парето (парето-оптимальной или эффективной), если не существует такой точки $x \in X$, для которой выполнено неравенство \[ f(x) \geq f(x^*). \] При этом вектор $f(x^*)$ называют оптимальным по Парето или эффективным.

(оптимальность по Парето, в позитивной форме).
Точка $x^* \in X$ называется оптимальной по Парето (парето-оптимальной или эффективной), если для любой точки $x \in X$ выполнено соотношение \[ f(x^*) \eqslantgtr f(x). \]

Также вводятся обозначения для множества всех эффективных точек \[ P_f(X) = \set{ x^* \in X: \text{ не существует } x \in X \text{ такого, что } f(x) \geq f(x^*) } \] и для множества всех эффективных векторов: \[ P(Y) = f(P_f(X)) = \set{ y^* \in Y: \text{ не существует } y \in Y \text{ такого, что } y \geq y^* }. \]

Оптимальность по Слейтеру

(оптимальность по Слейтеру, в негативной форме).
Точка $x^* \in X$ называется оптимальной по Слейтеру (слабо эффективной), если не существует такой точки $x \in X$, для которой выполнено неравенство \[ f(x) \gt f(x^*). \] При этом вектор $f(x^*)$ называют оптимальным по Слейтеру или слабо эффективным.

(оптимальность по Слейтеру, в позитивной форме).
Точка $x^* \in X$ называется оптимальной по Слейтеру (слабо эффективной), если для любой точки $x \in X$ существует такой номер $i \in I$, что \[ f_i(x^*) \geqslant f_i(x). \]

Также вводятся обозначения для множества всех слабо эффективных точек \[ S_f(X) = \set{ x^* \in X: \text{ не существует } x \in X \text{ такого, что } f(x) \gt f(x^*) } \] и для множества всех слабо эффективных векторов: \[ S(Y) = f(S_f(X)) = \set{ y^* \in Y: \text{ не существует } y \in Y \text{ такого, что } y \gt y^* }. \]

Имеют место включения: \[ P_f(X) \subset S_f(X), \qquad P(Y) \subset S(Y). \]

Оптимальность по Джеоффриону

(оптимальность по Джеоффриону).
Точка $x^* \in X$ называется оптимальной по Джеоффриону (собственно эффективной), если она эффективна и, кроме того, существует число $A \gt 0$ такое, что для всех номеров $i \in I$, всех $x \in X$, для которых выполнено неравенство \[ f_i(x) \gt f_i(x^*), \] и некоторого $j \in I$ такого, что \[ f_j(x) \lt f_j(x^*), \] выполняется неравенство \[ \frac{f_i(x) - f_i(x^*)}{f_j(x^*) - f_j(x)} \leqslant A. \]

Для обозначения множества всех собственно эффективных точек и векторов используют обозначения \[ G_f(X) \quad \text{и} \quad G(Y). \]

По определению собственной эффективности имеют место включения: \[ G_f(X) \subset P_f(X), \qquad G(Y) \subset P(Y). \]

Внутренняя и внешняя устойчивость множества Парето $P(Y)$

Множество Парето $P(Y)$ внутренне устойчиво в том смысле, что в нём не содержится ни одной такой пары векторов $y, y'$, которые были бы сравнимы по отношению $\geq$, то есть ни одно из соотношений \[ y \geq y', \qquad y' \geq y \] не имеет места. Это означает, что при переходе от одного эффективного вектора к другому происходит увеличение одной из компонент при уменьшении другой компоненты.

Множество Парето $P(Y)$ называют внешне устойчивым, если для любого $y \in Y \setminus P(Y)$ найдётся эффективный вектор $y^* \in P(Y)$ такой, что \[ y^* \geq y. \]

В случае конечного $Y$ множество эффективных векторов $P(Y)$ будет внешне устойчивым.

Определение: внешняя устойчивость множества Слейтера

Множество Слейтера $S(Y)$ называют внешне устойчивым, если для любого $y \in Y \setminus S(Y)$ найдётся слабо эффективный вектор $y^* \in S(Y)$ такой, что \[ y^* \gt y. \]

В случае конечного $Y$ множество слабо эффективных векторов $S(Y)$ будет внешне устойчивым.

Теорема Гермейера

(Гермейера).
Пусть $y^* \in Y$ и $y^* \gt \bvec{0}$. Вектор $y^*$ слабо эффективен тогда и только тогда, когда существует $\mu \in \bvec{M}$ такой, что \[ \min_{i \in I} \mu_i y_i^* \geqslant \min_{i \in I} \mu_i y_i \quad \text{для всех} \quad y \in Y. \]

Теорема 3.3 (Подиновского)

(Подиновского).
Вектор $y^* \in Y$ эффективен тогда и только тогда, когда для каждого $i \in I$ выполнено \[ y_i^* \geqslant y_i \qquad \forall y \in Y_i, \] где \[ Y_i = \set{ y \in Y: y_k \geqslant y_k^*, \quad k = 1, \dots, m, \quad k \neq i }. \]

Теорема 3.8 о геометрической характеризации собственно эффективных точек

Вектор $y^* \in Y$ собственно эффективен тогда и только тогда, когда найдётся $\varepsilon \in (0, 1/m)$, при котором выполнено равенство \[ Y \cap [ \Lambda_\varepsilon + y^* ] = \set{ y^* }, \] где \[ \Lambda_\varepsilon = \set{ z \in \R^m: \dp{\mu^i}{z} \geqslant 0, \quad i \in I }, \] а векторы $\mu^i$ имеют вид \[ \mu_j^i = \begin{cases} \varepsilon, & j \in I; \quad j \neq i, \\ 1 - (m - 1) \varepsilon, & j = i. \end{cases} \]

Теорема Моцкина

(Моцкина).
Пусть $a^i, b^j \in \R^n$, причём $i = \overline{1,m}$ и $j = \overline{1,k}$. Тогда имеет место один и только один из следующих случаев:

Однородная система линейных неравенств \[ \begin{aligned} \dp{a^i}{x} &\gt 0, & i &= \overline{1,m}, \\ \dp{b^j}{x} &\geqslant 0, & j &= \overline{1,k} \end{aligned} \] имеет решение $x \in \R^n$;
Однородная система линейных уравнений \[ \sum\limits_{i=1}^{m} \mu_i a^i + \sum\limits_{j=1}^{k} \lambda_j b^j = \bvec{0} \] имеет решение \[ \mu \geq \bvec{0}, \qquad \lambda \geqq \bvec{0}. \]

Теорема Таккера

(Таккера).
Пусть $a^i, b^j \in \R^n$, причём $i = \overline{1,m}$ и $j = \overline{1,k}$. Тогда имеет место один и только один из следующих случаев:

Однородная система линейных неравенств \[ \begin{aligned} \dp{a^i}{x} &\geqslant 0, & i &= \overline{1,m}, \\ \dp{b^j}{x} &\geqslant 0, & j &= \overline{1,k} \end{aligned} \] имеет решение $x \in \R^n$;
Однородная система линейных уравнений \[ \sum\limits_{i=1}^{m} \mu_i a^i + \sum\limits_{j=1}^{k} \lambda_j b^j = \bvec{0} \] имеет решение \[ \mu \gt \bvec{0}, \qquad \lambda \geqq \bvec{0}. \]

Теорема 3.10 Джеоффриона о характеризации собственно эффективных точек в терминах линейной свёртки критериев

(Джеоффриона).
Пусть множество $X \subset \R^n$ выпукло, а вектор-функция $f = (f_1, \dots, f_m)$ покомпонентно вогнута на нём. Точка $x^* \in X$ собственно эффективна тогда и только тогда, когда найдётся вектор $\mu \in \bvec{M}$, при котором имеет место равенство \[ \sum\limits_{i=1}^{m} \mu_i f_i(x^*) = \max_{x \in X} \sum\limits_{i=1}^{m} \mu_i f_i(x). \]

Определение: множество идеальных векторов

Множеством идеальных векторов называют множество \[ U = \set{ u \in \R^m: u_i \gt \sup_{x \in X} f_i(x), \quad i \in I }, \] предполагая, что все функции $f_i(x)$ являются ограниченными на множестве $X$.

Теорема 3.11 о характеризации собственно эффективных точек в терминах расстояния до идеальной точки

Пусть множество $X$ выпукло, а числовые функции $f_1, \dots, f_m$ ограничены сверху и покомпонентно вогнуты на нём. Точка $x^* \in X$ является собственно эффективной относительно $f$ тогда и только тогда, когда существует вектор $u \in U$, для которого имеет место неравенство \[ \norm{u - f(x^*)} = \min_{x \in X} \norm{u - f(x)}. \]

Определение: функция выбора

Пусть имеется непустое множество $\Omega$ объектов произвольной природы. Через $2^\Omega$ будем обозначать множество всех его подмножеств.

Однозначное отображение \[ C: A \to 2^\Omega, \] где $A = 2^\Omega \setminus \set{ \varnothing }$, называют функцией выбора, заданной на $A$, если для любого $Y \in A$ выполняется включение \[ C(Y) \subset Y. \]

Функция выбора каждому предъявляемому множеству $Y \in A$ сопоставляет определённое его подмножество $C(Y)$, которое обычно интерпретируют как множество выбираемых элементов. В частном случае, когда $C(Y) = \varnothing$, говорят об отказе от выбора.

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

Аксиомы выбора

(наследования).
Пусть $C$ — функция выбора, заданная на семействе подмножеств $A$. Для любых двух множеств $Y_1, Y_2 \in A$ таких, что $Y_1 \subset Y_2$, имеет место включение \[ Y_1 \cap C(Y_2) \subset C(Y_1). \]

Смысл этой аксиомы в следующем: если мы сужаем произвольное множество $Y_2$ до $Y_1$, то всякий элемент, попадающий в выбор из более широкого множества $Y_2$, войдёт в выбор из более узкого множества $Y_1$ при условии, что он содержится в $Y_1$.

(согласия).
Пусть $C$ — функция выбора, заданная на семействе подмножеств $A$. Для любого непустого подсемейства $A' \subset A$ имеет место включение: \[ \bigcap_{Y \in A'} C(Y) \subset C \paren{ \bigcap_{Y \in A'} Y }. \]

В соответствии с аксиомой согласия, элементы, выбираемые одновременно из нескольких множеств, обязательно должны входить в число выбираемых из объединения этих множеств.

(независимости от посторонних вариантов).
Пусть $C$ — функция выбора, заданная на семействе подмножеств $A$. Для всех множеств $Y_1, Y_2 \in A$ таких, что \[ C(Y_2) \subset Y_1 \subset Y_2, \] имеет место равенство \[ C(Y_1) = C(Y_2). \]

В соответствии с этой аксиомой, если в более узкое множество $Y_1$ по сравнению с множеством $Y_2$ вошли все элементы, выбираемые из более широкого множества $Y_2$, то в выбор $C(Y_1)$ входят все элементы множества $C(Y_2)$ и не входят никакие другие элементы.

Задача многокритериального выбора (основные объекты и постановка)

Рассмотрим задачу многокритериального выбора $\left\langle X, f, \succ_X \right\rangle$, содержащую следующие объекты:

$X$ — множество возможных вариантов (решений), из которого осуществляется выбор;
$f = (f_1, \dots, f_m)$ — векторный критерий, определённый на множестве $X$ и принимающий числовые значения в арифметическом векторном пространстве $\R^m$;
$\succ_X$ — асимметричное бинарное отношение строгого предпочтения, заданное на множестве $X$. Запись $x \succ_X x'$ для вариантов $x, x' \in X$ означает, что вариант $x$ для лица, принимающего решения (ЛПР), предпочтительнее варианта $x'$.

Возможные варианты из $X$, которые должны быть найдены в результате решения задачи многокритериального выбора, будем именовать выбираемыми вариантами. Они образуют множество выбираемых вариантов $C(X)$.

Будем также использовать множество возможных $Y = f(X)$ и множество выбираемых векторов $C(Y) = f(C(X))$. Также будем считать, что на множестве возможных векторов $Y$ задано асимметричное отношение строгого предпочтения $\succ_Y$, которое согласовано с отношением $\succ_X$ следующим образом: \[ f(x) \succ_Y f(x') \iff x \succ_X x' \] для всех $x \in \tilde x$ и $x' \in \tilde x'$, где $\tilde x, \tilde x' \in \tilde X$, а $\tilde X$ — совокупность классов эквивалентности, порождённых отношением эквивалентности \[ x \sim x' \iff f(x) = f(x') \] на множестве $X$.

Задача многокритериального выбора $\left\langle Y, \succ_Y \right\rangle$ в терминах векторов содержит множество возможных векторов $Y \subset \R^m$ и отношение строгого предпочтения $\succ_Y$, заданное на $Y$, а её решением является множество выбираемых векторов $C(Y)$.

Аксиома Парето

(Парето).
Для любых двух векторов $y, y' \in Y$, удовлетворяющих неравенству \[ y \geq y', \] выполнено \[ y \succ_Y y'. \]

Аксиома исключения доминируемых векторов

(исключения доминируемых векторов).
Для любой пары векторов $y, y' \in Y$, удовлетворяющих соотношению \[ y \succ_Y y', \] выполнено $y' \not\in C(Y)$.

В соответствии с этой аксиомой всякий вектор, не выбираемый в паре, не должен выбираться из всего множества $Y$.

Принцип Эджворта-Парето

(принцип Эджворта-Парето).
Пусть выполнены аксиома Парето и аксиома исключения доминируемых векторов. Тогда для любого множества выбираемых векторов $C(Y)$ имеет место включение \[ C(Y) \subset P(Y). \]

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

Определение: полиэдрально вогнутая функция

Полиэдрально вогнутой называют функцию \[ h: \R^n \to \R \] вида \[ h(x) = \min_{j = 1, \dots, s} \paren{ \dp{c^j}{x} + \alpha_j }, \] где \[ c^j \in \R^n, \qquad \alpha_j \in \R \] для всех $j = 1, 2, \dots, s$.

Аксиома инвариантности отношения предпочтения

(инвариантность отношения предпочтения).
Отношение предпочтения $\succ$ инвариантно относительно линейного положительного преобразования: для любого $\alpha \gt 0$ и любых $c, y, y' \in \R^m$ выполняется \[ y \succ y' \implies \alpha y + c \succ \alpha y' + c. \]