令 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​λi​qi​qiT​,其中 λ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​λi​qi​
qiT​Y)=i=1∑n​λi​qiT​Yqi​≥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与左端矛盾。