凸优化从理论到代码：梯度下降、牛顿法、内点法与ADMM实战-北京尧图网络

简介这份资源是凸优化理论学习的心得配套代码包面向正在入门或希望系统梳理凸优化知识体系的机器学习、数据分析方向学习者。内容围绕学习路径展开涵盖入门书籍选择、Boyd《凸优化》结构解读、线性代数与微积分基础铺垫以及多所高校公开教程与资源的整理帮助读者少走弯路、建立清晰的知识框架。压缩包共3个文件以inscode工程配置、html页面和gitignore为主整体约5KB属于轻量级项目代码便于快速查看与二次整理。目前已有71人学习下载。读者可从中获得一份完整的学习路线参考包括课程资源索引、书籍章节脉络梳理以及基础学科补强建议适合作为凸优化自学的起步指南也便于结合代码工程结构理解资源组织方式。1. 凸优化学习心得从理论推导到代码复现的完整路径很多人学凸优化卡在同一个地方书上的对偶推导能看懂KKT 条件也能背但一到自己写代码求解就不知道从哪下手。这个项目代码包就是冲着这个痛点来的——它把凸优化从数学定义到算法实现再到数值验证串成了一条线每个核心概念都配了可运行的代码。适合正在学凸优化课程但作业写不动的学生也适合工作中需要手推优化模型再落地的算法工程师。代码包覆盖了凸集判定、凸函数验证、梯度下降、牛顿法、内点法、ADMM 等核心模块语言以 Python 为主依赖 NumPy 和 Matplotlib不需要额外的商业求解器。换句话说这是一份能让你从「看懂公式」过渡到「跑出结果」的实操材料。2. 凸优化代码包的结构拆解六个模块各自解决什么问题2.1 模块划分与依赖关系拿到代码包之后别急着跑main.py先花十分钟把目录结构看清楚。常见的组织方式是按「数学基础 → 无约束优化 → 有约束优化 → 应用案例」四层递进每个目录下再按算法拆分文件。我一般会先看requirements.txt和README确认依赖版本和入口脚本避免因为 NumPy 版本差异导致np.float报错这种低级翻车。典型的目录结构长这样convex-optimization/ ├── requirements.txt ├── basics/ │ ├── convex_set.py # 凸集判定与可视化 │ └── convex_function.py # 凸函数验证一阶/二阶条件 ├── unconstrained/ │ ├── gradient_descent.py # 梯度下降及变体 │ ├── newton_method.py # 牛顿法 │ └── line_search.py # 线搜索策略 ├── constrained/ │ ├── kkt_solver.py # KKT 条件数值验证 │ ├── interior_point.py # 内点法 │ └── admm.py # ADMM 交替方向乘子法 ├── applications/ │ ├── lasso_regression.py # Lasso 回归 │ ├── svm_dual.py # SVM 对偶求解 │ └── portfolio.py # 投资组合优化 └── utils/ ├── plot_utils.py # 收敛曲线、等高线绘制 └── timer.py # 算法耗时统计这个结构的好处是模块之间低耦合。比如你想单独测试牛顿法只需要from unconstrained.newton_method import NewtonSolver不用把整个包跑一遍。依赖方面核心计算只用到 NumPy可视化用 Matplotlib没有引入 CVXPY 或 SciPy 的优化模块——这是有意为之目的是让你看清算法本身的迭代逻辑而不是调一个黑匣子求解器。2.2 核心数据结构与接口约定代码包里所有求解器遵循统一的接口约定这是能复用的关键。每个 solver 类至少暴露三个方法__init__接收超参数fit接收目标函数和梯度函数solve执行迭代并返回结果字典。结果字典里固定包含x_opt最优解、f_opt最优值、history每步的目标函数值列表、n_iter迭代次数。# 统一的求解器接口示例 class GradientDescentSolver: def __init__(self, lr0.01, max_iter1000, tol1e-6): self.lr lr # 学习率控制每步走多远 self.max_iter max_iter # 最大迭代次数防止死循环 self.tol tol # 收敛阈值梯度范数小于此值认为收敛 def solve(self, f, grad_f, x0): x x0.copy() history [] for i in range(self.max_iter): g grad_f(x) if np.linalg.norm(g) self.tol: break x x - self.lr * g # 沿负梯度方向更新 history.append(f(x)) return {x_opt: x, f_opt: f(x), history: history, n_iter: i 1}这段代码里三个参数各有讲究。lr设大了会震荡甚至发散设小了收敛慢到你想砸键盘max_iter是后悔药防止目标函数不收敛时程序卡死tol决定了你什么时候认为「够了」。我一般先用lr0.01跑一遍看收敛曲线如果震荡就把lr砍半如果曲线太平就适当放大。history列表是后续画收敛图的基础别把它丢了。2.3 从数学定义到代码的映射关系凸优化代码包最有价值的地方在于它把数学定义直接翻译成了可验证的代码。比如凸集的定义是「集合内任意两点的连线仍在集合内」代码里就对应一个采样验证函数随机取若干对点检查线段上的点是否满足集合的约束条件。凸函数的一阶条件「f(y) ≥ f(x) ∇f(x)ᵀ(y-x)」和二阶条件「Hessian 矩阵半正定」也各有对应的数值验证脚本。这种映射关系看起来简单但实际写的时候有几个细节容易忽略。第一数值验证只能证伪不能证明——采样没找到反例不代表一定是凸的。第二Hessian 半正定的判定要用特征值分解而不是行列式因为行列式非负只是必要条件。第三浮点误差会让边界情况误判通常要加一个eps1e-8的容差。代码包里这些细节都处理了你在读的时候留意一下convex_function.py里的容差参数是怎么设的。3. 无约束优化算法的代码实现梯度下降、牛顿法与线搜索3.1 梯度下降的三种变体与收敛对比梯度下降是最容易上手但也最容易踩坑的算法。代码包里实现了三种变体批量梯度下降BGD、随机梯度下降SGD和小批量梯度下降Mini-batch GD。三者的区别在于每次更新时用多少样本计算梯度。# 三种梯度下降变体的核心差异 def bgd_update(x, X, y, lr): grad compute_grad(x, X, y) # 用全部样本算梯度 return x - lr * grad def sgd_update(x, X, y, lr): i np.random.randint(len(y)) # 随机选一个样本 grad compute_grad(x, X[i:i1], y[i:i1]) return x - lr * grad def minibatch_update(x, X, y, lr, batch_size32): idx np.random.choice(len(y), batch_size, replaceFalse) grad compute_grad(x, X[idx], y[idx]) return x - lr * gradBGD 每步都用全量数据梯度方向准但计算量大SGD 每步只用一个样本快但梯度噪声大收敛曲线会抖得像心电图Mini-batch 是折中方案batch_size一般取 32 到 256 之间。代码包里有一个对比脚本能在同一个凸二次目标函数上跑三种变体把收敛曲线画在一张图里。跑完之后你会直观看到BGD 曲线平滑但下降慢SGD 前期下降快但后期在最优解附近震荡Mini-batch 兼顾了两者。学习率的设置是另一个关键。固定学习率在简单问题上够用但遇到条件数大的问题就力不从心。代码包里额外实现了两种自适应策略一种是按迭代次数衰减lr lr0 / (1 decay * t)另一种是回溯线搜索。前者实现简单后者更鲁棒但每步要多算几次函数值。3.2 牛顿法的实现细节与 Hessian 矩阵处理牛顿法用二阶信息来加速收敛迭代公式是x x - H⁻¹∇f。理论上有二次收敛速度但实际实现有两个绕不开的问题Hessian 矩阵可能不可逆以及计算 Hessian 的代价可能很高。def newton_solve(f, grad_f, hess_f, x0, max_iter100, tol1e-8): x x0.copy() for i in range(max_iter): g grad_f(x) if np.linalg.norm(g) tol: break H hess_f(x) # 加正则项保证 Hessian 可逆 H_reg H 1e-6 * np.eye(len(x)) try: d np.linalg.solve(H_reg, -g) # 牛顿方向 except np.linalg.LinAlgError: d -g # 退化为梯度方向 # 回溯线搜索确定步长 t 1.0 while f(x t * d) f(x) 0.5 * t * g d: t * 0.5 x x t * d return x这段代码里有三个值得注意的点。第一H_reg加了1e-6的正则项这是防止 Hessian 奇异时的兜底手段代价是稍微偏离纯牛顿方向。第二np.linalg.solve比直接求逆np.linalg.inv(H) g数值更稳定速度也更快。第三回溯线搜索的 Armijo 条件f(xtd) ≤ f(x) 0.5*t*gd保证了每步都有充分下降t从 1.0 开始折半通常几次就能满足。牛顿法在低维问题比如维度小于 100上优势明显迭代次数通常是个位数。但维度一高Hessian 矩阵的存储和求逆就成了瓶颈。代码包里对高维情况提供了拟牛顿法BFGS的简化实现用梯度差来近似 Hessian 的逆省去了直接计算二阶导数的麻烦。3.3 线搜索策略的选择与参数调优线搜索解决的是「方向定了走多远」的问题。代码包里实现了三种策略固定步长、回溯线搜索Armijo 条件和精确线搜索黄金分割。固定步长最简单但最不靠谱精确线搜索最稳但每步开销大回溯线搜索是实际用得最多的。选择策略时我一般看两个指标每步的计算代价和总迭代次数。精确线搜索每步要解一个一维优化问题单步代价高但迭代次数少回溯线搜索单步代价低但可能需要更多迭代。在目标函数计算便宜的场景下比如简单的二次函数精确线搜索反而总耗时更短。代码包里有一个line_search.py专门做对比实验你可以改c1参数Armijo 条件的系数默认 1e-4看收敛行为的变化。c1设得太大会导致步长过小收敛慢设得太小则可能不满足下降条件。4. 有约束优化的代码实战KKT 条件、内点法与 ADMM4.1 KKT 条件的数值验证方法KKT 条件是有约束优化的核心理论但很多人学完之后不知道怎么用代码验证。代码包里的kkt_solver.py提供了一个数值验证框架给定一个等式约束和不等式约束的优化问题求解之后逐项检查 KKT 条件的满足程度。KKT 条件包含四部分平稳性条件∇f Σλᵢ∇gᵢ Σμⱼ∇hⱼ 0、原始可行性gᵢ(x) ≤ 0, hⱼ(x) 0、对偶可行性μⱼ ≥ 0和互补松弛性μⱼgⱼ(x) 0。代码里对每一项计算残差如果所有残差都小于容差就认为 KKT 条件满足。def check_kkt(x, f_grad, g_funcs, g_grads, h_funcs, h_grads, lambdas, mus, tol1e-4): # 平稳性残差 stationarity f_grad(x).copy() for lam, hg in zip(lambdas, h_grads): stationarity lam * hg(x) for mu, gg in zip(mus, g_grads): stationarity mu * gg(x) res_stat np.linalg.norm(stationarity) # 原始可行性残差 res_prim max( max(0, g(x)) for g in g_funcs ) if g_funcs else 0 res_prim max(res_prim, max(abs(h(x)) for h in h_funcs) if h_funcs else 0) # 对偶可行性 res_dual max(0, -min(mus)) if mus else 0 # 互补松弛性 res_comp max(abs(mu * g(x)) for mu, g in zip(mus, g_funcs)) if mus else 0 return {stationarity: res_stat, primal: res_prim, dual: res_dual, complementary: res_comp}这个验证框架的实用价值在于当你自己实现了一个求解器但不确定结果对不对时把解代进 KKT 检查一遍四项残差都小就说明解是靠谱的。容差tol一般设 1e-4 到 1e-6取决于问题的尺度。如果某一项残差特别大就针对性地排查——平稳性不满足说明梯度计算或乘子更新有问题互补松弛性不满足说明不等式约束的活跃集判断有误。4.2 内点法的障碍函数与中心路径内点法的思路是把不等式约束通过障碍函数「吸收」进目标函数把有约束问题转化为一系列无约束问题。代码包里用的是对数障碍函数φ(x) -Σ log(-gᵢ(x))当 x 靠近约束边界时障碍函数趋于无穷大从而把迭代点「挡」在可行域内部。def barrier_method(f, grad_f, g_funcs, grad_g_funcs, x0, t01.0, mu10.0, tol1e-6): x x0.copy() t t0 while True: # 定义障碍目标函数 def barrier_obj(x): val t * f(x) for g in g_funcs: gv g(x) if gv 0: return np.inf # 不可行点直接返回无穷 val - np.log(-gv) return val # 用牛顿法求解当前 t 下的无约束问题 x newton_solve(barrier_obj, None, None, x, max_iter50) # 检查对偶间隙 m len(g_funcs) if m / t tol: break t * mu # 增大 t逼近原问题 return x这段代码的核心逻辑是外层循环逐步增大t内层用牛顿法求解障碍问题。t越大障碍项的影响越小解越接近原问题的最优解。mu是增长因子一般取 10 到 20太小会导致外层迭代次数多太大则内层牛顿法可能不收敛。对偶间隙的估计用m/t当它小于tol时停止。内点法的收敛性很好理论上多项式时间内就能收敛到高精度解。但实现时要注意初始点必须在可行域内部严格满足所有不等式约束否则对数障碍函数没有定义。代码包里提供了一个寻找严格可行初始点的辅助函数用的是 Phase I 方法。4.3 ADMM 的拆分策略与收敛判据ADMM交替方向乘子法适合求解可以拆成两块变量的凸优化问题形式是min f(x) g(z) s.t. Ax Bz c。它的迭代分三步x 更新、z 更新、对偶变量更新。代码包里的admm.py用 Lasso 回归作为例子展示了完整的实现。def admm_lasso(A, b, lam, rho1.0, max_iter1000, tol1e-4): m, n A.shape x np.zeros(n) z np.zeros(n) u np.zeros(n) # 缩放后的对偶变量 for k in range(max_iter): # x 更新解一个岭回归 x np.linalg.solve(A.T A rho * np.eye(n), A.T b rho * (z - u)) # z 更新软阈值操作 z_old z.copy() z soft_threshold(x u, lam / rho) # 对偶变量更新 u u x - z # 收敛判据 r_norm np.linalg.norm(x - z) # 原始残差 s_norm np.linalg.norm(-rho * (z - z_old)) # 对偶残差 if r_norm tol and s_norm tol: break return zADMM 的关键参数是惩罚因子rho。rho太大原始残差下降快但对偶残差下降慢rho太小则反过来。实际使用中如果发现原始残差和对偶残差量级差很多就要调整rho。代码包里实现了自适应rho的策略当原始残差远大于对偶残差时增大rho反之减小。软阈值函数soft_threshold(v, kappa) sign(v) * max(|v| - kappa, 0)是 Lasso 问题的近端算子也是 ADMM 能高效求解 Lasso 的原因——z 更新有闭式解不需要迭代。5. 避坑与排查凸优化代码复现中的五个血泪教训5.1 梯度检查不通过数值梯度与解析梯度的偏差现象自己实现的解析梯度和数值梯度对不上相对误差超过 1e-4。原因常见的有三种——梯度公式推导错误、数值梯度的步长h选得不当、或者函数在某个点不可导但没做处理。数值梯度用(f(xh) - f(x-h)) / (2h)计算时h太大会引入截断误差太小会引入浮点舍入误差一般取1e-5到1e-7之间比较合适。解决代码包里有一个grad_check工具函数用中心差分做数值梯度逐分量对比解析梯度。如果某个分量的误差特别大就单独检查那一项的推导。另外注意如果目标函数里有max、abs或norm在零点不可导梯度检查要避开这些点。5.2 收敛曲线震荡学习率与条件数的关系现象梯度下降的收敛曲线上下震荡目标函数值不降反升。原因学习率相对于目标函数的曲率太大了。对于二次函数f(x) 0.5 xᵀQx梯度下降稳定的条件是lr 2 / λ_max(Q)其中λ_max是 Q 的最大特征值。如果问题的条件数λ_max / λ_min很大稳定学习率的上限会很小收敛也会很慢。解决先计算 Hessian 的最大特征值把学习率设成1 / λ_max左右。如果条件数太大考虑换用牛顿法或拟牛顿法或者对变量做预处理比如归一化来改善条件数。代码包里的plot_utils.py可以画出目标函数的等高线和迭代轨迹能直观看到震荡是怎么产生的。5.3 内点法在边界附近报 NaN对数障碍的定义域问题现象内点法迭代到某一步时目标函数变成 NaN程序崩溃。原因迭代点跑到了可行域外面log(-g(x))里的-g(x)变成负数或零对数无定义。这通常是因为牛顿步太大一步跨过了约束边界。解决在牛顿法里加回溯线搜索确保每步更新后所有不等式约束仍然严格满足。代码包里的barrier_method在计算障碍目标函数时做了检查遇到不可行点直接返回np.inf线搜索会自动缩小步长。另外初始点必须严格可行不能取在边界上。5.4 ADMM 残差不下降rho 参数的调整策略现象ADMM 跑了几百轮原始残差和对偶残差都卡在某个值不再下降。原因rho的设置导致原始问题和对偶问题的收敛速度严重不匹配。原始残差大说明x和z差得远需要增大rho来加强一致性约束对偶残差大说明对偶变量更新不够需要减小rho。解决用自适应rho策略每隔若干轮检查两个残差的比值。如果r_norm / s_norm 10把rho乘以 2如果s_norm / r_norm 10把rho除以 2。注意调整rho之后对偶变量u要按比例缩放否则会引入额外的震荡。代码包里admm.py的自适应版本已经处理了这个细节。5.5 数值精度导致 KKT 验证失败容差设置的经验现象求解结果看起来是对的但 KKT 检查的某一项残差总是比容差大一点点。原因浮点运算的累积误差。特别是当问题尺度很大或很小时绝对容差1e-4可能过严或过松。另外互补松弛性条件μⱼgⱼ(x) 0在数值上很难精确满足因为μⱼ和gⱼ(x)可能都不为零但乘积很小。解决用相对容差代替绝对容差比如res / (1 |f(x)|) tol。互补松弛性的检查可以放宽到|μⱼgⱼ(x)| 1e-3。如果只有这一项不满足而其他三项都很好通常不影响解的实际可用性。代码包里的check_kkt函数支持传入自定义容差你可以根据问题尺度调整。6. 进阶技巧用收敛曲线和等高线验证算法行为6.1 收敛曲线的正确读法收敛曲线是最直接的验证工具但很多人只看「有没有下降」就完事了。实际上曲线的形状能告诉你更多信息。横轴用迭代次数还是用耗时结论可能完全不同——牛顿法迭代次数少但每步慢梯度下降迭代次数多但每步快画在同一张图上才能公平比较。我一般会画三张图目标函数值随迭代次数的变化、梯度范数随迭代次数的变化、以及目标函数值随耗时的变化。第一张看收敛速度第二张看是否真的到了驻点第三张看实际效率。代码包里的plot_utils.py提供了plot_convergence函数支持同时画多条曲线并自动加图例。from utils.plot_utils import plot_convergence # 假设 results 是不同求解器返回的结果字典列表 plot_convergence( results, # 结果列表 labels[GD, Newton, ADMM], # 图例标签 x_axisiter, # 横轴迭代次数 y_axisf_val, # 纵轴目标函数值 log_scaleTrue # 纵轴取对数便于看后期收敛 )纵轴取对数是个实用技巧。线性坐标下后期的小幅下降看不出来取对数之后收敛速率一目了然——直线下降说明线性收敛曲线变陡说明超线性收敛。6.2 等高线与迭代轨迹的叠加分析对于二维问题把等高线和迭代轨迹画在一起是最直观的调试手段。你能看到迭代点是不是沿着「山谷」走有没有在窄长区域来回震荡牛顿法是不是一步就跳到了中心。from utils.plot_utils import plot_contour_with_path plot_contour_with_path( f, # 目标函数 x_range(-5, 5), # x 轴范围 y_range(-5, 5), # y 轴范围 paths[gd_path, newton_path], # 迭代轨迹列表 labels[GD, Newton], levels20 # 等高线条数 )等高线的形状反映了问题的条件数。圆形等高线说明条件数接近 1梯度下降也能很快收敛椭圆越扁说明条件数越大梯度下降越容易震荡。看到椭圆特别扁的时候我就会直接换牛顿法或者先做变量缩放。6.3 一个具体的调试习惯从那以后我每次实现一个新的优化算法都强制走一遍这个流程先用一个已知最优解的简单问题比如二维二次函数验证正确性再画收敛曲线和迭代轨迹确认行为符合预期最后才上真实数据。这个习惯帮我省下了大量排查时间——很多 bug 在简单问题上就会暴露不用等到复杂场景才发现。具体来说我会在tests/目录下放一个test_simple_quadratic.py里面定义一个f(x) 0.5 * xᵀQx cᵀx的目标函数Q 取正定矩阵最优解用解析公式x* -Q⁻¹c算出来。任何新算法先在这个问题上跑解和解析解对不上就说明实现有问题。这个测试文件不到 50 行但能拦住八成以上的低级错误。代码包里的applications/目录下还有 Lasso 回归、SVM 对偶和投资组合优化三个案例每个都是从问题建模到求解到结果可视化的完整流程。建议按顺序看Lasso 最简单适合理解 ADMM 的拆分思想SVM 对偶涉及不等式约束适合练 KKT 条件投资组合优化是二次规划适合对比内点法和 ADMM 的效果。把这几个案例跑通凸优化的代码落地能力基本就过关了。希望帮到你。本文还有配套的精品资源点击获取

凸优化从理论到代码：梯度下降、牛顿法、内点法与ADMM实战

相关推荐

鲲鹏云大数据实验：ARM节点Hadoop 2.8.3部署与OBS联通实操

MATLAB 2FSK调制解调仿真代码拆解：从信源到误码率曲线

Claude Code模板体系实战：CLAUDE.md与Slash Commands提效指南

更多资讯

Kafka接入AI实战：从Lag排查到Function Calling自动化运维

harness 工程化实践：用 AGENTS.md 与 Makefile 把 TaoToken 接入 CI 流水线

大模型推理-基于prefill和decode阶段特性，PD分离，势在必行！TaoToken统一Key下的PD分离部署大纲

2026年5月开源模型Token服务实测榜：TaoToken统一Key下DeepSeek/GLM/Kimi三层架构性能拆解

Codex 下载与本地部署实战：从安装到运行全流程指南（TaoToken 统一 Key 接入版）

QML自制数字软键盘：向TextInput/TextField键入数字并实现左移右移删除

今日更新

NetSpot 实战：用信道分析与频宽优化解决 Wi-Fi 卡顿

C++ split() 字符串分割的五种实现与性能实测

R语言坐标轴范围设置：从xlim/ylim到coord_cartesian的完整指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？