凸优化 - 最近点定理

---

设S为$\mathbb{R}^n$中的非空闭凸集，并令$y\notin S$，则$\存在$S$中的一个点$\bar{x}\，其最小距离为y，即$\left \| y-\bar{x} \右\| \leq \左\| yx \右\| \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,\在S$中存在$一个点$\hat{x}\，使得S到y的最小距离小于或等于$\left \| y-\hat{x}\right\|$。

定义 $\hat{S}=S \cap \left \{ x:\left \| yx \右\|\leq \左\| y-\hat{x} \right \| \右\}$

由于 $ \hat{S}$ 是闭有界的，并且由于范数是连续函数，因此根据 Weierstrass 定理，在 S$ 中存在一个最小点 $\h​​at{x} \ 使得 $\left \| y-\hat{x} \right \|=Inf\left \{ \left \| yx \right \|,x \in S \right \}$

独特性

假设 $\bar{x} \in S$ 使得 $\left \| y-\hat{x} \right \|=\left \| y-\hat{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-\hat{x} \right \|=\mu \left \| y-\hat{x} \right \|$，对于某些 $\mu$

现在$\左\| \mu \right \|=1.$ 如果 $\mu=-1$，则 $\left ( y-\hat{x} \right )=-\left ( y-\hat{x} \right )\右箭头 y=\frac{\hat{x}+\bar{x}}{2} \in S$

但是$y \in S$。因此矛盾。因此 $\mu=1 \Rightarrow \hat{x}=\bar{x}$

因此，最小化点是唯一的。

对于证明的第二部分，假设 $\left ( y-\hat{x} \right )^{\tau }\left ( x-\bar{x} \right )\leq 0$ 对于所有 $x\单位：新元

现在，

$\左\| yx \右\|^{2}=\左\| 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 )$

$\右箭头\左\| yx \右\|^{2}\geq \左\| 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}$ 是最小化点。

$\右箭头\左\| yx \右\|^{2}\geq \左\| 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$ for $x \in 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$

和

$\左\| 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 )$

$\右箭头\左\| y-\hat{x} \right \|^{2}+\lambda^{2}\left \| x-\hat{x} \right \|-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$

故得证。