近端算子

在现代数学优化理论中，近端算子（Proximal Operators）、莫洛厄包络（Moreau Envelope）、子梯度方法（Subgradient Methods）、支持向量机（Support Vector Machines, SVM）以及稀疏优化（Sparse Optimization）等概念占据着核心地位。这些工具不仅在理论研究中具有重要意义，而且在机器学习、信号处理、统计学等应用领域展现出广泛的实用性。本文旨在深入讲解这些知识点，全面覆盖相关理论基础、性质、计算方法以及实际应用，通过一些的习题解答帮助读者巩固理解。

凸分析基础

在进入优化方法与近端算子的深入探讨之前，理解凸分析的基础知识至关重要。凸分析为优化问题的研究提供了坚实的理论基础。

¶凸集与凸函数

凸集：在实数向量空间 中，一个集合 被称为凸集，如果对于任意的 和任意的 ，有

这意味着任意两点之间的线段完全包含在集合 内。

凸函数：一个函数 被称为凸函数，如果其定义域是一个凸集，并且对于任意的 在定义域内，以及任意的 ，满足

这表示函数图像的线段不低于函数本身，凸函数具有“凹向上”的形状。

凸集与凸函数的性质：

• 局部最小即全局最小：在凸函数的定义域内，任何局部最小点都是全局最小点。
• 支持超平面：对于凸集和凸函数，可以在任意边界点处找到支持超平面，这在优化问题中用于构建对偶问题和分析最优性条件。

¶子梯度与次梯度

对于非光滑凸函数，传统的梯度概念不足以描述其变化。为此，引入了子梯度的概念。

子梯度（Subgradient）：设 是一个凸函数，向量 称为 在点 处的子梯度，如果对于所有的 ，有

子梯度集合记作 。具体一点来说，对于一个光滑的凸函数，梯度（导数）在每一点都唯一地指示了函数在该点的最陡上升方向。然而，当函数在某些点不可微时（例如，函数在这些点处有尖点或折角），梯度不再存在。这时，子梯度的概念就派上用场了。

子梯度可以被视为在不可微点处的所有可能的“斜率”或“支撑平面”的集合。具体来说，对于一个凸函数 在点 处的子梯度 ，它满足以下条件：

这意味着，子梯度 定义了一条过点 的支撑线（在一维情况下）或支撑超平面（在多维情况下），并且函数 在所有点 上都位于这条线或超平面的上方或与其重合。

• 可微点（）：在 时，函数光滑且导数为 ；在 时，导数为 。
• 不可微点（）：在 处，函数有一个尖点。此时，子梯度集合 包含所有介于 和 之间的值。也就是说，任何 满足 都是 在 处的子梯度。

次梯度（Subdifferential）：子梯度集合 称为函数 在点 处的次梯度。

性质：

• 如果 在 处可微，则 仅包含梯度 。
• 子梯度集是凸集。
• 对于凸函数，子梯度的存在性：若 是凸函数且下半连续，则对于任意 在其定义域内， 非空。

优化问题的基本概念

优化问题通常形式化为：

其中， 是目标函数。根据 的性质，优化问题可以分为凸优化和非凸优化。凸优化由于其良好的理论性质和算法可行性，成为研究的重点。

凸优化的优点：

• 全局最优性：任何局部最优点都是全局最优点。
• 强对偶性：在满足一定条件下，原问题和对偶问题的最优值相等，便于问题求解。
• 丰富的算法：包括梯度下降、次梯度方法、内点法等高效算法。

近端算子（Proximal Operators）

近端算子是凸优化中的一个关键工具，尤其在处理非光滑项时发挥重要作用。它在优化算法中用于分解复杂问题，简化求解过程。

¶近端算子的定义

对于给定的函数 ，其近端算子定义为：
$$
\operatorname{prox}{f}(v) = \arg\min{x \in \mathbb{R}^n} \left( f(x) + \frac{1}{2} |x - v|_2^2 \right)
$$
其中， 表示欧几里得范数。

解释：近端算子通过在目标函数 上添加一个二次惩罚项，平衡函数值与与输入点 的距离，从而找到一个在 下的“近邻”点。

¶近端算子的性质

近端算子具有以下重要性质：

1. 非扩张性（Non-expansiveness）：对于任意 ，有
   $$
   |\operatorname{prox}{f}(v) - \operatorname{prox}{f}(w)|_2 \leq |v - w|_2
   $$
   这意味着近端算子不会扩展两个点之间的距离。

2. 单调性（Monotonicity）：如果 是凸函数，则近端算子 是单调的。

3. 与梯度算子的关系：当 是光滑函数时，近端算子与梯度算子存在紧密联系。例如，对于 $f(x) = \frac{1}{2} |x|2^2\operatorname{prox}{f}(v) = \frac{v}{1 + 1}$。

4. 可拆性（Separability）：如果 是分量独立的，即 ，则近端算子也具有分量独立性：
   $$
   \operatorname{prox}_{f}(v)i = \operatorname{prox}{f_i}(v_i)
   $$

常见的近端算子

¶-范数的近端算子（软阈值算子）

对于 $f(x) = \lambda |x|1 = \lambda \sum{i=1}^n |x_i|$
\operatorname{prox}_{\lambda |\cdot|_1}(v)i =

\operatorname{prox}{\lambda |\cdot|_1}(v) = \text{sign}(v) \cdot \max{ |v| - \lambda, 0 }
$$
其中， 为符号函数。软阈值算子将输入信号中的每个分量进行“软”压缩，即对绝对值较小的分量设为零，对较大的分量则向零方向收缩。具体图形如下：

图示说明：

• 红色曲线：表示软阈值算子 的输出。
• 蓝色虚线：表示恒等函数 。
• 灰色虚线：标示阈值 和 。

应用：在稀疏优化中，-范数的近端算子用于推动解的稀疏性。

¶指示函数的近端算子

设 为指示函数，即：

其中 是一个凸集。则其近端算子为集合 上的投影算子：
$$
\operatorname{prox}{f}(v) = P_C(v) = \arg\min{x \in C} |x - v|_2^2
$$
这表示将点 投影到集合 上，找到距离 最近的点。

对于下面的图而言，也就是说：

• 点 在凸集内时，投影点即为 本身。
• 点 在凸集外时，投影点是 到 上的最近点。

应用：在约束优化中，投影算子用于确保迭代点满足特定约束。

¶平方范数的近端算子

对于 $f(x) = \frac{\lambda}{2} |x|2^2$
\operatorname{prox}{f}(v) = \frac{v}{1 + \lambda}
$$
推导：
$$
\operatorname{prox}{f}(v) = \arg\min{x} \left( \frac{\lambda}{2} |x|_2^2 + \frac{1}{2} |x - v|_2^2 \right)

\lambda x + (x - v) = 0 \Rightarrow x = \frac{v}{1 + \lambda}
$$

平方范数的近端算子是一个线性缩放，将输入 缩放至 ，如下图：

¶更一般的近端算子

对于更一般的函数 ，近端算子可能没有闭式解，此时通常需要使用数值方法（如牛顿法、半平方法等）进行近似求解。

注意：计算近端算子时，函数 的结构和性质决定了其计算难度和所需方法。

莫洛厄包络（Moreau Envelope）

莫洛厄包络是近端算子的一个重要伴侣，提供了对非光滑函数的平滑化处理，使得优化问题更易处理。

¶莫洛厄包络的定义

对于闭合的凸函数 ，其莫洛厄包络定义为：

这实际上是在 上施加一个二次平滑化操作，得到一个新的光滑函数 。

¶莫洛厄包络的性质

¶与原函数的关系

• 相同的最小值：如果 取得最小值 $f^x^\widehat{f}(x^) = f(x^)$。
• 相同的最优解：最优解点 在 和 中相同。

证明：

设 $x^f$
f(x^) = \min_{y} f(y)

\widehat{f}(x^) = \min_{y} \left( f(y) + \frac{1}{2} |y - x^*|_22 \right)
$$
由于 $x^f$
\widehat{f}(x^) \leq f(x^) + \frac{1}{2} |x^* - x^*|_22 = f(x^*)
$$

另一方面，对于任意 ，
$$
\widehat{f}(x^) \geq f(x^) + \frac{1}{2} |x^* - x^*|_22 = f(x^*)
$$

因此，
$$
\widehat{f}(x^) = f(x^)
$$
即 和 在 处取得相同的最小值。

¶平滑性

莫洛厄包络 是一个光滑函数，即 具有连续的一阶导数。这对于设计高效的优化算法尤为重要，因为光滑函数可以利用梯度信息进行优化。

推导：

由于 是 与二次函数的卷积，且 是闭合凸函数， 自动具备1-光滑性。

¶梯度与近端算子的关系

莫洛厄包络的梯度与近端算子之间存在如下关系：

这表明，莫洛厄包络的梯度可以通过近端算子直接计算得到。

证明：

设 $y = \operatorname{prox}{f}(x)$
y = \arg\min{y} \left( f(y) + \frac{1}{2} |y - x|2^2 \right)

0 \in \partial f(y) + (y - x)

x - y \in \partial f(y)

\nabla \widehat{f}(x) = x - y = x - \operatorname{prox}{f}(x)
$$

应用：通过莫洛厄包络，可以将非光滑优化问题转化为光滑优化问题，利用梯度信息加速优化过程。

子梯度方法（Subgradient Methods）

子梯度方法是一类用于求解非光滑凸优化问题的迭代方法。尽管这些方法在收敛速度上不及光滑优化方法，但其适用范围更广，特别是在处理包含非光滑项的优化问题时表现突出。

¶子梯度的定义与性质

子梯度定义：

对于凸函数 ，向量 称为 在点 处的子梯度，如果对于所有 ，有

子梯度集合记作 。

性质：

1. 子梯度存在性：若 是闭合的凸函数且 是 的内部点，则 非空。
2. 凸性：子梯度集 是凸集。
3. 连续性：如果 是凸且下半连续，则子梯度集随着 的变化而变化，存在连续性性质。

¶子梯度下降法

子梯度下降法是一种基础的迭代优化方法，适用于非光滑凸优化问题。

算法描述：

给定初始点 ，步长序列 ，子梯度序列 ，迭代过程为：

其中，。

收敛性分析：

1. 步长选择：步长序列 的选择对算法的收敛性至关重要。常见的选择包括：

   • 固定步长：。
   • 随机步长： 随 逐渐减小，例如 。

2. 收敛性条件：

   • 若 且 ，则子梯度下降法保证收敛至最优值。
   • 对于特定的步长选择，如 ，可以保证收敛性。

3. 收敛速度：

   子梯度方法的收敛速度通常较慢，尤其是在非光滑情况下。理论上，误差的上界为 ，其中 是迭代次数。

应用：适用于求解包含非光滑项的凸优化问题，如支持向量机、LASSO 等。

支持向量机（Support Vector Machines, SVM）

支持向量机是一种广泛应用于分类问题的监督学习模型。其目标是寻找一个最优的分类超平面，最大化不同类别样本之间的间隔，以提升模型的泛化能力。

¶支持向量机的基本概念

基本思想：在特征空间中，支持向量机通过构建一个超平面将不同类别的样本分开，并尽可能地最大化分类间隔（即距离最接近的样本点的最小距离）。

线性支持向量机：对于线性可分的数据集，支持向量机寻找一个线性超平面，使得不同类别样本点位于超平面的两侧，并最大化到最近样本点的距离。

¶SVM的优化问题

在实际应用中，数据往往是不可完全线性可分的，因此引入了松弛变量和正则化项。支持向量机的优化问题可以表示为：

其中：

• 是第 个样本的特征向量。
• 是第 个样本的类别标签。
• 是正则化参数，控制模型的复杂度。

目标函数解析：

• 第一项 是铰链损失（Hinge Loss），用于衡量分类误差。
• 第二项 是正则化项，防止模型过拟合，提升泛化能力。

¶SVM的子梯度计算

对于非光滑的铰链损失，传统的梯度方法无法直接应用。因此，使用子梯度方法求解。

子梯度的构造：

对于每个样本 ，损失函数 ，其子梯度为：
$$
\partial f_i(w) = \begin{cases}
0 & \text{如果 } y_i x_i^\top w > 1, \

• y_i x_i & \text{如果 } y_i x_i^\top w < 1, \
  \text{任意在 } {- y_i x_i} \cup {0} & \text{如果 } y_i x_i^\top w = 1.
  \end{cases}
  $$

因此，整体目标函数 的子梯度为：

具体构造子梯度 为：

其中，
$$
g_i = \begin{cases}
0 & \text{如果 } y_i x_i^\top w > 1, \

• y_i x_i & \text{否则}.
  \end{cases}
  $$

解释：只有当样本 的预测值 小于等于 1 时，对应的梯度 被纳入总梯度 中。这些样本称为支持向量，对模型的决策边界有直接影响。

稀疏优化与LASSO

稀疏优化旨在寻找参数中大部分为零的解，这在高维数据分析中具有重要意义，如特征选择、模型简化等。LASSO（Least Absolute Shrinkage and Selection Operator）是一种经典的稀疏优化方法。

¶稀疏优化的背景与意义

在高维数据中，参数维度可能远大于样本数量（即 ，其中 是参数维度），这会导致模型过拟合、计算复杂度高等问题。通过引入稀疏性，可以：

• 选择重要特征：保留对模型预测最重要的特征，去除冗余或无关特征。
• 提高模型可解释性：简化模型结构，使得模型更易于理解和解释。
• 降低计算复杂度：减少非零参数的数量，提升计算效率。

¶LASSO优化问题

LASSO 的优化问题定义为：

其中：

• 是观测矩阵。
• 是观测向量。
• 是正则化参数，控制稀疏性程度。

目标函数解析：

• 第一项 是平方损失，衡量模型的拟合误差。
• 第二项 是 -范数正则化项，促进解的稀疏性。

¶LASSO的几何解释

LASSO 的几何解释源于 -范数的几何形状。与 -范数的圆形等高线不同，-范数的等高线呈菱形，具有尖锐的顶点。这些尖锐顶点倾向于与模型的约束平面相交于坐标轴上，从而促使解具有更多的零元素，实现稀疏性。

图示：

• -范数：等高线为圆形。
• -范数：等高线为菱形。

¶LASSO的解的性质

LASSO 的解具有以下性质：

1. 稀疏性：随着 的增大，解中非零元素的数量减少。
2. 唯一性：在一定条件下，LASSO 的解是唯一的，尤其当观测矩阵 满足某些条件（如强凸性）时。
3. 稳定性：LASSO 解对数据噪声具有一定的鲁棒性，尤其在高噪声环境下表现优异。

应用：LASSO 广泛应用于特征选择、信号恢复、基因数据分析等领域。

优化算法

在处理复杂的优化问题时，选择合适的优化算法至关重要。以下介绍两种常用的优化算法：前向-后向方法和加速的前向-后向方法。

¶前向-后向方法（Forward-Backward Method）

前向-后向方法（也称为 Proximal Gradient Method）适用于优化目标函数由光滑部分和非光滑部分组成的情形。其基本思想是将优化问题分解为两个部分，分别处理。

优化问题形式：

其中， 是光滑凸函数，具有 Lipschitz 连续梯度， 是非光滑凸函数，具有易于计算的近端算子。

算法描述：

给定初始点 ，步长 ，迭代过程为：

其中， 是函数 在点 处的梯度。

步骤解析：

1. 前向步骤：进行梯度下降，计算 。
2. 后向步骤：应用近端算子 $\operatorname{prox}{\alpha g}x{k+1}$。

收敛性分析：

• 步长要求：步长 需满足 ，其中 是 的 Lipschitz 常数。
• 收敛速度：在满足条件下，前向-后向方法的收敛速度为 ，其中 是迭代次数。

应用：前向-后向方法广泛应用于稀疏优化问题，如 LASSO，支持向量机等。

¶加速的前向-后向方法（Accelerated Forward-Backward Method）

加速的前向-后向方法通过引入动量项，提高算法的收敛速度，特别适用于大规模优化问题。

算法描述：

给定初始点 , ，步长 ，动量系数 ，迭代过程为：

步骤解析：

1. 计算动量系数：更新动量参数 和 。
2. 动量步骤：计算动量点 ，结合当前和上一个迭代点。
3. 前向步骤：在动量点 处进行梯度下降，得到临时点。
4. 后向步骤：应用近端算子，更新迭代点 。

收敛性分析：

• 步长要求：步长 同样需满足 ，其中 是 的 Lipschitz 常数。
• 收敛速度：加速的前向-后向方法的收敛速度为 ，显著优于普通前向-后向方法。

应用：适用于需要快速收敛的大规模稀疏优化问题，如大规模 LASSO、图像去噪等。

习题与详解

本节提供了四个综合性的习题，涵盖了近端算子、莫洛厄包络、子梯度方法、支持向量机和稀疏优化等知识点。每个习题后附有详尽的解答，帮助读者巩固所学内容。

¶习题1 - 计算近端算子

题目：

计算以下函数的近端算子 。

(a) -范数 $f(x) = |x|1 = \sum{i=1}^{n} |x_i|$。

(b) 指示函数的 -球

© -范数立方 $f(x) = \alpha |x|3^3 = \alpha \sum{i=1}^{n} |x_i|^3\alpha > 0$。

¶解答

¶(a) -范数的近端算子

目标：计算 。

解析：

近端算子的定义为：
$$
\operatorname{prox}{f}(v) = \arg\min{x} \left( |x|_1 + \frac{1}{2} |x - v|_2^2 \right)
$$
由于 是可分离的，即函数可以分解为各分量的和，因此近端算子的计算也可以逐分量进行。

分量优化：

对于每个 ，求解：

这是一个典型的软阈值问题，其解为：

¶(b) 指示函数的 -球的近端算子

目标：计算 $\operatorname{prox}{f}(v)$
f(x) = \begin{cases}
0 & \text{如果 } |x|\infty \leq 1, \
+\infty & \text{否则}.
\end{cases}
$$

解析：

指示函数的近端算子即为集合 上的投影算子 。

在 -球上，投影操作对每个分量独立进行：

结论：

¶© -范数立方的近端算子

目标：计算 ，其中
$$
f(x) = \alpha |x|3^3 = \alpha \sum{i=1}^{n} |x_i|^3
$$

解析：

近端算子的定义为：
$$
\operatorname{prox}{f}(v) = \arg\min{x} \left( \alpha |x|_3^3 + \frac{1}{2} |x - v|_2^2 \right)
$$
同样，由于 是可分离的，近端算子可以逐分量计算。

对于每个分量 ，求解：

设 （若 为负，则解为 ），则优化问题转化为：

对 求导并令其为零：

这是一个一元三次方程，通常没有解析解。需要使用数值方法（如牛顿法）进行求解。

结论：

对于 $f(x) = \alpha |x|3^3\operatorname{prox}{f}(v)x_ix_i \geq 0v_i$，对称处理。

¶习题2 - 莫洛厄包络的性质

题目：

给定任意闭合的凸函数 ，其莫洛厄包络定义为：
$$
\widehat{f}(x) = \min_{y \in \mathbb{R}^d} \left( f(y) + \frac{1}{2} |y - x|2^2 \right)
$$
且 $\operatorname{prox}{f}(x)yf$ 取得最小值。

(a) 证明 和 具有相同的最小值，并且它们的最优解相同。

(b) 证明 是凸且处处有界的。

© 证明 对 是连续的。

(d) 证明 ，从而 是连续可微的。

¶解答

¶(a) 证明 和 具有相同的最小值，并且它们的最优解相同

目标：证明 和 具有相同的最小值，且它们的最优解相同。

解析：

设 $x^f$
f(x^) = \min_{y} f(y)

\widehat{f}(x^) = \min_{y} \left( f(y) + \frac{1}{2} |y - x^*|_22 \right)
$$
由于 $x^f$
\widehat{f}(x^) \leq f(x^) + \frac{1}{2} |x^* - x^*|_22 = f(x^*)
$$

另一方面，对于任意 ，
$$
\widehat{f}(x^) \geq f(x^) + \frac{1}{2} |x^* - x^*|_22 = f(x^*)
$$

因此，
$$
\widehat{f}(x^) = f(x^)
$$
即 和 在 处取得相同的最小值。

结论：

和 具有相同的最小值，且它们的最优解相同。

¶(b) 证明 是凸且处处有界的

目标：证明 是凸函数且在所有 上有界。

解析：

1. 凸性：

   莫洛厄包络 是凸函数。具体地，设 是凸函数，则 是关于 的凸函数，因此 是两个凸函数的最小值，继而也是凸函数。

2. 有界性：

   对于任意 ，有：
   
   由于 是闭合的，且存在最优解 ，因此 是有限的。

结论：

是一个凸函数，并且在所有 上处处有界。

¶© 证明 对 是连续的

目标：证明 随 连续变化。

解析：

根据近端算子的非扩张性性质，对任意 ，有
$$
|\operatorname{prox}{f}(x) - \operatorname{prox}{f}(y)|_2 \leq |x - y|_2
$$
这表明近端算子是 Lipschitz 连续的，因而也是连续的。

结论：

对 是连续的。

¶(d) 证明 ，从而 是连续可微的

目标：证明 ，并且 是连续可微的。

解析：

设 ，则：

由于 是优化问题的最优解，满足：

即：

因此， 关于 的梯度为：

这意味着，莫洛厄包络 具有唯一的梯度，故 是连续可微的。

结论：

且 是连续可微的。

¶习题3 - 前向-后向方法并非总是最佳选择

题目：

考虑一组观测数据 ${(x_i, y_i)}{i=1}^nx_i \in \mathbb{R}^dy_i \in {\pm 1}$
\min{w \in \mathbb{R}^d} f(w) = \sum_{i=1}^n \max{0, 1 - y_i x_i^\top w} + \frac{\lambda}{2} |w|_2^2
$$`

(a) 对任意 ，证明存在一个子梯度 ，其形式为：

其中，
$$
g_i = \begin{cases}
0 & \text{如果 } y_i x_i^\top w > 1, \

• y_i x_i & \text{否则}.
  \end{cases}
  $$
  (b) 相较于简单的子梯度计算，论证计算 的难度与解决另一个支持向量机问题相当。

¶解答

¶(a) 构造 的子梯度

目标：证明 是 的一个子梯度，其中 如题所定义。

解析：

考虑 。

对于每个 ，定义损失函数：

根据 函数的性质， 的子梯度为：
$$
\partial f_i(w) = \begin{cases}
0 & \text{如果 } y_i x_i^\top w > 1, \

• y_i x_i & \text{如果 } y_i x_i^\top w < 1, \
  \text{任意在 } {- y_i x_i} \cup {0} & \text{如果 } y_i x_i^\top w = 1.
  \end{cases}
  $$
  由于 是各 的和加上正则化项 $\frac{\lambda}{2} |w|2^2$
  \partial f(w) = \sum{i=1}^n \partial f_i(w) + \lambda w
  $$
  选取 ，其中 如题所定义，则 。

结论：

是 的一个子梯度。

¶(b) 论证 的计算难度

目标：论证计算 的难度与解决另一个支持向量机问题相当。

解析：

计算 $\operatorname{prox}{\alpha f}(0)$
\operatorname{prox}{\alpha f}(0) = \arg\min_{w} \left( f(w) + \frac{1}{2\alpha} |w|2^2 \right)

\operatorname{prox}{\alpha f}(0) = \arg\min_{w} \left( \sum_{i=1}^n \max{0, 1 - y_i x_i^\top w} + \frac{\lambda}{2} |w|_2^2 + \frac{1}{2\alpha} |w|_2^2 \right)

\left( \frac{\lambda}{2} + \frac{1}{2\alpha} \right) |w|2^2 = \frac{\lambda + \frac{1}{\alpha}}{2} |w|2^2

\min{w} \sum{i=1}^n \max{0, 1 - y_i x_i^\top w} + \frac{\lambda + \frac{1}{\alpha}}{2} |w|_2^2
$$

这与原始的支持向量机优化问题形式相同，只是正则化参数由 变为 。因此，计算 相当于解决另一个支持向量机问题，其计算复杂度与原问题相当。

结论：

计算 的难度与解决另一个支持向量机问题相当，因其本质上是类似的优化问题。

总结

本教材深入探讨了近端算子、莫洛厄包络、子梯度方法、支持向量机以及稀疏优化等核心概念，详细讲解了它们的定义、性质、计算方法以及应用。通过具体的优化算法（如前向-后向方法和加速的前向-后向方法）和实际的编程实现，读者不仅能够理解理论，还能掌握实际应用技能。通过习题的详尽解答，读者可以进一步巩固所学内容，提升解决实际优化问题的能力。希望本教材能为读者在优化理论与应用领域的学习和研究提供有力支持。