凸最佳化 - 最近點定理

---

---

設S是$\mathbb{R}^n$中的一個非空閉凸集，且y∉S，則存在一個點$\bar{x}\in S$，其到y的距離最小，即$\left \| y-\bar{x} \right \| \leq \left \| y-x \right \| \forall x \in S.$

此外，$\bar{x}$是極小點當且僅當$\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq 0$ 或 $\left ( y-\hat{x}, x-\hat{x} \right )\leq 0$

證明

最近點的存在性

由於$S\ne \phi$，存在一個點$\hat{x}\in S$，使得S到y的最小距離小於等於$\left \| y-\hat{x} \right \|。

定義$\hat{S}=S \cap \left \{ x:\left \| y-x \right \|\leq \left \| y-\hat{x} \right \| \right \}$

由於$\hat{S}$是閉集且有界，並且由於範數是連續函式，則根據Weierstrass定理，存在一個極小點$\hat{x} \in S$，使得$\left \| y-\hat{x} \right \|=\inf\left \{ \left \| y-x \right \|,x \in S \right \}$

唯一性

假設$\bar{x} \in S$，使得$\left \| y-\hat{x} \right \|=\left \| y-\bar{x} \right \|= \alpha$

由於S是凸集，$\frac{\hat{x}+\bar{x}}{2} \in S$

但是，$\left \| y-\frac{\hat{x}+\bar{x}}{2} \right \|\leq \frac{1}{2}\left \| y-\hat{x} \right \|+\frac{1}{2}\left \| y-\bar{x} \right \|=\alpha$

它不可能是嚴格不等式，因為$\hat{x}$是距離y最近的點。

因此，$\left \| y-\frac{\hat{x}+\bar{x}}{2} \right \|=\mu \left \| y-\hat{x} \right \|$，對於某個μ

現在$\left \| \mu \right \|=1$。如果μ=-1，則$\left ( y-\hat{x} \right )=-\left ( y-\bar{x} \right )\Rightarrow y=\frac{\hat{x}+\bar{x}}{2} \in S$

但是y∈S。因此矛盾。因此μ=1 ⇒ $\hat{x}=\bar{x}$

因此，極小點是唯一的。

對於證明的第二部分，假設$\left ( y-\hat{x} \right )^{\tau }\left ( x-\bar{x} \right )\leq 0$ 對所有x∈S成立

現在，

$\left \| y-x \right \|^{2}=\left \| y-\hat{x}+ \hat{x}-x\right \|^{2}=\left \| y-\hat{x} \right \|^{2}+\left \|\hat{x}-x \right \|^{2}+2\left (\hat{x}-x \right )^{\tau }\left ( y-\hat{x} \right )$

$\Rightarrow \left \| y-x \right \|^{2}\geq \left \| y-\hat{x} \right \|^{2}$，因為$\left \| \hat{x}-x \right \|^{2}\geq 0$且$\left ( \hat{x}- x\right )^{T}\left ( y-\hat{x} \right )\geq 0$

因此，$\hat{x}$是極小點。

反之，假設$\hat{x}$是極小點。

$\Rightarrow \left \| y-x \right \|^{2}\geq \left \| y-\hat{x} \right \|^2 \forall x \in S$

由於S是凸集。

$\Rightarrow \lambda x+\left ( 1-\lambda \right )\hat{x}=\hat{x}+\lambda\left ( x-\hat{x} \right ) \in S$，對於x∈S和$\lambda \in \left ( 0,1 \right )$

現在，$\left \| y-\hat{x}-\lambda\left ( x-\hat{x} \right ) \right \|^{2}\geq \left \| y-\hat{x} \right \|^2$

並且

$\left \| y-\hat{x}-\lambda\left ( x-\hat{x} \right ) \right \|^{2}=\left \| y-\hat{x} \right \|^{2}+\lambda^2\left \| x-\hat{x} \right \|^{2}-2\lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )$

$\Rightarrow \left \| y-\hat{x} \right \|^{2}+\lambda^{2}\left \| x-\hat{x} \right \|^2-2 \lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\geq \left \| y-\hat{x} \right \|^{2}$

$\Rightarrow 2 \lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq \lambda^2\left \| x-\hat{x} \right \|^2$

$\Rightarrow \left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq 0$

證畢。