凸优化 - 最近点定理

设 S 为 $\mathbb{R}^n$ 中的非空闭凸集，且 $y otin S$，则 $\存在$一个点 $\bar{x}\in S$，且与 y 的距离最小，即 $\left \| y-\bar{x} ight \| \leq \left \| y-x ight \| \forall x \in S.$

此外，$\bar{x}$是极小点当且仅当 $\left ( y-\hat{x} ight )^{T}\left ( x-\hat{x} ight )\leq 0$或$\left ( y-\hat{x}, x-\hat{x} ight )\leq 0$

证明

最近点的存在

由于$S e \phi,\exists$存在一个点$\hat{x}\in S$，使得S与y的最小距离小于或等于$\left \| y-\hat{x} ight \|$。

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

由于 $ \hat{S}$ 是封闭且有界的，并且范数是连续函数，则根据魏尔斯特拉斯定理，存在一个最小点 $\h​​at{x} \in S$ 使得 $\left \| y-\hat{x} ight \|=Inf\left \{ \left \| y-x ight \|,x \in S ight \}$

唯一性

假设 $\bar{x} \in S$ 使得 $\left \| y-\hat{x} ight \|=\left \| y-\hat{x} ight \|= \alpha$

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

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

这不能是严格不等式，因为 $\hat{x}$ 与 y 最接近。

因此，$\left \| y-\hat{x} ight \|=\mu \left \| y-\hat{x} ight \|$，对于某个 $\mu$

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

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

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

对于证明的第二部分，假设对于所有 $x\in S$，$\left ( y-\hat{x} ight )^{ au }\left ( x-\bar{x} ight )\leq 0$

现在，

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

$\Rightarrow \left \| y-x ight \|^{2}\geq \left \| y-\hat{x} ight \|^{2}$ 因为 $\left \| \hat{x}-x ight \|^{2}\geq 0$ 和 $\left ( \hat{x}- x ight )^{T}\left ( y-\hat{x} ight )\geq 0$

因此，$\hat{x}$ 为极小点。

相反，假设 $\hat{x}$ 为极小点。

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

由于 S 是凸集。

$\Rightarrow \lambda x+\left ( 1-\lambda ight )\hat{x}=\hat{x}+\lambda\left ( x-\hat{x} ight ) \in S$ 其中 $x \in S$ 和 $\lambda \in \left ( 0,1 ight )$

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

并且

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

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

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

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

因此证明。