对偶锥与自对偶 - 好文

令 KKK 为一个锥，定义其对偶锥为K∗={y∣xTy≥0,∀x∈K}K^* = \{y|x^Ty \geq 0, \forall x \in K\}K∗
={y∣xTy≥0,∀x∈K}

在优化问题中常用的锥有：非负象限锥、半正定锥、范数锥。下面我们来看他们的对偶锥是什么。

<>非负象限

非负象限，记为 R+nR^n_+R+n，显然其对偶锥为自身：(1)yTx≥0,∀x⪰0⇔y⪰0y^Tx \geq 0, \forall x \succeq
0 \Leftrightarrow y \succeq 0 \tag{1}yTx≥0,∀x⪰0⇔y⪰0(1)

<>半正定锥

记为 S+nS^n_+S+n , 和非负象限锥一样，它也是自对偶的：(2)tr(XY)≥0,∀X⪰0⇔Y⪰0tr(XY) \geq 0, \forall
X \succeq 0 \Leftrightarrow Y \succeq 0 \tag{2}tr(XY)≥0,∀X⪰0⇔Y⪰0(2)证明：

若 Y∉S+nY \notin S^n_+Y∈/S+n，则存在 q∈Rnq \in \R^nq∈Rn 且 qTYq=tr(qTYq)=tr(qqTY)
<0q^TYq = tr(q^TYq) = tr(qq^TY) < 0qTYq=tr(qTYq)=tr(qqTY)<0那么对于半定矩阵 X=qqT，
tr(XY)<0X = qq^T，tr(XY) < 0X=qqT，tr(XY)<0，可知 Y∉(S+n)∗Y \notin (S^n_+)^*Y∈/
(S+n)∗，所以 (2) 的 “⇒\Rightarrow⇒” 得证。
若 X,Y⪰0X,Y \succeq 0X,Y⪰0，利用特征分解 X=∑i=1nλiqiqiTX = \sum_{i=1}^n
\lambda_iq_iq_i^TX=∑i=1nλiqiqiT，其中 λi≥0,i=1,…,n\lambda_i \geq 0, i=1,…,nλi≥
0,i=1,…,n。则tr(XY)=tr(∑i=1nλiqiqiTY)=∑i=1nλiqiTYqi≥0tr(XY) = tr(\sum_{i=1}^n
\lambda_iq_iq_i^TY)=\sum_{i=1}^n \lambda_iq_i^TYq_i \geq 0tr(XY)=tr(i=1∑nλiqi
qiTY)=i=1∑nλiqiTYqi≥0，所以 (2) 的 “⇐\Leftarrow⇐” 得证。

<>范数锥

令 ∣∣⋅∣∣||· ||∣∣⋅∣∣ 为定义在 Rn\R^nRn 上的范数。由它定义的范数锥为K={(x,t)∈Rn+1∣
    ∣∣x∣∣≤t}K = \{(x,t) \in \R^{n+1}|\;\; ||x|| \leq t\}K={(
x,t)∈Rn+1∣∣∣x∣∣≤t}其对偶锥为有对偶范数
<https://blog.csdn.net/itnerd/article/details/83447223> ∣∣⋅∣∣∗||· ||_*∣∣⋅∣∣∗
定义的范数锥K∗={(u,v)∈Rn+1∣    ∣∣u∣∣≤v}K^* = \{(u,v) \in
\R^{n+1}|\;\; ||u|| \leq v\}K∗={(u,v)∈Rn+1∣∣∣u∣∣≤v}即xTu+tv≥0,if  ∣∣x∣∣
≤t⇔∣∣u∣∣∗≤v x^Tu +tv \geq 0 , if \; ||x|| \leq t\Leftrightarrow ||u||_* \leq vxT
u+tv≥0,if∣∣x∣∣≤t⇔∣∣u∣∣∗≤v
“⇐\Leftarrow⇐” ：
已知 ∣∣u∣∣∗≤v||u||_* \leq v∣∣u∣∣∗≤v。若 t=0t = 0t=0，则 x=0x=0x=0，左端显然成立。假设 t>0
t > 0t>0 且 ∣∣x∣∣≤t||x|| \leq t∣∣x∣∣≤t，则有 ∣∣−x/t∣∣≤1||-x/t|| \leq 1∣∣−x/t∣∣≤1
，由对偶范数的定义 <https://blog.csdn.net/itnerd/article/details/83447223>可得uT(−x/t)≤∣∣u∣
∣∗≤vu^T(-x/t) \leq ||u||_* \leq vuT(−x/t)≤∣∣u∣∣∗≤v所以 xTu+tv≥0x^Tu +tv \geq 0xTu
+tv≥0

“⇒\Rightarrow⇒” ：
反证：假设右端不成立，即 ∣∣u∣∣∗>v||u||_* > v∣∣u∣∣∗>v，由对偶范数的定义，存在 x 满足 ∣∣x∣∣≤1||x||
\leq 1∣∣x∣∣≤1 且 uTx>vu^Tx > vuTx>v，取 t=1t=1t=1，则有uT(−x)+v<0u^T(-x) +v
< 0uT(−x)+v<0与左端矛盾。

热门工具换一换