Необходимые и достаточные условия для задачи векторной максимизации

Рассмотрим задачу максимизации векторного критерия $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 \in X$ , что выполнено

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

собственно эффективной (оптимальной по Джеофриону) относительно $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\,$ называют эффективным (слабо эффективным или собственно эффективным) вектором.

Теорема 1 ( 1979, [I, 1], с. 76-77). Точка $x^* \in X$ эффективна тогда и только тогда, когда для каждого $x \in X\,$ найдутся положительные числа

$\mu_1 , \mu_2 , \dots , \mu_m, \ \ \ \ \sum_{i=1}^{m}\mu_i = 1,\,$

(в общем случае зависящие от $x\,$ ), такие, что

$\sum_{i=1}^{m}\mu_i f_{i}(x^*) \ \underline{\underline{>}} \ \sum_{i=1}^{m}\mu_i f_{i}(x) . \,$

Теорема 2 (1979, [I, 1], с. 77-79). Точка $x^* \in X$ собственно эффективна тогда и только тогда, когда существует конечный набор $p\,$ положительных векторов

$\left \{ ( \mu_1^k, \mu_2^k, \dots , \mu_m^k ) \right \}, \ \ \sum_{i=1}^{m} \mu_i^{k}=1, \ \ k=1,2, \dots , p; \ \ p \ \underline{\underline{<}} \ m ,$

таких, что для всякого $x \in X$ найдется номер $k \in \left \{ 1,2, \dots , p \right \}$ , при котором имеет место неравенство

$\sum_{i=1}^{m}\mu_i^{k}f_{i}(x^*) \ \underline{\underline{>}}\ \sum_{i=1}^{m}\mu_i^{k}f_{i}(x) .$

Введем $m\,$ векторов $\mu^1, \mu^2, \dots , \mu^m$ размерности $m\,$ с компонентами

$\mu_i^k =\begin{cases} \varepsilon , \ \ \ i=1,2, \dots , m, \ \ i \ne k, \\ 1-(m-1) \varepsilon , \ \ \ i=k, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k=1,2, \dots , m. \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1) \end{cases}$

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

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

Приведенная выше теорема 2 и теорема Ю.Б. Гермейера влекут

Следствие (1982, [I, 1], с. 83). Пусть $y^* > \mathbf{0}$ . Допустимый вектор $y^* \in Y=f(X)$ является собственно эффективным тогда и только тогда, когда найдутся положительное число $\varepsilon$ и положительные в сумме равные единице числа $\lambda_1, \lambda_2, \dots , \lambda_m$ , что выполняется равенство

$\min _{i=1,2, \dots , m} \ \ \lambda_i \left \langle \mu^i , y^* \right \rangle = \max _{y \in Y}\ \ \min _{i=1,2, \dots ,m} \ \ \lambda_i \left \langle \mu^i , y\right \rangle .$

в котором векторы $\mu^1 , \mu^2 , \dots , \mu^m$ имеют вид (1).

Теорема 3 (1982, [I, 1], с. 83). Вектор $y^* \in Y$ является собственно эффективным тогда и только тогда, когда найдется такое положительное число $\varepsilon$ , что этот вектор слабо эффективен относительно линейной вектор-функции $( \left \langle \mu^1 , y \right \rangle , \left \langle \mu^2 , y \right \rangle , \dots , \left \langle \mu^m , y \right \rangle )$ на множестве $Y\,$ , где векторы $\mu^1 , \mu^2 , \dots , \mu^m$ определены равенством (1).

Введем полиэдральный (многогранный) конус

$\Lambda_ \varepsilon = \left \{ y \in \mathbb{R}^n : \left \langle \mu^i , y \right \rangle \ \underline{\underline{>}} \ 0 , \ \ i=1,2, \dots , m \right \}$

с векторами $\mu^1 , \mu^2 , \dots , \mu^m$ вида (1).

Теорема 4 (1982, [I, 1], с. 84-85). Вектор $y^* \in Y$ собственно эффективен относительно $f \,$ на множестве $X\,$ тогда и только тогда, когда существует положительное $\varepsilon$ , при котором

$[ Y - y^0 ] \cap \Lambda_\varepsilon =\left \{ \mathbf{0} \right \}.$

Замечание. При дополнительном предположении, что множество $X\,$ состоит из конечного числа элементов, словосочетание "собственно эффективный" в приведенных выше теоремах 2 - 4 может быть заменено на прилагательное <эффективный>.

Теорема 5 (1982, [I, 1], с. 106). Предположим, что функции $f_1, f_2, \dots , f_m$ положительны, а функции $\ln f_1, \ln f_2, \dots , \ln f_m$ вогнуты на множестве $X\,$ . Точка $x^* \in X$ слабо эффективна относительно $f \,$ тогда и только тогда, когда существуют такие положительные числа

$\mu_1 , \mu_2 , \dots , \mu_m, \ \ \ \ \sum_{i=1}^{m}\mu_i = 1,\,$

что выполняется равенство

$\prod_{i=1}^{m}(f_{i}(x^*))^{\mu_i} = \max _{x \in X} \ \prod_{i=1}^{m}(f_{i}(x))^{\mu_i} .$

Напомним, что функция $h\,$ называется квазивогнутой на множестве $X \subset \mathbb{R}^n$ , если неравенство

$h( \lambda x' +(1-\lambda ) x'') \ \underline{\underline{>}} \ \min \left \{ h(x' ), h(x'') \right \}$

имеет место для всех $x' , x'' \in X$ и всех $\lambda \in \left [ 0, 1 \right ]$ .

Теорема 6 (1976, [I, 1], с. 106-107). Пусть $m\,$ -мерная векторная функция $f = (f_1,f_2, \dots ,f_m)$ , $m > n+1,\,$ является (покомпонентно) квазивогнутой на выпуклом множестве $X \subset \mathbb{R}^n \,$ . Точка $x^* \in X$ слабо эффективна относительно $f \,$ тогда и только тогда, когда она слабо эффективна относительно некоторой не более чем $(n+1)\,$ -мерной векторной функции, составленной из компонент $f_1,f_2, \dots ,f_m$ .

Напомним, что $h\,$ полиэдрально вогнута, если

$h(x)= \min _{i=1,2, \dots ,s} ( \left \langle c^i , x \right \rangle + \alpha_i ), \ \ \ \ \ \ c^i \in \mathbb{R}^n , \ \ \ \alpha _i - const.$

Теорема 7 (1982, [I, 1], с. 117). Пусть

$X= \left \{ x \in \mathbb{R}^n : \ \ g_j \ \underline{\underline{>}} \ 0, \ \ j=1,2, \dots , k \right \}$

и все функции $f_1,f_2, \dots ,f_m, \ g_1, g_2, \dots , g_k$ полиэдрально вогнуты на $\mathbb{R}^n$ . Тогда множество эффективных точек совпадает с множеством собственно эффективных точек.

Рассмотрим числовую функцию $h\,$ , определенную на $\mathbb{R}^n$ . Будем предполагать, что она удовлетворяет локальному условию Липшица, т.е. для всякого ограниченного непустого множества $T \subset \mathbb{R}^n$ существует неотрицательная константа $L\,$ , при которой

$\left | h(x')-h(x'') \right | \ \underline{\underline{<}} \ L \left \| x' -x'' \right \| = L \sqrt{\left \langle x'-x'' , x'-x'' \right \rangle }$

для всех $x', x'' \in T$ . У такого рода функции $h\,$ градиент $\nabla h (\cdot)\,$ существует почти всюду (т.е. за исключением множества точек меры нуль).

Рассмотрим произвольную последовательность точек $\left \{ x^l \right \} \subset \mathbb{R}^n$ , в которых градиенты $\nabla h(x^l), \ l=1,2, \dots$ существуют, причем $\lim _{l \rightarrow \infty} x^l =x$ . Если существует предел $\lim _{l \rightarrow \infty} \nabla h(x^l )$ , то обозначим его $\hat {\nabla }h(x)$ . Выпуклую оболочку множества всех таких пределов будем обозначать $\partial h(x)$ и называть обобщенным градиентом функции $h\,$ в точке $x\,$ . Можно проверить, что множество $\partial h(x)$ является непустым выпуклым компактным множеством, причем если $h\,$ дифференцируема в точке $x\,$ , то $\partial h(x) = \left \{ \nabla h(x) \right \}$ .

Зафиксируем две векторные функции $f=(f_1,f_2, \dots ,f_m), \ g=(g_1, g_2, \dots , g_k)$ с компонентами, удовлетворяющими локальному условию Липшица на $\mathbb{R}^n$ , и введем множество допустимых точек

$X= \left \{ x \in \mathbb{R}^n : \ \ g_j \ \underline{\underline{>}}\ 0, \ \ j=1,2, \dots , k \right \}.$

Тем самым, далее будем иметь дело с задачей многоцелевого программирования. Для точки $x^* \in X$ посредством

$J(x^*)= \left \{ j : \ \ g_j (x^*)= 0 \right \}$

будем обозначать множество активных в точке $x^*\,$ ограничений.

Теорема 8 (1982, [I, 1], 133-134). Пусть точка $x^* \in X$ слабо эффективна относительно $f\,$ на множестве $X\,$ . Тогда найдутся векторы $\mu \in \mathbb{R}^n, \ \lambda \in \mathbb{R}^k, \ \ (\mu, \lambda ) \ \underline{\underline{>}} \ \mathbf{0}, (\mu, \lambda ) \ne \mathbf{0}$ и обобщенные градиенты

$\hat {\nabla } f_i(x^*) \in \partial f_i(x^*), \ \ i=1,2, \dots ,m; \ \ \hat {\nabla } g_j(x^*) \in \partial g_j(x^*) \ \ \ \forall j \in J(x^*),$

такие, что выполнено равенство

$\sum_{i=1}^{m} \mu_i \hat {\nabla} f_{i}(x^*) + \sum_{j \in J(x^*)}^{} \lambda_j \hat {\nabla} g_j(x*) = \mathbf{0}. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Если, кроме того, векторы $\hat {\nabla } g_j(x^*) \in \partial g_j (x^*) \ \ \ \forall j \in J(x^*)$ линейно независимы, то $\sum_{i=1}^m \mu_i=1.$

Напомним, что предел

$h'(x,e)=\lim _{\sigma \rightarrow +0} \frac{h(x+\sigma e)-h(x)}{\sigma}$

определяет производную функции $h\,$ в точке $x\,$ по направлению $e, \ e \ne \mathbf{0}\,$ .

Пусть числовая функция $h\,$ определена на $\mathbb{R}^n$ и удовлетворяет локальному условию Липшица. Обобщенная производная функции $h\,$ в точке $x\,$ по направлению $e, \ e \ne \mathbf{0}$ , определяется равенством

$h^0(x,e)=\lim _{\delta \rightarrow +0} \min _{\left \| (\sigma , \nu) \right \| \underline{\underline{<}} \delta, \ \nu >0 } \frac{h(x+\nu + \sigma e)-h(x+\nu )}{\sigma}.$

Функцию $h\,$ будем называть обобщенно псевдовогнутой, если для всех $x', x'' \in \mathbb{R}^n$ , таких что $h^0(x'',x'-x'') \ \underline{\underline{<}} \ 0$ , имеет место неравенство $h(x') \ \underline{\underline{<}} \ h(x'').$

Теорема 9 (1982, [I, 1], с. 135). Предположим, что все функции $f_1,f_2, \dots ,f_m$ обобщенно псевдовогнуты, а все функции $g_1, g_2, \dots , g_k$ квазивогнуты на $\mathbb{R}^n\,$ . Пусть равенство (2) имеет место для некоторых $\mu \in \mathbb{R}^n, \ \lambda \in \mathbb{R}^k, \ \ (\mu, \lambda ) \ \underline{\underline{>}} \ \mathbf{0}, \sum_{i=1}^m \mu_i =1$ , причем g_j^0 (x^*,e)=g'_j(x^*,e) для всех $e \ne \mathbf{0}$ и $j \in J(x^*)$ . Тогда точка $x^*\,$ слабо эффективна.