zhChinese    enEnglish
  ПМ-ПУ  » Структура » Преподаватели  » Ногин В.Д.  » НиД условия для задачи векторной максимизации

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

Рассмотрим задачу максимизации векторного критерия 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^*\, слабо эффективна.