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

Теоремы двойственности

Пусть две числовые векторные функции $f = (f_1,f_2, \dots ,f_m), \ \ g=(g_1,g_2, \dots ,g_k)$ определены на множестве $D \subset \mathbb{R}^n\,$ и $X = \left \{ x \in \mathbb{R}^n : \ \ g_j(x) \ \underline{\underline{>}} \ 0, \ \ j=1,2, \dots ,k \right \}, Y=f(X).$

Введем векторную функцию Лагранжа (см. [I, 1], [III, 2]) $L(x, \lambda)=(f_1(x)+\sum_{i=1}^{k}\lambda _jg_j(x), f_2(x)+\sum_{i=1}^{k}\lambda _jg_j(x), \dots , f_m(x)+\sum_{i=1}^{k}\lambda _jg_j(x))$ и множества $Q= \bigcup _{x \in D} Q(x), \ \ \ \ \ Q(x)=\bigcap _{\lambda \underline{\underline{>}}\mathbf{0} } \left \{ q \in \mathbb{R}^m : \ q \underline{\underline{<}} L(x, \lambda)\right \},$ $H= \bigcup _{\lambda \underline{\underline{>}} \mathbf{0}} H(\lambda), \ \ \ \ \ H(\lambda )=\bigcap _{x \in D} \left \{h \in \mathbb{R}^m : \ h => L(x, \lambda) \right \}$ где $\lambda =(\lambda _1, \lambda _2, \dots , \lambda _k)$ . Для векторов $a,b \in \mathbb{R}^m$ здесь приняты следующие обозначения

$a \underline{\underline{>}} b \ \ \Longleftrightarrow \ \ a_i \ \underline{\underline{>}} \ b_i , \ \ \ i=1,2, \dots , m,$

$a => b \ \ \Longleftrightarrow \ \ a=b$ или $a_i > b_i\,$ по крайней мере для одного $i \in \left \{ 1,2, \dots ,m \right \}$

Напомним, что $q^* \in Q\,$ называют максимальным элементом множества $Q\,$ , если

$q \ \underline{\underline{>}} \ q^*, \ \ \ q \in Q \ \Longrightarrow \ q=q^*,$

$h^* \in H\,$ называют минимальным элементом множества $H\,$ , если

$h \ \underline{\underline{<}} \ h^*, \ \ \ h \in H \ \Longrightarrow \ h=h^*.$

Введем множество $Max \, Q\,$ всех максимальных элементов множества $Q\,$ и множество $Min \, H\,$ всех минимальных элементов множества $H\,$ .

Прямая задача. Найти множество $Max \, Q\,$ .Двойственная задача. Найти множество $Min \,H\,$ .

Теорема 1 (1977, [I, 1], [III, 2]). $Max \,Q \cap Min \, H = Q \cap H.$

Теорема 2 (1977, [I, 1], [III, 2]). Предположим, что множество $D\,$ выпукло, все компоненты непрерывных векторных функций $f, \ g\,$ вогнуты на нем и выполняется условие регулярности Слейтера, т.е. найдется такой вектор $\hat{x} \in X\,$ , что $g_j( \hat{x} )>0, \ \ j=1,2, \dots , k.$ Пусть имеет место хотя бы одно из следующих условий:

(i) множества эффективных и собственно эффективных точек совпадают, т.е. $P(Y)=G(Y)\,$ ( см. [I, 1]);
(ii) все функции $f_1,f_2, \dots ,f_m$ строго вогнуты на множестве $D\,$ ;(iii) множества $D, Y\,$ замкнуты и замыкание множества $Min \,H\,$ является подмножеством множества $H\,$ .

Тогда

$Max \,Q \subset Min \,H.$

Теорема 3 (1977, [I, 1], [III, 2]). Пусть множество $D\,$ выпукло, все компоненты непрерывных векторных функций $f, \ g\,$ вогнуты на нем, имеет место условие регулярности Слейтера и множество $Q\,$ замкнуто. Тогда

$Q \cup H = \mathbb{R} ^m.$

Теорема 4 (1977, [I, 1], [III, 2]). При выполнении предположений предыдущей теоремы имеет место включение

$Min \,H \subset Max \, Q.$

Определенные теоремы двойственности получены (см. [I, 1], [III, 2]) для следующих двух случаев
(i) все функции $f_1,f_2, \dots ,f_m, \ \ g_1,g_2, \dots ,g_k\,$ вогнуты и дифференцируемы
(ii) все функции $f_1,f_2, \dots ,f_m, \ \ g_1,g_2, \dots ,g_k\,$ линейны.

Установлено, что предложенная двойственная конструкция представляет собой прямое обобщение известного двойственного подхода Гейла, Куна и Таккера (см. [I, 1], [III, 2]), развитого для случая линейных векторных функций $f, \ g\,$ .