极小值点的存在性与投影

本讲座关注优化问题中极小值点的存在性条件，以及向闭凸集投影的性质。主要内容包括刻画极小值点的概念、给出极小值点存在性的充分必要条件、分析凸函数情形的特殊性质，以及研究向闭凸集的投影问题。

极小值点的定义

设 S 是Hilbert空间 \mathcal{H} 的非空子集， f: S \to ]-\infty, +\infty] 是真函数， \hat{x} \in S 。极小值点的概念需要区分局部与全局、严格与非严格等不同情形。

点 \hat{x} 称为 f 的局部极小值点，如果 \hat{x} \in \text{dom } f 且存在 \hat{x} 的开邻域 O 使得对所有 x \in O \cap S 都有

局部极小值点的定义要求在 \hat{x} 的某个邻域内，函数值不小于 f(\hat{x}) 。这里的邻域是在全空间 \mathcal{H} 中定义的开集，然后与集合 S 求交得到 \hat{x} 在 S 中的邻域。这种定义方式使得即使 S 本身不是开集（例如 S 可能是闭集或者其他拓扑结构），我们依然可以讨论局部极小值点的概念。需要特别注意的是， \hat{x} 必须在 f 的定义域内，即 f(\hat{x}) 必须是有限值，否则讨论极小值点没有意义。

点 \hat{x} 称为 f 的全局极小值点，如果对所有 x \in S 都有

全局极小值点不需要邻域的概念，它直接要求 \hat{x} 的函数值是整个集合 S 上的最小值。全局极小值点显然也是局部极小值点，但反之不成立。在优化问题中，我们通常关心的是全局极小值点，因为它给出了问题的真正最优解。

严格性的概念进一步细化了极小值点的分类。点 \hat{x} 称为 f 的严格局部极小值点，如果存在 \hat{x} 的开邻域 O 使得对所有 x \in (O \cap S) \setminus \{\hat{x}\} 都有

这里关键的区别在于不等号是严格的，并且显式地排除了点 \hat{x} 本身。严格局部极小值点意味着在邻域内， \hat{x} 是唯一使函数达到最小值的点，其他所有点的函数值都严格大于 f(\hat{x}) 。

点 \hat{x} 称为 f 的严格全局极小值点（同时也是唯一的极小值点），如果对所有 x \in S \setminus \{\hat{x}\} 都有

严格全局极小值点不仅是全局最小值，而且是唯一的全局最小值点。这是最强的极小值点概念，在实际应用中，严格全局极小值点具有良好的稳定性和唯一性，使得优化算法的收敛性分析更加简洁。

紧集上极小值点的存在性

Weierstrass定理

设 S 是Hilbert空间 \mathcal{H} 的非空紧集， f: S \to ]-\infty, +\infty] 是真的下半连续函数。则存在 \hat{x} \in S 使得

Weierstrass定理是优化理论中最基本的存在性结果之一。它断言在紧集上，下半连续函数必定达到其下确界，即存在极小值点。这个定理的条件——紧性和下半连续性——都是必要的，缺少任何一个条件都可能导致极小值点不存在。

证明思路

证明从下确界的定义出发。设 \delta = \inf_{x \in S} f(x) ，根据下确界的定义，我们知道 \delta \in [-\infty, +\infty[ ，并且由于 f 是真函数（不恒为 +\infty ），这个下确界是有意义的。

下确界的刻画告诉我们：存在 S 中的序列 (x_n)_{n \in \mathbb{N}} 使得

这样的序列称为极小化序列，它的函数值逐渐逼近下确界。但这并不自动保证序列本身收敛，这正是需要紧性假设的地方。

由于 S 是紧集，根据紧集的序列刻画（在度量空间中，紧性等价于序列紧性），序列 (x_n)_{n \in \mathbb{N}} 存在收敛子序列。具体地说，存在 (x_n)_{n \in \mathbb{N}} 的子序列 (x_{k_n})_{n \in \mathbb{N}} 使得

极限点 \hat{x} 必然属于 S ，因为 S 作为紧集必然是闭集，而闭集包含其所有极限点。

最后利用下半连续性完成证明。根据下半连续函数的定义，对于收敛序列 x_{k_n} \to \hat{x} ，有

而 \liminf_{n \to \infty} f(x_{k_n}) = \lim_{n \to \infty} f(x_{k_n}) = \delta （因为 (x_{k_n}) 是 (x_n) 的子序列，而 (x_n) 的函数值收敛到 \delta ）。因此

但 \delta 是 f 在 S 上的下确界，意味着对所有 x \in S 都有 f(x) \geq \delta ，特别地 f(\hat{x}) \geq \delta 。结合上述不等式得到 f(\hat{x}) = \delta ，并且由于子序列的极限是有限的，我们得出 \delta \in \mathbb{R} 。这证明了 \hat{x} 是极小值点，且极小值是有限的。

这个证明清晰地展示了紧性、下半连续性和序列方法在存在性证明中的作用：紧性提供了序列的收敛子序列，下半连续性保证了函数值在极限点处不会"跳跃"到更低的值，两者结合保证了下确界可以达到。

强制函数

设 \mathcal{H} 是Hilbert空间， f: \mathcal{H} \to ]-\infty, +\infty] 。函数 f 称为强制的，如果

强制性条件的几何含义是：当点 x 远离原点（即 \|x\| 趋向无穷大）时，函数值 f(x) 必然趋向正无穷。这个条件在优化问题中至关重要，因为它保证了函数不会在无穷远处取得有限值或更小的值，从而迫使极小值点必须出现在有界区域内。

图示展示了三种不同的函数行为来帮助理解强制性概念。左图显示了一个典型的强制函数：当 x 趋向 \pm\infty 时，函数值都趋向 +\infty ，形成一个"碗状"结构。中图展示了另一个强制函数的例子，虽然函数在有界区域内可能有复杂的结构（如多个局部极小值），但在无穷远处依然趋向 +\infty 。右图通过红色虚线标记出非强制函数的特征：函数在某个有界区间上有定义（用蓝色实线和端点标记表示），但在此区间外取值为 +\infty （用蓝色虚线表示）。虽然这个函数在其定义域边界外确实是 +\infty ，但由于定义域本身是有界的，我们无法说 \lim_{\|x\| \to +\infty} f(x) = +\infty ——在趋向无穷的过程中，函数根本没有定义。因此右图不是强制函数的例子。

强制性是比紧性更弱但更易验证的条件。许多实际优化问题中的目标函数自然满足强制性，例如带有增长性惩罚项的能量泛函、正定二次型等。强制性将在无界域上的优化问题转化为等价的有界域问题，这是下面定理的核心思想。

强制函数极小值点的存在性定理

设 \mathcal{H} 是有限维Hilbert空间， f: \mathcal{H} \to ]-\infty, +\infty] 是真的下半连续强制函数。则 f 的极小值点集是非空紧集。

这个定理将Weierstrass定理从紧集推广到了整个空间的情形。当空间本身不是紧的（如 \mathbb{R}^n ），通过要求函数是强制的，我们可以保证极小值点的存在性。定理不仅断言至少存在一个极小值点，还说明所有极小值点构成的集合是紧的，这意味着极小值点集是闭的和有界的。

证明

证明分为几个步骤，核心思想是利用强制性将问题限制在一个紧子集上，然后应用Weierstrass定理。

由于 f 是真函数，存在 x_0 \in \mathcal{H} 使得 f(x_0) \in \mathbb{R} ，即 f(x_0) 是有限的。这个点 x_0 为我们提供了一个参考值，函数的最小值必然不超过 f(x_0) 。

强制性条件 \lim_{\|x\| \to +\infty} f(x) = +\infty 意味着：存在 \eta \in ]0, +\infty[ 使得对所有满足 \|x - x_0\| > \eta 的 x \in \mathcal{H} ，都有 f(x) > f(x_0) 。换句话说，在距离 x_0 足够远的地方，函数值一定严格大于 f(x_0) 。这个 \eta 的存在性来自于强制性的定义：由于 f(x) \to +\infty 当 \|x\| \to \infty ，我们可以找到足够大的半径使得在该半径外函数值超过任何给定的常数（这里是 f(x_0) ）。

定义集合

这是以 x_0 为中心、半径为 \eta 的闭球。在有限维Hilbert空间中（与 \mathbb{R}^n 同构），闭球是紧集（根据Heine-Borel定理，有界闭集是紧的）。此外， S \cap \text{dom } f \neq \varnothing 因为至少 x_0 \in S \cap \text{dom } f 。

关键观察是：对于所有 x \in \mathcal{H} \setminus S （即所有不在 S 中的点），都有 \|x - x_0\| > \eta ，因此根据强制性给出的性质， f(x) > f(x_0) 。这意味着 f 在 S 外部的值都严格大于 f(x_0) ，所以全局最小值必然在 S 内部达到。

根据Weierstrass定理，存在 \hat{x} \in S 使得

不等式成立是因为 x_0 \in S 。但对于任何 x \notin S ，我们有 f(x) > f(x_0) \geq f(\hat{x}) 。因此

即 \hat{x} 是 f 在整个空间 \mathcal{H} 上的全局极小值点。这证明了极小值点集非空。

接下来证明极小值点集 \text{Argmin } f \subset S 是有界的。设 \text{Argmin } f = \{x \in \mathcal{H} \mid f(x) = \inf_{x \in \mathcal{H}} f(x)\} 。对于任何极小值点 x \in \text{Argmin } f ，我们有 f(x) = f(\hat{x}) \leq f(x_0) 。如果 x \notin S ，则 f(x) > f(x_0) ，与 f(x) \leq f(x_0) 矛盾。因此所有极小值点都必须在 S 内，即 \text{Argmin } f \subset S 。由于 S 是有界的， \text{Argmin } f 也是有界的。

最后证明 \text{Argmin } f 是闭的。设 (x_n)_{n \in \mathbb{N}} 是 \text{Argmin } f 中的序列，且 x_n \to \hat{x} \in \mathcal{H} 。我们需要证明 \hat{x} \in \text{Argmin } f 。对所有 n ，有 f(x_n) = \inf_{x \in \mathcal{H}} f(x) 。由于 f 是下半连续的，

但 \inf_{x \in \mathcal{H}} f(x) 是下确界，意味着 f(\hat{x}) \geq \inf_{x \in \mathcal{H}} f(x) 。因此 f(\hat{x}) = \inf_{x \in \mathcal{H}} f(x) ，即 \hat{x} \in \text{Argmin } f 。这证明了 \text{Argmin } f 包含其所有极限点，因此是闭集。

综合有界性和闭性（在有限维空间中）， \text{Argmin } f 是紧集。

这个定理在于它不需要事先知道一个紧集，只需要验证函数的强制性（通常比验证定义域的紧性容易得多）。在实际应用中，许多优化问题的目标函数自然具有强制性，因此这个定理提供了一个强大的存在性工具。

练习1：Shannon熵函数的极小值点

Shannon熵函数定义为

这个函数在信息论中度量概率分布的不确定性。当某个分量为负时，函数值定义为 +\infty 以排除非物理的情况（概率不能为负）。

问题1：扩展定义使函数下半连续

为了使 f 在 \mathbb{R}^N 上下半连续，需要合理定义边界情况。将函数写成可分离形式

其中 \phi: \mathbb{R} \to ]-\infty, +\infty] 定义为 \phi(u) = u\log(u) \cdot \iota_{]0,+\infty[}(u) 。这里 \iota_{]0,+\infty[}(u) 是正半轴的示性函数。

关键问题是如何在 u = 0 处定义 \phi 的值使其下半连续。图中展示了函数 \phi(u) 的图像：当 u > 0 时， \phi(u) = u\log(u) ；当 u \to 0^+ 时，通过L'Hôpital法则或直接分析可知

为了保证下半连续性，在 u = 0 处应该定义 \phi(0) = 0 （对应测验的选项C）。这是因为下半连续函数要求 f(x_0) \leq \liminf_{x \to x_0} f(x) ，而右极限已经是0，所以在0处赋值0或任何非负值都能保持下半连续。但赋值0是最自然的选择，它使得 \phi 连续地延拓到0点。

当 u < 0 时， \phi(u) = +\infty 以保证概率非负性约束。这样扩展后的函数 \phi 是下半连续的，因此 f = \sum_{i=1}^N \phi(x^{(i)}) 作为下半连续函数的和也是下半连续的。

问题2：极小值点的存在性

考虑集合

这是单纯形——满足分量和为1的非负向量集合，对应于 N 个结果的概率分布。

函数 f 在问题1中已经扩展为下半连续且真的（在 C 内部取有限值）。集合 C 的任何闭子集在有限维空间 \mathbb{R}^N 中都是有界的（因为 C 本身有界：所有分量在 [0,1] 之间）。有界闭集在有限维空间中是紧的，因此根据Weierstrass定理， f 在 C 的任何非空闭子集上都存在极小值点。

练习2：正交矩阵集上的优化

问题1：矩阵空间的Hilbert空间结构

考虑 N \times N 实矩阵空间 \mathbb{R}^{N \times N} ，配备内积

这个内积可以展开为

这正是将矩阵按列堆叠成向量后的标准Euclidean内积。定义向量化映射

映射 \phi: \mathbb{R}^{N \times N} \to \mathbb{R}^{N^2} 是线性同构，并且保持内积： \langle A | B \rangle = \langle \phi(A) | \phi(B) \rangle_{\mathbb{R}^{N^2}} 。因此 \mathbb{R}^{N \times N} 配备迹内积后同构于 \mathbb{R}^{N^2} 配备标准内积，从而继承了Hilbert空间结构（有限维内积空间自动是完备的）。

问题2：正交矩阵集的紧性与极小值点存在性

正交矩阵集定义为

其中 I_N 是 N 阶单位矩阵。需要判断 \mathcal{O} 的拓扑性质。

有界性：对于任意 M \in \mathcal{O} ，由于 MM^\top = I_N ，取迹得到

但 \text{tr}(MM^\top) = \sum_{i=1}^N \sum_{j=1}^N M_{i,j}^2 = \|M\|_F^2 （Frobenius范数的平方），因此 \|M\|_F^2 = N ，即 \|M\|_F = \sqrt{N} 。这说明所有正交矩阵到原点的距离（在Frobenius范数意义下）都等于 \sqrt{N} ，因此 \mathcal{O} 是有界的。

闭性： \mathcal{O} 是连续映射 \Phi: M \mapsto MM^\top 的水平集 \Phi^{-1}(\{I_N\}) 。由于连续映射的原像保持闭集性质，而 \{I_N\} 是闭集（单点集在Hausdorff空间中总是闭的），所以 \mathcal{O} 是闭集。更直接地说，如果正交矩阵序列 M_n \to A （在Frobenius范数意义下收敛），则

因此 A \in \mathcal{O} ，这证明 \mathcal{O} 包含其所有极限点，即 \mathcal{O} 是闭的。

在有限维空间 \mathbb{R}^{N \times N} 中，有界闭集根据Heine-Borel定理是紧的。因此 \mathcal{O} 是紧集。

对于任何连续函数 f: \mathbb{R}^{N \times N} \to \mathbb{R} ，其在紧集 \mathcal{O} 上的限制 f|_{\mathcal{O}} 是紧集上的连续函数（连续函数也是下半连续的），根据Weierstrass定理必然存在极小值点。因此答案是肯定的：连续函数 f 在正交矩阵集上存在极小值点。

这个结论在实际应用中很重要，例如在计算机视觉中的旋转估计问题、量子力学中的酉变换优化等，都涉及在正交矩阵（或酉矩阵）集合上优化某个目标函数。紧性保证了这类优化问题总是有解的。

极小值点存在性的必要与充分条件

极小值点存在的必要条件（欧拉不等式）

本节讨论可微函数的极小值点必须满足的条件。设 D 是赋范空间 \mathcal{H} 的一个开子集，C \subset D。考虑函数 f: D \to ]-\infty, +\infty] 在点 \hat{x} \in C 处是Gâteaux可微的。当 \hat{x} 是 f 在 C 上的局部极小值点时，对于所有满足 [\hat{x}, y] \subset C 的 y \in \mathcal{H}，必然有

这个不等式称为欧拉不等式，它刻画了极小值点的一阶必要条件。这个条件背后的几何直观是：如果 \hat{x} 是极小值点，那么从 \hat{x} 出发沿着任何可行方向 y - \hat{x} 的方向导数都不能为负，否则沿该方向移动会使函数值下降，与 \hat{x} 是极小值点矛盾。

特别地，当 \hat{x} \in \text{int}(C)（即 \hat{x} 位于 C 的内部）时，由于所有方向都是可行的，上述条件简化为

这就是经典的一阶最优性条件：内部极小值点处的导数必为零。

证明的思路利用了极小值点的定义和Gâteaux导数的定义。对于任意 y \in \mathcal{H} 满足 [\hat{x}, y] \subset C，线段 [\hat{x}, y] 表示连接 \hat{x} 和 y 的所有点。由于这条线段完全在 C 内，我们可以找到足够小的 \delta \in [0,1]，使得对所有 \alpha \in ]0, \delta]，点 (1-\alpha)\hat{x} + \alpha y = \hat{x} + \alpha(y - \hat{x}) 都在 C 中。因为 \hat{x} 是局部极小值点，这些点的函数值不会小于 \hat{x} 处的函数值，即 f(\hat{x} + \alpha(y - \hat{x})) \geq f(\hat{x})。

将这个不等式改写为差商形式并取极限，就得到

这里关键在于差商的分子非负（因为 \hat{x} 是极小值点），分母为正（因为 \alpha > 0），所以整个差商非负，极限也非负。

当 \hat{x} 位于 C 的内部时，对于任意方向 z \in \mathcal{H}，我们可以找到足够小的 \delta > 0，使得线段 [\hat{x} - \delta z, \hat{x} + \delta z] 完全包含在 C 内。这意味着 \hat{x} \pm \delta z 都在 C 中。应用前面的欧拉不等式到方向 \pm \delta z，得到

即 f'(\hat{x})(\delta z) \geq 0 且 f'(\hat{x})(-\delta z) \geq 0。这两个不等式同时成立只有当 f'(\hat{x})(z) = 0 时才可能，而这对所有 z 都成立，因此 f'(\hat{x}) = 0。

这里需要注意一个术语：满足 f'(\hat{x}) = 0 的点 \hat{x} 称为 f 的临界点（critical point）。临界点是寻找极值点的候选点，但不是所有临界点都是极值点，还需要进一步的条件来判断。

极小值点存在的充分条件

前面的必要条件告诉我们极小值点必须满足什么，但满足这些条件的点不一定是极小值点。现在我们讨论充分条件：在什么条件下，一个临界点确实是极小值点。这需要用到二阶信息，即Hessian矩阵的性质。

设 C 是Hilbert空间 \mathcal{H} 的开子集，函数 f: C \to \mathbb{R} 在 C 上Fréchet可微。定理给出了两个不同的充分条件：

第一个充分条件针对严格局部极小值。如果 f 在点 \hat{x} \in C 处二次Fréchet可微，并且满足 \nabla f(\hat{x}) = 0（这是必要条件），同时存在某个 \eta > 0 使得对所有 h \in \mathcal{H} 都有

那么 f 在 \hat{x} 处有严格局部极小值。这个条件要求Hessian在 \hat{x} 处是强正定的自伴算子（在有限维空间中就是正定对称矩阵）。这里的"强"体现在不等式右边有一个严格的正下界 \eta \|h\|^2，而不仅仅是非负。

证明这个结论使用Taylor-Young公式。对于 \mathcal{H} \setminus \{0\} 中的任意 h，当 \|h\| 足够小时，\hat{x} + h \in C，我们可以将 f 在 \hat{x} 附近展开为

其中余项 \epsilon(h) \to 0 当 h \to 0。由于 \nabla f(\hat{x}) = 0（临界点条件）且Hessian满足强正定条件，线性项消失，我们得到

当 h 充分小时，余项 \epsilon(h) 可以任意小，特别地可以使得 \frac{\eta}{2} + \epsilon(h) > 0。因此存在 \delta > 0，使得当 0 < \|h\| < \delta 时，f(\hat{x} + h) > f(\hat{x})。这正是严格局部极小值的定义：在 \hat{x} 的某个邻域内，所有其他点的函数值都严格大于 f(\hat{x})。

第二个充分条件针对（非严格的）局部极小值，条件略有放松。如果 f 在包含 \hat{x} 的某个开邻域 D \subset C 上二次Fréchet可微，\hat{x} 处满足 \nabla f(\hat{x}) = 0，并且对所有 x \in D 和 h \in \mathcal{H} 都有

那么 f 在 \hat{x} 处有局部极小值。注意这里的条件比第一种情况弱：一是不等式右边是0而不是 \eta \|h\|^2，Hessian只需非负定而非强正定；二是条件要求在整个邻域 D 上都成立，而不仅仅在 \hat{x} 一点。

证明使用Taylor-MacLaurin公式的积分余项形式。设 B \subset D 是以 \hat{x} 为中心的开球。对于任意 x \in B，存在某个 y \in ]\hat{x}, x[（即 \hat{x} 和 x 之间的某点），使得

由于 \nabla f(\hat{x}) = 0，且 y 在 D 中（因为 y 在 \hat{x} 和 x 之间，而 B \subset D），利用Hessian的非负定性，我们得到

这表明在球 B 内所有点的函数值都不小于 \hat{x} 处的函数值，即 \hat{x} 是局部极小值点。

总结两个充分条件的区别：条件(1)通过在单点处要求Hessian强正定，保证了严格局部极小值；条件(2)通过在邻域上要求Hessian非负定，保证了局部极小值（但可能不严格）。前者结论更强但要求也更强，后者条件分布在整个邻域但只能得到较弱的结论。这两个定理为判断临界点是否为极小值点提供了实用的工具。

欧拉不等式的应用实例：最小二乘问题

最小二乘准则的优化问题

现在通过一个具体的最小二乘回归问题来展示欧拉不等式如何帮助我们找到极小值点。在统计学和机器学习中，我们经常需要寻找参数向量 \beta 来最小化残差平方和，这个目标函数记作

这里 Y 是观测数据向量，X 是设计矩阵，\beta 是待估计的参数向量。将范数的平方展开，可以写成内积的形式

继续展开这个内积，利用转置和分配律，得到

这个展开式将原问题转化为关于 \beta 的二次型加上线性项和常数项。根据欧拉不等式的必要条件，如果 \hat{\beta} 是极小值点，那么必须满足 \nabla \text{SCR}(\hat{\beta}) = 0。

梯度计算的数学基础

为了计算 \nabla_\beta \text{SCR}(\beta)，需要先明确两个基本的微分公式。设 v \in \mathbb{R}^q，z \in \mathbb{R}^q，M \in \mathbb{R}^{q \times q}。

第一个是线性函数的微分。对于函数 h(z) = v^{\top} z = \sum_{j=1}^q v_j z_j，它关于 z 的梯度是

因此对于线性形式 v^{\top} z，其梯度恰好就是系数向量 v。

第二个是二次型的微分。对于函数 h(z) = z^{\top} M z = \sum_{i,j=1}^p z_i M_{i,j} z_j，计算第 k 个分量的偏导数时，需要考虑 z_k 在求和中出现的所有项。这些项包括 z_k M_{k,j} z_j（当 i=k 时）和 z_i M_{i,k} z_k（当 j=k 时）。因此

将所有分量组合成向量形式，得到

这个公式表明二次型的梯度涉及矩阵及其转置的和。

最小二乘问题的解析解

回到最小二乘问题，目标函数为

应用前面的微分公式，对 \beta 求梯度。第一项是关于 \beta 的二次型，矩阵为 X^{\top} X，由于 X^{\top} X 是对称矩阵（即 (X^{\top} X)^{\top} = X^{\top} X），根据二次型微分公式得到其梯度为 2X^{\top} X\beta。第二项 -2Y^{\top} X\beta 是线性项，可以改写为 -2(X^{\top} Y)^{\top} \beta，其梯度为 -2X^{\top} Y。第三项 Y^{\top} Y 是常数，梯度为零。综合起来

根据欧拉不等式的必要条件，令梯度为零，即 \nabla_\beta \text{SCR}(\beta) = 0，得到

从而解出

这就是经典的最小二乘估计的正规方程解。这里假设矩阵 X^{\top} X 可逆，这在设计矩阵 X 列满秩时成立。

为了验证 \hat{\beta} 确实是极小值点而非鞍点或极大值点，需要检查二阶条件。计算Hessian矩阵，即梯度的梯度。由于 \nabla_\beta \text{SCR}(\beta) = 2X^{\top} X\beta - 2X^{\top} Y 是 \beta 的线性函数，其对 \beta 的导数为常矩阵

注意到Hessian不依赖于 \beta，在整个参数空间上都是同一个常矩阵。对于任意非零向量 h，计算二次型

当 X 列满秩时，Xh = 0 当且仅当 h = 0，因此对所有 h \neq 0 都有 \|Xh\|^2 > 0。这意味着存在 \eta > 0（依赖于 X 的最小奇异值）使得 \langle h | \nabla_\beta^2 \text{SCR}(\hat{\beta}) h \rangle \geq \eta \|h\|^2。根据前面讲的充分条件定理，\hat{\beta} 是严格局部极小值点，且由于目标函数是二次凸函数，它也是全局极小值点。

凸函数的极小值点性质

凸函数极小值点的基本定理

凸函数具有一些非常优美的性质，使得其优化问题相对容易处理。设 \mathcal{H} 是Hilbert空间，考虑函数 f: \mathcal{H} \to ]-\infty, +\infty] 是正常凸函数，这里"正常"是指其下确界 \mu = \inf f > -\infty，即函数在下方有界。关于这类函数的极小值点，有以下三个关键性质。

首先，函数取得最小值的点构成的集合 \{x \in \mathcal{H} \mid f(x) = \mu\} 本身是凸集。这个结论刻画了极小值点集合的几何结构：如果存在多个极小值点，它们之间的任何凸组合也是极小值点。为了证明这一点，设 \Omega = \{x \in \mathcal{H} \mid f(x) = \mu\} 是极小值点集合。任取 \Omega 中的两个点 (x, y) \in \Omega^2 和任意权重 \alpha \in ]0, 1[，由于 f 是凸函数，凸性定义给出

但 \mu 是 f 的下确界，因此函数值不可能小于 \mu，所以必然有 f(\alpha x + (1-\alpha)y) = \mu。这表明 \alpha x + (1-\alpha)y \in \Omega，证明了 \Omega 的凸性。

第二个性质说明凸函数的局部极小值点必然是全局极小值点。这是凸优化的核心优势：我们不用担心陷入局部最优而错过全局最优。假设 x_0 是 f 的一个局部极小值点，即存在 \delta > 0 使得对所有满足 \|x - x_0\| < \delta 的 x，都有 f(x) \geq f(x_0)。现在任取空间中的任意点 y \in \mathcal{H}，考虑线段 x_t = (1-t)x_0 + ty，其中 t \in [0,1]。当 t 充分小时，x_t 落在 x_0 的 \delta-邻域内，因此 f(x_t) \geq f(x_0)。同时由凸性

结合这两个不等式，得到 f(x_0) \leq (1-t)f(x_0) + tf(y)，整理后 tf(x_0) \leq tf(y)，即 f(x_0) \leq f(y)。由于 y 是任意选取的，这证明了 f(x_0) = \mu，即 x_0 是全局极小值点。

第三个性质针对严格凸函数：如果 f 是严格凸的（即对所有 x \neq y 和 \alpha \in ]0,1[，不等式 f(\alpha x + (1-\alpha)y) < \alpha f(x) + (1-\alpha)f(y) 严格成立），那么 f 最多有一个极小值点。这是因为如果存在两个不同的极小值点 x_1 \neq x_2，它们都满足 f(x_1) = f(x_2) = \mu，取它们的中点 \frac{1}{2}x_1 + \frac{1}{2}x_2，严格凸性给出

这与 \mu 是下确界矛盾。因此严格凸函数的极小值点（如果存在）是唯一的。

这三个性质共同揭示了凸优化问题的良好结构：不仅局部最优就是全局最优，而且在严格凸的情况下解是唯一的，这为算法的设计和收敛性分析提供了理论保证。

凸函数局部极小值点的全局性证明

前面我们已经建立了凸函数的几个基本性质。现在继续证明第二个关键性质：凸函数的任何局部极小值点必然是全局极小值点。设 \hat{x} 是 f 的一个局部极小值点，我们需要证明对所有 y \in \mathcal{H} \setminus \{\hat{x}\}（即除了 \hat{x} 本身以外的所有点），都有 f(\hat{x}) \leq f(y)。

证明的核心想法是利用凸性在局部和全局之间建立联系。对于任意给定的点 y \neq \hat{x}，我们可以找到足够小的 \alpha \in ]0, 1[ 使得点 \hat{x} + \alpha(y - \hat{x}) 落在 \hat{x} 的局部极小值邻域内。由于 \hat{x} 是局部极小值点，在该邻域内有 f(\hat{x}) \leq f(\hat{x} + \alpha(y - \hat{x}))。

另一方面，利用函数 f 的凸性，对于这个凸组合点 (1-\alpha)\hat{x} + \alpha y = \hat{x} + \alpha(y - \hat{x})，凸性定义给出

结合前面的局部最优性条件，我们得到不等式链

将左边的不等式整理，得到 f(\hat{x}) \leq (1-\alpha)f(\hat{x}) + \alpha f(y)，移项后 \alpha f(\hat{x}) \leq \alpha f(y)。因为 \alpha > 0，两边同时除以 \alpha 得到 f(\hat{x}) \leq f(y)。这对所有 y \in \mathcal{H} 都成立，因此 \hat{x} 确实是全局极小值点。

当 f 是严格凸函数时，上述凸性不等式变为严格不等式，即对于 y \neq \hat{x} 和 \alpha \in ]0,1[，有 f(\hat{x} + \alpha(y - \hat{x})) < (1-\alpha)f(\hat{x}) + \alpha f(y)。这导致最终的不等式也是严格的，即 f(\hat{x}) < f(y) 对所有 y \neq \hat{x} 成立。这进一步说明严格凸函数的极小值点（如果存在）不仅是全局的，而且是严格全局的。

极小值点的存在性与唯一性

前面讨论的性质都假设极小值点存在，但在什么条件下能保证极小值点的存在性呢？这需要额外的假设。设 \mathcal{H} 是Hilbert空间，C 是 \mathcal{H} 的闭凸子集，函数 f \in \Gamma_0(\mathcal{H})（表示 f 是下半连续正常凸函数），并且 f 的有效定义域与约束集 C 有非空交集，即 \text{dom} f \cap C \neq \varnothing。

定理断言，如果满足以下两个条件之一：函数 f 是强制的（coercive），或约束集 C 有界，那么存在 \hat{x} \in C 使得

这里"强制"是指当 \|x\| \to \infty 时 f(x) \to +\infty，它保证了即使在无界集上，函数值也会在远处变得很大，从而极小值必然在某个有界区域内达到。有界集条件则直接限制了搜索空间的大小。此外，如果 f 是严格凸的，那么极小值点 \hat{x} 是唯一的。

证明思路利用了一个技巧性的转化。虽然这个结果对无限维空间也成立，但为了简化证明，假设 \mathcal{H} 是有限维的。由于 C 是非空闭凸集，我们可以引入 C 的示性函数（indicator function）\iota_C，它定义为：当 x \in C 时 \iota_C(x) = 0，当 x \notin C 时 \iota_C(x) = +\infty。这个函数是下半连续凸函数。

考虑新的目标函数 f + \iota_C，它在 C 上与 f 相同，在 C 外为 +\infty。由于 \text{dom} f \cap C \neq \varnothing，函数 f + \iota_C 不恒为 +\infty，因此 f + \iota_C \in \Gamma_0(\mathcal{H})。当 f 是强制的或 C 有界时，f + \iota_C 也是强制的。根据下半连续强制函数在有限维空间中必达到其下确界的经典结果（这依赖于Weierstrass定理的推广），存在 \hat{x} \in C 使得

唯一性直接来自前面证明的严格凸函数最多有一个极小值点的性质。

凸可微函数极小值点的充要条件

对于凸且可微的函数，我们可以给出极小值点的一个优美的充要条件。设 \mathcal{H} 是Hilbert空间，函数 f: \mathcal{H} \to ]-\infty, +\infty] 在其有效定义域 \text{dom} f（开集）上Gâteaux可微且为凸函数。设 C \subset \text{dom} f 是非空凸集。那么 \hat{x} \in C 是 f 在 C 上的全局极小值点，当且仅当对所有 y \in C 都有

这个变分不等式是凸优化理论中的基本结果。当 \hat{x} 位于 C 的内部时，由于所有方向都是可行的，这个条件等价于 \nabla f(\hat{x}) = 0，即经典的一阶最优性条件。

充要性包含两个方向的证明。必要性（如果 \hat{x} 是极小值点则不等式成立）已经在前面讨论欧拉不等式时证明过了：对于极小值点，沿任何可行方向的方向导数都非负，而 \langle \nabla f(\hat{x}) | y - \hat{x} \rangle 正是从 \hat{x} 指向 y 的方向导数。

现在证明充分性：假设变分不等式成立，需要证明 \hat{x} 确实是极小值点。对于任意 y \in C，由于 f 是凸函数且Gâteaux可微，凸函数的一个关键性质（一阶条件刻画凸性）告诉我们：凸可微函数 f 的图像总是位于其在任何点的切平面之上，即对任意两点 \hat{x}, y，有

这个不等式表明线性化误差总是非负的。结合假设的变分不等式 \langle \nabla f(\hat{x}) | y - \hat{x} \rangle \geq 0，我们立即得到

因此对所有 y \in C 都有 f(y) \geq f(\hat{x})，这正是 \hat{x} 为全局极小值点的定义。这个证明的美妙之处在于它将凸性的几何性质（切平面总是在图像下方）与变分不等式结合起来，简洁地建立了充分性。

这个充要条件将极小值点的判定问题转化为验证一个变分不等式，在实际应用中特别有用，因为变分不等式通常比直接比较所有可行点的函数值更容易验证。对于约束优化问题，这个条件形成了Karush-Kuhn-Tucker条件的基础。

凹函数的极小值问题

凹函数极小化的特殊性质

这里讨论一个看似矛盾但实际上非常自然的问题：凹函数的极小化。在前面的讨论中，我们主要关注凸函数的极小化，因为凸函数的极小值问题具有良好的性质。但有时我们也需要考虑凹函数的极小化，虽然通常凹函数的极大化更常见。

问题设置如下：设 \mathscr{H} 是Hilbert空间，函数 f: \mathscr{H} \to \mathbb{R} 是凹的且Gâteaux可微，约束集 C \subset \mathscr{H}，点 \hat{x} \in \text{int}(C) 位于 C 的内部。我们希望在 C 上极小化 f。

这里提出一个测验问题：如果 f 在 C 上是常数函数，那么 \hat{x} 是否是 f 在 C 上的全局极小值点？答案是肯定的。

为了理解这个结论，需要回顾凹函数与凸函数的关系。如果 f 是凹函数，那么 -f 是凸函数。对于凸函数 -f 的极大化问题等价于凹函数 f 的极小化问题。现在假设 f 在 C 上恒为常数，不失一般性设 f(x) = c 对所有 x \in C 成立。

由于 \hat{x} 位于 C 的内部，如果它是极小值点，根据必要条件必然有 \nabla f(\hat{x}) = 0。这对常数函数自然成立，因为常数函数的梯度处处为零。现在利用凹函数的一阶特征：对于凹可微函数，其图像总是位于任意点的切平面之下（这与凸函数相反），即对所有 y 有

将 \nabla f(\hat{x}) = 0 代入，得到 f(y) \leq f(\hat{x}) 对所有 y 成立。但由于 f 在 C 上是常数，实际上 f(y) = f(\hat{x}) 对所有 y \in C 成立。因此 \hat{x} 确实是全局极小值点（同时也是全局极大值点）。

这个例子揭示了一个深刻的事实：当目标函数在约束集上恒为常数时，约束集中的任何点都既是极小值点又是极大值点。从优化的角度看，这意味着优化问题是平凡的——所有可行点都是最优的。

极小值点存在性与唯一性的判别准则

现在考虑一般的优化问题 \min_{x \in C} f(x)，其中 C \subset \mathbb{R}^n。我们需要判断在什么条件下能保证极小值点的存在性和唯一性。这里通过几个具体的陈述来澄清常见的误解。

第一个陈述考虑约束集不是凸集的情况。如果 C = C_1 \cup C_2，其中 C_1 和 C_2 都是凸集，并且 f 是严格凸函数，那么是否存在唯一的全局极小值点？这个陈述实际上是错误的。问题的关键在于两个凸集的并集不一定是凸集。例如，在平面上取两个不相交的圆盘，它们各自是凸的，但它们的并集显然不是凸的。

当约束集 C 不是凸集时，即使目标函数 f 是严格凸的，我们之前建立的所有关于凸优化的优美性质都可能失效。严格凸性只能保证在任何凸子集上最多有一个极小值点，但在非凸集上可能存在多个局部极小值点，每个都在不同的凸分支上。因此这个陈述的结论不能保证。

第二个陈述涉及Hessian的正定性。如果 C 不是凸集，f 二次Fréchet可微，并且Hessian \nabla^2 f(x) 对所有 x 都是正定的，那么解是否可能不唯一？这个陈述也是错误的。Hessian处处正定意味着目标函数是严格凸的（这可以通过二阶条件刻画凸性来验证），而严格凸函数在整个空间上最多有一个全局极小值点。即使约束集不是凸的，严格凸性仍然保证了全局极小值点（如果存在）的唯一性，因为如果有两个不同的全局极小值点，它们的函数值相同且都是全局最小值，但连接它们的线段上某点的函数值会严格小于端点值（由严格凸性），这与两个端点都是全局极小值矛盾。

第三个陈述说：如果 C 是凸的，f 二次Fréchet可微，Hessian \nabla^2 f(x) 对所有 x 都是正定的，那么至少存在一个极小值点。这个陈述的正确性需要额外条件。Hessian正定保证了函数的严格凸性，凸集和严格凸函数的组合保证了唯一性（如果极小值点存在的话），但并不自动保证存在性。存在性需要额外的条件，比如函数的强制性（当 \|x\| \to \infty 时 f(x) \to +\infty）或者约束集的有界性。如果这些条件都不满足，函数值可能在趋向无穷远时仍然递减，导致下确界无法达到。

线性约束下的二次优化问题

现在考虑一个更具体的问题：在线性等式约束下优化二次型。约束集定义为 C = \{x \in \mathbb{R}^n \mid Ax = b\}，其中 A \in \mathbb{R}^{p \times n} 且 p < n。这是一个仿射子空间（如果约束相容的话），维度为 n - p。目标函数是二次型 f(x) = x^{\top} Q x，其中 Q 是 n \times n 矩阵。

这类问题在最优控制、统计估计等领域广泛出现。现在讨论矩阵 Q 的性质与极小值点存在性、唯一性的关系。

第一个陈述说：如果 Q 正定（即 Q > 0），则存在唯一的极小值点。这个陈述是正确的。Q 正定意味着 f(x) = x^{\top} Q x 是严格凸函数，因为对任意 h \neq 0，Hessian的二次型 h^{\top} \nabla^2 f(x) h = 2h^{\top} Q h > 0（注意Hessian是 2Q）。严格凸性保证唯一性。关于存在性，由于 Q 正定，存在常数 \lambda_{\min} > 0（Q 的最小特征值）使得 x^{\top} Q x \geq \lambda_{\min} \|x\|^2，这意味着当 \|x\| \to \infty 时 f(x) \to +\infty，即函数是强制的。虽然约束集 C 可能无界（这取决于 A 和 b），但强制性保证了函数值在远处变得很大，因此下确界在 C 中某个有界区域达到。根据Weierstrass定理，连续函数在紧集上达到其最小值，结合强制性和 C 的闭性，极小值点必然存在。

第二个陈述说：如果 Q 半正定（即 Q \geq 0），则至少存在一个极小值点。这个陈述需要更仔细的分析。Q 半正定只能保证函数是凸的而非严格凸的，因此唯一性不能保证。关于存在性，半正定性不足以保证强制性。考虑 Q 的核空间（null space）\mathcal{N}(Q) = \{v \mid Qv = 0\}。如果约束子空间 C 与 \mathcal{N}(Q) 有非平凡交集，那么沿着这个交集方向，函数值不增长，极小值点可能在无穷远处或者根本不存在下确界。只有当 Q 在约束子空间的限制上正定时（即 Q 限制在 C 的方向子空间上是正定的），才能保证存在性。

第三个陈述说：如果 Q \geq 0 且 C 不是有界的，则可能不存在极小值点。这是正确的。一个简单的反例：设 Q = 0（零矩阵），则 f(x) = 0 对所有 x 成立。如果 C 无界且非空，那么 \inf_{x \in C} f(x) = 0 确实可以在 C 中达到（事实上任何点都是极小值点），所以这个特殊情况存在性成立。但如果取 Q 半正定但不是零矩阵，并且构造 C 使得沿着 Q 的核方向无界，那么可能出现下确界不能达到的情况。更准确地说，当 Q \geq 0 且 C 无界时，如果 C 包含 Q 的核空间的某个无界方向，则可能存在使得函数值趋于下确界但永远达不到的序列，此时极小值点不存在。因此这个陈述正确地指出了在缺乏强制性和有界性时存在性可能失效。

投影到闭凸集

投影算子的定义与存在唯一性

投影是优化理论中的核心概念，它联系了抽象的最优化问题与具体的几何直观。设 C 是Hilbert空间 \mathcal{H} 的非空闭凸子集。对于空间中的任意点 x \in \mathcal{H}，我们关心的问题是：C 中是否存在离 x 最近的点？如果存在，这个点是否唯一？

定理给出了肯定的答案。第一部分断言，对于每个 x \in \mathcal{H}，都存在唯一的点 \hat{x} \in C 使得 x 到 \hat{x} 的距离是 x 到 C 中所有点的距离中最小的。换句话说，\hat{x} 是 x 在 C 上的最近点或最佳逼近。这个从 \mathcal{H} 到 C 的映射 P_C: \mathcal{H} \to C，将每个点 x 映射到它在 C 中的最近点 \hat{x}，称为投影到 C 的投影算子。

第二部分给出了投影的刻画条件。点 \hat{x} 是 x 在 C 上的投影，即 \hat{x} = P_C(x)，当且仅当 \hat{x} \in C 且对所有 y \in C 都有

这个不等式有深刻的几何意义：从 \hat{x} 到 x 的向量 x - \hat{x} 与从 \hat{x} 到 C 中任何其他点 y 的向量 y - \hat{x} 的内积非正。这意味着向量 x - \hat{x} 与 C 在 \hat{x} 处形成的"朝外"方向形成钝角或直角，换言之，x - \hat{x} 垂直或几乎垂直地指向 C 的外部。

证明第一部分的关键在于将几何问题转化为优化问题。固定 x \in \mathcal{H}，定义函数 f: \mathcal{H} \to \mathbb{R} 为 f(y) = \|y - x\|^2。这个函数度量了 C 中的候选点 y 到给定点 x 的距离平方。寻找最近点的问题等价于在约束集 C 上最小化 f。

函数 f 具有优良的性质。首先，它是连续的，因为范数函数连续。其次，它是严格凸的。为了验证这一点，计算 f 的Hessian。对任意 y \in \mathcal{H}，可以将 f(y) = \|y - x\|^2 = \langle y - x | y - x \rangle 展开。它关于 y 的梯度是 \nabla f(y) = 2(y - x)（这可以通过直接计算内积的导数得到），因此Hessian是 \nabla^2 f(y) = 2I，其中 I 是恒等算子。对于任何非零向量 h，有 \langle h | \nabla^2 f(y) h \rangle = 2\|h\|^2 > 0，确认了严格凸性。第三，函数 f 是强制的：当 \|y\| \to \infty 时，\|y - x\|^2 \to \infty，因为 \|y - x\|^2 \geq (\|y\| - \|x\|)^2 由三角不等式得出。

由于 C 非空，有效定义域与约束集的交集 \text{dom} f \cap C = C \neq \varnothing。根据前面建立的极小值点存在性定理，强制的严格凸函数在非空闭凸集上必然有唯一的极小值点。因此存在唯一的 \hat{x} \in C 使得 f(\hat{x}) = \inf_{y \in C} f(y)，即 \hat{x} 是 x 在 C 中的唯一最近点。

第二部分的证明利用了凸优化的一阶最优性条件。函数 f(y) = \|y - x\|^2 是Gâteaux可微的，其梯度为 \nabla f(y) = 2(y - x)。根据凸可微函数极小值点的充要条件，\hat{x} 是 f 在凸集 C 上的极小值点当且仅当对所有 y \in C，变分不等式成立：

将 \nabla f(\hat{x}) = 2(\hat{x} - x) 代入，得到

因子 2 是正数可以约去，同时将不等式改写为

两边乘以 -1（不等号反向）得到

这正是定理第二部分给出的刻画条件。这个推导表明，投影点的变分不等式刻画本质上是距离最小化问题的一阶最优性条件的几何形式。

法锥的几何意义

为了更深入理解投影的性质，引入法锥的概念。设 C 是 \mathcal{H} 的非空子集。对于每个点 x \in \mathcal{H}，定义 C 在 x 处的法锥为

当 x 在 C 内时，法锥 N_C(x) 是所有与 C 的"内向方向"形成钝角或直角的向量的集合。更准确地说，如果 u \in N_C(x)，那么对于 C 中任何其他点 y，从 x 指向 y 的位移向量 y - x 与 u 的内积非正，意味着 u 要么垂直于这些位移，要么指向与它们相反的方向。几何上，法锥包含了所有"指向 C 外部"的方向。

法锥的几个特殊性质值得注意。如果 x 位于 C 的内部，即 x \in \text{int}(C)，那么存在以 x 为中心的开球完全包含在 C 内。这意味着从 x 出发的所有方向都有 C 中的点，因此对于任何非零向量 u，总能在某个方向上找到点 y \in C 使得 \langle u | y - x \rangle > 0。唯一满足对所有 y \in C 都有 \langle u | y - x \rangle \leq 0 的向量是零向量。因此内部点处的法锥退化为 N_C(x) = \{0\}。

当 C 本身是向量空间（特别是 \mathcal{H} 的线性子空间）时，法锥具有特别简洁的形式。对于任意 x \in C，由于 C 是向量空间，对于任何 y \in C 和任何标量 \lambda，都有 x + \lambda(y - x) \in C（即 C 关于任意线性组合封闭）。要使 u \in N_C(x)，需要对所有 y \in C 有 \langle u | y - x \rangle \leq 0。但由于 C 是向量空间，2x - y 也在 C 中，所以同时有 \langle u | 2x - y - x \rangle = \langle u | x - y \rangle \leq 0，即 \langle u | y - x \rangle \geq 0。结合两个不等式，必然 \langle u | y - x \rangle = 0。由于这对所有 y \in C 成立，u 正交于 C 中从 x 出发的所有方向，也就是正交于整个子空间 C。因此 N_C(x) = C^{\perp}，即 C 的正交补空间。

最后，将法锥概念与投影联系起来。设 C 是Hilbert空间 \mathcal{H} 的非空闭凸集。对于任意 x \in \mathcal{H}，点 \hat{x} 是 x 在 C 上的投影，即 \hat{x} = P_C(x)，当且仅当

这个等价性直接来自投影的刻画条件。根据定义，x - \hat{x} \in N_C(\hat{x}) 意味着 \hat{x} \in C 且对所有 y \in C 有 \langle x - \hat{x} | y - \hat{x} \rangle \leq 0，这正是投影的变分不等式条件。这个刻画给出了投影的几何图像：将点 x 投影到闭凸集 C 上，得到的投影点 \hat{x} 具有这样的性质：连接 \hat{x} 和 x 的向量恰好落在 C 在 \hat{x} 处的法锥内，即这个向量"垂直"于 C 在该点的切方向。对于光滑边界的凸集，这意味着连线垂直于边界；对于有棱角的凸集，连线落在该点处所有支撑超平面法向量张成的锥内。这个几何图像为投影算子的性质研究和应用提供了直观的理解。

向量子空间的法锥

前面提到当 C 是向量空间时，法锥有特殊的形式。现在详细推导这个结果。设 C 是 \mathscr{H} 的向量子空间，对于任意 x \in C，法锥定义为

由于 C 是向量空间，它对加法和数乘封闭。对于任意 y \in C，因为 x \in C，差 y - x 也在 C 中。更一般地，对于任何 v \in C，我们可以取 y = x + v（显然 y \in C 因为 C 是向量空间），此时 y - x = v。因此法锥的条件变为：对所有 v \in C 都有 \langle u | v \rangle \leq 0。

但向量空间的另一个关键性质是：如果 v \in C，那么 -v 也在 C 中（取标量 -1）。因此同时有 \langle u | v \rangle \leq 0 和 \langle u | -v \rangle = -\langle u | v \rangle \leq 0。这两个不等式只有在 \langle u | v \rangle = 0 时才能同时成立。由于这对所有 v \in C 都成立，u 必须与 C 中的每个向量正交。因此

这个结果表明，向量子空间在任何点处的法锥都是它的正交补空间，且不依赖于具体的点 x。

投影算子的具体例子

闭向量子空间的正交投影

第一个例子考虑 C 是Hilbert空间 \mathcal{H} 的闭向量子空间。此时投影算子 P_C 就是经典的正交投影。根据投影的刻画，对于任意 x \in \mathcal{H}，\hat{x} = P_C(x) 当且仅当

这个等价性来自前面建立的关系 x - \hat{x} \in N_C(\hat{x}) 结合向量子空间的法锥等于其正交补的事实。几何上，这意味着将点 x 分解为两个正交分量：一个在子空间 C 内（即 \hat{x}），另一个垂直于 C（即 x - \hat{x}）。这就是Hilbert空间的正交分解定理的几何表述。

仿射超平面的投影

第二个例子更具体。设 \mathcal{H} 是Hilbert空间，u \in \mathcal{H} \setminus \{0\} 是非零向量，\delta \in \mathbb{R} 是常数。定义闭仿射超平面

这是所有与固定向量 u 的内积等于 \delta 的点的集合，是一个余维数为1的仿射子空间。如果 \delta = 0，它就是向量 u 的正交补空间；如果 \delta \neq 0，它是该正交补空间的一个平移。

投影公式给出：对于任意 x \in \mathcal{H}，

这个公式的几何意义是：从 x 出发，沿着 u 方向（或其相反方向）移动适当的距离，使得到达超平面 C。校正项 \frac{\delta - \langle u | x \rangle}{\|u\|^2} u 的分子 \delta - \langle u | x \rangle 度量了 x 偏离超平面的"有符号距离"，分母 \|u\|^2 用于归一化。

为了验证这确实是投影，需要检查两个条件。首先，P_C(x) 必须在 C 中，即满足 \langle u | P_C(x) \rangle = \delta。计算

因此 P_C(x) \in C 得到验证。

其次，需要验证变分不等式：对所有 y \in C，有 \langle x - P_C(x) | y - P_C(x) \rangle \leq 0。注意到

这个向量平行于 u。对于任意 y \in C，计算内积

由于 y, P_C(x) \in C，都有 \langle u | y \rangle = \delta 和 \langle u | P_C(x) \rangle = \delta，所以 \langle u | y - P_C(x) \rangle = \delta - \delta = 0。因此整个内积为零，满足 \leq 0 的要求。这证明了给出的公式确实定义了投影算子。

闭半空间的投影

第三个例子考虑闭半空间

这是仿射超平面的一侧，包含所有与 u 的内积不超过 \delta 的点。投影公式是分段的：

这个公式的几何意义清晰：如果点 x 已经在半空间 C 内（即 \langle u | x \rangle \leq \delta），那么它就是自己的投影，无需移动。如果 x 在半空间外（即 \langle u | x \rangle > \delta），那么需要将它沿着法向量 u 的方向拉回到边界超平面 \langle u | x \rangle = \delta 上，投影公式与仿射超平面情况完全相同。这反映了一个几何事实：对于半空间外的点，最近点必然在边界上；对于半空间内的点，最近点就是自己。

投影算子的重要性质

坚定非扩张性

投影算子的第一个基本性质是坚定非扩张性（firmly nonexpansive）。这个性质说，对于任意两点 x, y \in \mathcal{H}^2，它们的投影之间的距离平方不超过原始向量差与投影差的内积：

这是比非扩张性更强的性质。为了证明它，利用投影的变分不等式刻画。由于 P_C(x) \in C 和 P_C(y) \in C，根据变分不等式，我们有

以及

将这两个不等式相加，得到

利用内积的双线性性质，可以重新组织这个表达式。左边可以写成

改变符号（注意 P_C(y) - P_C(x) = -(P_C(x) - P_C(y))），得到

即

整理后正是我们要证明的不等式。

非扩张性与连续性

从坚定非扩张性可以直接推导出非扩张性（nonexpansive property）：

证明使用Cauchy-Schwarz不等式。由坚定非扩张性，

如果 P_C(x) \neq P_C(y)，两边同时除以 \|P_C(x) - P_C(y)\| 得到所需不等式。如果 P_C(x) = P_C(y)，不等式显然成立（两边都是零）。

非扩张性的几何意义是：投影不会增加距离，它是一个"收缩"映射（或者说保持距离的弱化版本）。这立即蕴含投影算子是一致连续的：对于任意 \epsilon > 0，取 \delta = \epsilon，当 \|x - y\| < \delta 时就有 \|P_C(x) - P_C(y)\| \leq \|x - y\| < \epsilon。

距离函数的连续性

定义点 x 到集合 C 的距离为

由于投影的存在性和唯一性，这个下确界实际上可以达到，等于 x 到其投影点的距离。距离函数 d_C: \mathcal{H} \to \mathbb{R} 也是连续的。

为了证明连续性，对任意 x, y \in \mathcal{H}^2，估计距离函数值的差。利用三角不等式和投影的非扩张性，

这可以通过以下不等式链控制：

交换 x 和 y 的角色得到相反方向的不等式，因此 |d_C(y) - d_C(x)| \leq 2\|y - x\|。这证明了距离函数不仅连续，而且是Lipschitz连续的，Lipschitz常数为2。这个结果在优化算法的收敛性分析中经常用到，它保证了距离函数对输入的扰动不会过度敏感。

投影算子的应用实例

投影到正交象限

第一个练习考虑投影到 \mathbb{R}^N 中的正交象限 C = [0, +\infty[^N。这个集合包含所有坐标都非负的点，是一个闭凸锥。对于任意点 x \in \mathbb{R}^N，我们需要找到它在 C 上的投影。

投影公式非常直观：定义 \hat{x} = (\hat{x}^{(i)})_{1 \leq i \leq N}，其中每个分量由下式给出

这个公式的几何意义是：对于每个坐标分别处理，如果该坐标已经非负，则保持不变；如果该坐标为负，则将其"截断"到零。这是因为正交象限的边界由各个坐标平面组成，负坐标点的最近点必然在相应的坐标面上。

验证这确实是投影需要检查变分不等式。首先，显然 \hat{x} \in C 因为所有坐标都非负。其次，对于任意 y \in C，需要验证 \langle y - \hat{x} | x - \hat{x} \rangle \leq 0。展开这个内积，得到

关键观察是：只有在 x_i < 0 的指标 i 处，x_i - \hat{x}^{(i)} 才非零（此时等于 x_i - 0 = x_i < 0）。对于这些指标，由于 y \in C，必然 y_i \geq 0，而 \hat{x}^{(i)} = 0，所以 y_i - \hat{x}^{(i)} = y_i \geq 0。因此每个非零项都是非负数乘以负数，结果为非正：

这证明了 P_C(x) = \hat{x}，即投影就是将每个负坐标替换为零的逐分量截断操作。

投影到闭球

第二个练习考虑投影到以 \bar{x} 为中心、半径为 \rho 的闭球 B(\bar{x}, \rho) = \{x \in \mathbb{R}^N \mid \|x - \bar{x}\| \leq \rho\}。这也是一个闭凸集。投影公式取决于点 x 是否已经在球内：

几何意义清晰：如果点 x 已经在球内（包括边界），它就是自己的投影。如果 x 在球外，投影点位于从球心 \bar{x} 指向 x 的射线与球面的交点。公式 \bar{x} + \rho \frac{x - \bar{x}}{\|x - \bar{x}\|} 表示从球心出发，沿着单位方向 \frac{x - \bar{x}}{\|x - \bar{x}\|} 移动距离 \rho，正好到达球面。

验证这是投影的关键在于球外情况。首先 \hat{x} \in C 是显然的，因为 \|\hat{x} - \bar{x}\| = \rho。对于任意 y \in C，计算内积

提取公因子 \frac{x - \bar{x}}{\|x - \bar{x}\|}，这个单位向量记为 u。右边的因子变为 (x - \bar{x}) - \rho u = \|x - \bar{x}\| u - \rho u = (\|x - \bar{x}\| - \rho)u。因此

继续展开内积，

第一个因子 \|x - \bar{x}\| - \rho 非负（因为假设 x \notin C 即 \|x - \bar{x}\| > \rho，等号情况已经在第一个分支处理）。实际上当 x 严格在球外时这个因子为正。对于第二个因子，由于 y \in C 即 \|y - \bar{x}\| \leq \rho，根据Cauchy-Schwarz不等式，

因此第二个因子 \langle y - \bar{x} | u \rangle - \rho \leq 0。两个因子符号相反（或有一个为零），所以乘积非正，满足变分不等式。这证明了投影公式的正确性。

关于球投影的测验分析

测验6提出了一个二维的具体问题。设 y = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \in \mathbb{R}^2，B 是以原点 \begin{bmatrix} 0 \\ 0 \end{bmatrix} 为中心、半径为5的闭球。

第一个陈述说投影无法定义因为 B 不是凸的。这显然是错误的。闭球是凸集的典型例子：任取球内两点，连接它们的线段上所有点到球心的距离都不超过两端点到球心距离的凸组合，因此也在球内。投影是良定义的。

第二个陈述考虑 y = \begin{bmatrix} 3\alpha \\ 4\alpha \end{bmatrix}，其中 \alpha \neq 0。声称投影仅在 \alpha \geq 1 时定义，此时给出 \begin{bmatrix} 3 \\ 4 \end{bmatrix}。这个陈述部分正确但不完整。首先注意到 \|y\| = \sqrt{9\alpha^2 + 16\alpha^2} = 5|\alpha|。当 |\alpha| < 1 时，点 y 已经在球内，投影就是 y 本身，而不是未定义。当 |\alpha| \geq 1 时，y 在球外或边界上，投影应该是从原点指向 y 方向上半径为5的点，即 \frac{5}{\|y\|} y = \frac{5}{5|\alpha|} \begin{bmatrix} 3\alpha \\ 4\alpha \end{bmatrix} = \frac{1}{|\alpha|} \begin{bmatrix} 3\alpha \\ 4\alpha \end{bmatrix}。当 \alpha = 1 时这确实给出 \begin{bmatrix} 3 \\ 4 \end{bmatrix}，但当 \alpha > 1 或 \alpha < 0 时结果不同。所以这个陈述不准确。

第三个陈述说对于 \alpha \neq 0，投影总是定义的，且当 |\alpha| \geq 1 时给出 \begin{bmatrix} 3\alpha/|\alpha| \\ 4\alpha/|\alpha| \end{bmatrix}。这是正确的。投影对所有点都定义（因为球是闭凸集）。当 |\alpha| \geq 1 即 \|y\| \geq 5 时，投影公式给出 \frac{5}{\|y\|} y = \frac{5}{5|\alpha|} \begin{bmatrix} 3\alpha \\ 4\alpha \end{bmatrix} = \begin{bmatrix} 3\alpha/|\alpha| \\ 4\alpha/|\alpha| \end{bmatrix}。注意 \alpha/|\alpha| = \text{sgn}(\alpha)，所以当 \alpha > 0 时得到 \begin{bmatrix} 3 \\ 4 \end{bmatrix}，当 \alpha < 0 时得到 \begin{bmatrix} -3 \\ -4 \end{bmatrix}。这个陈述完整且正确。

关于立方体投影的测验分析

测验7考虑投影到三维立方体 C = \{x \in \mathbb{R}^3 \mid |x_1| \leq \alpha, |x_2| \leq \beta, |x_3| \leq \gamma\}，其中 \alpha, \beta, \gamma > 0。

第一个陈述说投影无法定义因为 C 不是闭的。这是错误的。集合 C 是三个闭区间 [-\alpha, \alpha]、[-\beta, \beta]、[-\gamma, \gamma] 的笛卡尔积，因此是闭集。而且它显然是有界凸集（任意两点的凸组合的每个坐标都满足相应的界）。投影是良定义的。

第二个陈述说投影在 C 上定义且构成连续映射。这是正确的。前面已经证明了闭凸集上的投影算子是一致连续的（甚至是非扩张的），利用了投影的存在唯一性和坚定非扩张性质。对于立方体这样的闭凸集，所有这些结果都适用。

第三个陈述给出具体例子：如果 y = \begin{bmatrix} \alpha/2 \\ -2\beta \\ 3\gamma \end{bmatrix}，那么投影的坐标是 \begin{bmatrix} \alpha/2 \\ -\beta \\ \gamma \end{bmatrix}。这是正确的。立方体的投影可以分坐标独立计算（因为约束条件是可分离的）：对于第 i 个坐标，投影就是将 y_i 限制在 [-\alpha_i, \alpha_i] 范围内。具体地，第一个坐标 \alpha/2 已经在 [-\alpha, \alpha] 内，保持不变；第二个坐标 -2\beta 超出了下界 -\beta，被截断到 -\beta；第三个坐标 3\gamma 超出了上界 \gamma，被截断到 \gamma。因此投影确实是 \begin{bmatrix} \alpha/2 \\ -\beta \\ \gamma \end{bmatrix}。这个例子展示了投影到矩形区域（或高维立方体）的逐坐标截断性质。

可行性问题与POCS算法

可行性问题的基本设置

在许多实际应用中，我们需要找到同时满足多个约束条件的点。这类问题称为可行性问题。设 \mathcal{H} 是Hilbert空间，m \in \mathbb{N} \setminus \{0,1\} 是大于1的自然数。给定 m 个闭凸子集 (C_i)_{1 \leq i \leq m}，假设它们的交集非空，即

可行性问题的目标是找到一个点 \hat{x} 使得

换句话说，我们需要找到同时属于所有集合 C_1, C_2, \ldots, C_m 的一个点。这样的点称为可行点。在图像处理、信号恢复、约束优化等领域，可行性问题无处不在。每个集合 C_i 通常代表一个约束条件，交集中的点就是满足所有约束的解。

与显式计算交集不同（这在高维空间中通常是困难的），我们采用迭代投影的方法来逼近可行点。这就是接下来要介绍的POCS算法。

POCS算法的基本形式

POCS（Projection Onto Convex Sets）算法是一种经典的迭代方法，通过循环地将当前点投影到各个约束集上来寻找可行点。算法的基本步骤如下：

对于每个自然数 n \in \mathbb{N}，定义 i_n - 1 为 n 除以 m 的余数。这意味着 i_n \in \{1, 2, \ldots, m\}，且指标按照循环模式重复：i_0 = 1, i_1 = 2, \ldots, i_{m-1} = m, i_m = 1, i_{m+1} = 2, \ldots。算法从任意初始点 x_0 \in \mathcal{H} 开始，对于 n = 0, 1, 2, \ldots，迭代更新

这个迭代过程的几何意义是：在第 n 步，将当前点 x_n 投影到集合 C_{i_n} 上得到下一个点 x_{n+1}。由于指标 i_n 按照 1, 2, \ldots, m, 1, 2, \ldots 的循环模式变化，算法依次对每个约束集进行投影，然后重复这个过程。

这个算法的直观思想是：如果当前点不满足某个约束，就将它投影到该约束集上（这是满足该约束的最近的调整）。通过循环地对所有约束进行这种调整，希望最终收敛到满足所有约束的点。

POCS算法的松弛形式

基本POCS算法可以加入松弛参数来提高灵活性和收敛性。松弛版本引入一个参数序列 (\lambda_n)_{n \geq 0}，满足 \lambda_n \in [\epsilon_1, 2 - \epsilon_2]，其中 (\epsilon_1, \epsilon_2) \in ]0, +\infty[^2 且 \epsilon_1 + \epsilon_2 < 2。这些参数控制每次投影的"步长"。

松弛算法的迭代公式变为

当 \lambda_n = 1 时，这就退化为基本POCS算法。当 0 < \lambda_n < 1 时，称为欠松弛（under-relaxation），新点只向投影点移动部分距离；当 1 < \lambda_n < 2 时，称为过松弛（over-relaxation），新点超过投影点移动。

松弛参数的约束条件 \epsilon_1 \leq \lambda_n \leq 2 - \epsilon_2 确保了既不能太接近0（否则收敛太慢），也不能太接近2或超过2（否则可能发散）。参数 \epsilon_1 + \epsilon_2 < 2 保证了松弛参数有一个非退化的取值区间。

松弛形式可以改写为更直观的凸组合形式：

这表明新点是当前点和投影点的加权平均，权重由松弛参数决定。这种形式在理论分析和实际应用中都很有用，因为它清楚地显示了算法如何在"保持当前位置"和"移向投影点"之间权衡。

POCS算法的收敛性

POCS算法的核心理论结果是收敛性定理：在上述设置下，POCS算法生成的序列 (x_n)_{n \in \mathbb{N}} 弱收敛到交集 \bigcap_{i=1}^m C_i 中的某个点。这里"弱收敛"是指在Hilbert空间的弱拓扑意义下收敛，对于有限维空间这就是通常的收敛。

这个结果的意义深远：即使不知道交集的显式表达式，只要能够对每个集合进行投影，通过循环投影就能够逼近可行点。算法的收敛性不依赖于初始点的选择，这使得它在实践中非常稳健。

收敛性的证明依赖于投影算子的非扩张性和坚定非扩张性。关键观察是：对于交集中的任意点 \hat{x}，每次投影都不会增加到 \hat{x} 的距离（因为投影是非扩张的），而且如果当前点不在某个集合 C_i 中，投影到 C_i 会严格减小到 \hat{x} 的距离。通过精心的分析可以证明，序列 \|x_n - \hat{x}\| 收敛，进而可以推导出序列 (x_n) 本身的弱收敛性。

拟循环规则的推广

基本POCS算法使用严格的循环规则：投影的顺序是 C_1, C_2, \ldots, C_m, C_1, C_2, \ldots，周而复始。收敛性定理的一个重要备注是：即使将循环规则替换为拟循环规则（quasi-cyclic rule），结果仍然成立。

拟循环规则的定义是：指标序列 (i_n)_{n \geq 0} 满足存在某个 K \in \mathbb{N} 使得对所有 n \in \mathbb{N}，集合 \{1, 2, \ldots, m\} 包含在 \{i_n, i_{n+1}, \ldots, i_{n+K}\} 中。换句话说，在任意连续的 K+1 次迭代中，所有 m 个集合都至少被访问一次。

这个推广大大增加了算法的灵活性。不需要严格按照 1, 2, \ldots, m 的顺序投影，只要保证每个集合被"足够频繁"地访问即可。例如，可以根据当前点与各个集合的距离来动态选择下一个投影的集合（选择距离最大的集合），或者使用某种随机选择策略，只要满足拟循环条件即可。

拟循环规则的实用意义在于：在某些应用中，对某个约束集的投影计算可能比其他约束集更耗时。拟循环规则允许我们使用自适应策略，比如优先对容易计算的集合进行投影，或根据违反程度来确定投影顺序，从而在保持收敛性的同时提高算法的实际效率。这使得POCS算法不仅是一个优美的理论工具，也是一个在实践中高度灵活和有效的计算方法。