V. О квадратичных и полноквадратичных задачах выпуклого программирования ⁵

Объектом рассмотрения будет задача

$$\hspace*{-2.7mm}\max\{ -x^T Q_0 x +(c_0, x)\, \vert\, x^T Q_j x +(a_j, x)\! \leq\! b_j,\ j\!=\!1,...,m \},$$ (1)

в которой $\{ x,\ c_0 \}\,\subset$Rⁿ, { Q_k }_k=0^m -- матрицы размерности n x n. Сквозным образом будем предполагать матрицу Q₀ положительно определенной (т.е. $x^T Q_0 x >0,\ \ \forall \,x\neq 0$), матрицы { Q_j }_j=1^m -- неотрицательно определенными (т.е. $x^T Q_j x\geq 0,\ \ \forall \,x$). Если все Q_j, $j=1,\,...\,,m$, -- нулевые матрицы, то (1) -- общая задача квадратичного программирования:

$$\max\,\{ (c_0,\ x) -x^T Q_0 x\ \mbox{$\,\mid\,$}\ Ax\leq b \};$$ (2)

здесь A -- матрица со строками a_j, b -- вектор с координатами b_j, $j=1,\,...\,,m$. Если в (2) вместо Q₀ взять $\mbox{$\alpha$}\,Q_0$, $\mbox{$\alpha$}> 0$, то получим задачу

$$\max\,\{ (c_0,\ x) -\mbox{$\alpha$}\,x^T Q_0 x\ \mbox{$\,\mid\,$}\ Ax\leq b \},$$ (3)

выступающую в качестве регуляризирующей (по Тихонову) задачу линейного программирования

$$L:\ \max\,\{ (c_0,\ x)\ \mbox{$\,\mid\,$}\ Ax\leq b \}.$$

Ниже будут рассмотрены некоторые вопросы, относящиеся к теории задач вида (1), в первую очередь, вопросы двойственности, регуляризации, несобственности.

1. Двойственность

Если $F(x,\ u) = f_0(x) -\mbox{$\sum\limits_{j=1}^{m}$} u_j f_j(x)$ -- функция Лагранжа, поставленная в соответствие задаче математического программирования

$$P:\ \max\,\{ f_0(x)\ \mbox{$\,\mid\,$}\ f_j(x) \leq 0,\ \ j=1,\,...\,,m \}$$ (4)

с дифференцируемыми функциями {f_k(x)}_k=0^m, то двойственной к P [1, § 23] является

$$P^*:\ \min\,\{ F(x,\ u)\ \mbox{$\,\mid\,$}\ \bigtriangledown _x F(x,\ u) =0,\ \ u\geq 0 \}.$$ (5)

Формирование такой двойственности основано на универсальной схеме, в силу которой в качестве двойственной к P выступает задача $\min\limits_{u\geq 0}\max\limits_{(x)}F(x,u)$, что в случае дифференцируемости функций f_k(x), $k=0,1,\,...\,,m$ приводит к выписанной задаче P^*.

Если (4) -- задача выпуклого программирования (ВП), то справедливо

Утверждение 1 (прямая теорема двойственности)
[1, теорема 24.3]. Пусть задача выпуклого программирования P удовлетворяет условиям:

1⁰.

P разрешима.

2⁰.

Функции {f_k(x)}_k=0^m дифференцируемы.

3⁰.

Существует допустимый для P вектор p такой, что f_j(p)<0 для нелинейных f_j(x) (условие регулярности).

Тогда P^* разрешима, при этом ${\,\mathrm{opt}}P ={\,\mathrm{opt}}P^*$.

Далее функции {f_k(x)}_k=0^m будут иметь вид, соответствующий задаче (1), т.е. $f_0(x) = (c_0,\ x) -x^T Q_0 x$, $f_j(x) = x^T Q_j x +(a_j,\ x) -b_j$, $j=1,\,...\,,m$.

Лемма 1   Задача P^*, определенная согласно (5) для $F(x,\ u) = f_0(x) -(u,\ F(x))$, $F(x) = [f_1(x),\,...\,,f_m(x)]$, может быть эквивалентно преобразована к виду

$$\min \{(b, u) + \frac{\textstyle 1}{\textstyle 4} (c_0-A^Tu)^T Q_u^{-1} (c_0-A^Tu) \mbox{$\,\mid\,$}u\geq 0\},\eqno (1)^*$$

где $Q_u:=\ Q_0 + \mbox{$\sum\limits_{j=1}^{m}$} u_jQ_j$.

Д о к а з а т е л ь с т в о. Элементарные преобразования функции Лагранжа $F(x,\ u) = (c_0,\ x) -x^T Q_0 x -\mbox{$\sum\limits_{j=1}^{m}$} u_j [x^T Q_j x +(a_j,\ x) -b_j]$ дают

$$F(x,\ u) = (b,\ u) + (c_0-A_0^Tu,\ x) -x^T Q_u x.$$ (6)

Так как $\bigtriangledown _x F(x,\ u) =-2Q_ux + (c_0-A^Tu)=0$, то $x= \frac{\textstyle 1}{\textstyle 2}\, Q_u^{-1} (c_0-A^Tu)$. Подставляя найденное значение для x в соотношение (6), получаем тот вид минимизируемой функции, который и фигурирует в двойственной задаче (1)^*.

З а м е ч а н и е 1. Если в исходной задаче (1) имеется требование $x\geq 0$, то (1)^* принимает вид

$$\min_{u\geq 0}\, \{(b,\ u) +\frac{\textstyle 1}{\textstyle 4} (c-A^Tu)_+^T\, Q_u^{-1}\, (c-A^Tu)_+ \};$$ (7)

здесь $(\,\cdot\,)_+$ означает положительную срезку вектора, стоящего внутри скобки.

З а м е ч а н и е 2. Если положить $Q_0 = \mbox{$\alpha$}\,E$, $\mbox{$\alpha$}> 0$ (E -- единичная матрица), Q_j=0, $j=1,\,...\,,m$, то задача (1) примет вид

$$\max\,\{ (c_0,\ x) -\mbox{$\alpha$}\,\mbox{$\parallel$}x\mbox{$\parallel$}^2\ \mbox{$\,\mid\,$}\ Ax\leq b \},$$ (8)

а задача (1)^* -- вид

$$\min_{u\geq 0}\, \{(b,\ u) + \frac{\textstyle 1}{\textstyle 4... ...\mbox{$\parallel$} c_0-A^Tu \mbox{$\parallel$}^2 \}.\eqno (8)^*$$

На самом деле, как в случае задач (8) и (8)^*, так и в более общей ситуации задач (1) и (1)^*, справедлив и обратный переход, связанный с формированием двойственных задач, т.е. ((1)^*)^* и ((8)^*)^*. Здесь справедлива взаимная двойственность, т.е. $((1)^*)^*\equiv$(1) и, в частности, $((8)^*)^*\equiv$(8). Во избежание громоздких преобразований ограничимся проверкой второго соотношения.

Лемма 2   Задача ((8)^*)^*, двойственная к (8)^*, совпадает с задачей (8).

Д о к а з а т е л ь с т в о. Перепишем задачу (8)^* в виде

$$\min_{u\geq 0}\, \{(b,\ u) + \frac{\textstyle 1}{\textstyle 4... ...el$}y \mbox{$\parallel$}^2\ \mbox{$\,\mid\,$}\ y = c_0-A^Tu \},$$

и поставим ей в соответствие функцию Лагранжа

$$F(u,y;x,v):= (b, u) + \frac{\textstyle 1}{\textstyle 4\mbox{$... ...{$\parallel$}y \mbox{$\parallel$}^2 + (c_0-A^Tu -y, x) -(v, u),$$

в которой u и y -- свободные переменные, а x и $v\geq 0$ -- множители Лагранжа, соотнесенные ограничениям y = c₀-A^Tu и $u\geq 0$ соответственно. Задача ((8)^*)^*, двойственная к (8)^*, запишется в виде

$$\max\, \{F(\,\cdot\,)\ \mbox{$\,\mid\,$}\ \bigtriangledown _{[u,y]} F(\,\cdot\,) =0, v\geq 0\}.$$

Нужно показать, что она может быть преобразована в задачу (8).

Сделаем преобразования функции $F(\,\cdot\,)$ и уравнения $\bigtriangledown _{[u,y]} F(\,\cdot\,) =0$:

$$\begin{array}{rcl} F(\,\cdot\,) & = & \frac{\textstyle 1}{\t... ...textstyle 1}{\textstyle 2\mbox{$\alpha$}}\, y-x= 0. \end{array}$$

С учетом этих соотношений получаем

$$F(\,\cdot\,) = (c_0,\ x) -\mbox{$\alpha$}\, \mbox{$\parallel$}x \mbox{$\parallel$}^2,$$

а сама задача ((8)^*)^* примет вид

$$\max\, \{ (c_0,\ x) -\mbox{$\alpha$}\, \mbox{$\parallel$}x \mbox{$\parallel$}^2\ \mbox{$\,\mid\,$}\ Ax-b=-v\leq 0\},$$

т.е. вид задачи (8). Лемма доказана.

Теорема 1 (двойственности)   Пусть в задаче (1) Q₀ -- положительно определенная матрица, {Q_j}_j=1^k -- неотрицательно определенные. Если для ограничений задачи (1) выполнено условие регулярности (пусть в форме 3⁰), то задачи (1) и (1)^* разрешимы, при этом ${\,\mathrm{opt}}(\ref{f1}) ={\,\mathrm{opt}}(1)^*$.

Д е й с т в и т е л ь н о, из совместности системы ограничений задачи (1) и ограниченности лебеговых множеств $\{x\ \mbox{$\,\mid\,$}\ f_0(x)\geq \mbox{$\alpha$}\}$, где f₀(x) = (c₀, x) -x^T Q₀ x, вытекает разрешимость этой задачи. В силу общей теоремы двойственности, сформулированной выше как утверждение 1, разрешима и задача (5), соотнесенная к (1), причем opt(1)=opt(5). Но так как переход от задачи (5) к задаче (1)^* был эквивалентным (хотя и сопровождавшимся исключением из записи задачи переменной x), то равенство opt(1)=opt(1)^* соблюдается.

З а м е ч а н и е 3. Применительно к частной ситуации (8)-(8)^* сформулированной теореме можно придать такую редакцию:

Если $M=\{x\ \mbox{$\,\mid\,$}\ Ax\leq b\} \neq \emptyset$, то задачи (8) и (8)^* разрешимы, при этом opt(8)=opt(8)^*.

З а м е ч а н и е 4. Если в (8) есть требование $x\geq 0$, то (8)^* принимает вид

$$\min\,\{ (b,\ u) + \frac{\textstyle 1}{\textstyle 4\mbox{$\al... ...(c-A^Tu)_+\,\mbox{$\parallel$}^2\ \mbox{$\,\mid\,$}\ u\geq 0\}.$$

2. Взаимная сопряженность методов регуляризации и квадратичных штрафных функций для задач линейного программирования

В этом пункте свяжем с задачей линейного программирования (ЛП) вида

$$L:\ \max\,\{ (c,\ x) \mbox{$\,\mid\,$}Ax\leq b,\ \ x\geq 0\}$$ (9)

задачу регуляризации (по Тихонову)

$$L_{reg}:\ \max\,\{ (c,\ x) -\mbox{$\alpha$}\,\mbox{$\paralle... ...box{$\parallel$}^2\ \mbox{$\,\mid\,$}\ Ax\leq b,\ \ x\geq 0 \}$$ (10)

и задачу, реализующую квадратичный метод штрафных функций,

$$L_{pen}: \max \{ (c, x) -R\, \mbox{$\parallel$}\,(Ax-b)_+\,\mbox{$\parallel$}^2 \mbox{$\,\mid\,$}x\geq 0\},\ R>0.$$ (11)

Приведем хорошо известные факты (см., например, [3]):

Если v₀ -- двойственная оценка неравенства $(c, x)\geq \mbox{$\alpha$}_0$ (:=optL) в задаче $\min \{ \mbox{$\parallel$}x\mbox{$\parallel$}^2 \mbox{$\,\mid\,$}Ax\leq b,\ x\geq 0,\ (c, x)\geq \mbox{$\alpha$}_0\}$, то при $\mbox{$\alpha$}^{-1} > \vert v_0\vert$:

$$% latex2html id marker 14474{\,\mathrm{arg}}(\ref{f10}) ={... ...\parallel$}^2\ \mbox{$\,\mid\,$}\ x\,\in\,{\,\mathrm{Arg}}L\}.$$ (12)

Если L разрешима и $\tilde {u}\,\in\,$ArgL^*, то

$$0\leq {\,\mathrm{opt}}L_{pen} -{\,\mathrm{opt}}L \leq \frac... ...style 4R}\, \mbox{$\parallel$}\tilde {u} \mbox{$\parallel$}^2.$$ (13)

Запишем задачу, двойственную к (10), имея в виду схему перехода от (1) к (1)^*:

$$\min\,\{ (b,\ u) + \frac{\textstyle 1}{\textstyle 4\mbox{$\al... ...\mbox{$\parallel$}^2\ \mbox{$\,\mid\,$}\ u\geq 0\}.\eqno (10)^*$$

С другой стороны, запишем задачу, двойственная к которой совпадала бы с L_pen. Такой задачей будет

$$(L^*)_{reg}: \min \{ (b, u) + \frac{\textstyle 1}{\textstyle... ... \mbox{$\parallel$}^2 \mbox{$\,\mid\,$}A^Tu\geq c,\ u\geq 0\}.$$ (14)

Задача (10)^*, полученная по схеме перехода (1) $\rightarrow (1)^*$, как раз и дает задачу (11), что легко проверяется. Обсуждаемые задачи свяжем схемой:

Приведенная схема фиксирует следующие факты:

1)

Двойственная задача (10)^* к задаче регуляризации L_reg реализует квадратичный метод штрафных функций для L^* -- двойственной к L (и обратно).

2)

Двойственная к задаче (L^*)_reg, т.е. к задаче, регуляризирующей L^*, реализует квадратичный метод штрафных функций для L (и обратно).

Приведенные факты как раз и выражают смысл того, что метод регуляризации и квадратичный метод штрафных функций находятся в соотношении взаимной сопряженности. Это обстоятельство было вскрыто в работе автора [2] (см. формулы (8) и (9) этой работы). С учетом соотношения (12) (также принадлежащего автору) отсюда следует утверждение, смысл которого в следующем: хотя квадратичный метод штрафных функций решает задачу L приближенно, тем не менее двойственная к нему задача решает задачу L^* точно. Строгой формулировкой этого результата автор в то время не располагал (о нем мне сообщил в 1995 г. А.И.Голиков).

Теперь приведем строгую формулировку этого факта, положив в основу задачу

$$\max \{ (c, x) -R\,(Ax-b)_+^T Q (Ax-b)_+ \mbox{$\,\mid\,$}x\geq 0\},$$ (15)

соотнесенную задаче L в соответствии с квадратичным методом штрафных функций; здесь R>0 -- штрафной параметр, Q -- положительно определенная матрица. В соответствии со схемой двойственности (1) $\rightarrow (1)^*$ задача (15) будет двойственной к

$$\min \{ (b, u) +\frac{\textstyle 1}{\textstyle 4R}\, u^T Q^{-1} u \mbox{$\,\mid\,$}A^Tu\geq c,\ u\geq 0\},$$ (16)

т.е. $(16)^* \equiv (\ref{f15})$. Последняя выступает как задача регуляризации (по Тихонову) задачи L^* при стабилизаторе u^T Q^-1 u. Теорема 1 в рассматриваемой ситуации принимает следующую простую формулировку.

Утверждение 2   Если $M:=\ \{x\geq 0\ \mbox{$\,\mid\,$}\ Ax\leq b\} \neq\emptyset$, то задачи (15) и (16) разрешимы, при этом ${\,\mathrm{opt}}(\ref{f15}) ={\,\mathrm{opt}}(\ref{f16})$.

З а м е ч а н и е 5. В нашем случае соотношения (12) и (13) принимают вид:

$$% latex2html id marker 14531{\,\mathrm{arg}}(\ref{f16}) =... ...^T Q^{-1} u\ \mbox{$\,\mid\,$}\ x\,\in\, {\,\mathrm{Arg}}L^*\}$$ (17)

при $\left ( \frac{\textstyle 1}{\textstyle 4R} \right )^{-1} > \vert v_0\vert$ (т.е. при $R>\frac{\textstyle \vert v_0\vert}{\textstyle 4}$), где v₀ -- двойственная оценка неравенства $(b,\ u)\leq \mbox{$\beta$}$ в задаче

$$\min \{ u^T Q^{-1} u\ \mbox{$\,\mid\,$}\ A^Tu\geq c,\ \ u\geq 0,\ \ (b, u)\leq \mbox{$\beta$}\},$$

где $\mbox{$\beta$}:=$ optL^*.

Если задача L разрешима и $\tilde {u}\,\in\,$ArgL^*, то

$$% latex2html id marker 145450\leq {\,\mathrm{opt}}(\ref{f... ...\textstyle 1}{\textstyle 4R}\, \tilde {u}^T Q^{-1} \tilde {u}.$$ (18)

Теорема 2   Если в квадратичном методе штрафных функций (15) параметр R выбран в соответствии с замечанием 5, т.е. $R>\frac{\textstyle 1}{\textstyle 4}\, \vert v_0\vert$, то

$$% latex2html id marker 15100 0\leq {\,\mathrm{opt}}(\ref{f15... ...ac{\textstyle 1}{\textstyle 4R} \tilde {u}^T Q^{-1} \tilde {u},$$

где $\tilde {u}$ -- нормальное решение (в смысле ${\,\mathrm{arg}}\min \{ u^T Q^{-1} u \mbox{$\,\mid\,$}$ $A^Tu \geq c$, $u\geq 0\})$ задачи L^*.

Д е й с т в и т е л ь н о, с одной стороны, согласно (17): ${\,\mathrm{opt}}(\ref{f16}) = (b,\ \tilde {u}) + \frac{\textstyle 1}{\textstyle 4R}\, \tilde {u}^T Q^{-1} \tilde {u} =$opt $L + \frac{\textstyle 1}{\textstyle 4R}\, \tilde {u}^T Q^{-1} \tilde {u}$; с
другой -- в соответствии с утверждением 2: opt(15)=opt(16), т.е.

$$% latex2html id marker 15120 0\leq {\,\mathrm{opt}}(\ref{f15}) -{\,\mathrm{opt}}L =$$

$$= (b,\ \tilde {u}) -{\,\mathrm{opt}}L + \frac{\textstyle 1}{\... ...\textstyle 1}{\textstyle 4R}\, \tilde {u}^T Q^{-1} \tilde {u},$$

что и требовалось.

3. Несобственные задачи квадратичного программирования

Метод тихоновской регуляризации и метод квадратичных штрафных функций допускают соединение в рамках одной задачи, соотнесенной задаче L, пусть в постановке (9). Построим задачи

$$\hspace*{-5mm} P: \max_{x\geq 0} \{(c, x) -\frac{\textstyle 1}{\textstyle 4r}\, x^T Qx -R\,(Ax-b)_+^T S (Ax-b)_+ \},$$ (19)

$$\begin{array}{c} P^*: \min \{(b, u) +\frac{\textstyle 1}{\t... ... +\\ [12pt] + r\,(c-A^Tu)_+^T Q^{-1} (c-A^Tu)_+ \}; \end{array}$$ (20)

здесь Q и S -- положительно определенные матрицы, R и r -- положительные параметры. Задачи P и P^* являются взаимно двойственными в смысле того правила формирования двойственности, которое было реализовано в ч. 1, в частности, формирование задачи (1)^* из (1) и (16) из (15). Конечно, сказанное требует обоснования, хотя и носит чисто выкладочный характер. В силу определенной громоздкости этих выкладок обоснование опускаем.

Для анализа связей между задачами P и L, а также P^* и L^*, выпишем отдельно задачи

$$\max\, \{(c,\ x) -\frac{\textstyle 1}{\textstyle 4r}\, x^T Qx\ \mbox{$\,\mid\,$}\ x\,\in\, M\},$$ (21)

$$\min\, \{(b,\ u) +\frac{\textstyle 1}{\textstyle 4R}\, u^T S^{-1}u\ \mbox{$\,\mid\,$}\ u\,\in\, M^*\},$$ (22)

где $M= \{ x\geq 0 \mbox{$\,\mid\,$}Ax\leq b\}$, $M^*=\{u\geq 0\ \mbox{$\,\mid\,$} A^Tu\geq c\}$. Двойственными к ним будут

$$\min_{u\geq 0}\, \{(b,\ u) +r\, (c-A^Tu)_+^T Q^{-1} (c-A^Tu)_+ \},\eqno (21)^*$$

$$\hspace*{-8mm}\max_{x\geq 0}\, \{(c,\ x) -R\,(Ax-b)_+^T S (Ax-b)_+ \}.\eqno (22)^*$$

Переход от задач (21) и (22) к P и P^* связан с применением к первым техники квадратичного метода штрафных функций, для которого имеют место оценки уклонения. А именно, если, например, речь идет о задаче

$$\max\,\{ f(x)\ \mbox{$\,\mid\,$}\ Ax\leq b,\ \ x\geq 0\}$$ (23)

и ее редукции к задаче

$$\max_{x\geq 0}\,\{ f(x) -R\,(Ax-b)_+^T S (Ax-b)_+ \},$$ (24)

то в ситуации разрешимости задачи (23) справедлива оценка

$$% latex2html id marker 15170 0\leq {\,\mathrm{opt}}(\ref{f24... ...textstyle 4R}\, \mbox{$\parallel$}\bar{u} \mbox{$\parallel$}^2,$$

где $\bar{u}\,\in\,$Arg(23)^* [см., например, [3], теорема 5.2]. Применительно к ситуации задачи (21) эта оценка запишется так:

$$% latex2html id marker 146100\leq {\,\mathrm{opt}}P -{\,\... ...tstyle 4R}\, \mbox{$\parallel$}\bar{u}_r \mbox{$\parallel$}^2,$$ (25)

где $\bar{u}_r\,\in\,$Arg(21)^*. В соответствии с (17) при достаточно большом r>0:

$$% latex2html id marker 15186 {\,\mathrm{arg}}(\ref{f21}) ={\... ...ox{$\,\mid\,$}\ x\,\in\, {\,\mathrm{Arg}}L\}\ (=:\ \tilde {x}),$$

следовательно,

$$% latex2html id marker 15188 {\,\mathrm{opt}}(\ref{f21}) = (... ...\frac{\textstyle 1}{\textstyle 4r}\, \tilde {x}^T Q \tilde {x}.$$

Используя это соотношение, получаем

$$% latex2html id marker 14631\begin{array}{c} \vert{\,\math... ...tyle 1}{\textstyle 4r}\, \tilde {x}^T Q \tilde {x}. \end{array}$$ (26)

Аналогично:

$$\vert{\,\mathrm{opt}}P^* -{\,\mathrm{opt}}L^*\vert \leq \fr... ...\textstyle 1}{\textstyle 4R}\, \tilde {u}^T S^{-1} \tilde {u},$$ (27)

где $\bar{x}_R\,\in\,$Arg(22)^*, $\tilde {u}\,\in\,$Arg $\min\,\{ u^T S^{-1} u\ \mbox{$\,\mid\,$} u\,\in\,$ArgL^*}. Подведем итоги (в форме теоремы) по совокупности свойств, связывающих задачи (19) и (20).

Теорема 3   Задачи P и P^* (т.е. (19) и (20)) связывают следующие утверждения:

1⁰.

P и P^* взаимно двойственны, в частности,
$P^* \stackrel {(*)}{\longrightarrow } (P^*)^* \equiv P$.

2⁰.

P и P^* разрешимы независимо от разрешимости или неразрешимости L.

3⁰.

${\,\mathrm{opt}}P ={\,\mathrm{opt}}P^*$.

4⁰.

Если E -- общее значение левых частей в соотношениях (26) и (27), то

$$E\leq \min \left\{ \frac{\textstyle 1}{\textstyle 4R}\, \mbox... ...yle 1}{\textstyle 4R}\, \tilde {u}^T S^{-1} \tilde {u} \right\}$$

(смысл $\bar{u}_r$ и $\bar{x}_R$ разъяснен выше).

Сделаем пояснения к каждому пункту сформулированной выше теоремы.

1. Чтобы получить вид задачи P^* как двойственной к P, вначале P следует переписать в виде
   
   $$\max\, \{ (c,\ x) - \frac{\textstyle 1}{\textstyle 4r}\, x^T Q x -R\, y^T Q y\ \mbox{$\,\mid\,$}$$
   
   
   
   
   $$\mbox{$\,\mid\,$}\ Ax-b\leq y,\ \ y\geq 0,\ \ x\geq 0\};$$
   
   
   далее, построить для нее функцию Лагранжа
   
   F(x,y;u,v,w) =
   
   
   
   
   $$\hspace*{-10mm} =(c, x) -\frac{\textstyle 1}{\textstyle 4r}\, x^T Q x -R\, y^T Q y -(u, Ax-b-y) +(v, x) +(w, y),$$
   
   
   через которую и строится двойственная задача в форме:
   
   $$\hspace*{-10mm} \min \{F(x,y;u,v,w) \mbox{$\,\mid\,$}\! \bigtriangledown _{[x,y]} F(x,y;u,v,w) =0, [u, v, w]\geq 0\}.$$
   
   
   Последняя же путем эквивалентных преобразований приводится к виду P^*. По аналогичной схеме проверяется и обратный переход, а именно:
   $P^* \stackrel {(*)}{\longrightarrow } (P^*)^* \equiv P$.
2. Разрешимость задач P и P^* будет следовать из проверки хотя бы того факта, что каждое из лебеговых множеств $f(x)\geq \mbox{$\alpha$}$, $f^*(u)\leq \mbox{$\beta$}$ выпукло и ограничено (может быть и пустым); здесь f(x) -- максимизируемая функция в задаче P, f^*(u) -- минимизируемая функция в задаче P^*, $\mbox{$\alpha$}$ и $\mbox{$\beta$}$ -- действительные числа.
3. Свойство 3⁰ вытекает из утверждения 1.
4. Оценка для E составляет содержание неравенств (26) и (27).

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

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. -M.: Наука, 1976. -190 с.
2. Еремин И.И. Несобственные задачи квадратичного программирования и вопросы регуляризации // Сб. `Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования''. -Свердловск: УНЦ АН СССР, 1985. -C. 47-53.
3. Еремин И.И. Противоречивые модели оптимального планирования.
   -M.: Наука, 1988. -160 с.