ПМ-ПУ :: Ногин Владимир Дмитриевич :: Топологические свойства множества Парето

Топологические свойства множества Парето

Рассмотрим задачу максимизации векторного критерия $f = (f_1,f_2, \dots ,f_m)$ на множестве возможных точек $X, \ X \subset \mathbb{R}^n \,$ . Пусть $Y=f (X) \subset \mathbb{R}^m\,$ означает образ множества $X\,$ при отображении $f\,$ .

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

$f_{i}(x) \ \underline{\underline{>}} \ f_{i}(x^*), \ i=1,2, \dots ,m,$ и $f(x) \ne f(x^*)$ ;

собственно эффективной (оптимальной по Джеофриону) относительно $f \,$ на множестве $X\,$ , если $x^*\,$ эффективна и существует такая положительная константа $M\,$ , что для всякого $x \in X$ и каждого $i\,$ , при которых $f_{i}(x) > f_{i}(x^*)\,$ , и некоторого $j\,$ , такого что $f_{j}(x) < f_{j}(x^*),\,$ выполнено неравенство

$\frac{ f_{i}(x) - f_{i}(x^*)}{ f_{j}(x^*) - f_{j}(x)} \ \underline{\underline{<}} \ M$ .

В случае, когда точка $x^* \in X$ является эффективной (слабо эффективной или собственно эффективной), вектор $y^* =f(x^*) \in Y\,$ называют эффективным (слабо эффективным или собственно эффективным) вектором.

Обозначим посредством $P_f(X)\,$ и $G_f(X)\,$ множество эффективных и собственно эффективных точек, а через $P(Y)\,$ и $G(Y)\,$ множество эффективных и собственно эффективных векторов, т.е. $P(Y)=f(P_f(X))\,$ и $G(Y)=f(G_f(X))\,$ .

Теорема 1 (1982, [I,1]). Предположим, что множество $Y\,$ замкнуто и существуют такие положительные числа $\mu _1, \mu_2, \dots ,\mu _m, \ \ \sum_{i=1}^m \mu _i=1$ , что для некоторой $const\,$ и всех $\ x \in X$ имеет место неравенство

$\sum_{i=1}^m \mu _i f_i(x) \ \underline{\underline{<}} \ const .$

Тогда множество $G(Y)\,$ плотно в множестве $P(Y)\,$ , т.е.

$G(Y) \subset P(Y) \subset \overline {G(Y)} (1)$

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

Теорема 2 (1982, [I,1]). Предположим, что множество $Y\,$ выпукло и замкнуто. Тогда имеют место включения (1).

Теорема 3 (1982, [I,1]). Предположим, что множество $X\,$ выпукло, все компоненты векторной функции $f \,$ вогнуты и непрерывны на множестве $X\,$ и множество $Y\,$ замкнуто. Тогда имеют место включения (1). Более того,

$Y_> \subset P(Y) \subset \overline {Y} _>$

где

$Y_> = \left \{ y^* \in Y : \ \sum _{i=1}^m \mu _i y_i^* = \max _{y \in Y} \sum _{i=1}^m \mu _i y_i, \ \ \quad \exists \ \mu _1, \mu _2, \dots , \mu _m > 0, \ \quad \sum _{i=1}^m \mu _i =1 \right \}.$

Теорема 4 (1982, [I,1]). Пусть множество $X\,$ выпукло и компактно, все компоненты векторной функции $f \,$ вогнуты и непрерывны на $X\,$ , причем по крайней мере одна компонента векторной функции $f \,$ строго вогнута. Тогда имеют место включения

$G_f(X) \subset P_f(X) \subset \overline {G_f(X)}.$