无约束凸优化精讲：从凸性原理到收敛性分析与工程实现

我在读优化理论的时候其实卡得最久的就是第四章“无约束凸优化”。原因很简单这一章表面上只讲“没有约束、求最小值”这一件事但几乎所有后续章节——约束优化、对偶理论、内点法以及机器学习里的梯度训练、正则化路径底层都是从这里长出来的。凸优化里那些“看起来莫名其妙”的性质比如局部最优就是全局最优、梯度为零就是最优解都源于这一章对凸函数结构的严格刻画。这篇不是什么教科书复述是我把这一章从定理到代码过了一遍之后留下的理解、推导和踩坑记录。适合正在啃优化理论的研究生、想搞懂机器学习训练过程的工程师以及所有需要自己实现优化算法的人。1. 无约束凸优化到底在解决什么问题1.1 问题的标准形式与两类典型场景无约束凸优化的标准形式极短$$ \min_{x \in \mathbb{R}^n} ; f(x) $$其中要求$f$是凸函数而且没有等式约束、没有不等式约束变量$x$的每个分量可以自由取值。形式越短越容易让人低估它。实际上绝大多数实际优化问题要么本身就是无约束形式要么可以靠罚函数、增广拉格朗日等方法转化为无约束形式求解。所以这一章教的东西不只是“一个特例”而是优化方法的核心引擎。两类最常见的场景是第一类是模型拟合问题。比如最小二乘$$ \min_{x} ; \frac{1}{2}|Ax - b|_2^2 $$以及加了L2正则的岭回归、不加正则的逻辑回归。这类问题的特点是目标函数光滑、可微、凸性天然满足是凸优化的理想对象。第二类是损失函数加正则项的经验风险最小化$$ \min_{x} ; \frac{1}{m}\sum_{i1}^{m} \ell_i(x) \lambda r(x) $$其中损失$\ell_i$和正则项$r$都要求是凸函数。SVM的对偶问题、Lasso、稀疏字典学习即便最终形态带约束其子问题也常常是无约束凸优化。我在实际工程里体会最深的一点是判断一个问题能不能用这一章的方法就看目标函数是否凸、是否连续可微。只要这两点确认了剩下的就是选择算法、调节步长、验证收敛这条路非常清晰。1.2 凸性为什么是“黄金性质”教材上定义凸函数用的是不等式$$ f(\theta x (1-\theta)y) \le \theta f(x) (1-\theta)f(y), \quad \forall \theta \in [0,1] $$这个不等式看上去像一句“废话”但它直接带来三个工程上极其值钱的推论。第一个推论是局部最优等于全局最优。对凸函数来说任何局部极小点都必然是全局极小点。这句话意味着你跑任何迭代算法只要你不被困在非极小点比如鞍点或迭代点发散最后得到的输出就是全局最优。这对工程人员的意义是你可以把“找全局最优”这个听起来很难的事简化为“找到梯度为零的点”。第二个推论是所有极小点的集合是凸集。也就是说如果有多个最优解它们连成的线段上所有点也都是最优解。这在现实中意味着如果你跑两次算法得到两个不同的解它们的凸组合依然是最优解你可以放心地取平均来作为稳健解。第三个推论是凸函数可以被一阶信息完全刻画。一阶泰勒展开给出全局下界$$ f(y) \ge f(x) \nabla f(x)^T (y - x) $$这个性质是所有梯度类方法收敛性证明的基石。我第一次意识到这个下界有多有用是在推导梯度下降收敛速率的时候——没有它你甚至没法证明步长合适时迭代一定会下降更别说给出收敛速度的估计。当然不是所有凸函数都“好惹”。凸函数可能是不可微的比如绝对值函数$|x|$、Lasso的L1范数。对于这种函数本章前半段的微分工具会失效需要引入次梯度。我在第6节会专门说这个坑。2. 最优性条件怎么知道已经找到最优了2.1 梯度为零一阶必要条件无约束问题里最经典的最优性条件是$$ \nabla f(x^*) 0 $$对于一般可微非凸函数这只是必要条件极小点必须满足它但满足它的点可能是极大点或鞍点。然而在凸函数中这个条件升级为充要条件只要梯度为零就一定是全局极小点。这个由凸性的全局下界直接推出不需要任何二阶信息。我在实际编程中会把这个条件作为“停机判据”之一。常见做法是检查梯度的范数是否小于某个容差$$ |\nabla f(x_k)|_2 \le \epsilon $$但这里有个容易翻车的细节$\epsilon$该设多大如果设得太小比如$10^{-14}$在双精度浮点下目标函数的数值梯度误差可能已经干扰判断如果设得太大比如$10^{-2}$对强凸问题倒是够用但对条件数很大的病态问题梯度范数小不代表你离最优解近。我的经验是先用相对误差$|x_k - x_{k-1}| /|x_{k-1}|$辅助判断再辅助看目标函数下降量三管齐下比单看梯度范数稳得多。一阶条件还有一个直观解释在最优解处函数对每个变量的偏导都必须为零否则你总能沿着某个坐标方向微小移动一步让函数值下降。这跟爬山爬到山顶的原理一样——只不过我们是在向下找谷底。2.2 Hessian正定与二阶条件局部与全局的唯一性对于非凸问题判断一个点是不是极小点还得看Hessian矩阵$$ \nabla^2 f(x^*) \succ 0 $$即Hessian正定。但在凸优化里Hessian半正定$\nabla^2 f(x) \succeq 0$是凸函数的二阶充要刻画只要$f$二阶连续可微。对凸函数$\nabla^2 f(x^*) \succ 0$通常被用来保证最优解的唯一性。如果Hessian只是半正定那么可能有无穷多个最优解它们的集合看起来像一个平坦的“谷底”。这个“谷底”现象在实际实验里非常常见。比如逻辑回归如果不加正则项当特征线性可分时损失函数在参数空间中可能沿着某个方向保持恒定你会看到迭代过程中梯度范数降得很小但参数还在缓慢漂移。这不一定是你算法写错了而是问题本身的解不唯一。解决办法之一就是加一个小的强凸正则项$\frac{\lambda}{2}|x|^2$人为制造全局强凸性让解唯一且收敛加快。顺便说一个我经常用的判断技巧对一个二次型函数$f(x) \frac{1}{2}x^T Q x - b^T x$直接看$Q$的特征值就能判断凸性。所有特征值非负则凸所有特征值大于0则强凸最大与最小特征值的比值就是条件数它直接决定梯度下降有多难收敛。这个简化模型能帮你预判很多算法的表现。3. 三种主流算法及其选择逻辑3.1 梯度下降朴素但有普适性梯度下降的迭代式非常简单$$ x_{k1} x_k - t_k \nabla f(x_k) $$其中$t_k$是步长。它的思想就是沿着当前点的负梯度方向走一步因为负梯度是函数值下降最快的方向。不过“下降最快”只是针对局部无穷小步长而言的一旦步子迈大了方向就可能“失真”这也是后面所有调步长技巧的出发点。我在教学生的时候常说梯度下降是所有方法里你最该先掌握的“基准线”。它不需要额外存储不需要算二阶导数对大规模问题总能跑起来。它的缺点也非常诚实收敛速度强烈依赖问题条件数。如果目标函数是一个等比椭圆状的二次函数梯度下降会在山谷两侧来回震荡慢慢蹭向谷底这种现象你画迭代轨迹图时看得一清二楚。梯度下降在机器学习里最出名的变体是随机梯度下降SGD。严格地说SGD更新用的是单个样本的梯度是真实梯度的无偏估计因此每一步都带有噪声。但噪声在凸优化中不一定全是坏事它有时能帮你跳过一些不是特别深的局部极值。当然对凸问题本就没有局部极值所以SGD分析起来更“纯粹”。3.2 步长选择的三种做法与注意点步长怎么选是这一章实操含量最高的地方。我见过太多人在这一步翻车。常见做法有三类。第一类是固定步长。比如设$t0.01$。这种做法最简单但风险最高步长太大迭代发散或震荡步长太小收敛缓慢到你想砸电脑。好在对于梯度满足Lipschitz连续的函数后面会详说存在理论安全步长上限$t \le 1/L$但在实际中$L$往往不知道只能靠实验试探。第二类是回溯线搜索backtracking line search。思路是先给一个大步长比如$t1$然后反复缩小步长直到满足Armijo条件$$ f(x - t \nabla f(x)) \le f(x) - c t |\nabla f(x)|^2 $$其中$c$通常取$10^{-4}$。这个条件保证了你每步至少获得“与步长成比例”的下降量。回溯搜索的好处是不需要知道Lipschitz常数自适应地选步长坏处是每一步要多算几次目标函数值对于成本高的目标函数是负担。第三类是精确线搜索在当前方向$-\nabla f(x_k)$上求解$$ t_k \arg\min_{t \ge 0} ; f(x_k - t \nabla f(x_k)) $$对二次型目标函数这个最小值可以用闭式解算出非常漂亮但对一般函数精确线搜索每一步都要做一次一维优化代价偏高。工程上我很少用精确线搜索最常用的还是回溯法因为它稳定、几乎不引入额外参数。我自己的默认配置是起点步长$t1$倍率$\beta0.8$Armijo常数$c10^{-4}$。这套参数对逻辑回归、Softmax回归这类问题基本不用改。3.3 牛顿法让Hessian帮你加速梯度下降只用一阶信息走一步看一步像个“近视眼”。牛顿法则利用了二阶信息每一步近似求解当前点处的二次模型$$ x_{k1} x_k - \left(\nabla^2 f(x_k)\right)^{-1} \nabla f(x_k) $$这个更新公式的来源是对$f$在$x_k$处做二阶泰勒展开后求展开式的极小点。对二次函数牛顿法一步就收敛对一般强凸函数它在最优解附近有二次收敛速率——这意味着误差的平方每次迭代都会减半迭代次数从几十次直接降到几次。代价当然也有计算和存储Hessian矩阵及其逆对维度$n$是$O(n^2)$乃至$O(n^3)$的复杂度。$n$一旦到十万、百万量级这条路就走不通了。所以牛顿法适合中小规模问题或者作为“最终抛光器”先用梯度法跑到大致区域再用牛顿法收尾到高精度。牛顿法还有个著名的翻车点当Hessian不正定时牛顿方向可能根本不是下降方向。所以在非凸问题上直接套牛顿法很危险但在凸问题上Hessian天然半正定只要保证可逆问题小很多。即便这样数值上仍可能遇到Hessian几乎奇异的情况。我的处理方式是在Hessian的对角线上加一个小的正数$\delta I$即正则化牛顿法$$ x_{k1} x_k - \left(\nabla^2 f(x_k) \delta I\right)^{-1} \nabla f(x_k) $$这个$\delta$可以理解为一种信任区域机制防止一步跳得太远。3.4 拟牛顿法用更小的代价逼近二阶信息拟牛顿法是牛顿法和梯度下降之间的折中。它不直接计算Hessian而是通过迭代中梯度差和目标函数差去近似Hessian的逆。最出名的当属BFGS方法以及内存受限版本L-BFGS。BFGS维护一个矩阵$B_k$近似Hessian更新公式看上去繁琐但其动机很朴素我们希望$B_{k1}$满足割线方程$$ B_{k1} (x_{k1} - x_k) \nabla f(x_{k1}) - \nabla f(x_k) $$同时尽量保持$B_k$的信息。这个技术避免了二阶导数计算每一步代价只有向量内积和矩阵向量乘是$O(n^2)$存储、$O(n^2)$计算。L-BFGS更进一步不显式存储$B_k$只保存最近几步的差值对存储降到$O(mn)$$m$通常取3到20。我在高维稀疏问题上基本首选L-BFGS。很多现代机器学习库的求解器比如scikit-learn里的LogisticRegression就默认用L-BFGS都以它为核心。原因很简单在维度从几千到几百万时梯度下降太慢牛顿法存不下矩阵L-BFGS恰好卡在中间性能出奇地好。不过要注意L-BFGS对初始矩阵的选择和线搜索的质量更敏感我会配合強健的回溯线搜索一起用。4. 收敛性分析能收敛和收敛得快是两回事4.1 两个关键常数Lipschitz光滑与强凸参数很多教材会把收敛性证明写得很长但剥开来看真正起作用的只有两个常数。第一个是Lipschitz光滑常数$L$假设梯度满足$$ |\nabla f(x) - \nabla f(y)| \le L |x - y| $$直观意思是梯度的变化率有上界$L$越大梯度变化越剧烈函数族的“活动上限”越高。对二次函数$f(x)\frac{1}{2}x^T Q x - b^T x$$L$就是$Q$的最大特征值。第二个是强凸参数$m$如果$$ f(y) \ge f(x) \nabla f(x)^T (y - x) \frac{m}{2}|y - x|^2 $$就说这个凸函数是$m$-强凸的。直观上强凸意味着函数不仅凸还“鼓得像一个碗”在任何方向上都有正曲率兜底。二次函数中$m$对应$Q$的最小特征值。这两个常数的比值$\kappa L/m$叫做条件数。$\kappa$越接近1问题越“圆润好解”$\kappa$越大问题越“瘦长病态”。这就是为什么特征标准化能让梯度下降收敛快几十倍——它直接降低了有效条件数。4.2 梯度下降的线性收敛与步长上限在$f$满足$L$-光滑和$m$-强凸的条件下取固定步长$t 1/L$梯度下降的误差满足$$ |x_{k} - x^|_2^2 \le \left(1 - \frac{m}{L}\right)^k |x_0 - x^|_2^2 $$这是一个等比数列衰减叫做线性收敛。迭代次数要达到精度$\epsilon$大约需要$$ O\left(\kappa \log\frac{1}{\epsilon}\right) $$步。如果$\kappa1$一次迭代误差就能缩得很小如果$\kappa10^6$那抱歉可能要上百万步才能达到满意精度。这个公式还指出了步长的理论安全上限固定步长必须满足$0 t \le 2/(Lm)$否则几何因子$|1 - t m|$会大于1迭代直接发散。工程上如果不想算这些常数就用回溯线搜索它本质上是在自动逼近一个安全步长。我实际测试过一组对比条件数100的问题梯度下降约几百步收敛条件数10000的问题同样的算法、同样的精度可能要走几万步。这两个结论和理论公式是对得上的。遇到后者第一反应不应该是硬调步长而是考虑预处理或换用牛顿类方法。4.3 牛顿法的局部二次收敛牛顿法的收敛性分析有一个“美妙但脆弱”的结果如果起始点足够接近最优解$x^$并且Hessian在$x^$附近一致正定且Lipschitz连续那么$$ |x_{k1} - x^| \le C |x_k - x^|^2 $$这就是二次收敛误差按平方衰减。假设当前误差是$10^{-1}$那么后续误差大约为$10^{-2}, 10^{-4}, 10^{-8}, 10^{-16}$眨眼之间就达到机器精度。这就是为什么高斯-牛顿法、L-BFGS在收敛细节上会表现出“突飞猛进”的曲线。它的脆弱之处在于“足够接近”这个前提。牛顿法天生有全局收敛障碍如果起始点离最优解太远Hessian不稳定或者方向出错迭代可能跑偏。经典补救方案是加线搜索或者信任区域确保每一步都让目标函数下降。我在做数值实验时从来不会从零开始裸跑牛顿法而是要配上一个回溯线搜索才放心。没有线搜索的牛顿法就像没有刹车的跑车。5. 实操从零实现一套无约束凸优化流程5.1 用Logistic回归做实验对象理论讲完一定要上手写代码。我选逻辑回归作为实验对象因为它的目标函数是光滑凸函数梯度、Hessian都有解析式而且维度可调非常适合验证算法。假设样本$(a_i, b_i)$其中$a_i \in \mathbb{R}^n$是特征向量$b_i \in {0, 1}$是标签。带L2正则的逻辑回归损失为$$ f(x) \frac{1}{m}\sum_{i1}^{m} \left[\log(1 e^{a_i^T x}) - b_i a_i^T x\right] \frac{\lambda}{2}|x|_2^2 $$梯度写出来是$$ \nabla f(x) \frac{1}{m}\sum_{i1}^{m} \left(\sigma(a_i^T x) - b_i\right) a_i \lambda x $$其中$\sigma(z) 1/(1e^{-z})$是Sigmoid函数。Hessian则是$$ \nabla^2 f(x) \frac{1}{m}\sum_{i1}^{m} \sigma(a_i^T x)\left(1 - \sigma(a_i^T x)\right) a_i a_i^T \lambda I $$注意$\sigma$取值在0到1之间所以$\sigma(1-\sigma) \le 1/4$Hessian始终正定强凸性由$\lambda I$兜底。这个性质让逻辑回归成为测试凸优化算法最安全的沙盒——不会突然出现非凸的诡异行为。5.2 Python实现梯度下降和牛顿法下面这段代码我尽量精简但保留核心流程。它实现了三个算法固定步长梯度下降、回溯线搜索梯度下降、带回溯线搜索的牛顿法。import numpy as np def sigmoid(z): # 稳定版sigmoid防止exp溢出 return np.where(z 0, 1.0 / (1.0 np.exp(-z)), np.exp(z) / (1.0 np.exp(z))) def make_logistic(X, y, lam1e-3): def f(x): z X x return np.mean(np.logaddexp(0, z) - y * z) 0.5 * lam * np.dot(x, x) def grad(x): p sigmoid(X x) return X.T (p - y) / len(y) lam * x def hess(x): p sigmoid(X x) D p * (1 - p) A X * D[:, None] return (A.T X) / len(y) lam * np.eye(X.shape[1]) return f, grad, hess def backtracking_line_search(f, x, direction, grad_norm): t 1.0 c 1e-4 beta 0.8 while f(x t * direction) f(x) - c * t * grad_norm**2: t * beta return t def gradient_descent(grad, x0, f, t, max_iter1000, tol1e-8): x x0.copy() hist [] for _ in range(max_iter): g grad(x) gnorm np.linalg.norm(g) hist.append(gnorm) if gnorm tol: break x - t * g return x, hist def backtracking_gradient_descent(f, grad, x0, max_iter1000, tol1e-8): x x0.copy() hist [] for _ in range(max_iter): g grad(x) gnorm np.linalg.norm(g) hist.append(gnorm) if gnorm tol: break d -g t_step backtracking_line_search(f, x, d, gnorm) x t_step * d return x, hist def newton_method(f, grad, hess, x0, max_iter50, tol1e-10): x x0.copy() hist [] for _ in range(max_iter): g grad(x) gnorm np.linalg.norm(g) hist.append(gnorm) if gnorm tol: break H hess(x) # 加一点正则化防止H接近病态 H 1e-8 * np.eye(x.shape[0]) d -np.linalg.solve(H, g) t_step backtracking_line_search(f, x, d, gnorm) x t_step * d return x, hist有几个实现细节值得说。第一我用了np.logaddexp来计算$\log(1e^z)$避免了$z$很大时的指数上溢如果你直接写np.log(1 np.exp(z))当$z1000$时会直接得到inf梯度变成nan。第二回溯线搜索的循环终止用梯度的范数平方这比单独用目标函数下降量更可靠。第三牛顿法里我加了1e-8的对角正则这个习惯救了我很多次——当Hessian接近半正定时直接solve可能报奇异矩阵错误。5.3 数值实验对照收敛曲线与条件数影响我生成了一组维度$n50$、样本数$m200$的随机数据让特征矩阵$X$服从标准正态分布然后把标签做一次线性决策后采样。分别跑固定步长梯度下降$t0.1$、回溯梯度下降和牛顿法记录每次迭代的梯度范数。固定步长$t0.1$在这个问题上表现尚可梯度范数呈近似的线性下降但到$10^{-5}$左右开始变慢。回溯梯度下降的迭代次数略多因为每步都要额外算几次函数值但整体更稳不容易震荡。牛顿法是最夸张的前几步还在缓慢下降一旦进入二次收敛区五六步之内梯度范数就从$10^{-3}$砸到$10^{-12}$几乎一步一个数量级。我还做过一个“坏条件数”实验将特征矩阵$X$乘以一个对角缩矩阵让某些特征的尺度放大100倍。同样的步长$t0.1$直接发散因为梯度在某些方向上幅度剧烈固定步长完全不管用。换成回溯线搜索后能收敛但速度仍然不如对特征做标准化后的版本。这个实验告诉我一个铁律在跑任何优化算法之前先看特征尺度、做标准化效果胜过调一晚上步长。6. 常见问题与排查技巧6.1 Loss不降反升步长太大还是梯度算错这是最常遇到的故障。我的排查顺序是固定的第一输出每一步目标函数值看它是“一开始就涨”还是“中途涨”。一开始就涨几乎都是步长太大改成回溯线搜索立刻就好。中途涨要怀疑数值稳定性比如sigmoid溢出、数据里有NaN、或目标函数里出现了除零。第二步是检查梯度实现。有一个很实用的手段叫“有限差分检查”用$$ g_i \approx \frac{f(x \epsilon e_i) - f(x - \epsilon e_i)}{2\epsilon} $$来和你的解析梯度对比$\epsilon$取$10^{-6}$左右。如果相对误差超过$10^{-4}$那多半是梯度公式写错了。我每写一个目标函数都会先跑一遍这个检查再上算法几乎能杜绝“算法没错梯度错了”的白忙一场。第三步是看数据里有没有异常值。大特征值或极端标签会让梯度出现非理性的大数即使理论上步长是安全的数值上也会出问题。我习惯在进入优化前做一次np.isfinite检查确保数据里没有无穷和NaN。6.2 Hessian不可逆时怎么办凸函数的Hessian是半正定的理论上有逆的疑问不大但数值上经常遇到。典型情况是特征高度共线或者某个方向上没有足够样本支撑导致Hessian近似奇异。np.linalg.solve会抛出LinAlgError或者解出一个巨量方向的更新。我的处理很直接在Hessian上加一个小的对角正则$\delta I$$\delta$从$10^{-8}$起调。如果还不行就说明问题本身接近“秩亏”这时候去检查特征是否冗余、样本量是否太少比硬调$\delta$更本质。还有一个替代思路不用Hessian改用L-BFGS它对秩亏的耐受力更强。在算法层面这也是为什么“线搜索”在牛顿法中必不可少。奇异Hessian产生的更新方向可能根本不是下降方向如果没有线搜索把关这一步就会直接毁掉整个迭代。6.3 目标函数不是光滑凸函数时怎么办现实世界中很多凸问题是不可微的比如Lasso中的L1正则项$|x|$它在零点没有定义梯度。拿标准梯度下降去逼近只会在零点附近来回震荡永远收敛不到精确解。这时候有两条路。第一条是把问题写成光滑函数加近端算子形式用近端梯度法Proximal Gradient Method迭代更新变成$$ x_{k1} \operatorname{prox}_{t h}(x_k - t \nabla f(x_k)) $$对L1范数prox算子就是软阈值操作也即把每个分量往零缩一缩。第二条是使用次梯度算法在不可微点随便选一个次梯度方向当作梯度用然后逐步减小步长比如$t_k 1/\sqrt{k}$可以保证收敛到最优但速度很慢。工程上我遇到L1正则问题首选近端梯度而非次梯度因为实际收敛速度快得多代码也不复杂。6.4 特征缩放和初值选择的经验最后聊两个看似“不值一提”却影响巨大的工程习惯。特征缩放的道理前面已经说了它直接改变条件数。我在所有凸优化试验前都会做标准化让每个特征的均值接近0、标准差为1。这带来的收益经常是收敛速度数量级的提升。尤其用L2正则时不标准化的后果就是正则强度在不同特征上完全不一致解出来的系数也没法解释。初值选择则视问题而定。对强凸问题初值几乎不影响收敛性只影响收敛前期的步数所以可以从零向量出发。但对病态问题一个聪明的初值能省下几百次迭代。我常用的“聪明初值”包括对线性模型用最小二乘闭式解近似对新任务沿用旧任务的模型输出或者先用大量较小的步长跑几十步再切换到大步长效应的算法。不要小看这一步它能直接决定一个算法在时间预算下是“完成”还是“半途而废”。结合我自己的项目经验最后一句话提醒给大家掌握无约束凸优化的标志不是能把公式背出来而是能在一个不了解收敛性的新任务上用一套标准流程——检查凸性、验证梯度、做特征缩放、选择或调试步长、观察收敛曲线——快速得到可信解。这个流程多跑几遍第四章你就真正拿下了。