凸优化 - 极锥

设 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}xp^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$

    $\右箭头 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^*$，则 C$ 中存在一些 $\bar{y} \，使得 $p^T \bar{y}>0$ 且 $p^T\left ( \lambda \bar {y} \right )$ 可以通过使 $\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^* \right \}$

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

但是 $p^Tx> \alpha$

这就是矛盾。

因此，$x \in C$

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