凸优化 - 极锥

---

---

设S是$\mathbb{R}^n$中的一个非空集，则S的极锥，记为$S^*$，由$S^*=\left \{p \in \mathbb{R}^n, p^Tx \leq 0 \: \forall x \in S \right \}$给出。

备注

• 即使S不是凸集，极锥也总是凸的。

• 如果S为空集，则$S^*=\mathbb{R}^n$。

• 极性可以被视为正交性的推广。

设$C\subseteq \mathbb{R}^n$，则C的正交空间，记为$C^\perp =\left \{ y \in \mathbb{R}^n:\left \langle x,y \right \rangle=0 \forall x \in C \right \}$。

引理

设$S,S_1$和$S_2$是$\mathbb{R}^n$中的非空集，则以下陈述为真：

• $S^*$是一个闭凸锥。

• $S \subseteq S^{**}$，其中$S^{**}$是$S^*$的极锥。

• $S_1 \subseteq S_2 \Rightarrow S_{2}^{*} \subseteq S_{1}^{*}$。

证明

步骤1 − $S^*=\left \{ p \in \mathbb{R}^n,p^Tx\leq 0 \: \forall \:x \in S \right \}$

• 设$x_1,x_2 \in S^*\Rightarrow x_{1}^{T}x\leq 0 $ 且 $x_{2}^{T}x \leq 0,\forall x \in S$

  对于$\lambda \in \left ( 0, 1 \right ),\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]^Tx=\left [ \left ( \lambda x_1 \right )^T+ \left \{\left ( 1-\lambda \right )x_{2} \right \}^{T}\right ]x, \forall x \in S$

  $=\left [ \lambda x_{1}^{T} +\left ( 1-\lambda \right )x_{2}^{T}\right ]x=\lambda x_{1}^{T}x+\left ( 1-\lambda \right )x_{2}^{T}\leq 0$

  因此 $\lambda x_1+\left ( 1-\lambda \right )x_{2} \in S^*$

  因此 $S^*$是一个凸集。

• 对于$\lambda \geq 0,p^{T}x \leq 0, \forall \:x \in S$

  因此，$\lambda p^T x \leq 0,$

  $\Rightarrow \left ( \lambda p \right )^T x \leq 0$

  $\Rightarrow \lambda p \in S^*$

  因此，$S^*$是一个锥。

• 要证明$S^*$是闭的，即要证明如果$p_n \rightarrow p$ 当$n \rightarrow \infty$时，则$p \in S^*$。

  $\forall x \in S, p_{n}^{T}x-p^T x=\left ( p_n-p \right )^T x$

  当$p_n \rightarrow p$ 当$n \rightarrow \infty \Rightarrow \left ( p_n \rightarrow p \right )\rightarrow 0$

  因此 $p_{n}^{T}x \rightarrow p^{T}x$。但$p_{n}^{T}x \leq 0, \: \forall x \in S$

  因此，$p^Tx \leq 0, \forall x \in S$

  $\Rightarrow p \in S^*$

  因此，$S^*$是闭的。

步骤2 − $S^{**}=\left \{ q \in \mathbb{R}^n:q^T p \leq 0, \forall p \in S^*\right \}$

设$x \in S$，则$ \forall p \in S^*, p^T x \leq 0 \Rightarrow x^Tp \leq 0 \Rightarrow x \in S^{**}$

因此，$S \subseteq S^{**}$

步骤3 − $S_2^*=\left \{ p \in \mathbb{R}^n:p^Tx\leq 0, \forall x \in S_2 \right \}$

由于$S_1 \subseteq S_2 \Rightarrow \forall x \in S_2 \Rightarrow \forall x \in S_1$

因此，如果$\hat{p} \in S_2^*, $则$\hat{p}^Tx \leq 0,\forall x \in S_2$

$\Rightarrow \hat{p}^Tx\leq 0, \forall x \in S_1$

$\Rightarrow \hat{p}^T \in S_1^*$

$\Rightarrow S_2^* \subseteq S_1^*$

定理

设C是非空闭凸锥，则$C=C^**$

证明

$C=C^{**}$根据前面的引理。

要证明：$x \in C^{**} \subseteq C$

设$x \in C^{**}$且$x \notin C$

然后根据基本分离定理，存在一个向量$p \neq 0$和一个标量$\alpha$，使得$p^Ty \leq \alpha, \forall y \in C$

因此，$p^Tx > \alpha$

但由于$\left ( y=0 \right ) \in C$且$p^Ty\leq \alpha, \forall y \in C \Rightarrow \alpha\geq 0$且$p^Tx>0$

如果$p \notin C^*$，则存在某个$\bar{y} \in C$使得$p^T \bar{y}>0$，并且可以通过取$\lambda$足够大使得$p^T\left ( \lambda \bar{y} \right )$任意大。

这与$p^Ty \leq \alpha, \forall y \in C$的事实相矛盾。

因此，$p \in C^*$

由于$x \in C^*=\left \{ q:q^Tp\leq 0, \forall p \in C^* \right \}$

因此，$x^Tp \leq 0 \Rightarrow p^Tx \leq 0$

但$p^Tx> \alpha$

这是矛盾的。

因此，$x \in C$

因此 $C=C^{**}$。