凸优化 - 极锥

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

备注

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

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

• 极性可以看作是正交性的推广。

设 $C\subseteq \mathbb{R}^n$然后是 C 的正交空间，表示为 $C^\perp =\left \{ y \in \mathbb{R}^n:\left \langle x,y ight angle=0 \forall x \in C ight \}$。

引理

设 $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 ight \}$

• 设 $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 ight ),\left [ \lambda x_1+\left ( 1-\lambda ight )x_2 ight ]^Tx=\left [ \left ( \lambda x_1 ight )^T+ \left \{\left ( 1-\lambda ight )x_{2} ight \}^{T} ight ]x, \forall x \in S$

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

  因此 $\lambda x_1+\left ( 1-\lambda ight )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 ight )^T x \leq 0$

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

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

• 为了证明 $S^*$ 是封闭的，即证明如果 $p_n ightarrow p$ 为 $n ightarrow \infty$，则 $p \in S^*$

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

  当 $p_n ightarrow p$ 为 $n ightarrow \infty \Rightarrow \left ( p_n ightarrow p ight ) ightarrow 0$

  因此 $p_{n}^{T}x ightarrow 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^* ight \}$

设 $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 ight \}$

由于 $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 otin C$

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

因此，$p^Tx > \alpha$

但因为 $\left ( y=0 ight ) \in C$ 且 $p^Ty\leq \alpha, \forall y \in C \Rightarrow \alpha\geq 0$ 且 $p^Tx>0$

若 $p otin C^*$，则存在某个 $\bar{y} \in C$ 使得 $p^T \bar{y}>0$ 且 $p^T\left ( \lambda \bar{y} ight )$ 可以通过将 $\lambda$ 取得足够大而任意变大。

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

因此，$p \in C^*$

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

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

但 $p^Tx> \alpha$

因此矛盾。

因此，$x \in C$

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