1. 凸优化中的方向导数非光滑函数的“指南针”在光滑函数的优化世界里梯度是我们最信赖的“向导”它清晰地指出了函数值上升最快的方向。然而当我们踏入非光滑凸函数的领域——比如带有L1正则项的LASSO回归、支持向量机的Hinge损失函数或是各种带约束的工程问题——梯度这个向导就“失踪”了。函数在某些点不可微我们失去了那个明确的局部方向指示。这时方向导数Directional Derivative就成了我们手中新的、更通用的“指南针”。这个“指南针”的工作原理很直观对于一个凸函数F在点x处我们想知道沿着方向h走一小步函数值会如何变化。数学上我们考察这个差商[F(x t*h) - F(x)] / t其中t是一个趋于0的正数。凸函数的一个美妙性质由命题3.5保证是这个差商随着t的减小是单调不减的。正是这种单调性确保了极限dF(x; h) lim_{t↓0} [F(x t*h) - F(x)] / t总是存在的尽管可能是正负无穷。这个极限值dF(x; h)就是函数F在点x处沿方向h的方向导数。为什么这个“指南针”如此重要首先它给出了函数沿任意方向的局部线性变化率。即使函数在x点不可微即梯度不存在沿某些方向的方向导数依然可能是有限的。其次它和次梯度Subgradient有着深刻的联系。命题3.52告诉我们对于任何次梯度g ∈ ∂F(x)都有dF(x; h) ≥ g^T h。这意味着所有次梯度与方向h的内积都给出了函数沿该方向变化率的一个下界。更关键的是如果x在定义域的相对内部那么这个下界是可以取到的即dF(x; h) max_{g∈∂F(x)} g^T h。你可以这样理解在不可微点次梯度集合构成了一个“梯度云”而沿方向h的方向导数等于这个“梯度云”中在h方向上投影最长的那个向量与h的内积。这个性质是后续次梯度下降算法设计的基石。实操中的一个关键点计算方向导数本身通常不是目的我们的目标是利用它来判断最优性。命题3.50给出了一个极其简洁而强大的判据x*是凸函数F的极小点当且仅当在x*处沿任何方向h的方向导数都非负即dF(x*; h) ≥ 0对所有h成立。直观上如果存在某个方向使得方向导数为负那就意味着沿着这个方向走一小步函数值会下降那么x*就不可能是极小点。这个判据完全绕开了梯度是处理非光滑优化问题最优性条件的第一原理。注意方向导数dF(x; h)关于方向h本身是一个正齐次且次可加的凸函数命题3.51。这意味着dF(x; λh) λ dF(x; h)(λ0)并且dF(x; h1h2) ≤ dF(x; h1) dF(x; h2)。这个性质在理论分析中非常有用它保证了方向导数作为方向h的函数具有良好的凸性便于进行进一步的操作和估计。1.1 从理论到计算一个L1正则化的例子让我们通过一个机器学习中常见的例子来具体感受一下。考虑函数F(x) ψ(x) λ||x||_1其中ψ是一个光滑凸函数比如最小二乘损失||x||_1是L1范数各分量绝对值之和λ是正则化系数。这个函数在那些使得某个x_i 0的点上是不可微的。如何计算它在某点x沿方向h的方向导数根据定义我们需要计算lim_{t↓0} [ψ(xth) λ||xth||_1 - ψ(x) - λ||x||_1] / t。由于ψ光滑其贡献部分就是∇ψ(x)^T h。关键在于L1范数这部分。对于第i个分量|x_i t h_i|在t很小时的行为取决于x_i是否为零若x_i ≠ 0则|x_i t h_i| sign(x_i) * (x_i t h_i)其导数为sign(x_i) * h_i。若x_i 0则|0 t h_i| t |h_i|其关于t的导数为|h_i|。因此综合起来dF(x; h) ∇ψ(x)^T h λ * Σ_{i: x_i≠0} sign(x_i) h_i λ * Σ_{i: x_i0} |h_i|。这个表达式清晰地展示了在非光滑点x_i0L1范数对方向导数的贡献是λ乘以方向分量绝对值的和这解释了为什么L1正则化倾向于产生稀疏解在零点附近只有当沿某个方向移动带来的ψ函数下降足以“克服”λ|h_i|这项惩罚时移动才是有利的这迫使许多h_i即许多x_i保持为零。2. 次梯度下降在“梯度云”中寻找下山路有了方向导数这个“指南针”我们自然想用它来指导优化迭代就像梯度下降法那样。最直接的想法是在不可微点我们有一个次梯度集合∂F(x)能否从中选一个作为“梯度”来用这就是次梯度下降Subgradient Descent的朴素思想x_{t1} x_t - α_t g_t其中g_t ∈ ∂F(x_t)α_t是步长。然而这里有一个严重的陷阱。对于光滑函数负梯度-∇F(x)保证是一个下降方向至少在局部。但对于次梯度g_t-g_t并不保证是下降方向。因为次梯度不等式F(y) ≥ F(x) g^T (y-x)只给出了函数值的一个下界当y x - αg时我们得到F(x - αg) ≥ F(x) - α||g||^2。这个不等式的方向是“错的”它只告诉我们函数值可能不会下降得比这个下界更快但无法保证下降。事实上如果你在非光滑点错误地选择了一个次梯度沿着它的负方向走函数值完全可能上升。那么真正的下降方向在哪里我们需要在次梯度集合∂F(x)中寻找一个特殊的向量。命题3.52告诉我们dF(x; h) max_{g∈∂F(x)} g^T h。为了让-h成为下降方向我们需要dF(x; -h) 0即max_{g∈∂F(x)} (-g^T h) 0这等价于对于所有g ∈ ∂F(x)都有g^T h 0。换句话说我们需要一个方向h它与次梯度集合中的每一个向量的夹角都小于90度。一个自然的选择是选择次梯度集合中范数最小的那个向量即h argmin_{g∈∂F(x)} ||g||。可以证明原文3.5.4节这个最小范数次梯度恰好满足||h||^2 ≤ g^T h对所有g ∈ ∂F(x)成立从而-h确实是一个下降方向事实上它是最速下降方向。这就引出了理论上的次梯度下降算法x_{t1} x_t - α_t * (argmin_{g∈∂F(x_t)} ||g||)。但问题来了在每一步都计算整个次梯度集合中的最小范数元素对于复杂函数来说其计算代价可能非常高甚至不比解决原优化问题本身简单。这就使得上述“理想”算法在实践中往往不可行。2.1 实用次梯度方法与收敛性分析因此实践中广泛使用的是更简单的版本朴素次梯度方法。它直接随机或按某种规则从次梯度集合∂F(x_t)中选取一个次梯度g_t然后进行更新x_{t1} x_t - α_t g_t。由于下降方向无法保证我们不能再指望函数值序列F(x_t)是单调下降的。那么如何判断算法的进展呢常用的策略是跟踪历史平均点\bar{x}_t (Σ_{j1}^{t} α_j x_j) / (Σ_{j1}^{t} α_j)。对于凸函数在一定的步长条件下例如步长满足α_t → 0且Σ α_t → ∞可以证明这个平均点\bar{x}_t会收敛到某个最优解。其收敛速度通常是O(1/√T)量级这比梯度下降法的O(1/T)要慢。这是因为次梯度方法本质上是在用“更差”的局部信息单个次梯度而非梯度来导航其迭代路径更加迂回曲折。步长选择是关键。常见的步长规则有固定小步长α_t α。简单但需要精心选择α且只能收敛到最优解的一个邻域内。递减步长α_t α / √t或α_t α / t。这是常用的策略能保证精确收敛到最优解。1/√t规则在理论上有更好的鲁棒性而1/t规则在某些情况下能达到O(1/T)的收敛速率针对平均点。Polyak步长α_t [F(x_t) - F^*] / ||g_t||^2其中F^*是最优值。这被认为是最优的步长策略因为它利用了函数值间隙的信息。但在实际中最优值F^*通常是未知的需要估计或使用其上界。实操心得在机器学习中应用次梯度方法例如直接对带有L1正则化的损失函数进行优化我的经验是监控历史平均不要只看最后一步的x_t一定要计算并输出\bar{x}_t这才是最终的解。谨慎对待函数值F(x_t)可能会震荡甚至偶尔上升这是正常的。绘制其曲线时更应关注其整体下降趋势和F(\bar{x}_t)的行为。处理不可微点在像L1正则化这样的问题中在x_i0的点次梯度是一个集合[-λ, λ]。通常的实践是直接取g_i λ * sign(x_i)当x_i≠0或g_i 0当x_i0。虽然0是合法的次梯度但取0可能会导致算法停滞在非最优点。一种更激进的策略是取g_i λ * sign(∇ψ(x)_i)当x_i0且|∇ψ(x)_i| λ否则取0这有时能带来更快的收敛。与近端方法对比对于“光滑函数非光滑正则项”这种常见结构次梯度方法通常比后续要讲的近端梯度下降慢得多。除非问题规模很小或近端算子难以计算否则近端方法是更优的选择。3. 近端算子将非光滑部分“打包”处理次梯度方法虽然通用但收敛慢。对于一大类结构化的非光滑优化问题即目标函数可以分解为F(x) G(x) H(x)的形式其中G是光滑的通常可微且梯度 Lipschitz 连续而H是非光滑但“简单”的凸函数例如L1范数、L2范数、指示函数等近端方法Proximal Methods提供了强大得多的工具。其核心思想是我们不对复杂的F直接操作而是通过一个称为近端算子Proximal Operator的映射将非光滑部分H“打包”成一个可以高效求解的子问题。近端算子的定义非常优美对于闭凸函数H和标量α 0点x的近端映射定义为prox_{αH}(x) argmin_{v} { H(v) 1/(2α) * ||v - x||^2 }这个定义可以这样理解我们想在H(v)和接近原始点x之间做一个权衡。最小化H(v)会驱使v趋向于H的极小点而最小化||v-x||^2会驱使v停留在x附近。参数α控制着这个权衡α很大时1/(2α)很小惩罚项||v-x||^2的权重低近端算子会优先让H(v)变小α很小时近端算子会输出一个非常接近x的点。近端算子的关键性质命题3.55v prox_{αH}(x)当且仅当(x - v) / α ∈ ∂H(v)。这个条件等价于0 ∈ ∂H(v) (v - x)/α这恰恰是函数H(v) 1/(2α)||v-x||^2在v点取极小值的一阶最优性条件。特别地x*是H的极小点当且仅当x* prox_{αH}(x*)即x*是近端算子的不动点。3.1 经典例子L1范数与投影算子理解近端算子最好的方式是看几个例子L1范数LASSO正则化H(x) λ||x||_1。它的近端算子就是著名的软阈值Soft Thresholding算子[prox_{αλ||·||_1}(x)]_i sign(x_i) * max(|x_i| - αλ, 0)这个操作对向量x的每个分量独立进行如果|x_i| αλ就向零收缩αλ如果|x_i| ≤ αλ就直接置为零。这个算子有解析解计算代价是O(n)极其高效。这正是近端方法威力所在——它将复杂的、不可微的L1正则化项转化为了一个逐元素的、可并行计算的简单操作。凸集的指示函数设H(x) I_Ω(x)即x ∈ Ω时为0否则为∞。那么近端算子prox_{αI_Ω}(x)退化为prox_{αI_Ω}(x) argmin_{v ∈ Ω} ||v - x||^2这正是x到凸集Ω的欧几里得投影记作proj_Ω(x)。这个例子揭示了近端算子是投影算子的推广。二次函数如果H(x) (1/2) x^T Q x b^T x是一个光滑凸函数那么它的近端算子也有解析解涉及求解一个线性方程组(I αQ) v x - αb。当Q具有特殊结构如对角矩阵时求解也非常快。近端算子的另一个重要性质是“非扩张性”命题3.56||prox_H(x) - prox_H(y)|| ≤ ||x - y||。这意味着近端算子是一个“收缩”映射这个性质对于分析算法的收敛性至关重要。4. 近端梯度下降融合光滑与非光滑的优雅算法现在我们回到最初的结构化问题min_x F(x) G(x) H(x)。近端梯度下降Proximal Gradient Descent算法结合了梯度下降的效率和近端算子的处理非光滑项的能力。其迭代格式简洁而强大x_{t1} prox_{α_t H}( x_t - α_t ∇G(x_t) )这个算法可以看作是两个步骤的复合梯度步Gradient Step对光滑部分G执行一步梯度下降y_t x_t - α_t ∇G(x_t)。近端步Proximal Step对非光滑部分H应用近端算子x_{t1} prox_{α_t H}(y_t)。为什么这个算法有效从最优性条件来看F的极小点x*满足0 ∈ ∇G(x*) ∂H(x*)。而我们的迭代中x_{t1}满足(x_t - α_t ∇G(x_t) - x_{t1}) / α_t ∈ ∂H(x_{t1})整理得∇G(x_t) (x_{t1} - x_t)/α_t ∈ -∂H(x_{t1})。当算法收敛时x_{t1} ≈ x_t上式就近似于∇G(x_t) ∈ -∂H(x_t)即接近最优性条件。收敛性分析假设G是 Lipschitz 连续可微的常数为L即||∇G(x) - ∇G(y)|| ≤ L||x-y||。那么只要步长α_t ≤ 1/L近端梯度下降就能保证函数值单调下降F(x_{t1}) ≤ F(x_t)。更进一步的如果G还是凸的那么算法能以O(1/T)的速率收敛到最优函数值定理3.57。如果G是强凸的即存在m0使得∇^2 G(x) ⪰ mI那么算法能线性收敛定理3.58即||x_t - x*|| ≤ (1 - αm)^t ||x_0 - x*||。一个重要特例投影梯度下降。当H(x)是凸集Ω的指示函数I_Ω(x)时近端算子就是投影算子。此时近端梯度下降退化为x_{t1} proj_Ω( x_t - α_t ∇G(x_t) )这正是求解带约束光滑凸优化问题的经典投影梯度下降法。由此可见近端梯度下降统一了无约束梯度下降和投影梯度下降。4.1 算法实现与加速技巧近端梯度下降的伪代码实现非常清晰输入初始点 x0 梯度 Lipschitz 常数 L或通过回溯线搜索估计 最大迭代次数 T 设置步长 α 1/L for t 0 to T-1 do // 1. 计算光滑部分的梯度 g ∇G(x_t) // 2. 执行梯度步 y x_t - α * g // 3. 执行近端步需要能高效计算 prox_{αH} x_{t1} prox_{αH}(y) // 可选检查收敛条件如 ||x_{t1} - x_t|| / α ε end for 输出 x_T步长选择与回溯线搜索我们并不总是能精确知道L。一种鲁棒的方法是使用回溯线搜索Backtracking Line Search。给定参数β ∈ (0, 1)例如0.8我们从某个初始步长α开始反复尝试α β * α直到满足以下充分下降条件G(x_{t1}) ≤ G(x_t) ∇G(x_t)^T (x_{t1} - x_t) (1/(2α)) ||x_{t1} - x_t||^2其中x_{t1} prox_{αH}(x_t - α∇G(x_t))。这个条件保证了迭代的稳定性。加速近端梯度方法FISTA近端梯度下降的O(1/T)收敛速率可以被加速到O(1/T^2)这是由Nesterov开创的最优一阶方法思想。其加速版本通常称为FISTAFast Iterative Shrinkage-Thresholding Algorithm迭代格式如下输入 x0, α ≤ 1/L, y0 x0, θ0 1 for t 0 to T-1 do x_{t1} prox_{αH}( y_t - α ∇G(y_t) ) θ_{t1} (1 sqrt(1 4θ_t^2)) / 2 y_{t1} x_{t1} ((θ_t - 1)/θ_{t1}) * (x_{t1} - x_t) end forFISTA引入了一个辅助序列y_t和一个动量参数θ_t在每一步用y_t它是x_t和x_{t-1}的某种外推来计算梯度从而获得了更快的收敛速度。在实际的机器学习问题中FISTA通常是默认选择。常见问题与排查算法不收敛或震荡首先检查步长α是否过大。确保α ≤ 1/L或使用回溯线搜索。其次检查近端算子的实现是否正确。对于L1范数软阈值操作sign(x)*max(|x|-λ,0)中的λ应该是α * 正则化系数不要漏掉α。收敛速度慢如果问题条件数较差G的 Hessian 矩阵特征值分布很广基础的近端梯度下降会很慢。考虑使用加速版本FISTA或者如果问题结构允许尝试拟牛顿类的近端方法如近端拟牛顿法。近端算子计算困难这是近端方法的主要瓶颈。如果H的近端算子没有解析解或计算成本很高算法就失去了优势。此时需要具体问题具体分析有时可以对H进行分解如H(x)h(Ax)利用 Moreau 分解或交替方向乘子法ADMM来处理。如何验证结果对于凸问题可以计算对偶间隙Duality Gap。如果对偶问题可以构造见下文对偶理论部分当对偶间隙接近于零时就强有力地证明了原问题解的最优性。此外可以监控前后迭代点的变化||x_{t1} - x_t||和函数值的变化|F(x_{t1}) - F(x_t)|当其小于预设阈值时停止。5. 对偶理论与增广拉格朗日法从另一个视角求解对于带有约束的凸优化问题对偶理论提供了一个极其强大的视角和工具集。考虑问题min_x F(x)约束为x ∈ Ω其中Ω {x: γ_i(x)0, i∈E; γ_i(x)≤0, i∈I}γ_i是凸函数等式约束为仿射。我们引入拉格朗日函数L(x, λ) F(x) Σ_{i∈E∪I} λ_i γ_i(x)其中要求λ_i ≥ 0对于i ∈ I。对偶函数定义为L*(λ) inf_{x∈R^d} L(x, λ)。由于对于任意可行点x∈Ω和满足符号约束的λ有L(x, λ) ≤ F(x)所以对偶函数值给出了原问题最优值的一个下界L*(λ) ≤ min_{x∈Ω} F(x)。对偶问题就是最大化这个下界max_{λ∈D} L*(λ)其中D是λ的定义域λ_i ≥ 0, i∈I。原问题最优值p*和对偶问题最优值d*的差p* - d*称为对偶间隙。在凸优化且满足一定约束规格如Slater条件存在一个严格可行点即等式约束成立不等式约束严格小于0下强对偶性成立即对偶间隙为零p* d*。此时原问题的最优解x*和对偶问题的最优解λ*满足KKT条件定理3.62原始可行性x* ∈ Ω。对偶可行性λ_i* ≥ 0对于i ∈ I。互补松弛条件λ_i* * γ_i(x*) 0对于i ∈ I。平稳性条件0 ∈ ∂F(x*) Σ_{i∈E∪I} λ_i* ∂γ_i(x*)。5.1 增广拉格朗日法将对偶上升与近端结合直接求解对偶问题有时比求解原问题更简单。一种经典的算法是对偶上升法交替更新原始变量和对偶变量。x_{k1} argmin_x L(x, λ_k) // 最小化拉格朗日函数 λ_i^{(k1)} λ_i^{(k)} α_k γ_i(x_{k1}) // 对偶变量更新对于等式约束对于不等式约束更新规则为λ_i^{(k1)} max(0, λ_i^{(k)} α_k γ_i(x_{k1}))。然而最小化L(x, λ_k)可能并不比解原问题简单。增广拉格朗日法Augmented Lagrangian Method也称乘子法Method of Multipliers通过给拉格朗日函数增加一个惩罚项来改进它L_ρ(x, λ) F(x) Σ_i λ_i γ_i(x) (ρ/2) Σ_i γ_i(x)^2其中ρ 0是惩罚参数。增广拉格朗日函数L_ρ关于x通常比原始的L更好优化因为惩罚项使函数在可行集外急剧增大改善了凸性。算法的迭代步骤变为公式3.58x_{k1} argmin_x L_{ρ_k}(x, λ_k) λ_i^{(k1)} λ_i^{(k)} ρ_k γ_i(x_{k1}) // 对于等式约束 λ_i^{(k1)} max(0, λ_i^{(k)} ρ_k γ_i(x_{k1})) // 对于不等式约束与近端算子的联系增广拉格朗日法的对偶更新步骤可以看作是在对偶函数L*上应用了近端点法Proximal Point Method。具体来说λ_{k1}是求解max_λ { L*(λ) - 1/(2ρ_k) ||λ - λ_k||^2 }得到的。近端点法在对偶空间上是收敛的这为增广拉格朗日法提供了理论保证。ADMM面向可分结构的强大变种当目标函数可以写成F(x) f(x) g(z)约束为Ax Bz c的形式时交替方向乘子法Alternating Direction Method of Multipliers, ADMM将增广拉格朗日法与坐标下降结合形成了极其高效的算法x_{k1} argmin_x L_ρ(x, z_k, λ_k) // 固定z, λ更新x z_{k1} argmin_z L_ρ(x_{k1}, z, λ_k) // 固定x, λ更新z λ_{k1} λ_k ρ (A x_{k1} B z_{k1} - c) // 更新乘子ADMM的魅力在于x和z的子问题通常是独立的、且可能因为f和g的特殊结构如L1范数、核范数而具有解析解或高效解法。它在图像处理、统计学习、分布式优化等领域应用非常广泛。个人体会在实际工程中方向导数、次梯度和近端方法并非孤立的理论概念而是一个连贯的工具链。当你面对一个非光滑凸优化问题时我的建议是首先审视问题结构是否能写成G(x) H(x)的形式H(x)的近端算子是否容易计算如果是近端梯度下降或FISTA是你的首选。如果约束复杂但目标函数光滑考虑增广拉格朗日法或ADMM。特别是当约束是线性等式或不等式且变量有可分离结构时ADMM往往能发挥巨大威力。次梯度方法作为保底当问题结构非常复杂无法方便地应用近端算子或拉格朗日法时朴素的次梯度方法配合历史平均是一个鲁棒但较慢的选择。务必注意步长策略的调整。对偶理论用于验证与洞察即使你不直接求解对偶问题计算对偶间隙也是验证算法结果最优性的黄金标准。同时对偶变量λ通常有丰富的物理或统计意义如支持向量机中的支持向量能提供对问题更深刻的理解。最后记住这些方法的核心思想面对非光滑性我们通过方向导数来刻画它通过次梯度来包含它通过近端算子来驯服它通过对偶理论来绕过它。掌握这套从理论到实践的工具你将能从容应对机器学习、信号处理、运筹学中众多棘手的非光滑凸优化挑战。