当目标函数带有不可导项（比如稀疏正则、 TV 正则）或约束难以直接处理时，“直接做梯度下降”常常会卡住：要么没有梯度，要么每一步都很难保证可行。近端算子提供了一种非常工程化、也非常漂亮的解决方式——可以把更新理解成“先按光滑部分走一步，再用一个带惩罚的最小化把解拉回到更合理的结构上”。本文会从凸分析与子梯度的最小必要背景出发，逐步引出 Moreau 包络与近端映射的性质、常见近端的闭式解与计算技巧，并把它们放回到 ISTA/FISTA 、 ADMM 、 SVM 与稀疏优化这些具体算法里解释：为什么它们能工作、什么时候会收敛得更快、实现时最容易错在哪里；最后配合习题把关键推导走一遍，确保你不仅“看懂”，还能“用起来”。

凸分析基础

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

凸集与凸函数

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

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

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

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

凸集与凸函数的性质：

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

子梯度与次梯度

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

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

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

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

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

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

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

性质：

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

优化问题的基本概念

优化问题通常形式化为：

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

凸优化的优点：

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

近端算子（ Proximal Operators）

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

近端算子的定义

对于给定的函数，其近端算子定义为：

其中，表示欧几里得范数。

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

近端算子的性质

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

非扩张性（ Non-expansiveness）：对于任意，有

这意味着近端算子不会扩展两个点之间的距离。

单调性（ Monotonicity）：如果是凸函数，则近端算子是单调的。
与梯度算子的关系：当是光滑函数时，近端算子与梯度算子存在紧密联系。例如，对于，有。
可拆性（ Separability）：如果是分量独立的，即，则近端算子也具有分量独立性：

常见的近端算子

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

对于，其近端算子称为软阈值算子，定义为： $如果如果如果$

简化表示为：

其中，为符号函数。软阈值算子将输入信号中的每个分量进行“软”压缩，即对绝对值较小的分量设为零，对较大的分量则向零方向收缩。具体图形如下：

图示说明：

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

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

指示函数的近端算子

设为指示函数，即： $如果否则$

其中是一个凸集。则其近端算子为集合上的投影算子：

这表示将点投影到集合上，找到距离最近的点。

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

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

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

平方范数的近端算子

对于，其近端算子为：

推导：

对求导并令其为零：

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

更一般的近端算子

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

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

莫洛厄包络（ Moreau Envelope）

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

莫洛厄包络的定义

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

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

莫洛厄包络的性质

与原函数的关系

相同的最小值：如果取得最小值在点，则。
相同的最优解：最优解点在和中相同。

证明：

设是的最优解，即

则：

由于是的最优解，有：

另一方面，对于任意，

因此，

即和在处取得相同的最小值。

平滑性

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

推导：

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

梯度与近端算子的关系

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

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

证明：

设，即

对求导，得到：

其中。因此，

结合莫洛厄包络的定义，可得：

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

子梯度方法（ Subgradient Methods）

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

子梯度的定义与性质

子梯度定义：

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

子梯度集合记作。

性质：

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

子梯度下降法

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

算法描述：

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

其中，。

收敛性分析：

步长选择：步长序列的选择对算法的收敛性至关重要。常见的选择包括：
- 固定步长：。
- 随机步长：随逐渐减小，例如。
收敛性条件：
- 若且，则子梯度下降法保证收敛至最优值。
- 对于特定的步长选择，如，可以保证收敛性。
收敛速度：

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

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

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

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

支持向量机的基本概念

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

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

SVM 的优化问题

在实际应用中，数据往往是不可完全线性可分的，因此引入了松弛变量和正则化项。支持向量机的优化问题可以表示为： $Extra close brace or missing open brace\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$

其中：

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

目标函数解析：

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

SVM 的子梯度计算

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

子梯度的构造：

对于每个样本

，损失函数

，其子梯度为：$$f_i(w) =

Extra close brace or missing open brace\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 =

如 果 否 则

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

稀疏优化与 LASSO

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

稀疏优化的背景与意义

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

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

LASSO 优化问题

LASSO 的优化问题定义为：

其中：

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

目标函数解析：

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

LASSO 的几何解释

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

图示：

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

LASSO 的解的性质

LASSO 的解具有以下性质：

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

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

优化算法

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

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

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

优化问题形式：

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

算法描述：

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

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

步骤解析：

前向步骤：进行梯度下降，计算。
后向步骤：应用近端算子进行投影，得到新的迭代点。

收敛性分析：

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

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

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

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

算法描述：

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

步骤解析：

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

收敛性分析：

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

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

习题与详解

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

习题 1 - 计算近端算子

题目：

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

(a)-范数。

指示函数的-球 $如果否则$ (c)-范数立方，其中。

解答

(a)-范数的近端算子

目标：计算。

解析：

近端算子的定义为：

由于是可分离的，即函数可以分解为各分量的和，因此近端算子的计算也可以逐分量进行。

分量优化：

对于每个，求解：

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

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

目标：计算，其中 $如果否则$

解析：

指示函数的近端算子即为集合$C = {x ^n : |x|_ } $上的投影算子$ P_C(v)$。

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

结论： $Extra close brace or missing open brace\operatorname{prox}_{f}(v)_i = \min\{\max\{v_i, -1} , 1 }$

(c)-范数立方的近端算子

目标：计算，其中

解析：

近端算子的定义为：

同样，由于是可分离的，近端算子可以逐分量计算。

对于每个分量，求解：

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

对求导并令其为零：

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

结论：

对于，其近端算子的每个分量需要通过数值方法求解以下方程：

解得：

其中，。对于负的，对称处理。

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

题目：

给定任意闭合的凸函数，其莫洛厄包络定义为：

且是唯一的使得上式取得最小值的。假设取得最小值。

证明和具有相同的最小值，并且它们的最优解相同。
证明是凸且处处有界的。
证明对是连续的。
证明$(x) = {x - _{f}(x) } $，从而$ $是连续可微的。

解答

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

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

解析：

设是的最优解，即

则：

由于是的最优解，有：

另一方面，对于任意，

因此，

即和在处取得相同的最小值。

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

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

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

解析：

凸性：

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

对于任意，有：

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

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

(c) 证明对是连续的

目标：证明随连续变化。

解析：

根据近端算子的非扩张性性质，对任意，有

这表明近端算子是 Lipschitz 连续的，因而也是连续的。

结论：对是连续的。

(d) 证明$(x) = {x - _{f}(x) } $，从而$ $是连续可微的

目标：证明$(x) = {x - _{f}(x) } $，并且$ $是连续可微的。

解析：

设，则：

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

即：

因此，关于的梯度为：

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

结论： $Extra close brace or missing open brace\partial \widehat{f}(x) = \{x - \operatorname{prox}_{f}(x) }$

且是连续可微的。

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

题目：

考虑一组观测数据，其中是特征向量，是对应标签。支持向量机（ SVM）通过求解以下优化问题来训练分类器： $Extra close brace or missing open brace\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$ `

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

其中，$$g_i =

如 果 否 则

$ $相较于简单的子梯度计算，论证计算$ _{f}(0)$的难度与解决另一个支持向量机问题相当。

解答

(a) 构造的子梯度

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

解析：

考虑 $Extra close brace or missing open bracef(w) = \sum_{i=1}^n \max\{0, 1 - y_i x_i^\top w} + \frac{\lambda}{2} \|w\|_2^2$ 。

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

根据

函数的性质，

的子梯度为：$$f_i(w) =

Extra close brace or missing open brace\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}

由于是各的和加上正则化项，其子梯度为各部分子梯度的和。因此，

选取，其中如题所定义，则。

结论：是的一个子梯度。

(b) 论证的计算难度

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

解析：

计算的定义为：

将代入， $Extra close brace or missing open brace\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)$

简化正则化项：

因此，问题转化为： $Extra close brace or missing open brace\min_{w} \sum_{i=1}^n \max\{0, 1 - y_i x_i^\top w} + \frac{\lambda + \frac{1}{\alpha}} {2} \|w\|_2^2$

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

结论：

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

总结

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

凸分析基础

凸集与凸函数

子梯度与次梯度

优化问题的基本概念

近端算子（ Proximal Operators）

近端算子的定义

近端算子的性质

常见的近端算子

指示函数的近端算子

平方范数的近端算子

更一般的近端算子

莫洛厄包络（ Moreau Envelope）

莫洛厄包络的定义

莫洛厄包络的性质

与原函数的关系

平滑性

梯度与近端算子的关系

子梯度方法（ Subgradient Methods）

子梯度的定义与性质

子梯度下降法

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

支持向量机的基本概念

SVM 的优化问题

SVM 的子梯度计算

稀疏优化与 LASSO

稀疏优化的背景与意义

LASSO 优化问题

LASSO 的几何解释

LASSO 的解的性质

优化算法

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

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

习题与详解

习题 1 - 计算近端算子

解答

(a)-范数的近端算子

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

(c)-范数立方的近端算子

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

解答

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

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

(c) 证明对是连续的

(d) 证明$(x) = {x - _{f}(x) } ，从而$是连续可微的

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

解答

(a) 构造的子梯度

(b) 论证的计算难度

总结

(d) 证明$(x) = {x - _{f}(x) } $，从而$ $是连续可微的