凸最佳化 - 極錐

---

---

設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^{**}$。