II. Лексикографическая двойственность для несобственных задач линейного и квадратичного программирования ²

Рассматриваются вопросы лексикографической двойственности для задач линейного и квадратичного программирования. Проблема формулируется так: как поставить исходную задачу лексикографической оптимизации, чтобы двойственная задача допускала лексикографическое прочтение, при этом чтобы эта пара объектов была связана математически содержательными соотношениями. В статье поставленный вопрос решается для линейных и квадратичных задач оптимизации.

1. Введение

1.1. Двойственность для разрешимых задач математического программирования (МП)

Под двойственной задачей к задаче МП

$$C:\ \sup \{ f_0(x)\ \vert \ f_j(x)\leq0\ \ (j=1,..., m),\ \ x\geq0 \}$$

понимают

$$C^*:\ \inf_{u\geq0}\ \sup_{x\geq0}F(x,\ u),$$

где $F(x,\ u)=f_0(x)-\sum_{j=1}^mu_jf_j(x)\ -\$функция Лагранжа, соотнесенная задаче C. Двойственности в МП может быть придан простой игровой смысл: пусть f_j(x)=f_j⁰(x)-b_j $(j=1,...,\ m)\ -$ используемые в производстве (предприятии, отрасли) ресурсы, $f_j^0(x)\ -\$затраты j-го ресурса, приходящиеся на вектор $x\geq 0$, $f_0(x)\ -\$доход от реализации продукции x. Если наравне с Производством (первый игрок) ввести Рынок (второй игрок) с функциями поглощения продукции и формирования цен $u^T=[u_1,...,u_m]\geq~\!0$ на ресурсы b_j, то F(x, u) выступает в качестве платежной функции. Если к данной игре применить принцип гарантированного результата, то получится пара задач: $\sup_{x\geq0} \inf_{u\geq0}F(x,\ u)$ и $\inf_{u\geq0} \sup_{x\geq0}F(x,\ u)$. Первая из них эквивалентна исходной задаче C, а вторая является двойственной по определению. Если $C\ -$задача линейного программирования $L:\ \sup\{(c,\ x)\ \vert \ Ax \leq b,$ $x\geq0\}$, то двойственная к ней эквивалентно преобразуется к виду $L^*:\inf\{(b.\ u)\ \vert \ A^Tu \geq c,$ $u\geq0\}$. Эти задачи связывает утверждение: они одновременно разрешимы или неразрешимы, в случае разрешимости их оптимальные значения совпадают (теорема двойственности).

1.2. Несобственные задачи МП и аппроксимация [1]

О п р е д е л е н и е. Задача C называется собственной, если C и C^* разрешимы и их оптимальные значения совпадают. В противном случае задача C называется несобственной (НЗ).

В частности, если ограничения задачи C несовместны (противоречивы), то $C\ -$ несобственная. Задача аппроксимации (коррекции) несобственной модели C, т.е. поиск разрешимой модели, ``ближайшей'' к C, может быть поставлена, в частности, следующим образом. Пусть $\{C(\triangle)\}$ - параметрический класс задач, поглощающий C, т.е. $C(\triangle_0)~\!=~\!C$ при некотором $\triangle_0 \in K_0$. Положим $K=\{\triangle \in K_0\ \vert\ C(\triangle)\ -$ собственная}. Если $\varphi(\triangle)\ -\$функция качества коррекции, то задача оптимальной коррекции может быть записана так:

$$\min \{ \varphi(\triangle)\ \vert \ \triangle \in K\}.$$

П р и м е р. Пусть $C(\triangle): \sup\{f_0(x)-(\triangle c, x) \ \vert \ f_j(x) \leq \triangle b_j(j),$ $x\geq0\},\ \ \triangle = [\triangle c, \triangle b] \in K_0=\{\triangle \geq0\}$. В качестве $\varphi(\triangle)$ можно выбрать, например, $\parallel \triangle c \parallel^2+\parallel \triangle b \parallel^2$. Если $\widetilde{\triangle} =[\widetilde{\triangle c},\ \widetilde{\triangle b}]\ -$ оптимальный вектор задачи коррекции по критерию $\varphi(\triangle)$, то модель $\max \{ f_0(x)-(\widetilde{\triangle c},\ x)\ \vert \ f_j(x) \leq \widetilde{\triangle b_j}(j),\ \ x \geq0\}$ выступает в качестве модели компромисса. Понятно, что если C разрешима и регулярна, то $\widetilde{\triangle} = 0$.

1.3. Схема двойственности для НЗ ЛП

$$\begin{array}{rrcl} L & \stackrel{\pi}{\longrightarrow} & &\... ...{\longrightarrow} & & \hspace*{-0.3cm}P^\char93 . \end{array}$$

Ее смысл состоит в сопоставлении задачам L и L^* по единому правилу $\pi$ собственных задач P и P^#, которые бы аппроксимировали в том или ином смысле задачи L и L^* и были связаны между собой классической теоремой двойственности. Приведем одну из реализаций задач P и P^#:

$$P:\, \sup \{ (c, x) - \sum_{j=1}^{m_0} R_j\, \mbox{$\parallel... ...^+ \mbox{$\parallel$}_{p(j)}\ \vert \ A_0x \leq b^0,\ x \geq 0,$$

$$\mbox{$\parallel$}x^i \mbox{$\parallel$}_{q(i)} \leq r_i\ \ (i=1,...,\ n_0) \};$$

$$P^{\char93 }:\, \inf\{(b, u) + \sum_{i=1}^{n_0} r_i\, \mbox{$... ...box{$\parallel$}^* _{q(i)}\ \vert \ B^T_0 u \geq c^0,\ u \geq0,$$

$$\mbox{$\parallel$}u^j \mbox{$\parallel$}^*_{p(j)} \leq R_j\ \ (j=1,...,\ m_0) \}.$$

Здесь A_jx-b^j и B^T_i u-cⁱ соответствуют произвольному разбиению систем $Ax\leq b$ и $A^Tu \geq c$ на подсистемы, $\{R_j, r_i\}\ -$ неотрицательные параметры; {b^j} и {u^j}, {cⁱ} и $\{x^i\}\ -$ разбиения векторов b и $u,\ \ c$ и x на подвекторы, соответствующие разбиению систем $Ax\leq b$ и $A^Tu \geq c$ на подсистемы; $\{\mbox{$\parallel$}\cdot \mbox{$\parallel$}_{p(j)}\}$, $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_{q(i)} \}\ -$ наборы произвольных норм в соответствующих пространствах, $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}^*_{p(j)} \}$, $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}^*_{q(i)} \}\ -$ им сопряженные нормы; ``+'' над вектором означает замену его отрицательных координат нулями.

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

Теорема (двойственности) [1]. Пусть подсистемы $A_0x\leq b^0$, $x\geq 0$ и $B^T_0u\geq c^0$, $u\geq 0$ совместны, а параметры R_j и r_i выбраны из условий:

$$R_j> \min\,\{ \mbox{$\parallel$}u^j \mbox{$\parallel$}^*_{p(j)}\ \vert \ B^T_0 u \geq c^0,\ \ u\geq0 \},$$

$$r_i\geq \min \{ \mbox{$\parallel$}x^i \mbox{$\parallel$}_{q(i)}\,\ \ \vert \ A_0x\leq b^0,\ \ x\geq0 \}.$$

Тогда оптимальные значения задач P и P# конечны и совпадают. При этом, если $\sup$ в задаче P достигается, то и $\inf$ в задаче P# достигается.

Для большого числа частных реализаций задач P и P# условия теоремы выполняются автоматически. Приведем два примера таких случаев:

$$\left\{ \begin{array}{l} \max \{ (c,\ x)-(R,\ (Ax-b)^+)\ \ve... ...(r,\ (c-A^Tu)^+)\ \vert \ 0\leq u\leq R\}; \end{array}\right.$$

$$\left\{ \begin{array}{l} \max \{ (c,\ x)-R_0 \mbox{$\paralle... ...lel$}u \mbox{$\parallel$}^*_p \leq R_0 \}. \end{array}\right.$$

1.4. Общая схема формирования двойственности для НЗ МП

Пусть в C функции {f_j(x)}^m₀ дифференцируемы. Выше были определены отображения $(\ast)$ и (#). Дополним их отображением (l), заключающимся в линеаризации задачи в точке p. Приведем общую схему двойственности для нелинейного программирования:

Приведем вид задач P и P^# для C, получающихся в силу изображенной схемы. Пусть $A^x\ -$ матрица частных производных функций {f_j(x)}₁^m, b_x=A^xx-F(x), где F^T(x)=[f₁(x),..., f_m(x)], $c_x=[\partial f_0(x)/ \partial x_1,..., \partial f_0(x)/ \partial x_n ]^T$; F^T(x)=[F₀(x),..., F_m0(x)]; A_j^x, B_i^x, b^j_x, cⁱ_x (j=0,..., m₀; $i=0,..., n_0)\ -$ разбиения матрицы A^x и векторов b_x, c_x на фрагменты по аналогии разбиений матрицы A и векторов b, c на фрагменты A_j, B_i и b^j, cⁱ. Тогда:

$$P:\, \sup \{ f_0(x)-\sum_{j=1}^{m_{0}}R_j \mbox{$\parallel$}F_j^+(x) \mbox{$\parallel$}\ \vert$$

$$F_0(x) \leq0,\ \ x\geq0, \mbox{$\parallel$}x^i \mbox{$\parallel$}\leq r_i\ \ (i=1,..., n_0)\},$$

$$P^{\char93 }:\, \inf \{ F(x, u)-(\nabla_x F(x,u), x)+ \sum_ {... ...arallel$}(c_x^i-(B_i^x)^Tu)^+ \mbox{$\parallel$}^{\ast}\ \vert$$

$$(B_0^x)^Tu \geq c^0_x,\ \ u\geq0,\ \ \mbox{$\parallel$}u^j \mbox{$\parallel$}^{\ast} \leq R_j\ \ (j=1,..., m_0) \}.$$

В предположениях выпуклости задачи C и дифференцируемости ее определяющих функций имеет место аналог теоремы двойственности из п. 1.3.

2. Лексикографическая двойственность для задач ЛП: первая постановка

Симметричная двойственность для лексикографической задачи линейного программирования - это двойственность для такой постановки задачи ЛП, когда в качестве двойственного объекта выступает также лексикографическая задача ЛП, при этом эти задачи связаны математически содержательными регулярными соотношениями.

Пусть $z=[z_{i_{1}} ,..., z_{i_{k}}]^T \in$R^k. Лексикографический порядок $\stackrel{(l)}{\leq}$ в R^k, отвечающий упорядочению индексов координат p=(i₁ ,..., i_k), определяется следующим образом: $z \stackrel{(l)}{\leq} z'$, если первая пара несовпадающих координат с номером i_t удовлетворяет неравенству $z_{i_{t}} < z_{i_{t}}'$; совпадение всех координат соответствует равенству z=z'. Этот порядок естественным образом определяет экстремальные элементы на том или ином множестве $Z \subset$ R^k. Например, элемент $\tilde{z} \in Z$ лексикографически максимален
(l-максимальный) на Z, если из $\bar{z} \stackrel{(l)}{\geq} \tilde{z},\ \tilde{z} \in Z$ вытекает $\bar{z}=\tilde{z}$. Аналогично определяется лексикографически минимальный элемент. Заметим, что лексикографический экстремум связан с экстремумом в последовательном программировании, а именно: l-максимальный элемент $\tilde{z}\ -\$это оптимальный вектор заключительной из последовательности задач:

Здесь Arg...$\ -\$оптимальное множество обозначенной вслед задачи.

2.1. Постановка задачи

В основе построения первого варианта лексикографической двойственности (l-двойственности) лежит соответствие каркасов

$$\begin{array}{ccc} \left [ \begin{array}{lc} C^T & \\ A &... ...ay}{cc} B^T & \\ A^T & C \end{array}\right ] , \end{array}$$

где $C=[c_0, c_1,..., c_k],\ \ B=[b_0, b_1,..., b_s], \{c_i\}_0^k \subset$Rⁿ, $\{b_j\}_0^s \subset$R^m. Запишем задачу лексикографической максимизации:

$L_p(r): \max_p\{(c_i, x)\}_0^k$ при ограничениях $Ax \leq b(r),\ x \geq0$

(вектор b(r) правых частей ограничений зависит от параметра r, смысл которого будет уточнен ниже); запись векторов - столбцовая. Будем исходить (для определенности) из упорядочения (по ``важности'') p=(k, k-1,..., 0) максимизируемых линейных функций {(c_i, x)}₀^k. Задача L_p(r) может пониматься как задача последовательного программирования на отыскание решения заключительной из задач:

Для целей построения симметричной двойственности вектору правых частей в L_p(r) придадим вид: $b(r)=b_0+\sum_{j=1}^s r_jb_j$, где $\{b_j\}_0^s\ -\$фиксированный набор векторов из R^m, $\{r_j\}_1^s\ -$ неотрицательные параметры. В традиционной интерпретации задачи ЛП, когда вектор правых частей выступает в качестве вектора ресурсов, на b(r) можно смотреть следующим образом: $b_0\ -\$обеспеченный ресурсный вектор плюс ``смесь'' $\sum_{j=1}^sr_jb_j$ других ресурсных наборов {b_j}₁^s.

Лексикографически двойственную к L_p(r) задачу поставим в форме:

$$L_q^{(l)}(R):\ \min_q\{(b_j,\ u)\}_0^s {\mbox{\it {при\ \ ограничениях}}}$$

$$A^Tu \geq c_0+\sum_{i=1}^kR_ic_i,\ \ \ u \geq0.$$

Здесь $\{R_i\}_1^k\ -\$неотрицательные параметры. Упорядочение q функций $\{(b_j,\ u)\}_0^s$ можно считать (для определенности) таким: q=(s, s-1,..., 0). Упорядочения p и q могут быть произвольными, однако форма записи задач L_p(r) и L_q^(l)(R) требует, чтобы функции $(c_0,\ x)$ и $(b_0,\ u)$ стояли в этих упорядочениях на последнем месте. От L_p(r) и L_q^(l)(R) можно перейти к скаляризованным, с помощью $r \geq0$ и $R \geq0$ соответственно, задачам:

$$L(r, R): \max \{(c_0, x)+\!\sum_{i=1}^kR_i(c_i, x) \vert Ax \leq b_0+\sum_{j=1}^sr_jb_j,\, x \geq0\},$$

$$L^{\ast}(R, r): \min \{(b_0, u)+\!\sum_{j=1}^sr_j(b_j, u) \vert A^Tu \geq c_0+\sum_{i=1}^kR_ic_i,\, u \geq0\}.$$

Эти задачи являются взаимно двойственными в классическом смысле, поэтому их оптимальные значения совпадают.

Четыре введенные для рассмотрения задачи, а именно: L_p(r) и L_q^(l)(R), L(r, R) и $L^{\ast}(R, r)$ связаны между собой важными свойствами, которые и составляют содержание двойственности для лексикографической постановки задачи линейного программирования.

2.2. Предварительные результаты

Лемма 2.1. Пусть задача ЛП

$$L:\ \max\{(c,\ x)\ \vert \ Ax \leq b,\ \ x \geq0\}$$

разрешима. Существует независящий от b вектор $\bar{R}>0$, $\bar{R}\in$R^m такой, что $\{0\leq u\leq \bar{R}\} \bigcap$Arg $L^{\ast} \neq \emptyset$.

Д о к а з а т е л ь с т в о. Пусть $\{p^k\}\ -\$совокупность вершин многогранника $M^{\ast}$ системы $A^Tu \geq c,\ \ u\geq0$. Ранг ее совпадает с размерностью пространства переменной u, поэтому по крайней мере одна вершина этого многогранника существует. В качестве $\bar{R}_j$ можно взять $\max_{(k)}p_j^k$, где $p_j^k\ - j$-я координата вектора p^k. Вектором $\bar{R}$ будет $[\bar{R}_1,..., \bar{R}_m]$. Смысл этой конструкции понятен: в качестве решения задачи $L^{\ast}$ независимо от реализации вектора b выступает одна из вершин многогранника $M^{\ast}$. Поэтому выбор $\bar{R}$ по нашему правилу (с запасом ``прочности'') обеспечивает, независимо от b, непустоту рассматриваемого пересечения.

Лемма 2.2. Для разрешимой задачи последовательного программирования

$$\mbox {$\max_p$} \left\{ \left[ \begin{array}{c} (c_0,\ x)... ... x) \end{array}\right]\ \vert \ Ax\leq b,\ \ x\geq0 \right\}$$ (2.1)

выбор числа R₁>0, обеспечивающего эквивалентный (в смысле совпадения оптимальных множеств) переход к задаче

$$\max\{(c_0,\ x)+R_1(c_1,\ x)\ \vert \ Ax \leq b,\ \ x\geq0\},$$ (2.2)

можно осуществить независимо от реализации вектора b.

Д о к а з а т е л ь с т в о. Дело в том [2], что выбор R₁ осуществляется из условия: $R_1> \mid \bar{u}_1 \mid$, где $\bar{u}_1\ -\$двойственная оценка неравенства $(c_1,\ x)\geq \mbox{$\alpha$}_1$ в задаче

$$\max\{(c_0,\ x)\ \vert \ Ax\leq b,\ \ (c_1,\ x)\geq \mbox{$\alpha$}_1, x\geq0\},$$ (2.3)

$\mbox{$\alpha$}_1=\max\{(c_1,\ x)\ \vert \ Ax\leq b,\ \ x\geq0\}$. Число $\mbox{$\alpha$}_1$, естественно, зависит от b. Но по лемме 2.1, примененной к задаче (2.3), выбор R₁ возможен независящим от b и $\mbox{$\alpha$}_1(b)$. Лемма доказана.

Обобщением содержания лемм 2.1 и 2.2 (с учетом их доказательств) может служить

Лемма 2.3. Если задача L_p(r) разрешима, то существует не пустая область конструктивно определяемых значений параметра R=[R₁,..., R_k] таких, что

$$\begin{array}{c} \mbox{Arg}\ L_p(r)=\mbox {Arg}\,\max \{(c_... ...i,\ x)\ \vert \\ [8pt] Ax\leq b(r),\ \ x\geq0\}, \end{array}$$ (2.4)

причем выбор R не зависит от b(r).

Д о к а з а т е л ь с т в о этой леммы состоит в последовательном применении двух предыдущих лемм.

Лемма 2.4. Пусть в задачах L_p(r) и $L_q^{(l)}(R):\ p=(i_k,..., i_1, 0)$, q=(j_s,..., j₁, 0). При условии совместности их систем ограничений необходимым и достаточным условием разрешимости задач L_p(r) и L_q^(l)(R) является выполнимость соотношений:

$$\begin{array}{c} c_{i_{\scriptstyle t}} \in {\mbox{cone}} ... ...h {$\mathrm{R}$}}}_n^{+}\\ [4pt] (t=0,1,..., k); \end{array}$$ (2.5)

$$\begin{array}{c} b_{j_{\scriptstyle l}} \in {\mbox{cone}} ... ...h {$\mathrm{R}$}}}_m^{+}\\ [4pt] (l=0, 1,...,s), \end{array}$$ (2.6)

соответственно; здесь $a_j\ -\ j$-я строка, $h_i\ -\ i$-й столбец матрицы A.

Содержание этой леммы состоит в переформулировке применительно к рассматриваемой ситуации условия разрешимости обычной задачи ЛП, например, в форме $\max\{(c,\ x)\ \vert \ Ax\leq b,$ $x\geq0\}$, а именно: при непустоте ее допустимого множества (т.е. при совместности ее системы ограничений) разрешимость эквивалентна выполнимости соотношения $c \in \mbox {cone}\, \{a_j^T\}_1^m$, что, в свою очередь, эквивалентно разрешимости системы $A^Tu \geq c,\ \ u\geq0$. Понятно, что получение условий (2.5), (2.6) требует последовательного применения выписанного соотношения.

Теорема 2.1. Если задачи $L_{ji}: \max\{(c_i,\ x)\ \vert \ A_jx\leq b_j$, $x\geq0\}$ (i=0,..., k; j=0,..., s) разрешимы, то существует непустая область конструктивно определяемых значений параметров $r \geq0$ и $R \geq0$ таких, что

$$\left. \begin{array}{c} \mbox{Arg}\, L_p(r) = \mbox {Arg}\... ...(r,\ R) = \mbox{opt}\, L^{\ast}(R,\ r). \end{array}\right \}$$ (2.7)

Этот результат можно изобразить схемой:

$$\begin{array}{rlcrl} & \hspace*{-3mm}L_p(r) & \stackrel {\mb... ...grightarrow}} & & \hspace*{-3mm} L^{\ast}(R,\ r). \end{array}$$

В этой схеме $(l)\ -\$символ отображения в лексикографически двойственную задачу, $(\ast)\ -\$символ отображения в классически двойственную задачу, $\stackrel {\mbox{\footnotesize Arg}}{\widetilde {\longrightarrow}}$ означает переход к эквивалентной задаче в смысле наследования (сохранения) оптимального множества.

З а м е ч а н и я к формулировке теоремы.

1. Задачи $L(r,\ R)$ и $L^{\ast}(R, r)$ являются взаимно двойственными (в классическом смысле), поэтому их оптимальные значения совпадают$\ -\$в этом смысле 3-е соотношение в (2.7) приведено для полноты.

2. Предположение о разрешимости задач {L_ji} влечет разрешимость систем ограничений в задачах $L(r,\ R)$ и $L^{\ast}(R, r)$ при любых $r \geq0$, $R \geq0$. Действительно, если $\bar{x}_j\ -\$допустимый вектор для L_ji, $\bar{u}_i\ -\$допустимый вектор для $L_{ji}^{\ast}$ (его существование вытекает из теоремы двойственности), то векторы $\bar{x}=\bar{x}_0+ \sum_{j=1}^sr_j \bar{x}_j$ и $\bar{u}=\bar{u}_0+ \sum_{i=1}^kR_i\bar{u}_i$ будут допустимыми для $L(r,\ R)$ и $L^{\ast}(R, r)$, что и обеспечивает их разрешимость.

Пояснение к доказательству теоремы. По лемме 2.3 можно обеспечить выбор $R=\bar{R}>0$, при котором будет выполняться первое из соотношений (2.7)$\ -\$каково бы ни было $r \geq0$. С другой стороны, по этой же лемме можно обеспечить выбор $r=\bar{r}>0$, при котором справедливо второе соотношение из (2.7)$\ -\$каково бы ни было $R \geq0$. Значения $\bar{R}$ и $\bar{r}$ и будут необходимыми значениями параметров R и r, обеспечивающими справедливость теоремы 2.1.

Конструктивизм нахождения $\bar{R}$ и $\bar{r}$ вскрывается доказательством леммы 2.

З а м е ч а н и е. Можно было бы показать, что множества значений $R \geq0$ и $r \geq0$, для которых справедлива теорема, являются конусами (не замкнутыми).

3. (l)-двойственность для несобственных задач ЛП -- частный случай

Ниже мы рассмотрим задачу ЛП в обычной постановке, но с акцентом на упорядочение (по ``важности'') ограничений как в прямой задаче L, так и в двойственной $L^{\ast}$. Такая постановка определяет однозначный выбор максимально совместных подсистем (МСП) в их системах ограничений. Пусть

$$L:\ \max\{(c,\ x)\ \vert \ Ax\leq b,\ \ x\geq0\},$$

$$L^{\ast}:\ \min\{(b,\ u)\ \vert \ A^Tu\geq c,\ \ u\geq0\}.$$

Упорядочения неравенств в ограничениях определим перестановками p=(j_m,..., j₁), q=(i_n,..., i₁), придав этому смысл: j_l+1-е неравенство в системе $Ax\leq b$ ``важнее''
j<sub>l</sub>-о, а i<sub>t+1</sub>-е неравенство в системе $A^Tu \geq c$ ``важнее'' i_t-о (l=1,..., m-1; t=1,..., n-1).

Для определенности будем считать p=(1,..., m), q=(1,..., n). МСП формируются путем наращивания числа неравенств, начиная с конца (включение условия $x\geq 0$ в МСП производим автоматически). При таком наращивании возможны перескоки, т.е. ситуации, когда включение очередного неравенства ведет к несовместности, однако включение вместо него последующего неравенства дает совместную подсистему. Таких перескоков может быть несколько. На допущение таких перескоков при образовании МСП можно смотреть как на исправление (пересмотр) первоначальной упорядоченности ограничений (по ``важности'').

Чтобы не усложнять нумерацию при выделении МСП, будем считать, что перескоков нет. Выпишем таким образом выделенные МСП:

$$l_j(x):= (a_j, x)-b_j\leq0,\ \ x\geq0\ \ (j=k+1,..., m);$$ (3.1)

$$-h_i(u):= (h_i, u)-c_i\geq0,\ \ u\geq0\ \ (i=s+1,..., n).$$ (3.2)

Здесь: $Ax-b\leq0 \sim l_j(x)\leq0$ (j=1,..., m), $A^Tu-c\geq0~\sim$ $-h_i(u)\geq0$ (i=1,..., n). Множества решений систем (3.1) и (3.2) обозначим соответственно M₀ и $M_0^{\ast}$. Для неравенств, не вошедших в системы (3.1) и (3.2), по смыслу их иерархии будут отыскиваться минимальные невязки на основе принципа лексикографического минимума. В соответствии с этим сформулируем задачи:

$$\begin{array}{c} L_p(r): \max_p \left\{ \left [ \begin{arra... ...geq0,\ \ u \in M_0^{\ast},\ \ u^1\leq R \right \}, \end{array}$$

где $p=(0,1,..., k),\ \ q=(0, 1,..., s)$, а нулевые индексы в этих перестановках приписаны целевым функциям (c, x) и $(b,\ u);\ x^1$ и $u^1\ -\$компоненты векторов x и u, соответствующие разбиению системы $Ax\leq b$ на подсистемы $l_j(x)\leq0$ (j=1,..., k) и (3.1), и системы $-h_i(u)\geq0$ на подсистемы $-h_i(u)\geq0$ (i=1,..., s) и (3.1), что схематически можно изобразить так:

$$\begin{tabular}{r\vert\vert c\vert c\vert\vert c\vert\vert} \... ... \ x^1$} & \multicolumn{1}{c}{ } \\ \cline{2-3} \end{tabular}$$

Заметим, что вхождение ограничений $x^1\leq r$ и $u^1\leq R$ в задачах L_p(r) и L_q^# требуется существом дела.

Скаляризация задачи L_p с помощью вектора R и задачи L_q^# - с помощью вектора r приводит к паре задач:

$$L_p(r, R): \max\{(c, x)- \sum_{j=1}^k R_jl_j^+(x)\ \vert x\in M_0,\ \ x^1\leq r\},$$

$$L_q^{\char93 }(R, r): \min\{(b, u)+ \sum_{i=1}^l r_ih_i^+(u) \ \vert u\in M_0^{\ast},\ \ u^1\leq R\}.$$

Так как M₀ и $M_0^{\ast}$ определяются соответствующими МСП, то $l_j(x)\geq0$, $\forall x\in M_0$ (j=1,..., k) и $h_i(u)\geq0,\ \forall u \in M_0^{\ast}$ (i=1,..., l), что позволяет l_j⁺(x) и h_i⁺(u) заменить на l_j(x) и h_i(u) для отмеченных индексов j и i.

Задачи L_p(r, R) и L_q^#(R, r) связаны утверждением [I]:

Если R и r выбраны так, что

$$M_0 \cap \{x\ \vert \ x^1\leq r\} \neq \emptyset ,\qquad M_0^{\ast} \cap \{u \ \vert \ u^1\leq R\} \neq \emptyset ,$$

то эти задачи разрешимы и их оптимальные значения совпадают.

Нижеследующая теорема (с учетом сформулированного утверждения) дает связь между задачами L_p, L_q^#, L_p(r, R) и L_q^#(R, r).

Теорема 3.1. Существует непустая область конструктивно определяемых параметров $r \geq0$ и $R \geq0$ таких, что

$$\mbox {Arg}\ L_p(r)=\mbox {Arg}\ L_p(r,\ R) \neq \emptyset ,$$

$$\mbox {Arg}\ L_q^{\char93 }(R)=\mbox {Arg}\ L_q^{\char93 }(R,\ r) \neq \emptyset ,$$

$$\mbox {opt}\ L_p(r,\ R)=\mbox {opt}\ L_q^{\char93 }(R, r).$$

З а м е ч а н и е. Если задача L разрешима (тогда разрешима и $L^{\ast}$), то задачи L_p(r) и $L_p(r,\ R)$ совпадают с L, а задачи L_q^#(R) и $L_q^{\char93 }(R,\ r)$ совпадают с $L^{\ast}$. Так что теорема 3.1 формулируется специально для неразрешимых задач линейного программирования, в которых ограничения упорядочены (со смыслом упорядочения ``по важности'').

4. Двойственность для несобственных задач ЛП в лексикографической интерпретации

Пусть P и $P^{\char93 }\ -\$задачи из п. 1.

Важным является вопрос об аппроксимационном смысле задач P и P^# по отношению к L и $L^{\ast}$. Ниже этот смысл будет раскрыт через термины лексикографической оптимизации.

Будем исходить (в содержательном плане) из того, что системы ограничений задач L и $L^{\ast}$ разбиты на подсистемы $A_jx\leq b^j$ (j=1,..., m₀) и $B_i^Tu\geq c^i$ (i=1,..., n₀), причем неравенства из одной подсистемы не ранжируются, а сами подсистемы ранжируются, например, в соответствии с такими упорядочениями: (0, m₀,..., 1) и (0, n₀,..., 1). Введенному упорядочению можно придать следующий смысл: ограничения $A_0x\leq b^0$, $x\geq 0$ и $B_0^Tu\geq c^0$, $u\geq 0$ носят директивный характер и предполагаются совместными, остальные$\ -\$факультативными (в целом же они могут быть несовместными). Однако в силу введенной упорядоченности подсистем функции $f_j(x) = \mbox{$\parallel$}(A_j x - b^j)^+ \mbox{$\parallel$}_{p(j)}$ (j=1,...,m₀); $g_i(u) = \mbox{$\parallel$}(c^i - B_i^T u)^+ \mbox{$\parallel$}_{q(i)}^{\ast}$ (i=1,..., n₀), играющие роль невязок соответствующих подсистем, должно минимизировать последовательным образом в соответствии с упорядочениями p=(m₀,..., 1) и q=(n₀,..., 1). Как уже было отмечено в предыдущих параграфах, это эквивалентно постановке следующих двух задач лексикографической оптимизации:

$$P_p(r):\ \max\nolimits_p \left \{ \left [ \begin{array}{c} ... ...\\ (c,\ x) \end{array} \right ] \ \vert \ x\in M(r) \right \},$$

$$P_q^{\char93 }(R):\ \min\nolimits_q \left \{ \left [ \begin{... ... \end{array} \right ] \ \vert \ u\in M^{\char93 }(R) \right \},$$

где M(r) и $M^{\char93 }(R)\ -\$допустимые множества задач P и P^#, соответственно, символы p и q определяют введенную упорядоченность невязок с тем дополнением, что функционалы $(c,\ x)$ и $(b,\ u)$ в этих упорядочениях поставлены на последнее место.

Теорема 4.1. Пусть нормы $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_{p(j)} \},\ \ \{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_{q(i)} \}$ монотонны вместе со своими сопряженными и кусочно-линейны. Тогда существует не пустая область конструктивно определяемых $r \geq0$ и $R \geq0$ таких, что

$$\mbox{Arg}\ P=\mbox {Arg}\ P_p(r) \neq \emptyset ,$$ (4.1)

$$\mbox {Arg}\ P^{\char93 }=\mbox {Arg}\ P_q^{\char93 }(R) \neq \emptyset ,$$ (4.2)

$$\mbox {opt}\ P=\mbox {opt}\ P^{\char93 }.$$ (4.3)

П о я с н е н и я к д о к а з а т е л ь с т в у. Соотношение (4.3) выполняется в силу основной теоремы двойственности для несобственных задач ЛП (она была приведена в п. 1). Что касается соотношений (4.1) и (4.2), то суть их доказательств та же, что и теоремы (2.1). Уточнения требует лишь следующее обстоятельство. Когда мы определяем $R_{m_{0}}> \bar{u}_{m_{0}}$, где $\bar{u}_{m_{0}}\geq0\ -\$двойственная оценка ограничения $f_{m_{0}}(x) = \mbox{$\parallel$}(A_{m_{0}}x-b^{m_{0}})^+ \mbox{$\parallel$}_{p(m_0)} \leq \mbox{$\alpha$}_{m_{0}}$ $(:= \mbox{opt}\, \min \{f_{m_{0}}(x) \vert \ x\in M(r)\}$ в задаче

$$\min\{f_{m_{0}-1}(x)\ \vert \ x\in M(r),\ \ f_{m_{0}}(x) \leq \mbox{$\alpha$}_{m_{0}}\},$$ (4.4)

то существование $\bar{u}_{m_{0}}$ должно быть обеспечено условием регулярности для системы ограничений задачи (4.4). Но это условие выполнено в силу предположения о кусочной линейности всех входящих в написание задач P и P^# норм. В этом случае неравенство $f_{m_{0}}(x)\leq \mbox{$\alpha$}_{m_{0}}$, равным образом и неравенства $\mbox{$\parallel$}x^i \mbox{$\parallel$}_{q(i)} \leq r_i$ (i=1,..., n₀), могут быть эквивалентным образом записаны в форме систем линейных неравенств. Это обстоятельство и позволяет снять заботы о выполнимости условия регулярности как в задаче (4.4), так и во всех остальных, которые возникают при доказательстве теоремы в соответствии со схемой обоснования теоремы 2.1.

Рассмотрим частный случай задач P_p(r) и P_q^#(R) в форме:

$$\mbox {$\max_p$} \left\{ \left [ \begin{array}{c} -\mbox{... ... \ \mbox{$\parallel$}x \mbox{$\parallel$}_q \leq r \right \},$$ (4.5)

$$\min\nolimits_q \left \{ \left [ \begin{array}{c} \mbox{$\p... ...mbox{$\parallel$}_p^{\ast} \leq R \right \}. \eqno(4.5)^{\ast}$$

Здесь p и q соответствуют упорядочениям функций сверху вниз, т.е., например, в (4.5) вначале минимизируется невязка $\mbox{$\parallel$}(Ax-b)^+ \mbox{$\parallel$}_p$, а на Arg этой задачи максимизируется функция $(c,\ x)$.

Нас будет интересовать случай несобственности L 3-го рода:

$$\min_{x\geq0} \mbox{$\parallel$}(Ax-b)^+ \mbox{$\parallel$}_p... ...ox{$\parallel$}(c-A^Tu)^+ \mbox{$\parallel$}_q^{\ast}= \beta >0$$

(т.е. системы $Ax\leq b$, $x\geq 0$ и $A^Tu \geq c$, $u\geq 0$ несовместны).

Задачи P и P^# из п. 1.3, соответствующие рассматриваемой ситуации, запишем в следующей форме:

$$\max \{(c,\ x)-R\,\mbox{$\alpha$}\, \mbox{$\parallel$}(Ax-b)... ...\ \mbox{$\parallel$}x \mbox{$\parallel$}_q \leq \beta\, r \},$$ (4.6)

$$\min \{(b,\ u)+r\, \beta\, \mbox{$\parallel$}(c-A^Tu)^+ \mbox... ...l$}_p^{\ast} \leq \mbox{$\alpha$}\, R \}.\eqno (4.6)^{\char93 }$$

Понятно, что теорема 4.1 для этой пары задач справедлива. Но мы хотим в этих задачах невязки заменить на их квадраты, что часто является выигрышным с вычислительной точки зрения. Итак, наравне с (4.6) и (4.6)^# выпишем задачи

$$\max \{ (c,\ x)-R\, \mbox{$\parallel$}(Ax-b)^+ \mbox{$\paral... ... \ \mbox{$\parallel$}x\mbox{$\parallel$}_q \leq \beta\, r \},$$ (4.7)

$$\min \{ (b,\ u)+r\, \mbox{$\parallel$}(c-A^Tu)^+ \mbox{$\para... ...l$}_p^{\ast} \leq \mbox{$\alpha$}\, R \}.\eqno (4.7)^{\char93 }$$

Таким образом, (4.7) и (4.7)^# отличаются от (4.6) и (4.6)^# степенями норм невязок и тем, что из коэффициентов перед ними убраны множители $\mbox{$\alpha$}$ и $\beta$. В математическом (в частности, в ЛП) программировании штрафование невязок ограничений первой или второй степенью несет эффект существенного различия: в случае $\mbox{$\parallel$}(Ax-b)^+ \mbox{$\parallel$}_p$ получаем эквивалентную сводимость исходной задачи ЛП к задаче без ограничений, в случае $\mbox{$\parallel$}(Ax-b)^+ \mbox{$\parallel$}^2\ -\$асимптотическую сводимость.

Отмеченный эффект различия в рассматриваемом случае исчезает, что объясняется условием $\mbox{$\alpha$}> 0$, $\beta >0$. Ниже будет показано, что при некоторых предположениях (уже фигурировавших ранее) реализуется следующая схема двойственности:

$$\begin{array}{ccrlcrl} (4.5)_p & \stackrel {\mbox {\footnote... ...ightarrow}} & & \hspace*{-0.3cm}(4.7)^{\char93 }. \end{array}$$

Здесь $\stackrel {\mbox {\footnotesize Arg}} {\stackrel {\subset } {\longrightarrow}}$ означает $\mbox {Arg}\,(4.6)\,\subset \, \mbox {Arg}\,(4.7), Arg\,(4.6)^{\char93 }\,\subset \linebreak\mbox {Arg}\,(4.7)^{\char93 }$. Обратим внимание на то, что в силу теоремы двойственности для НЗ ЛП (см. п.1.3): opt(4.6)=opt(4.6)^#.

Теорема 4.2. Пусть нормы $\mbox{$\parallel$}\cdot \mbox{$\parallel$}_p$ и $\mbox{$\parallel$}\cdot \mbox{$\parallel$}_q$ монотонны (вместе со своими сопряженными) и кусочно-линейны. Тогда существует не пустая область конструктивно определяемых r>0 и R>0 таких, что реализуется выше приведенная схема.

Д о к а з а т е л ь с т в о. Справедливость левой части схемы определяется теоремой 4.1. Убедимся в справедливости правой части нашей схемы, т.е. в справедливости включений Arg(4.6)$\subset$Arg(4.7) и Arg $(4.6)^{\char93 }\subset$Arg(4.7)^#. Рассмотрим, например, первое из них. Максимизируемые функции в (4.6) и (4.7) обозначим через f₁(x) и f₂(x), соответственно. Эти функции являются вогнутыми. В силу смысла числа $\mbox{$\alpha$}> 0$ имеем $f_1(x) \geq f_2(x)$ для любых допустимых x, т.е. для $x\geq 0$, $\mbox{$\parallel$}x \mbox{$\parallel$}_q \leq \beta\,r$. При этом, если $\tilde{x}\in$Arg(4.6), то с использованием верхнего соотношения левой части схемы получим $\mbox{$\parallel$}(A\tilde{x}-b)^+ \mbox{$\parallel$}_p= \mbox{$\alpha$}$, следовательно, opt $(4.6) = f_1(\tilde{x}) = (c,\ \tilde{x}) - R\,\mbox{$\alpha$}^{2} = f_2(\tilde{x})$, отсюда вытекает $\tilde{x}\in$Arg(4.7), т.е. доказываемое включение справедливо. Аналогично доказывается и второе включение, надо лишь учесть тот факт, что если норма кусочно-линейна, то и сопряженная норма является таковой.

5. l-двойственность для задач квадратичного программирования

Будем отталкиваться от l-постановки задачи квадратичного программирования следующего вида:

$$K_p(r):\ l-\max\nolimits_p \left \{ \left [ \begin{array}{c}... ...Qx \\ C^Tx \end{array} \right ] \ \vert \ Ax\leq Br \right \},$$

здесь $Q\ -\$положительно определенная матрица, $p\ -\$упорядочение перечисленных в квадратных скобках функций (как и ранее, выделенная здесь функция -1/2x^TQx в названном упорядочении стоит на последнем месте), $r\ -\$неотрицательный параметр. По аналогии с предыдущим материалом задаче K_p(r) можно сопоставить скаляризованную задачу

$$K(r,\ R):\ \max \{-1/2x^TQx+(C^Tx,\ R)\ \vert \ Ax\leq B\,r \}.$$

Двойственная к ней имеет вид:

$$K^{\ast}(r,\ R):\ \min \{F(x,\ u)\ \vert \ \nabla_xF(x,\ u)=0,\ \ u\geq0 \},$$

где $F(x,\ u)=-1/2x^TQx+(C^Tx,\ R)-(u,\ Ax-Br)\ -$функция Лагранжа, соответствующая постановке K(r, R), следовательно, $\nabla_xF(x,\ u)=-Qx-A^Tu+CR$. Так как матрица Q невырожденная, то из $\nabla_xF(x,\ u)=0$ получаем x=Q^-1(CR-A^Tu). Подставляя это значение x в $F(x,\ u)$, получим (после некоторых элементарных преобразований): $F(x, u)=1/2(CR-A^Tu)^TQ^{-1}(CR-A^Tu)+(u,\ Br)$. Задача $K^{\ast}(\cdot)$ принимает вид:

$$K^{\ast}(r,\ R):\ \min \{f(u)+(u,\ Br)\ \vert \ u\geq0 \},$$

где f(u)=1/2(CR-A^Tu)^TQ^-1(CR-A^Tu). Это задача квадратичного строго выпуклого программирования.

Задаче $K^{\ast}(\cdot)$ поставим в соответствие l-задачу

$$K_l^{\ast}(r,\ R):\ \min\nolimits_q \left \{ \left [ \begin{... ...}{c}f(u)\\ B^Tu \end{array} \right ]\ \vert \ u\geq0 \right \},$$

где $q\ -\$упорядочение стоящих в квадратных скобках функций, причем f(u) в этом упорядочении стоит на последнем месте.

Теорема 5.1. При условии совместности при любых $r \geq0$ системы $Ax\leq Br$ существует не пустая область значений векторных параметров r и R таких, что

$$\mbox{Arg}\, K_p(r)=\mbox{Arg}\, K(r,\ R) \neq \emptyset ,$$

$$\mbox{Arg}\,K^{\ast}(r,\ R)=\mbox{Arg}\,K_l^{\ast}(r,\ R) \neq \emptyset ,$$

$$\mbox{opt}\, K(r,\ R)=\mbox{opt}\, K^{\ast}(r,\ R).$$

З а м е ч а н и е. Теоремы такого типа, сформулированные выше, имеют однотипное доказательство. Это наводит на мысль, что возможна такая общая постановка задачи и формулировка общей теоремы двойственности, из которой указанные теоремы вытекали бы в качестве следствий. В значительной степени это так и есть. Однако, во-первых, как задача, так и формулировка были бы при этом громоздкими, а во-вторых, были бы утеряны естественные по своей постановке формы задания исходной задачи. Впрочем, надо все же отметить, что у доказательства названных теорем есть свои нюансы.

Каснемся еще одной ситуации, относящейся к несобственной задаче квадратичного программирования

$$K:\ \max \{ -1/2x^TQx\ \vert \ Ax\leq b \}.$$

Если система $Ax\leq b$ несовместна, то при невырожденности Q имеет место несобственность первого рода, т.е.

$$\{ u\geq0\ \vert\ \max_{(x)}F(x,\ u) < +\infty \} \neq \emptyset .$$

Выпишем задачи:

$$K(R): \!\max\{-1/2x^TQx- \!\sum_{j=1}^{m_0} R_j \mbox{$\paral... ...x-b^j)^+ \mbox{$\parallel$}_{p(j)} \, \vert \, A_0x\leq b^0 \},$$

$$K_l:\ \max\nolimits_p \left \{ \left [ \begin{array}{l}-1/2x... ...{m_0}(x) \end{array} \right ] \ \vert \ A_0x\leq b^0 \right \},$$

$$K_l^{\char93 }:\ l-\min \{1/2(b-A^Tu)^TQ^{-1}(b-A^Tu)+(b,\ u)\ \vert$$

$$u\geq0,\ \ \mbox{$\parallel$}u^j \mbox{$\parallel$}_{p(j)}^{\ast} \leq R_j\ \ (j=1,..., m_0) \}.$$

В написании этих задач неразъясненных ранее символов нет; напомним лишь, что $f_j(x) = \mbox{$\parallel$}(A_j x - b^j)^+ \mbox{$\parallel$}_{p(j)}$ (j=1,..., m₀).

Теорема 5.2. Пусть выполнены условия:

$1^0.\ Q\ -\$положительно определенная матрица;

2⁰. подсистема $A_0x\leq b^0$ системы $Ax\leq b$ совместна;

3⁰. нормы $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_{p(j)} \}_1^{m_0}\ -\$кусочно-линейны и монотонны.
Тогда существует не пустая область значений R_j (j=1,..., m₀) таких, что

$$\mbox{Arg}\, K_l = \mbox{Arg}\, K(R) \neq \emptyset ,$$

$$\mbox{opt}\, K(R) = \mbox{opt}\, K_l^{\char93 }.$$

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. -М.: Наука, 1983. -336 с.
2. Еремин И.И. О задачах последовательного программирования //
   Сибирск. матем. журн. -1973. -Т. 14,  1. -C. 53-63.

90С25
Eremin, I.I. The lexicographic duality for improper problems in linear and quadratic programming. (Russian)
Trudy Inst. Mat. i Mekh. (Ekaterinburg) 1 (1992), 178-192.

This paper deals with lexicographic duality in linear and quadratic programming. The problem is so considered as how to formulate the primary lexicographic program to obtain the dual program which would permit lexicographic interpretation. Moreover, these programs must be connected by substantial mathematical relationships. In the paper this problem is solved for linear and quadratic programs.