Теоремы существования

Рассмотрим задачу максимизации векторного критерия $f = (f_1,f_2, \dots ,f_m)$ на множестве возможных точек $X, \ X \subset \mathbb{R}^n \,$ . Пусть $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$ .

Теорема 1 (1980, [I, 1], [III, 5]). Пусть все компоненты векторной функции $f \,$ вогнуты и непрерывны на непустом выпуклом замкнутом множестве $X\,$ и множество $f(X)\,$ замкнуто. Собствено эффективные точки относительно $f \,$ на множестве $X\,$ существуют тогда и только тогда, когда найдутся такие положительные числа $\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 .$

Следствие 1 (1980, [I, 1], [III, 5]). В условиях выполнения предположений теоремы 1 множество эффективных точек непусто тогда и только тогда, когда непусто множество собственно эффективных точек.

Множество эффективных точек называют внешне устойчивым [I, 1], если для любого $x \in X\,$ найдется такая эффективная точка $x^*\,$ , что $f_i(x^*) \ \underline{\underline{>}} \ f_i(x), \ \ i=1,2, \dots , m$ .

Следствие 2 (1980, [I, 1], [III, 5]). В условиях выполнения теоремы 1 множество эффективных точек является внешне устойчивым.

Далее рассмотрение ограничим случаем линейных критериев:

$f(x) = ( \left \langle c^1,x \right \rangle , \left \langle c^2,x \right \rangle ,\dots ,\left \langle c^m,x \right \rangle),(1)$

где через $\left \langle a , b \right \rangle$ обозначается скалярное произведение двух $n\,$ -мерных векторов, т.е.

$\left \langle a , b \right \rangle = \sum_{i=1}^{n} a_i b_i .$

Обозначим символом $K\,$ выпуклый конус, порожденный векторами $c^1, c^2, \dots ,c^m\,$ , символом $aff \, K\,$ аффинную оболочку этого конуса, $ri \, K\,$ - его относительную внутренность, $0^+(X)\,$ - рецессивный конус выпуклого множества $X\,$ и $(0^+(X))^0\,$ - поляру рецессивного конуса (по поводу этой терминологии см. книгу Рокафеллара Р. Выпуклый анализ. - М.: Мир, 1973).

Теорема 2 (1975, [III, 5]). Пусть вектор функция $f\,$ линейна и имеет вид (1), множество $X\,$ непусто, выпукло и замкнуто. Предположим, что выполняется по крайней мере одно из следующих двух условий:
(i) $aff \, K \supset aff \, (0^+(X))^0\,$ (это условие заведомо выполняется, если $\dim K=n\,$ );
(ii) для любого $z \in [ (0^+(X))^0 \setminus ri \, (0^+(X))^0]$ линейная функция $\left \langle z , \cdot \right \rangle$ достигает максимума на множестве $X\,$ .

Тогда собственно эффективные точки относительно $f\,$ на множестве $X\,$ существуют тогда и только тогда, когда $(0^+(X))^0 \bigcap ri \, K \ne \empty$ .