凸优化 - 最近点定理

---

---

设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$

证毕。