next up previous
Next: VI Задачи дизъюктивного программирования Up: book Previous: IV Двойственность для несобственных


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

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

\begin{displaymath}
\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 \},
\end{displaymath} (1)

в которой $\{ x,\ c_0 \}\,\subset $Rn, { Qk }k=0m -- матрицы размерности n x n. Сквозным образом будем предполагать матрицу Q0 положительно определенной (т.е. $x^T Q_0
x >0,\ \ \forall \,x\neq 0$), матрицы { Qj }j=1m -- неотрицательно определенными (т.е. $x^T Q_j x\geq 0,\ \ \forall \,x$). Если все Qj, $j=1,\,...\,,m$, -- нулевые матрицы, то (1) -- общая задача квадратичного программирования:
\begin{displaymath}
\max\,\{ (c_0,\ x) -x^T Q_0 x\ \mbox{$\,\mid\,$}\ Ax\leq b \};
\end{displaymath} (2)

здесь A -- матрица со строками aj, b -- вектор с координатами bj, $j=1,\,...\,,m$. Если в (2) вместо Q0 взять $\mbox{$\alpha$}\,Q_0$, $\mbox{$\alpha$}> 0$, то получим задачу
\begin{displaymath}
\max\,\{ (c_0,\ x) -\mbox{$\alpha$}\,x^T Q_0 x\ \mbox{$\,\mid\,$}\ Ax\leq b \},
\end{displaymath} (3)

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

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

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


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

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

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

с дифференцируемыми функциями {fk(x)}k=0m, то двойственной к P [1, § 23] является
\begin{displaymath}
P^*:\ \min\,\{ F(x,\ u)\ \mbox{$\,\mid\,$}\ \bigtriangledown _x F(x,\ u) =0,\ \ u\geq 0 \}.
\end{displaymath} (5)

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

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


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

10.
P разрешима.
20.
Функции {fk(x)}k=0m дифференцируемы.
30.
Существует допустимый для P вектор p такой, что fj(p)<0 для нелинейных fj(x) (условие регулярности).
Тогда P* разрешима, при этом ${\,\mathrm{opt}}P ={\,\mathrm{opt}}P^*$.

Далее функции {fk(x)}k=0m будут иметь вид, соответствующий задаче (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)]$, может быть эквивалентно преобразована к виду

\begin{displaymath}\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)^*\end{displaymath}

где $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]$ дают

\begin{displaymath}
F(x,\ u) = (b,\ u) + (c_0-A_0^Tu,\ x) -x^T Q_u x.
\end{displaymath} (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)* принимает вид

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

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

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

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

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

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

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

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

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

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

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

\begin{displaymath}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),\end{displaymath}

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

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

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

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

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

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

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

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

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

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

Теорема 1 (двойственности)   Пусть в задаче (1) Q0 -- положительно определенная матрица, {Qj}j=1k -- неотрицательно определенные. Если для ограничений задачи (1) выполнено условие регулярности (пусть в форме 30), то задачи (1) и (1)* разрешимы, при этом % latex2html id marker 14908
${\,\mathrm{opt}}(\ref{f1}) ={\,\mathrm{opt}}(1)^*$.

Д е й с т в и т е л ь н о, из совместности системы ограничений задачи (1) и ограниченности лебеговых множеств $\{x\ \mbox{$\,\mid\,$}\ f_0(x)\geq \mbox{$\alpha$}\}$, где f0(x) = (c0, x) -xT Q0 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)* принимает вид

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


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

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

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

задачу регуляризации (по Тихонову)
\begin{displaymath}
L_{reg}:\ \max\,\{ (c,\ x) -\mbox{$\alpha$}\,\mbox{$\paralle...
...box{$\parallel$}^2\ \mbox{$\,\mid\,$}\ Ax\leq b,\ \ x\geq 0 \}
\end{displaymath} (10)

и задачу, реализующую квадратичный метод штрафных функций,
\begin{displaymath}
L_{pen}: \max \{ (c, x) -R\, \mbox{$\parallel$}\,(Ax-b)_+\,\mbox{$\parallel$}^2 \mbox{$\,\mid\,$}x\geq 0\},\ R>0.
\end{displaymath} (11)

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

Если v0 -- двойственная оценка неравенства $(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$:

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

Если L разрешима и $\tilde {u}\,\in\,$ArgL*, то
\begin{displaymath}
0\leq {\,\mathrm{opt}}L_{pen} -{\,\mathrm{opt}}L \leq \frac...
...style 4R}\,
\mbox{$\parallel$}\tilde {u} \mbox{$\parallel$}^2.
\end{displaymath} (13)

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

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

С другой стороны, запишем задачу, двойственная к которой совпадала бы с Lpen. Такой задачей будет
\begin{displaymath}
(L^*)_{reg}: \min \{ (b, u) + \frac{\textstyle 1}{\textstyle...
... \mbox{$\parallel$}^2 \mbox{$\,\mid\,$}A^Tu\geq c,\ u\geq 0\}.
\end{displaymath} (14)

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

\begin{picture}
% latex2html id marker 14021
(120,85)(0,0)
\put(30,25){\makebox(...
...6){\makebox(0,0)[c]{(pen)}}
\put(60,8){\makebox(0,0)[c]{Схема~1}}
\end{picture}

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

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

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

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

соотнесенную задаче L в соответствии с квадратичным методом штрафных функций; здесь R>0 -- штрафной параметр, Q -- положительно определенная матрица. В соответствии со схемой двойственности (1) $\rightarrow
(1)^*$ задача (15) будет двойственной к
\begin{displaymath}
\min \{ (b, u) +\frac{\textstyle 1}{\textstyle 4R}\, u^T Q^{-1} u \mbox{$\,\mid\,$}A^Tu\geq
c,\ u\geq 0\},
\end{displaymath} (16)

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

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

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

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

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

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

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

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

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

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

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

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

Д е й с т в и т е л ь н о, с одной стороны, согласно (17): % latex2html id marker 15116
${\,\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), т.е.

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


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

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


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

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

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


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

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

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

    $\displaystyle \max\, \{(c,\ x) -\frac{\textstyle 1}{\textstyle 4r}\, x^T Qx\ \mbox{$\,\mid\,$}\ x\,\in\,
M\},$ (21)
    $\displaystyle \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\}$. Двойственными к ним будут

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


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

Переход от задач (21) и (22) к P и P* связан с применением к первым техники квадратичного метода штрафных функций, для которого имеют место оценки уклонения. А именно, если, например, речь идет о задаче
\begin{displaymath}
\max\,\{ f(x)\ \mbox{$\,\mid\,$}\ Ax\leq b,\ \ x\geq 0\}
\end{displaymath} (23)

и ее редукции к задаче
\begin{displaymath}
\max_{x\geq 0}\,\{ f(x) -R\,(Ax-b)_+^T S (Ax-b)_+ \},
\end{displaymath} (24)

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

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

где $\bar{u}\,\in\,$Arg(23)* [см., например, [3], теорема 5.2]. Применительно к ситуации задачи (21) эта оценка запишется так:
\begin{displaymath}
% latex2html id marker 146100\leq {\,\mathrm{opt}}P -{\,\...
...tstyle 4R}\,
\mbox{$\parallel$}\bar{u}_r \mbox{$\parallel$}^2,
\end{displaymath} (25)

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

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

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

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

Используя это соотношение, получаем
\begin{displaymath}
% latex2html id marker 14631\begin{array}{c}
\vert{\,\math...
...tyle 1}{\textstyle 4r}\, \tilde {x}^T Q \tilde {x}.
\end{array}\end{displaymath} (26)

Аналогично:
\begin{displaymath}
\vert{\,\mathrm{opt}}P^* -{\,\mathrm{opt}}L^*\vert \leq \fr...
...\textstyle 1}{\textstyle 4R}\, \tilde {u}^T S^{-1} \tilde {u},
\end{displaymath} (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)) связывают следующие утверждения:
10.
P и P* взаимно двойственны, в частности,
$P^* \stackrel {(*)}{\longrightarrow } (P^*)^* \equiv P$.
20.
P и P* разрешимы независимо от разрешимости или неразрешимости L.
30.
${\,\mathrm{opt}}P ={\,\mathrm{opt}}P^*$.
40.
Если E -- общее значение левых частей в соотношениях (26) и (27), то

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

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

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

  1. Чтобы получить вид задачи P* как двойственной к P, вначале P следует переписать в виде

    \begin{displaymath}\max\, \{ (c,\ x) - \frac{\textstyle 1}{\textstyle 4r}\, x^T Q x -R\, y^T Q y\ \mbox{$\,\mid\,$}\end{displaymath}


    \begin{displaymath}\mbox{$\,\mid\,$}\ Ax-b\leq y,\ \ y\geq 0,\ \ x\geq 0\};\end{displaymath}

    далее, построить для нее функцию Лагранжа

    F(x,y;u,v,w) =


    \begin{displaymath}\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),\end{displaymath}

    через которую и строится двойственная задача в форме:

    \begin{displaymath}\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\}.\end{displaymath}

    Последняя же путем эквивалентных преобразований приводится к виду 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. Свойство 30 вытекает из утверждения 1.
  4. Оценка для E составляет содержание неравенств (26) и (27).

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

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


next up previous
Next: VI Задачи дизъюктивного программирования Up: book Previous: IV Двойственность для несобственных
Список научных трудов Еремина И.И.
e-mail: Еремин И.И.
TopList