对偶锥与自对偶

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

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

非负象限

非负象限，记为 $R_{+}^n$，显然其对偶锥为自身：$$y^{T}x\ge 0,\forall x⪰0\iff y⪰0\text{\hspace{1em}(1)}$$

半正定锥

记为 $S_{+}^n$ , 和非负象限锥一样，它也是自对偶的：$$tr(XY)\ge 0,\forall X⪰0\iff Y⪰0\text{\hspace{1em}(2)}$$证明：

若 $Y\notin S_{+}^n$， 则存在 $q\in {\mathbb{R}}^n$ 且 $$q^{T}Yq=tr(q^{T}Yq)=tr(q{q}^{T}Y)<0$$那么对于半定矩阵 $X=q{q}^T，tr(XY)<0$，可知 $Y\notin (S_{+}^n{)}^{\ast }$，所以 (2) 的 “$\Rightarrow$” 得证。
若 $X,Y⪰0$，利用特征分解 $X={\sum }_{i=1}^n{\lambda }_i{q}_i{q}_i^T$，其中 ${\lambda }_i\ge 0,i=1,\dots ,n$。则$$tr(XY)=tr(\sum _{i=1}^n{\lambda }_i{q}_i{q}_i^{T}Y)=\sum _{i=1}^n{\lambda }_i{q}_i^{T}Y{q}_i\ge 0$$，所以 (2) 的 “$\Leftarrow$” 得证。

范数锥

令 $||\cdot ||$ 为定义在 ${\mathbb{R}}^n$ 上的范数。由它定义的范数锥为 K = { ( x , t ) ∈ R n + 1 ∣ &ThickSpace;&ThickSpace; ∣ ∣ x ∣ ∣ ≤ t } K = \{(x,t) \in \R^{n+1}|\;\; ||x|| \leq t\} K={(x,t)∈Rn+1∣∣∣x∣∣≤t}其对偶锥为有对偶范数 $||\cdot |{|}_{\ast }$ 定义的范数锥 K ∗ = { ( u , v ) ∈ R n + 1 ∣ &ThickSpace;&ThickSpace; ∣ ∣ u ∣ ∣ ≤ v } K^* = \{(u,v) \in \R^{n+1}|\;\; ||u|| \leq v\} K∗={(u,v)∈Rn+1∣∣∣u∣∣≤v}即$$x^{T}u+tv\ge 0,if||x||\le t\iff ||u|{|}_{\ast }\le v$$
“$\Leftarrow$” ：
已知 $||u|{|}_{\ast }\le v$。若 $t=0$，则 $x=0$，左端显然成立。假设 $t>0$ 且 $||x||\le t$，则有 $||-x/t||\le 1$，由对偶范数的定义可得$$u^T(-x/t)\le ||u|{|}_{\ast }\le v$$所以 $x^{T}u+tv\ge 0$

“$\Rightarrow$” ：
反证：假设右端不成立，即 $||u|{|}_{\ast }>v$，由对偶范数的定义，存在 x 满足 $||x||\le 1$ 且 $u^{T}x>v$，取 $t=1$，则有$$u^T(-x)+v<0$$与左端矛盾。