一个优化问题是否满足强对偶性是不容易检验的, 所以需要对凸优化问题给出一个方便的检验条件, 即所谓 Slater 条件.
考虑凸优化问题 { min ? f 0 ( x ) s.t? f i ( x ) ≤ 0 , i = 1 , ? ? , p , A x = b , x ∈ Ω , \begin{align} \begin{cases}\min f_0(x)\\\text{s.t}~f_i(x)\leq0,\quad i=1,\cdots,p,\\Ax=b,\\x\in\Omega,\end{cases}\end{align} ? ? ??minf0?(x)s.t?fi?(x)≤0,i=1,?,p,Ax=b,x∈Ω,???其中 { f i } i = 0 p \{f_i\}_{i=0}^p {fi?}i=0p? 是凸函数， A ∈ R q × n , b ∈ R q , Ω ? R n A\in\mathbb{R}^{q\times n},b\in\mathbb{R}^q,\Omega\subset\mathbb{R}^n A∈Rq×n,b∈Rq,Ω?Rn 是一个凸集. 我们假设约束函数 f 1 , . . . , f p f_1,...,f_p f1?,...,fp? 如下条件满足： ? ∞ < f i ( x ) < ∞ , i = 0 , 1 , ? ? , p , ? x ∈ Ω . \begin{align} -\infty<f_i(x)<\infty,\quad i=0,1,\cdots,p,\quad\forall x\in\Omega.\end{align} ?∞<fi?(x)<∞,i=0,1,?,p,?x∈Ω.??
定义 4.1 (Slater 条件) 对于凸优化问题(5.4.1), 若存在
x
0
∈
D
∩
r
i
(
Ω
)
x_0\in\mathcal{D}\cap\mathbf{ri}(\Omega)
x0?∈D∩ri(Ω), 满足
f
i
(
x
0
)
<
0
,
i
=
1
,
?
?
,
p
,
f_i(x_0)<0,\quad i=1,\cdots,p,
fi?(x0?)<0,i=1,?,p,
定义 4.2 (弱 Slater 条件) 对于本节中的优化问题(1), 若
{
f
i
}
i
=
1
p
\{f_i\}_{i=1}^p
{fi?}i=1p? 中非仿射函数
f
i
f_i
fi? 都存在严格可行点，即存在
x
i
∈
D
x_i\in\mathcal{D}
xi?∈D 使得
f
i
(
x
i
)
<
0
f_i(x_i)<0
fi?(xi?)<0,且
D
∩
r
i
(
Ω
)
≠
?
\mathcal{D}\cap\mathbf{ri}(\Omega)\neq\emptyset
D∩ri(Ω)=?, 则称其满足弱
S
l
a
t
e
r
Slater
Slater 条件.
注：当所有约束函数均为仿射函数且 Ω = R n \Omega=\mathbb{R}^n Ω=Rn 时，弱 Slater 条件即为 D ≠ ? . D\neq\emptyset. D=?.
对于仅含集约束的优化问题 { min ? f 0 ( x ) s.t x ∈ Ω , \begin{cases}\min f_0(x)\\\text{s.t}\quad x\in\Omega,\end{cases} {minf0?(x)s.tx∈Ω,?有 D = Ω \mathcal{D}=\Omega D=Ω.定义其 Largrane 函数为 L ( x ) : = f 0 ( x ) L(x):=f_0(x) L(x):=f0?(x). 相应的对偶函数为 g ( λ , μ ) : = inf ? x ∈ Ω L ( x ) = inf ? x ∈ D f 0 ( x ) = ξ ? . g(\lambda,\mu):=\inf_{x\in\Omega}L(x)=\inf_{x\in\mathcal{D}}f_0(x)=\xi^*. g(λ,μ):=x∈Ωinf?L(x)=x∈Dinf?f0?(x)=ξ?.因而对偶问题的最优值为 η ? = ξ ? \eta^*=\xi^* η?=ξ?, 强对偶性满足，而且对偶问题是可解的.
定理 4.1 ( S l a t e r ) \mathrm{( Slater) } (Slater) 设本小节的凸优化问题 { min ? f 0 ( x ) s.t? f i ( x ) ≤ 0 , i = 1 , ? ? , p , A x = b , x ∈ Ω , \begin{cases}\min f_0(x)\\\text{s.t}~f_i(x)\leq0,\quad i=1,\cdots,p,\\Ax=b,\\x\in\Omega,\end{cases} ? ? ??minf0?(x)s.t?fi?(x)≤0,i=1,?,p,Ax=b,x∈Ω,?满足 ? ∞ < f i ( x ) < ∞ , i = 0 , 1 , ? ? , p , ? x ∈ Ω . -\infty<f_i(x)<\infty,\quad i=0,1,\cdots,p,\quad\forall x\in\Omega. ?∞<fi?(x)<∞,i=0,1,?,p,?x∈Ω., 且可以满足 定义 4.2 所述的弱 ( S l a t e r ) \mathrm{( Slater) } (Slater) 条件，那么强对偶性成立，且对偶问题是可解的.
Emmm，由于这个命题需要证明的引理太多了，我就偷个懒好啦~
虽然没有把证明写出来, 但有点还是需要说明的，即存在不满足强对偶性的凸优化问题，比如下例.
例 4.2 如下优化问题是凸的, 但不满足强对偶性. { min ? e ? x s.t? x 2 / y ≤ 0 , ( x , y ) ∈ Ω , \begin{cases}\min e^{-x}\\\text{s.t }x^2/y\leq0,\\(x,y)\in\Omega,\end{cases} ? ? ??mine?xs.t?x2/y≤0,(x,y)∈Ω,?其中 Ω : = { ( x , y ) ∣ x ∈ R , ? y > 0 } \Omega:=\{(x,y)|x\in\mathbb{R},\mathrm{~}y>0\} Ω:={(x,y)∣x∈R,?y>0}
证. 根据凸函数的定义，可以判断 x 2 / y x^2/y x2/y 是凸的，于是该优化问题是凸问题 ，可行集为 D = { ( x , y ) ∈ Ω ∣ x 2 ≤ 0 } = { ( 0 , y ) ∣ y > 0 } . \mathcal{D}=\{(x,y)\in\Omega|x^2\leq0\}=\{(0,y)|y>0\}. D={(x,y)∈Ω∣x2≤0}={(0,y)∣y>0}.因而其最优值为 ξ ? = inf ? ( x , y ) ∈ D e ? x = 1. \xi^*=\inf_{(x,y)\in\mathcal{D}}e^{-x}=1. ξ?=inf(x,y)∈D?e?x=1.
根据定义可以写出其 Lagrange 函数 L ( x , y , λ ) : = e ? x + λ x 2 / y L(x,y,\lambda):=e^{-x}+\lambda x^2/y L(x,y,λ):=e?x+λx2/y, 所以对偶函数为 g ( λ ) = inf ? ( x , y ) ∈ Ω L ( x , y , λ ) = inf ? x ∈ R , y > 0 ( e ? x + λ x 2 / y ) = { 0 ? λ ≥ 0 , ? ∞ λ < 0. g(\lambda)=\inf_{(x,y)\in\Omega}L(x,y,\lambda)=\inf_{x\in\mathbb{R},y>0}(e^{-x}+\lambda x^2/y)=\begin{cases}0&\forall\lambda\ge0,\\[2ex]-\infty&\lambda<0.\end{cases} g(λ)=(x,y)∈Ωinf?L(x,y,λ)=x∈R,y>0inf?(e?x+λx2/y)=? ? ??0?∞??λ≥0,λ<0.?
于是 η ? = sup ? λ ≥ 0 g ( λ ) = 0 ≠ ξ ? \eta^*=\sup_{\lambda\geq0}g(\lambda)=0\neq\xi^* η?=supλ≥0?g(λ)=0=ξ?. 所以强对偶性不成立.
优化问题
{
min
?
f
0
(
x
)
s
.
t
f
i
(
x
)
≤
0
,
i
=
1
,
?
?
,
p
,
h
j
(
x
)
=
0
,
j
=
1
,
?
?
,
q
,
x
∈
Ω
,
\begin{align} \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\Omega,\end{cases}\end{align}
?
?
??minf0?(x)s.tfi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q,x∈Ω,???的不等式约束和等式约束统称为代数约束, 而称约束
x
∈
?
x ∈ ?
x∈? 为集
约束. 实际上这两种约束常常可以等价地相互表示, 所得到的优化问题是同解的. 类似地,当优化问题的目标函数
f
0
f_0
f0? 取值为无穷大时, 可以将之转换为集约束. 这些转换虽然不影响原问题的同解性, 但它们的对偶问题却发生了变化.
将上述的优化问题进行适当变形后可以得到一个新的优化问题，设原问题及其对偶问题的最优值分别为 ξ ? \xi^* ξ? 和 η ? ; \eta^*; η?; 设新问题及其对偶问题的最优值分别为 ξ ~ ? \tilde{\xi}^* ξ~?? 和 η ~ ? \tilde{\eta}^* η~??. 下面看看 ξ ? \xi^* ξ? 与 ξ ~ ? \tilde{\xi}^* ξ~?? 以及 η ? \eta^* η? 与 η ~ ? \tilde{\eta}^* η~?? 有哪些数值关系.
对于优化问题(3)，当 f 0 , f 1 , . . . , f p f_0,f_1,...,f_p f0?,f1?,...,fp? 的取值范围为 R ∪ { ∞ } \mathbb{R}\cup\{\infty\} R∪{∞} 时，考虑如下优化问题 { min ? f 0 ( x ) s.t?? f i ( x ) ≤ 0 , i = 1 , ? ? , p , h j ( x ) = 0 , j = 1 , ? ? , q , x ∈ Ω ~ , \begin{align}\begin{cases}\min f_0(x)\\\text{s.t }~f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\tilde{\Omega},\\\end{cases}\end{align} ? ? ??minf0?(x)s.t??fi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q,x∈Ω~,???
其中 Ω ^ : = { x ∈ Ω ∣ f i ( x ) < ∞ , i = 0 , 1 , . . . , p } . \begin{align}\hat{\Omega}:=\{x\in\Omega|f_i(x)<\infty,i=0,1,...,p\}.\end{align} Ω^:={x∈Ω∣fi?(x)<∞,i=0,1,...,p}.??
根据
Ω
^
\hat{\Omega}
Ω^ 的定义可以知道
Ω
~
?
Ω
\tilde{\Omega}\subset\Omega
Ω~?Ω 且其可行集为
D
~
=
D
∩
d
o
m
(
f
0
)
.
\tilde{\mathcal{D}}=\mathcal{D}\cap\mathrm{dom}(f_0).
D~=D∩dom(f0?). 由于
f
0
(
x
)
=
∞
,
?
?
x
∈
D
?
d
o
m
(
f
0
)
f_0(x)=\infty,\mathrm{~}\forall x\in\mathcal{D}\setminus\mathrm{dom}(f_0)
f0?(x)=∞,??x∈D?dom(f0?)，所以有
ξ
?
~
:
=
inf
?
x
∈
D
~
f
0
(
x
)
=
inf
?
x
∈
D
f
0
(
x
)
=
ξ
?
.
\tilde{\xi^*}:=\inf_{x\in\tilde{\mathcal{D}}}f_0(x)=\inf_{x\in\mathcal{D}}f_0(x)=\xi^*.
ξ?~?:=x∈D~inf?f0?(x)=x∈Dinf?f0?(x)=ξ?.这说明(4)与原问题(3)同解. 又根据下确界
inf
\text{inf}
inf 的性质有
g
~
(
λ
,
μ
)
:
=
inf
?
x
∈
Ω
~
L
(
x
,
λ
,
μ
)
≥
inf
?
x
∈
Ω
L
(
x
,
λ
,
μ
)
=
g
(
λ
,
μ
)
.
\tilde{g}(\lambda,\mu):=\inf_{x\in\tilde{\Omega}}L(x,\lambda,\mu)\geq\inf_{x\in\Omega}L(x,\lambda,\mu)=g(\lambda,\mu).
g~?(λ,μ):=x∈Ω~inf?L(x,λ,μ)≥x∈Ωinf?L(x,λ,μ)=g(λ,μ).所以
η
~
?
≥
η
?
.
\tilde{\eta}^*\geq\eta^*.
η~??≥η?.
特别地，如果将(5)替换成下式 Ω ~ : = { x ∈ Ω ∣ f 0 ( x ) < ∞ } . \begin{align} \tilde{\Omega}:=\{x\in\Omega|f_0(x)<\infty\}.\end{align} Ω~:={x∈Ω∣f0?(x)<∞}.??那么 L ( x , λ , μ ) = ∞ , ? ? x ∈ Ω ? Ω ~ L(x,\lambda,\mu)=\infty,\:\forall x\in\Omega\setminus\tilde{\Omega} L(x,λ,μ)=∞,?x∈Ω?Ω~, 从而 g ( λ , μ ) = inf ? x ∈ Ω L ( x , λ , μ ) = inf ? x ∈ Ω ~ L ( x , λ , μ ) = g ~ ( λ , μ ) , g(\lambda,\mu)=\inf_{x\in\Omega}L(x,\lambda,\mu)=\inf_{x\in\tilde{\Omega}}L(x,\lambda,\mu)=\tilde{g}(\lambda,\mu), g(λ,μ)=x∈Ωinf?L(x,λ,μ)=x∈Ω~inf?L(x,λ,μ)=g~?(λ,μ),因而 η ~ ? = η ? \tilde{\eta}^*=\eta^* η~??=η?.综上所述，可以得到如下的命题.
命题 5.1.1 设优化问题(3)满足
{
?
∞
<
f
i
(
x
)
≤
∞
i
=
0
,
1
,
?
?
,
p
,
?
∞
<
h
j
(
x
)
<
∞
j
=
1
,
?
?
,
q
,
?
x
∈
Ω
.
\begin{cases}-\infty<f_i(x)\leq\infty&i=0,1,\cdots,p,\\-\infty<h_j(x)<\infty&j=1,\cdots,q,\end{cases}\quad\forall x\in\Omega.
{?∞<fi?(x)≤∞?∞<hj?(x)<∞?i=0,1,?,p,j=1,?,q,??x∈Ω., 记问题(3)和(4)的对偶函数分别为
g
(
λ
,
μ
)
g(\lambda,\mu)
g(λ,μ) 和
g
~
(
λ
,
μ
)
\tilde{g}(\lambda,\mu)
g~?(λ,μ),那么
ξ
~
?
:
=
inf
?
x
∈
D
~
f
0
(
x
)
=
inf
?
x
∈
D
f
0
(
x
)
=
ξ
?
,
g
~
(
λ
,
μ
)
≥
g
(
λ
,
μ
)
,
?
λ
∈
R
+
p
,
μ
∈
R
q
.
\tilde\xi^*:=\inf_{x\in\tilde D}f_0(x)=\inf_{x\in\mathcal D}f_0(x)=\xi^*,\quad\tilde g(\lambda,\mu)\geq g(\lambda,\mu),\quad\forall\lambda\in\mathbb R_+^p,\quad\mu\in\mathbb R^q.
ξ~??:=x∈D~inf?f0?(x)=x∈Dinf?f0?(x)=ξ?,g~?(λ,μ)≥g(λ,μ),?λ∈R+p?,μ∈Rq.因而，
η
~
?
≥
η
?
\tilde{\eta}^*\geq\eta^*
η~??≥η?. 特别，若将(5)所定义的
Ω
~
\tilde{\Omega}
Ω~ 替换成(6), 那么
η
~
?
=
η
?
\tilde{\eta}^*=\eta^*
η~??=η?.
如果我们回顾第4小节中的Slater 定理可以发现，优化问题(1)中的目标函数 f 0 f_{0} f0? 和约束函数 f 1 , . . . , f p f_1,...,f_p f1?,...,fp? 都是有限取值，利用上述的命题 5.1.1可以将Slater 定理推广如下：
推论 5.1.2 (Slater 定理的推广) 对凸优化问题(1), 若如下条件满足：
(1) 对任意的 x ∈ Ω x\in\Omega x∈Ω 有 : ? ∞ < f 0 ( x ) ≤ ∞ :-\infty<f_0(x)\leq\infty :?∞<f0?(x)≤∞, 且 ? ∞ < f i ( x ) < ∞ , ? i = 1 , . . . , p ; -\infty<f_i(x)<\infty,\:i=1,...,p; ?∞<fi?(x)<∞,i=1,...,p;
(2) { f i } i = 1 p \left\{f_i\right\}_{i=1}^p {fi?}i=1p? 中非仿射函数 f i f_i fi? 都存在 x i ∈ D ∩ d o m ( f 0 ) x_i\in\mathcal{D}\cap\mathbf{dom}(f_0) xi?∈D∩dom(f0?) 使得 f i ( x i ) < 0 f_i(x_i)<0 fi?(xi?)<0;
(3) D ∩ r i ( Ω ∩ d o m ( f 0 ) ) ≠ ? \mathcal{D}\cap\mathbf{ri}(\Omega\cap\mathbf{dom}(f_0))\neq\emptyset D∩ri(Ω∩dom(f0?))=?,
则强对偶性成立，且对偶问题的最优值是可解的.
证.考虑如下凸优化问题: { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p , A x = b , x ∈ Ω ~ , \begin{align}\begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\\quad Ax=b,\\\quad x\in\tilde{\Omega},&\end{cases}\end{align} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p,Ax=b,x∈Ω~,????其中 Ω ~ : = Ω ∩ d o m ( f 0 ) \tilde{\Omega}:=\Omega\cap\mathbf{dom}(f_0) Ω~:=Ω∩dom(f0?).记 ξ ~ ? \tilde{\xi}^* ξ~?? 和 η ~ ? \tilde{\eta}^* η~?? 是问题(7)及其对偶问题的最优值. 易见，问题(7)的可行集为 D ~ = D ∩ d o m ( f 0 ) \tilde{D} = \mathcal{D} \cap \mathbf{dom}( f_0) D~=D∩dom(f0?). 由此可见问题 (7)满足 Slater 定理 4.1 的全部条件，因而 ξ ~ ? = η ~ ? \tilde{\xi}^*=\tilde{\eta}^* ξ~??=η~??,并且 (7)的对偶问题的最优值 η ~ ? \tilde{\eta}^* η~?? 是可解的.
根据 命题 5.1.1可以知道，问题(7)和问题(1)是同解的，并且相应的对偶问题也是同解的，于是(1)也是强对偶并且对偶问题是可解的.
对于优化问题(3)，即优化问题 { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p , h j ( x ) = 0 , j = 1 , ? ? , q , x ∈ Ω , \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\Omega,\end{cases} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q,x∈Ω,?，设其可行集为 D \mathcal{D} D.如果将该优化问题的一个不等式约束转换为集合约束，便能够得到如下的问题： { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p ? 1 , h j ( x ) = 0 , j = 1 , ? ? , q , x ∈ Ω ~ , \begin{align} \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p-1,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\tilde{\Omega},\end{cases}\end{align} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p?1,hj?(x)=0,j=1,?,q,x∈Ω~,???其中 { Ω ~ : = { x ∈ Ω ∣ f p ( x ) ≤ 0 } , D ~ : = { x ∈ Ω ~ ∣ f i ( x ) ≤ 0 , i = 1 , ? ? , p ? 1 ; h j ( x ) = 0 , j = 1 , ? ? , q } = D . \begin{cases}\tilde{\Omega}:=\{x\in\Omega|f_p(x)\leq0\},\\\tilde{\mathcal{D}}:=\{x\in\tilde{\Omega}|f_i(x)\leq0,i=1,\cdots,p-1;h_j(x)=0,j=1,\cdots,q\}=\mathcal{D}.\end{cases} {Ω~:={x∈Ω∣fp?(x)≤0},D~:={x∈Ω~∣fi?(x)≤0,i=1,?,p?1;hj?(x)=0,j=1,?,q}=D.?，由于 D ~ = D \tilde{\mathcal{D}}=\mathcal{D} D~=D，于是问题(8)与问题(3)是同解的.下面我们来看看这两个问题的对偶问题是否改变了.
根据这两个集合的定义可以知道
D
~
?
Ω
~
\tilde{\mathcal{D}}\subset\tilde{\Omega}
D~?Ω~，其 Lagrange 函数为
L
~
(
x
,
λ
~
,
μ
)
:
=
f
0
(
x
)
+
∑
i
=
1
p
?
1
λ
~
i
f
i
(
x
)
+
∑
j
=
1
q
μ
j
h
j
(
x
)
.
\tilde{L}(x,\tilde{\lambda},\mu):=f_0(x)+\sum_{i=1}^{p-1}\tilde{\lambda}_if_i(x)+\sum_{j=1}^q\mu_jh_j(x).
L~(x,λ~,μ):=f0?(x)+i=1∑p?1?λ~i?fi?(x)+j=1∑q?μj?hj?(x).根据这些记号，下面给出如下的命题.
命题 5.2.1 设优化问题(3)和优化问题(8)的对偶函数分别为 g ( λ , μ ) g(\lambda,\mu) g(λ,μ) 和 g ~ ( λ ~ , μ ) \tilde{g}(\tilde{\lambda},\mu) g~?(λ~,μ), 那么 ? λ : = \forall\lambda:= ?λ:= ( λ ~ T , λ p ) T ∈ R + p , ? μ ∈ R q (\tilde{\lambda}^T,\lambda_p)^T\in\mathbb{R}_+^p,\:\mu\in\mathbb{R}^q (λ~T,λp?)T∈R+p?,μ∈Rq,有 g ( λ , μ ) ≤ g ~ ( λ ~ , μ ) g(\lambda,\mu)\leq\tilde{g}(\tilde{\lambda},\mu) g(λ,μ)≤g~?(λ~,μ).从而 sup ? λ ? 0 g ( λ , μ ) ≤ sup ? λ ~ ? 0 g ~ ( λ ~ , μ ) ≤ inf ? x ∈ D ~ f 0 ( x ) = inf ? x ∈ D f 0 ( x ) . \sup\limits_{\lambda\succeq0}g(\lambda,\mu)\leq\sup\limits_{\tilde{\lambda}\succeq0}\tilde{g}(\tilde{\lambda},\mu)\leq\inf\limits_{x\in\tilde{\mathcal{D}}}f_0(x)=\inf\limits_{x\in\mathcal{D}}f_0(x). λ?0sup?g(λ,μ)≤λ~?0sup?g~?(λ~,μ)≤x∈D~inf?f0?(x)=x∈Dinf?f0?(x).因而，当问题(3)满足强对偶性时，问题(8) 亦然，且二者的对偶问题具有相同的最优值.
证.根据拉格朗日函数的定义，问题 (3)的 Lagrange 函数为 L ( x , λ , μ ) = L ~ ( x , λ ~ , μ ) + λ p f p ( x ) . L(x,\lambda,\mu)=\tilde{L}(x,\tilde{\lambda},\mu)+\lambda_pf_p(x). L(x,λ,μ)=L~(x,λ~,μ)+λp?fp?(x).因而有： ? λ : = ( λ ~ T , λ p ) T ∈ R + p , ? μ ∈ R q . ??由于? Ω ~ ? Ω , ??有 \forall\lambda:=(\tilde{\lambda}^T,\lambda_p)^T\in\mathbb{R}_+^p,~\mu\in\mathbb{R}^q.~\text{ 由于 }\tilde{\Omega}\subset\Omega,~\text{\ 有} ?λ:=(λ~T,λp?)T∈R+p?,?μ∈Rq.??由于?Ω~?Ω,??有 g ( λ , μ ) = inf ? x ∈ Ω L ( x , λ , μ ) ≤ inf ? x ∈ Ω ~ L ( x , λ , μ ) ≤ inf ? x ∈ Ω ~ L ~ ( x , λ ~ , μ ) = g ~ ( λ ~ , μ ) . g(\lambda,\mu)=\inf_{x\in\Omega}L(x,\lambda,\mu)\leq\inf_{x\in\tilde{\Omega}}L(x,\lambda,\mu)\leq\inf_{x\in\tilde{\Omega}}\tilde{L}(x,\tilde{\lambda},\mu)=\tilde{g}(\tilde{\lambda},\mu). g(λ,μ)=x∈Ωinf?L(x,λ,μ)≤x∈Ω~inf?L(x,λ,μ)≤x∈Ω~inf?L~(x,λ~,μ)=g~?(λ~,μ).
根据问题(8)的弱对偶性，以及上述不等式，有 sup ? λ ? 0 g ( λ , μ ) ≤ sup ? λ ~ ? 0 g ~ ( λ ~ , μ ) ≤ inf ? x ∈ D ~ f 0 ( x ) = inf ? x ∈ D f 0 ( x ) . \sup_{\lambda\succeq0}g(\lambda,\mu)\leq\sup_{\tilde{\lambda}\succeq0}\tilde{g}(\tilde{\lambda},\mu)\leq\inf_{x\in\tilde{\mathcal{D}}}f_0(x)=\inf_{x\in\mathcal{D}}f_0(x). λ?0sup?g(λ,μ)≤λ~?0sup?g~?(λ~,μ)≤x∈D~inf?f0?(x)=x∈Dinf?f0?(x).所以这就证明了优化问题(3)的强对偶性可以推出优化问题(8)的强对偶性，且两个优化问题有相同的最优值.
此外，如果将优化问题(3)的一个等式约束转换为集约束，也就是考虑如下的优化问题： { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p , h j ( x ) = 0 , j = 1 , ? ? , q ? 1 , x ∈ Ω ~ , \begin{align} \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q-1,\\x\in\tilde{\Omega},\end{cases}\end{align} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q?1,x∈Ω~,???其中 { Ω ~ : = { x ∈ Ω ∣ f p ( x ) ≤ 0 } , D ~ : = { x ∈ Ω ~ ∣ f i ( x ) ≤ 0 , i = 1 , ? ? , p ; h j ( x ) = 0 , j = 1 , ? ? , q ? 1 } = D . \begin{cases}\tilde{\Omega}:=\{x\in\Omega|f_p(x)\leq0\},\\\tilde{\mathcal{D}}:=\{x\in\tilde{\Omega}|f_i(x)\leq0,i=1,\cdots,p;h_j(x)=0,j=1,\cdots,q-1\}=\mathcal{D}.\end{cases} {Ω~:={x∈Ω∣fp?(x)≤0},D~:={x∈Ω~∣fi?(x)≤0,i=1,?,p;hj?(x)=0,j=1,?,q?1}=D.?，由于 D ~ = D \tilde{\mathcal{D}}=\mathcal{D} D~=D，可以用类似于上述命题的方法证明如下的命题，证明就不贴上来了，因为方法是类似的.
命题 5.2.2 设优化问题(3)和优化问题(9)的对偶函数分别为 g ( λ , μ ) g(\lambda,\mu) g(λ,μ) 和 g ~ ( λ ~ , μ ) \tilde{g}(\tilde{\lambda},\mu) g~?(λ~,μ), 那么 ? μ : = \forall\mu:= ?μ:= ( μ ~ T , μ p ) T ∈ R + p , ? λ ∈ R q (\tilde{\mu}^T,\mu_p)^T\in\mathbb{R}_+^p,\:\lambda\in\mathbb{R}^q (μ~?T,μp?)T∈R+p?,λ∈Rq,有 g ( λ , μ ) ≤ g ~ ( λ , μ ~ ) g(\lambda,\mu)\leq\tilde{g}(\lambda,\tilde{\mu}) g(λ,μ)≤g~?(λ,μ~?).从而 sup ? λ ? 0 g ( λ , μ ) ≤ sup ? λ ? 0 g ~ ( λ , μ ~ ) ≤ inf ? x ∈ D ~ f 0 ( x ) = inf ? x ∈ D f 0 ( x ) . \sup\limits_{\lambda\succeq0}g(\lambda,\mu)\leq\sup\limits_{\lambda\succeq0}\tilde{g}(\lambda,\tilde{\mu})\leq\inf\limits_{x\in\tilde{\mathcal{D}}}f_0(x)=\inf\limits_{x\in\mathcal{D}}f_0(x). λ?0sup?g(λ,μ)≤λ?0sup?g~?(λ,μ~?)≤x∈D~inf?f0?(x)=x∈Dinf?f0?(x).因而，当问题(3)满足强对偶性时，问题(9) 亦然，且二者的对偶问题具有相同的最优值.
这节的标题是对偶的对偶，不经会引人发问：对偶的对偶会不会类似于负负得正一样而变回原问题呢？好吧，先卖个关子，具体如何先看下文.
考虑如下问题： { min ? ? g ( λ , μ ) s . t ? λ ? 0 \begin{align}\begin{cases}\min-g(\lambda,\mu)\\\mathrm{s.t}\quad-\lambda\preceq0&\end{cases}\end{align} {min?g(λ,μ)s.t?λ?0????的对偶，并称之为原问题 { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p , h j ( x ) = 0 , j = 1 , ? ? , q , x ∈ Ω , \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\Omega,\end{cases} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q,x∈Ω,?的二次对偶问题.此外，补充定义 g ( λ , μ ) g(\lambda,\mu) g(λ,μ) 在 λ ? 0 \lambda\prec 0 λ?0 处的值为 ? ∞ -\infty ?∞，于是(10)的拉格朗日函数和对偶函数分别为 L d u a l ( λ , μ , α ) : = ? [ g ( λ , μ ) + α T λ ] 和 g d u a l ( α ) : = inf ? λ , μ L d u a l ( λ , μ , α ) . L_\mathrm{dual}(\lambda,\mu,\alpha):=-[g(\lambda,\mu)+\alpha^T\lambda]\quad\text{和}\quad g_\mathrm{dual}(\alpha):=\inf_{\lambda,\mu}L_\mathrm{dual}(\lambda,\mu,\alpha). Ldual?(λ,μ,α):=?[g(λ,μ)+αTλ]和gdual?(α):=λ,μinf?Ldual?(λ,μ,α).因此，(10)的对偶问题就是 { max ? g d u a l ( α ) s . t ? α ? 0. \begin{align}\begin{cases}\max g_{\mathrm{dual}}(\alpha)\\\mathrm{s.t~}\alpha\succeq0.&\end{cases}\end{align} {maxgdual?(α)s.t?α?0.????好了，现在来回答一下我们在开头的疑问，一般情况下，对偶的对偶未必就是原问题.实际上我们可以发现，二次对偶函数 g d u a l ( α ) g_{dual}(\alpha) gdual?(α) 的变量 α \alpha α 与 λ \lambda λ 是同维数的，是原问题(3)的不等式约束的个数，所以与原问题的变量 x x x 的维度并不一定相同，也就是说二次对偶问题不一定能够回到原问题.
设 ξ d u a l ? \xi_\mathrm{dual}^* ξdual?? 和 η d u a l ? \eta_\mathrm{dual}^* ηdual?? 分别是问题(10) 及其对偶问题(11)的最优值， ξ ? \xi^* ξ? 和 η ? \eta^* η? 分别是原问题(3)及其对偶问题的最优值. 显然有 η d u a l ? ≤ ξ d u a l ? = ? η ? \eta_\mathrm{dual}^*\leq\xi_\mathrm{dual}^*=-\eta^* ηdual??≤ξdual??=?η?. 那么又会有一个自然的问题：二次对偶的最优值 η d u a l ? \eta_\mathrm{dual}^* ηdual?? 与原问题的最优值 ξ ? \xi^* ξ? 有什么关系？先看下面的命题.
命题 6.1 (对偶之对偶) 设优化问题(3)即 { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p , h j ( x ) = 0 , j = 1 , ? ? , q , x ∈ Ω , \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\Omega,\end{cases} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q,x∈Ω,?满足条件 { ? ∞ < f i ( x ) ≤ ∞ i = 0 , 1 , ? ? , p , ? ∞ < h j ( x ) < ∞ j = 1 , ? ? , q , ? x ∈ Ω . \begin{cases}-\infty<f_i(x)\leq\infty&i=0,1,\cdots,p,\\-\infty<h_j(x)<\infty&j=1,\cdots,q,\end{cases}\quad\forall x\in\Omega. {?∞<fi?(x)≤∞?∞<hj?(x)<∞?i=0,1,?,p,j=1,?,q,??x∈Ω. 那么 η ? = ? ξ d u a l ? ≤ ? η d u a l ? ≤ ξ ? , \begin{align} \eta^*=-\xi_{\mathrm{dual}}^*\leq-\eta_{\mathrm{dual}}^*\leq\xi^*,\end{align} η?=?ξdual??≤?ηdual??≤ξ?,??因此，当原问题也就是优化问题(3)满足强对偶性的时候，对偶问题(11)即 { max ? g d u a l ( α ) s . t ? α ? 0. \begin{cases}\max g_{\mathrm{dual}}(\alpha)\\\mathrm{s.t~}\alpha\succeq0.&\end{cases} {maxgdual?(α)s.t?α?0.??也满足强对偶性.
证.由于 g ( λ , μ ) = inf ? x ∈ Ω L ( x , λ , μ ) g(\lambda,\mu)=\inf_{x\in\Omega}L(x,\lambda,\mu) g(λ,μ)=infx∈Ω?L(x,λ,μ)，其中 L ( x , λ , μ ) L(x,\lambda,\mu) L(x,λ,μ) 是优化问题(3)的拉格朗日函数，根据拉格朗日函数以及对偶函数的定义，有 g d u a l ( α ) = ? sup ? λ , μ [ g ( λ , μ ) + α T λ ] = ? sup ? λ ? 0 , μ [ g ( λ , μ ) + α T λ ] = ? sup ? λ ? 0 , μ inf ? x ∈ Ω [ L ( x , λ , μ ) + α T λ ] = ? sup ? λ ? 0 , μ inf ? x ∈ Ω ( f 0 ( x ) + λ T [ f ( x ) + α ] + μ T h ( x ) ) , \begin{aligned} g_{\mathrm{dual}}(\alpha)&=-\sup_{\lambda,\mu}[g(\lambda,\mu)+\alpha^T\lambda]=-\sup_{\lambda\succeq0,\mu}[g(\lambda,\mu)+\alpha^T\lambda] \\ &=-\sup_{\lambda\succeq0,\mu}\inf_{x\in\Omega}[L(x,\lambda,\mu)+\alpha^T\lambda] \\ &=-\sup_{\lambda\succeq0,\mu}\inf_{x\in\Omega}\big(f_0(x)+\lambda^T[f(x)+\alpha]+\mu^Th(x)\big), \end{aligned} gdual?(α)?=?λ,μsup?[g(λ,μ)+αTλ]=?λ?0,μsup?[g(λ,μ)+αTλ]=?λ?0,μsup?x∈Ωinf?[L(x,λ,μ)+αTλ]=?λ?0,μsup?x∈Ωinf?(f0?(x)+λT[f(x)+α]+μTh(x)),?其中 f ( x ) : = ( f 1 ( x ) , ? ? , f p ( x ) ) T , h ( x ) : = ( h 1 ( x ) , ? ? , h q ( x ) ) T f(x):=(f_1(x),\cdots,f_p(x))^T,\quad h(x):=(h_1(x),\cdots,h_q(x))^T f(x):=(f1?(x),?,fp?(x))T,h(x):=(h1?(x),?,hq?(x))T是优化问题(3)的约束函数所构成的向量.于是根据 sup \text{sup} sup 和 inf \text{inf} inf 的性质，有 ? sup ? α ? 0 g d u a l ( α ) = inf ? α ? 0 sup ? λ , ? 0 μ inf ? x ∈ Ω ( f 0 ( x ) + λ T [ f ( x ) + α ] + μ T h ( x ) ) ≤ inf ? x ∈ Ω inf ? α ? 0 sup ? λ ? 0 , μ ( f 0 ( x ) + λ T [ f ( x ) + α ] + μ T h ( x ) ) ≤ inf ? x ∈ D ( f 0 ( x ) + inf ? α ? 0 sup ? λ ? 0 , μ ( λ T [ f ( x ) + α ] ) ) . \begin{aligned} -\sup_{\alpha\succeq0}g_{\mathrm{dual}}(\alpha)& \begin{aligned}&=\inf_{\alpha\succeq0}\sup_{\lambda,\succeq0\mu}\inf_{x\in\Omega}\left(f_0(x)+\lambda^T[f(x)+\alpha]+\mu^Th(x)\right)\end{aligned} \\ &\begin{aligned}&\leq\inf_{x\in\Omega}\inf_{\alpha\succeq0}\sup_{\lambda\succeq0,\mu}\left(f_0(x)+\lambda^T[f(x)+\alpha]+\mu^Th(x)\right)\end{aligned} \\ &\begin{aligned}&\leq\inf_{x\in\mathcal{D}}\Big(f_0(x)+\inf_{\alpha\succeq0}\sup_{\lambda\succeq0,\mu}\Big(\lambda^T[f(x)+\alpha]\Big)\Big).\end{aligned} \end{aligned} ?α?0sup?gdual?(α)??=α?0inf?λ,?0μsup?x∈Ωinf?(f0?(x)+λT[f(x)+α]+μTh(x))??≤x∈Ωinf?α?0inf?λ?0,μsup?(f0?(x)+λT[f(x)+α]+μTh(x))??≤x∈Dinf?(f0?(x)+α?0inf?λ?0,μsup?(λT[f(x)+α])).??对任意的 x ∈ D x\in\mathcal{D} x∈D. 由于优化问题(3)满足条件 { ? ∞ < f i ( x ) ≤ ∞ i = 0 , 1 , ? ? , p , ? ∞ < h j ( x ) < ∞ j = 1 , ? ? , q , ? x ∈ Ω . \begin{cases}-\infty<f_i(x)\leq\infty&i=0,1,\cdots,p,\\-\infty<h_j(x)<\infty&j=1,\cdots,q,\end{cases}\quad\forall x\in\Omega. {?∞<fi?(x)≤∞?∞<hj?(x)<∞?i=0,1,?,p,j=1,?,q,??x∈Ω.可以知道 f ( x ) ∈ R f(x)\in\mathbb{R} f(x)∈R. 令 α : = ? f ( x ) ? 0 \alpha:=-f(x)\succeq0 α:=?f(x)?0，则有 inf ? α ? 0 sup ? λ ? 0 , μ ( λ T [ f ( x ) + α ] ) ≤ sup ? λ ? 0 , μ ( λ T [ f ( x ) ? f ( x ) ] ) ) = 0. \begin{aligned}\inf_{\alpha\succeq0}\sup_{\lambda\succeq0,\mu}\left(\lambda^T[f(x)+\alpha]\right)\leq\sup_{\lambda\succeq0,\mu}\left(\lambda^T[f(x)-f(x)]\right))=0.\end{aligned} α?0inf?λ?0,μsup?(λT[f(x)+α])≤λ?0,μsup?(λT[f(x)?f(x)]))=0.?所以 ? η d u a l ? = ? sup ? α ? 0 g d u a l ( α ) ≤ inf ? x ∈ D f 0 ( x ) = ξ ? . \begin{aligned}-\eta_{\mathrm{dual}}^*=-\sup_{\alpha\succeq0}g_{\mathrm{dual}}(\alpha)\leq\inf_{x\in\mathcal{D}}f_0(x)=\xi^*.\end{aligned} \\ ?ηdual??=?α?0sup?gdual?(α)≤x∈Dinf?f0?(x)=ξ?.?联立上文二次对偶问题得到的不等式 η d u a l ? ≤ ξ d u a l ? = ? η ? \eta_\mathrm{dual}^*\leq\xi_\mathrm{dual}^*=-\eta^* ηdual??≤ξdual??=?η?，就可以得到 η ? = ? ξ d u a l ? ≤ ? η d u a l ? ≤ ξ ? \begin{aligned} \eta^*=-\xi_{\mathrm{dual}}^*\leq-\eta_{\mathrm{dual}}^*\leq\xi^*\end{aligned} η?=?ξdual??≤?ηdual??≤ξ??
注: 原问题(3)不满足强对偶性时, 根据弱对偶性, 对偶问题的最优值 η ? η^? η? 提供了原问题之最优值 ξ ? ξ^? ξ? 的一个下界. 不等式(12)表明, 多做一次对偶便可以获得原问题(3)的一个更好的下界 ? η d u a l ? ?η_{dual}^? ?ηdual??. 那么, 反复求解对偶问题的能逐步逼近原问题吗?
虽然一般对偶问题的对偶未必是原问题, 但对于线性规划而言, 却是肯定的. 所谓线性规划, 是指目标函数和约束函数都是仿射函数的优化问题, 线性规划可以写成如下标准形式 { min ? ? c T x , s . t ? A x = b , x ? 0. \begin{align}\begin{cases}\min~c^Tx,\\\mathrm{s.t}~Ax=b,\\x\succeq0.&\end{cases}\end{align} ? ? ??min?cTx,s.t?Ax=b,x?0.????
命题 6.2 线性规划(13)的二次对偶是原问题.
证. 线性规划(13)的 Lagrange 函数为 L ( x , λ , μ ) : = c T x ? λ T x + μ T ( A x ? b ) = ( c ? λ + A T μ ) T x ? b T μ . L(x,\lambda,\mu):=c^Tx-\lambda^Tx+\mu^T(Ax-b)=(c-\lambda+A^T\mu)^Tx-b^T\mu. L(x,λ,μ):=cTx?λTx+μT(Ax?b)=(c?λ+ATμ)Tx?bTμ.
所以其对偶函数为
g
(
λ
,
μ
)
:
=
inf
?
x
∈
R
n
L
(
x
,
λ
,
μ
)
=
{
?
b
T
μ
λ
=
A
T
μ
+
c
,
?
∞
其他?
.
g(\lambda,\mu):=\inf_{x\in\mathbb{R}^n}L(x,\lambda,\mu)=\begin{cases}-b^T\mu&\lambda=A^T\mu+c,\\-\infty&\text{其他 }.\end{cases}
g(λ,μ):=x∈Rninf?L(x,λ,μ)={?bTμ?∞?λ=ATμ+c,其他?.?因而, 对偶问题及其 Lagrange 函数分别为
{
min
?
?
g
(
λ
,
μ
)
s
.
t
?
λ
?
0
,
\begin{cases}\min-g(\lambda,\mu)\\\mathrm{s.t}\quad-\lambda\preceq0,&\end{cases}
{min?g(λ,μ)s.t?λ?0,??
和
L
d
u
a
l
(
λ
,
μ
,
α
)
=
?
g
(
λ
,
μ
)
?
α
T
λ
=
{
b
T
μ
?
α
T
λ
λ
=
A
T
μ
+
c
,
∞
其他?
.
L_{\mathrm{dual}}(\lambda,\mu,\alpha)=-g(\lambda,\mu)-\alpha^T\lambda=\begin{cases}b^T\mu-\alpha^T\lambda&\lambda=A^T\mu+c,\\[2ex]\infty&\text{其他 }.\end{cases}
Ldual?(λ,μ,α)=?g(λ,μ)?αTλ=?
?
??bTμ?αTλ∞?λ=ATμ+c,其他?.?于是, 对偶函数问题的对偶函数为
g
d
u
a
l
(
α
)
:
=
inf
?
λ
,
μ
L
d
u
a
l
(
λ
,
μ
,
α
)
=
inf
?
μ
[
b
T
μ
?
α
T
(
A
T
μ
+
c
)
]
=
{
?
α
T
c
A
α
=
b
,
?
∞
其他?
.
g_{\mathrm{dual}}(\alpha):=\inf_{\lambda,\mu}L_{\mathrm{dual}}(\lambda,\mu,\alpha)=\inf_{\mu}[b^T\mu-\alpha^T(A^T\mu+c)]=\begin{cases}-\alpha^Tc&A\alpha=b,\\[2ex]-\infty&\text{其他 }.\end{cases}
gdual?(α):=λ,μinf?Ldual?(λ,μ,α)=μinf?[bTμ?αT(ATμ+c)]=?
?
???αTc?∞?Aα=b,其他?.?
所以, 二次对偶问题为
{
max
?
g
d
u
a
l
(
α
)
s.t
α
?
0.
即
{
min
?
c
T
α
s.t
A
α
=
b
,
α
?
0.
\begin{cases}\max g_{\mathrm{dual}}(\alpha)\\\text{s.t}\quad\alpha\succeq0.\end{cases}\quad\text{即}\quad\begin{cases}\min c^T\alpha\\\text{s.t}\quad A\alpha=b,\\\alpha\succeq0.\end{cases}
{maxgdual?(α)s.tα?0.?即?
?
??mincTαs.tAα=b,α?0.?也就是说最后所得的问题就是原问题(3)，即线性规划的二次对偶问题是原问题.
考虑如下仿射约束优化问题之对偶函数的计算: { min ? f ( x ) , s.t A x ? b , C x = d , \begin{align}\begin{cases}\min f(x),\\\text{s.t}Ax\preceq b,\\Cx=d,\end{cases}\end{align} ? ? ??minf(x),s.tAx?b,Cx=d,???其中 f : R n → R f:\mathbb{R}^n\to\mathbb{R} f:Rn→R.此时，取 Ω : = R n \Omega:=\mathbb{R}^n Ω:=Rn. 那么 L ( x , λ , μ ) = f ( x ) + ( A T λ + C T μ ) T x ? ( b T λ + d T μ ) , dom ? ( L ) : = R n × R p × R q . L(x,\lambda,\mu)=f(x)+(A^T\lambda+C^T\mu)^Tx-(b^T\lambda+d^T\mu),\quad\operatorname{dom}(L):=\mathbb{R}^n\times\mathbb{R}^p\times\mathbb{R}^q. L(x,λ,μ)=f(x)+(ATλ+CTμ)Tx?(bTλ+dTμ),dom(L):=Rn×Rp×Rq.此时，对偶函数为 g ( λ , μ ) = inf ? x ∈ R n [ f ( x ) + ( A T λ + C T μ ) T x ] ? ( b T λ + d T μ ) . \begin{align}g(\lambda,\mu)=\inf_{x\in\mathbb{R}^n}[f(x)+(A^T\lambda+C^T\mu)^Tx]-(b^T\lambda+d^T\mu).\end{align} g(λ,μ)=x∈Rninf?[f(x)+(ATλ+CTμ)Tx]?(bTλ+dTμ).??
例 7.1 设
A
∈
R
q
×
n
,
?
b
∈
R
q
A\in\mathbb{R}^{q\times n},\mathrm{~}b\in\mathbb{R}^q
A∈Rq×n,?b∈Rq，优化问题
min
?
x
T
x
,
?
s
.
t
?
A
x
=
b
\min x^Tx,\quad\mathrm{~s.t~}\quad Ax=b
minxTx,?s.t?Ax=b的对偶函数为
g
(
μ
)
=
?
1
4
μ
T
A
A
T
μ
?
b
T
μ
g(\mu)=-\frac14\mu^TAA^T\mu-b^T\mu
g(μ)=?41?μTAATμ?bTμ
证.令 f 0 ( x ) : = x T x f_0(x):=x^Tx f0?(x):=xTx.根据(15),该优化问题的对偶函数为 g ( μ ) = inf ? x ∈ R n [ x T x + ( A T μ ) T x ] ? b T μ . g(\mu)=\inf_{x\in\mathbb{R}^n}[x^Tx+(A^T\mu)^Tx]-b^T\mu. g(μ)=x∈Rninf?[xTx+(ATμ)Tx]?bTμ.上式右端第一项的下确界在满足 2 x + A T μ = 0 2x+A^T\mu=0 2x+ATμ=0 的 x x x 处达到，即 x = ? A T μ / 2 x=-A^T\mu/2 x=?ATμ/2.将之代入上式即得 g ( μ ) = ? 1 4 μ T A A T μ ? b T μ g(\mu)=-\frac14\mu^TAA^T\mu-b^T\mu g(μ)=?41?μTAATμ?bTμ.
例 7.2 设 A ∈ R q × n , b ∈ R q , ∥ ? ∥ A\in\mathbb{R}^{q\times n},\quad b\in\mathbb{R}^q,\parallel\cdot\parallel A∈Rq×n,b∈Rq,∥?∥ 是 R n \mathbb{R}^n Rn 中任意范数，则优化问题 min ? ∥ x ∥ , s . t A x = b \min\|x\|,\quad\mathrm{s.t}\quad Ax=b min∥x∥,s.tAx=b的对偶函数为 g ( μ ) = { ? b T μ ∥ A T μ ∥ ? ≤ 1 , ? ∞ ∥ A T μ ∥ ? > 1. g(\mu)=\begin{cases}-b^T\mu&\|A^T\mu\|_*\leq1,\\-\infty&\|A^T\mu\|_*>1.&\end{cases} g(μ)={?bTμ?∞?∥ATμ∥??≤1,∥ATμ∥??>1.??
证.令
f
0
(
x
)
:
=
∥
x
∥
f_0(x):=\|x\|
f0?(x):=∥x∥.根据(15),该优化问题的对偶函数为
g
(
μ
)
=
inf
?
x
∈
R
n
[
∥
x
∥
+
(
A
T
μ
)
T
x
]
?
b
T
μ
.
\begin{aligned}g(\mu)&=\inf_{x\in\mathbb{R}^n}[\|x\|+(A^T\mu)^Tx]-b^T\mu.\end{aligned}
g(μ)?=x∈Rninf?[∥x∥+(ATμ)Tx]?bTμ.?
(1) 当
∥
A
T
μ
∥
?
≤
1
\|A^T\mu\|_* \leq1
∥ATμ∥??≤1 时，利用内积的性(只是作为类比来理解)，可以得到
(
A
T
μ
)
T
x
≥
?
∥
A
T
μ
∥
?
∥
x
∥
(A^T\mu)^Tx\geq-\|A^T\mu\|_*\|x\|
(ATμ)Tx≥?∥ATμ∥??∥x∥, 于是
inf
?
x
∈
R
n
[
∥
x
∥
+
(
A
T
μ
)
T
x
]
≥
inf
?
x
∈
R
n
(
1
?
∥
A
T
μ
∥
?
)
∥
x
∥
≥
0
,
\begin{aligned}\inf_{x\in\mathbb{R}^n}[\|x\|+(A^T\mu)^Tx]\ge\inf_{x\in\mathbb{R}^n}(1-\|A^T\mu\|_*)\|x\|\ge0,\end{aligned}
x∈Rninf?[∥x∥+(ATμ)Tx]≥x∈Rninf?(1?∥ATμ∥??)∥x∥≥0,?而取
x
=
0
x=0
x=0 可知
inf
?
x
∈
R
n
[
∥
x
∥
+
(
A
T
μ
)
T
x
]
≤
0
\inf_{x\in\mathbb{R}^n}[\|x\|+(A^T\mu)^Tx]\leq0
infx∈Rn?[∥x∥+(ATμ)Tx]≤0. 所以
inf
?
x
∈
R
n
[
∥
x
∥
+
(
A
T
μ
)
T
x
]
=
0.
\inf_{x\in\mathbb{R}^n}[\|x\|+(A^T\mu)^Tx]=0.
infx∈Rn?[∥x∥+(ATμ)Tx]=0.
注: 当范数 ∥ ? ∥ ∥ · ∥ ∥?∥ 为 Euclidean 范数时, 例 7.1和例 7.2中的优化问题是等价的. 然而, 它们的对偶函数完全不同.
例 7.3 线性规划 { min ? ? c T x s.t ? A x = b , ? x ? 0. \begin{cases}\min\:c^Tx\\\text{s.t}\:Ax=b,\\[2ex]\:x\succeq0.\end{cases} ? ? ??mincTxs.tAx=b,x?0.?的对偶函数为 g ( λ , μ ) = inf ? x ∈ R n ( c ? λ + A T μ ) T x ? b T μ = { ? b T μ , c ? λ + A T μ = 0 , ? ∞ , 其他 ? . g(\lambda,\mu)=\inf_{x\in\mathbb{R}^n}(c-\lambda+A^T\mu)^Tx-b^T\mu=\begin{cases}-b^T\mu,&c-\lambda+A^T\mu=0,\\[2ex]-\infty,&\text{其他}\:.\end{cases} g(λ,μ)=x∈Rninf?(c?λ+ATμ)Tx?bTμ=? ? ???bTμ,?∞,?c?λ+ATμ=0,其他.?
包括但不限于以下内容：
(1)[BBV04] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
(2)[BOG94] JR Bar-On and KA Grasse. Global optimization of a quadratic functional with quadratic equality constraints. Journal of Optimization Theory and Applications, 82(2):379–386, 1994.
(3)[BOG97] JR Bar-On and KA Grasse.Global optimization of a quadratic functional with quadratic equality constraints, part 2. Journal of Optimization Theory and Applications,93(3):547–556, 1997.
(4)[Dau88] I. Daubechies. Time-frequency localization operators: a geometric phase space approach. IEEE Transactions on Information Theory, 34(4):605–612, 1988.
(5)[DMA97] G.Davis, S. Mallat, and M. Avellaneda. Greedy adaptive approximation. J Constructive Approximation, 13(1):57–98, 1997.
(6)张恭庆, 林源渠, 郭懋正. 泛函分析讲义 (下册). 北京大学出版社, 1990.
(7)袁亚湘, 孙文瑜. 最优化理论和方法. 北京: 科学出版社, 1997.