简介哈工大组合优化与凸优化研究生课程实验资料包面向修读该课程的研究生以及希望系统入门优化领域的算法工程师。资料以动手实验为主线配合详尽的实验报告和说明书帮助读者将拉格朗日对偶、KKT条件、梯度下降、牛顿法等理论概念落地为可运行的代码与可视化结果。压缩包内含262个文件主要为bmp/png图像实验过程截图与结果展示、Python脚本py与pyc源码及编译缓存、xml/iml工程配置文件以及mat数据文件整体约47.1MB目录层级分明便于按Lab1无约束优化、Lab2有约束优化等模块分别查看。资源覆盖了组合优化典型问题如旅行商、网络流与凸优化经典算法并提供实验环境说明、参数调优思路和结果分析可直接用于课程设计或论文复现。已有294人学习使用适合需要快速掌握优化实验流程、撰写实验报告或补充项目案例的读者。1. 组合优化与凸优化实验拿到压缩包后先看说明书再看报告研究生课程里把组合优化和凸优化放进同一个实验单元并不是为了让课程表显得丰满而是在逼你快速区分两类问题变量离散、搜索空间爆炸的组合问题和变量连续、可微性优先的凸问题。哈工大这套课程实验包含 Lab1 无约束优化、Lab2 有约束优化以及对应的实验报告和说明书。拿到手之后建议的顺序是先读说明书再读报告最后自己跑一遍算法因为报告结论往往是选定参数后的结果说明书才写清楚这些参数从哪里来。对正在做工程优化的人来说这套材料最大的价值在于它把推导、编码和实验记录串成了同一条链路可以直接复用到参数调优和运筹实践中。2. 组合优化的三件套动态规划矩阵、贪心失效点与回溯剪枝2.1 先判断问题的拓扑再选主算法组合优化实验里最常见的失误是拿到问题就写贪心。贪心算法只在局部最优与全局最优强相关的问题上可靠比如最小生成树和活动选择一旦问题带有重叠子结构贪心的单步最优策略就会污染后续决策。我的习惯是先画决策图把每一步的候选集合和状态转移画出来如果发现同一个子状态被多次重复计算就优先考虑动态规划如果状态空间分叉多但路径数量可控就用回溯加剪枝只有确认每一步的局部决策不影响未来状态时才把贪心作为主算法否则只能当初始解生成器。问题特征适用算法时间代价典型失败模式重叠子问题 最优子结构动态规划多项式但状态维数可能膨胀状态定义遗漏约束维度局部最优整体最优一致贪心算法低近乎线性只证明局部性缺少全局反例分叉多但可行域可控回溯 剪枝指数级最坏情况剪枝条件过弱导致堆栈溢出目标与约束均为线性单纯形 / 内点法多项式可接受标准形式转换错误判断完成后再把实验说明书里的算例套进目标函数。说明书里给出的通常是最小规模的调试算例不是完整算力压力测试。先用小算例验证算法逻辑再放大数据规模能省掉大量排错时间。2.2 动态规划实验容量约束下的状态转移实现动态规划的核心动作是定义状态和写出转移方程代码反而是最简单的部分。以典型的背包型资源分配为例状态dp[i][w]表示前i个物品在容量w下能获得的最大价值。# knapsack_dp.py def knapsack_dp(weights, values, capacity): n len(weights) # dp[i][w] 表示遍历到第 i 个物品、剩余容量为 w 时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for w in range(capacity 1): if weights[i - 1] w: # 放不下就继承前 i-1 个物品的结果放得下则比较放与不放 dp[i][w] max( dp[i - 1][w], dp[i - 1][w - weights[i - 1]] values[i - 1] ) else: dp[i][w] dp[i - 1][w] return dp[n][capacity]这段代码的逻辑完全由转移方程驱动dp[i-1][w]是不取当前物品的结果dp[i-1][w - weights[i-1]] values[i-1]是腾出容量后取当前物品的结果。两个分支取最大值就保证了每一层只保留最优子结构。capacity 1的列数听上去浪费内存却换来无边界判断的简洁循环。如果实验问题换成了流水线调度或最长公共子序列只需要改状态含义和转移式子外层的双循环框架可以整体保持。实际实验报告中我发现很多同学把容量定义成了二维数组的第一维导致打印出来的最优路径和决策表完全无法对齐。建议统一用dp[i][w]的 i 表示物品下标、w 表示容量下标这样在回溯找具体选择方案时不需要额外维护一张平行表。至于想还原选择了哪些物品可以在循环里额外记录choice[i][w] 1代表放入了物品 i最后从(n, capacity)逆推即可。2.3 回溯实验图着色问题的剪枝策略回溯算法在组合优化实验中的作用是兜底当动态规划的状态膨胀到内存无法承载时回溯配合剪枝是唯一能在合理时间内给出可行解的手段。图着色问题的核心是保证相邻顶点颜色不同实验里常用来对比不同剪枝策略的耗时差异。# graph_coloring_backtrack.py # 顶点编号为 0..n-1graph[v][u] 为 1 表示 v 与 u 相邻 def is_safe(graph, colors, v, c): return all(not graph[v][u] or colors[u] ! c for u in range(v)) def solve_coloring(graph, max_colors, colors, v): if v len(graph): return True for c in range(1, max_colors 1): if is_safe(graph, colors, v, c): # 剪枝只试可用颜色 colors[v] c if solve_coloring(graph, max_colors, colors, v 1): return True colors[v] 0 # 回溯还原现场 return Falseis_safe就是剪枝条件的落地实现它只检查当前候选顶点 v 与已着色顶点是否冲突不需要检查未着色顶点。这里的剪枝力度决定了搜索树的实际规模实验报告里应当记录 max_colors 从小到大的运行时间变化。当 max_colors 等于图的色数时搜索时间会出现明显跳变这个拐点就是验证色数下界最直接的实验证据。如果实验对象换成了 n 皇后问题is_safe改成检查列和对角线的冲突即可回溯框架不必改动。回溯代码最难调试的地方是还原现场。很多人只在找到可行解时返回忘记在失败分支恢复状态导致后续分支带着残留的着色结果继续搜索最终得到错误解。实验报告里建议专门画一张状态恢复流程表记录每个递归入口和出口的 colors 数组变化这样可以快速定位哪一层回溯没有清理干净。3. 凸性判定与无约束优化Lab1 报告中梯度下降的停止条件从哪来3.1 凸函数判定与一维搜索的适用前提Lab1 无约束优化实验里最容易被忽视的第一步不是写梯度函数而是验证目标函数是否凸。凸函数满足f(λx1 (1-λ)x2) ≤ λf(x1) (1-λ)f(x2)在工程上通常直接检查 Hessian 矩阵是否半正定。对于二次型目标函数Hessian 是常数矩阵特征值非负即凸对于一般光滑函数则需要在迭代点附近采样近似估计 Hessian 并检查特征值符号。一维搜索是整个实验的地基因为多维下降法本质上也是反复调用一维搜索来确定步长。黄金分割法不需要函数可导只依赖函数值的大小比较适用范围最宽。以下实现选取区间(a, b)内两个内插点c和d每次迭代丢弃较差一侧的子区间。# golden_section.py def golden_section(f, a, b, tol1e-6): # 黄金分割比用来在两个内插点之间保持固定收缩率 phi (5 ** 0.5 - 1) / 2 c b - phi * (b - a) d a phi * (b - a) while b - a tol: if f(c) f(d): b d # 极小值在 [a, d] 内 else: a c # 极小值在 [c, b] 内 c b - phi * (b - a) d a phi * (b - a) return (a b) / 2每轮迭代区间缩短为原来的 0.618 倍这比二分法的 0.5 慢但优势是完全不依赖导数信息对非光滑目标函数也稳定。实验里如果遇到目标函数带有绝对值项或分段线性项梯度不存在的位置会让梯度下降直接崩溃此时黄金分割法是唯一能保证收敛的选择。要注意tol控制的是区间宽度而不是函数值误差写实验报告时应该把这两者分开记录。黄金分割法的内插点复用逻辑经常被写错更新区间后新的 c 或 d 其中一个是上一轮保留下来的如果重新计算全部两个点计算量会增加但精度不会提高。二分法版本的收敛速度更快但不是针对函数值而是针对一维函数导数的符号变化。它的前提是步长对应的导数值在区间两端异号这个前提在函数单调区间内才成立。实验对比章节里通常建议两种方法各跑一组数据基准测试项目包括迭代次数、剩余区间宽度和最终函数值误差。3.2 多维场景下的梯度下降参数整定多维无约束优化的实验目标通常是等高线图上的收敛路径可视化。梯度下降的实现非常短难点在于学习率选择、终止条件和迭代日志设计。# grad_descent.py import numpy as np def grad_descent(theta0, grad_fn, lr0.01, max_iter1000, tol1e-6): theta np.array(theta0, dtypefloat) for i in range(max_iter): g grad_fn(theta) g_norm np.linalg.norm(g) if g_norm tol: # 梯度模长小于阈值即停止 break theta - lr * g # 沿负梯度方向更新 # 实际实验中在这里记录 theta、g_norm 和 f(theta)用于画收敛曲线 return theta这里的lr固定会导致两个问题学习率过大时迭代会在极小值附近来回震荡g_norm不降反升学习率过小时收敛速度慢到实验报告里只能画出一条近乎水平的价格曲线。我更推荐实验里先跑三组不同量级的 lr比如 0.1、0.01、0.001看g_norm的变化曲线选那条稳定下降且没有锯齿的。终止条件也不应该只依靠g_norm更严谨的做法是同时检查相邻两轮目标函数值的相对变化量当abs(f_new - f_old) / abs(f_old)小于某个阈值时停止这样能避免梯度接近零但目标函数仍在缓慢变化的情况。方法是否使用 Hessian收敛速度单步计算成本适用场景梯度下降否线性收敛低大规模参数调优牛顿法是二阶收敛高需存储并求逆 Hessian小型高精度问题拟牛顿 BFGS近似 Hessian超线性中等中小规模光滑优化L-BFGS有限内存 Hessian超线性低高维大规模优化牛顿法的引入时机取决于 Hessian 的可靠性。如果目标函数光滑且维数不高牛顿法的步长理论上远优于梯度下降的固定步长但 Hessian 出现半正定缺失时牛顿方向可能不是下降方向。拟牛顿法用 BFGS 公式逐步逼近 Hessian 的逆规避了显式求逆的计算量是 sklearn 等库底层最常配的默认优化器。实验报告里如果写成“牛顿法更快”而不说明 Hessian 的修正策略评阅人通常一眼就看出来是套结论。3.3 从目标函数形式反推所需优化器无约束实验的任务往往不止一个目标函数而是给一组函数家族让你对比。我的经验是先对函数做简单分类二次型函数优先用牛顿法因为 Hessian 是常数矩阵一次迭代就能收敛非二次光滑函数用拟牛顿大规模参数问题用 L-BFGS。分类依据来自一个核心事实梯度下降只用了目标函数的一阶信息收敛速度受 Hessian 条件数影响极大。条件数大时等高线呈狭长椭圆状梯度方向几乎指向椭圆短轴收敛路径会呈 Z 字形。这种情况下即使调小学习率也只是让 Z 字变密并没有改变路径本质。更聪明的做法是引入动量项让当前更新方向带有历史梯度的惯性抑制短轴方向的振荡。实验报告中最有价值的内容是记录不同起始点下优化器最终是否收敛到同一个极小值。凸函数的局部最优即全局最优这一性质决定了从任何起点出发梯度类方法都应该收敛到同一解。如果实验中出现了不同终点那大概率是数值精度问题或代码 bug而不是理论的反例。这一步验证值得专门写进报告的结论部分它能把“我跑了算法”升级成“我验证了算法的凸性假设”。4. 拉格朗日对偶与惩罚法Lab2 有约束优化实验的落地路径4.1 约束类型分类与拉格朗日乘子的工程意义Lab2 把问题维度从自由空间拉回到可行域内所有算法选择的出发点都变成“如何让迭代点不违反约束”。约束问题标准形式是min f(x)加上等式约束h_i(x)0和不等式约束g_j(x)≤0。拉格朗日乘子的引入把这组约束编码进了目标函数L(x, λ, μ) f(x) Σλ_i h_i(x) Σμ_j g_j(x)。这里的 λ 和 μ 在最优解处有明确含义它们量化了约束边界对目标函数值的边际影响在做资源分配实验时乘子值等于该资源的影子价格。工程上处理约束问题一般不直接求解 KKT 方程组而是在原问题和对偶问题之间交替迭代。对偶问题的优势是它通常变成无约束问题且对偶函数总是凹函数无论原问题是否凸。但在实验实现时要注意强对偶条件的边界如果 Slater 条件不满足对偶间隙不为零直接落到对偶解还不能宣布原问题解决。实验说明书里常出现的罚函数法就是对这一过程的数值逼近。4.2 惩罚函数法实现与参数敏感性惩罚函数法的思路最简单直接把违反约束的程度转换成目标函数的额外代价然后交给无约束优化器处理。外部惩罚法的典型形式是f(x) ρ * (max(0, g(x))² h(x)²)惩罚系数 ρ 从较小值逐步增大。# penalty_method.py import numpy as np from scipy.optimize import minimize def f(x): return (x[0] - 2) ** 2 (x[1] 1) ** 2 def g(x): # 不等式约束x[0] x[1] - 1 0 return x[0] x[1] - 1 def penalized_objective(x, rho): # 外点罚函数只惩罚违反约束的部分 return f(x) rho * max(0, g(x)) ** 2 rho 1.0 for _ in range(10): res minimize(penalized_objective, x0[0.0, 0.0], args(rho,), methodBFGS) rho * 10 # 逐轮增大惩罚权重迫使解向可行域内部移动 print(res.x, f(res.x), g(res.x))这段代码每轮把rho提高一个数量级用上一轮的解作为当前轮的初值本质上是一种续跑策略。初始rho太小约束会被当不存在rho增长过快会让目标函数梯度被惩罚项梯度支配导致优化器在可行域边界抖动。报告里建议专门画一张rho与约束违反量的关系表观察约束何时趋近于零。罚函数法最大的坑在于最终解是近似可行解工程验收时需要用绝对容差去判断是否真正满足约束。方法约束类型实现复杂度收敛类型主要限制外部罚函数法等式与不等式低逼近可行解惩罚系数无限增大会引入病态 Hessian内部罚函数法不等式为主中从内部逼近边界初始点必须在可行域内部增广拉格朗日法等式为主中高强对偶下精确收敛乘子更新规则需额外推导内点法线性或凸约束高多项式时间内收敛需要预处理与势函数维护内部罚函数法禁止迭代点穿越约束边界它的惩罚项在边界处趋向无穷大所以初始点必须在可行域内部。这个前提条件在实际代码里很容易被忽视一旦初始点落在边界外侧目标函数值直接变成无穷大优化器当场报错。增广拉格朗日法则在罚函数基础上加入乘子项可以通过乘子更新让解精确满足等式约束而不是像纯罚函数那样不断增大惩罚系数。4.3 内点法实验的核心迭代逻辑内点法在实验课程里通常只是概念讲解但如果高级实验要求复现核心逻辑可以拆成三步把不等式约束转成对数壁垒项-t * Σlog(-g_j(x))再通过牛顿法求解带壁垒项的 KKT 条件最后更新壁垒参数 t 并重复直到满足对偶间隙要求。参数 t 控制了壁垒项的强度t 越小壁垒作用越强迭代点离约束边界越远t 越来越大时壁垒逐渐消失迭代点靠向真正的边界解。用最优性条件解读对偶残差、中心性残差和原始可行残差三者在每个内点迭代步内被同时压小。工程实现对新手极不友好的一点是阶梯式障碍牛顿步的步长选择必须保证迭代后的点仍然严格在可行域内部所以通常需要沿着牛顿方向做线搜索缩小步长以避免越界。实验报告里如果只写了一版内点法结果而没有记录步长收缩过程基本等于没做数值验证。这个细节也是评阅时判断学生是否真正跑通代码的关键点之一。用 SciPy 的 SLSQP 求解带约束的非线性问题能避开手工写内点法全部细节但也可以作为基准去验证自己手写内点法代码的正确性。最标准的对照测试是同一目标函数和约束分别用内点法、SLSQP 和惩罚函数法求解三种方法应该收敛到同一目标函数值偏差只在约束处理容差级别。如果三种方法差值超出 1e-6 量级几乎可以断定有一版代码存在逻辑问题。5. 从实验报告反推参数收敛曲线与容差验证的实用技巧5.1 用迭代日志重画收敛判定线实验报告里经常只放最终损失曲线但这恰恰丢失了最重要的信息算法在第几步停止为什么在那一轮停止。更实用的做法是改造成带日志的循环把每次迭代的目标函数值、梯度范数和参数更新量分别落盘成列表。回到第一种方法定位第一次满足终止条件的迭代序号对照该轮的梯度范数你会发现手动改过阈值之后算法往往会提前或延后数轮停住。收敛曲线的横坐标一定要写迭代次数而不是时间因为这个实验的核心比较对象是算法收敛步数不是墙钟时间。# convergence_log.py def run_with_logs(optimize_fn, theta0, **kwargs): log [] for state in optimize_fn(theta0, **kwargs): # 约定 optimize_fn 每轮产出 (iter, fval, grad_norm, step_size) log.append(state) return log将日志转成 DataFrame 以后可以按下面的标准去检查梯度范数是否单调下降目标函数值是否出现回升步长如果来自线搜索回落规律是否符合预期。这三类检查能帮你快速判断算法收敛的性质而不是只看到包装的最终结果。5.2 容差设定过松导致的假收敛实验报告里最常见的假收敛发生在停止阈值过大时。想象梯度范数阈值设成 1e-3而目标函数在极小值附近相当平缓梯度值本来就在 1e-4 量级这时候算法会认为已经收敛实际离最优解还很远。验证方法是拿两组不同容差去跑同一个算例对比最终目标函数差值和达到停止条件的迭代次数。如果容差从 1e-4 改到 1e-6目标函数值变化超过目标量级的 5%就说明之前的结果存在系统性偏差。另一个容易被忽略的点是要观察收敛时步长的绝对值如果步长小于数值精度后续迭代没有任何意义应该人工终止。5.3 里程碑式回归验证把整个压缩包里两个实验报告当作一次完整项目的交付物可以建立三条回归线无约束部分验证梯度下降、牛顿法、拟牛顿法在同一目标函数上的轨道重合性有约束部分验证惩罚法、增广拉格朗日内点法与 SLSQP 在相同约束条件下的目标值一致性跨实验部分验证拉格朗日乘子与灵敏度分析的结论对齐性。三者都通过后这份实验报告才不是一份演示文档而是一份可以交付给后续研究直接复用的实验基座。本文还有配套的精品资源点击获取 组合优化与凸优化实验指南：从梯度下降到拉格朗日对偶的实践路径
简介哈工大组合优化与凸优化研究生课程实验资料包面向修读该课程的研究生以及希望系统入门优化领域的算法工程师。资料以动手实验为主线配合详尽的实验报告和说明书帮助读者将拉格朗日对偶、KKT条件、梯度下降、牛顿法等理论概念落地为可运行的代码与可视化结果。压缩包内含262个文件主要为bmp/png图像实验过程截图与结果展示、Python脚本py与pyc源码及编译缓存、xml/iml工程配置文件以及mat数据文件整体约47.1MB目录层级分明便于按Lab1无约束优化、Lab2有约束优化等模块分别查看。资源覆盖了组合优化典型问题如旅行商、网络流与凸优化经典算法并提供实验环境说明、参数调优思路和结果分析可直接用于课程设计或论文复现。已有294人学习使用适合需要快速掌握优化实验流程、撰写实验报告或补充项目案例的读者。1. 组合优化与凸优化实验拿到压缩包后先看说明书再看报告研究生课程里把组合优化和凸优化放进同一个实验单元并不是为了让课程表显得丰满而是在逼你快速区分两类问题变量离散、搜索空间爆炸的组合问题和变量连续、可微性优先的凸问题。哈工大这套课程实验包含 Lab1 无约束优化、Lab2 有约束优化以及对应的实验报告和说明书。拿到手之后建议的顺序是先读说明书再读报告最后自己跑一遍算法因为报告结论往往是选定参数后的结果说明书才写清楚这些参数从哪里来。对正在做工程优化的人来说这套材料最大的价值在于它把推导、编码和实验记录串成了同一条链路可以直接复用到参数调优和运筹实践中。2. 组合优化的三件套动态规划矩阵、贪心失效点与回溯剪枝2.1 先判断问题的拓扑再选主算法组合优化实验里最常见的失误是拿到问题就写贪心。贪心算法只在局部最优与全局最优强相关的问题上可靠比如最小生成树和活动选择一旦问题带有重叠子结构贪心的单步最优策略就会污染后续决策。我的习惯是先画决策图把每一步的候选集合和状态转移画出来如果发现同一个子状态被多次重复计算就优先考虑动态规划如果状态空间分叉多但路径数量可控就用回溯加剪枝只有确认每一步的局部决策不影响未来状态时才把贪心作为主算法否则只能当初始解生成器。问题特征适用算法时间代价典型失败模式重叠子问题 最优子结构动态规划多项式但状态维数可能膨胀状态定义遗漏约束维度局部最优整体最优一致贪心算法低近乎线性只证明局部性缺少全局反例分叉多但可行域可控回溯 剪枝指数级最坏情况剪枝条件过弱导致堆栈溢出目标与约束均为线性单纯形 / 内点法多项式可接受标准形式转换错误判断完成后再把实验说明书里的算例套进目标函数。说明书里给出的通常是最小规模的调试算例不是完整算力压力测试。先用小算例验证算法逻辑再放大数据规模能省掉大量排错时间。2.2 动态规划实验容量约束下的状态转移实现动态规划的核心动作是定义状态和写出转移方程代码反而是最简单的部分。以典型的背包型资源分配为例状态dp[i][w]表示前i个物品在容量w下能获得的最大价值。# knapsack_dp.py def knapsack_dp(weights, values, capacity): n len(weights) # dp[i][w] 表示遍历到第 i 个物品、剩余容量为 w 时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for w in range(capacity 1): if weights[i - 1] w: # 放不下就继承前 i-1 个物品的结果放得下则比较放与不放 dp[i][w] max( dp[i - 1][w], dp[i - 1][w - weights[i - 1]] values[i - 1] ) else: dp[i][w] dp[i - 1][w] return dp[n][capacity]这段代码的逻辑完全由转移方程驱动dp[i-1][w]是不取当前物品的结果dp[i-1][w - weights[i-1]] values[i-1]是腾出容量后取当前物品的结果。两个分支取最大值就保证了每一层只保留最优子结构。capacity 1的列数听上去浪费内存却换来无边界判断的简洁循环。如果实验问题换成了流水线调度或最长公共子序列只需要改状态含义和转移式子外层的双循环框架可以整体保持。实际实验报告中我发现很多同学把容量定义成了二维数组的第一维导致打印出来的最优路径和决策表完全无法对齐。建议统一用dp[i][w]的 i 表示物品下标、w 表示容量下标这样在回溯找具体选择方案时不需要额外维护一张平行表。至于想还原选择了哪些物品可以在循环里额外记录choice[i][w] 1代表放入了物品 i最后从(n, capacity)逆推即可。2.3 回溯实验图着色问题的剪枝策略回溯算法在组合优化实验中的作用是兜底当动态规划的状态膨胀到内存无法承载时回溯配合剪枝是唯一能在合理时间内给出可行解的手段。图着色问题的核心是保证相邻顶点颜色不同实验里常用来对比不同剪枝策略的耗时差异。# graph_coloring_backtrack.py # 顶点编号为 0..n-1graph[v][u] 为 1 表示 v 与 u 相邻 def is_safe(graph, colors, v, c): return all(not graph[v][u] or colors[u] ! c for u in range(v)) def solve_coloring(graph, max_colors, colors, v): if v len(graph): return True for c in range(1, max_colors 1): if is_safe(graph, colors, v, c): # 剪枝只试可用颜色 colors[v] c if solve_coloring(graph, max_colors, colors, v 1): return True colors[v] 0 # 回溯还原现场 return Falseis_safe就是剪枝条件的落地实现它只检查当前候选顶点 v 与已着色顶点是否冲突不需要检查未着色顶点。这里的剪枝力度决定了搜索树的实际规模实验报告里应当记录 max_colors 从小到大的运行时间变化。当 max_colors 等于图的色数时搜索时间会出现明显跳变这个拐点就是验证色数下界最直接的实验证据。如果实验对象换成了 n 皇后问题is_safe改成检查列和对角线的冲突即可回溯框架不必改动。回溯代码最难调试的地方是还原现场。很多人只在找到可行解时返回忘记在失败分支恢复状态导致后续分支带着残留的着色结果继续搜索最终得到错误解。实验报告里建议专门画一张状态恢复流程表记录每个递归入口和出口的 colors 数组变化这样可以快速定位哪一层回溯没有清理干净。3. 凸性判定与无约束优化Lab1 报告中梯度下降的停止条件从哪来3.1 凸函数判定与一维搜索的适用前提Lab1 无约束优化实验里最容易被忽视的第一步不是写梯度函数而是验证目标函数是否凸。凸函数满足f(λx1 (1-λ)x2) ≤ λf(x1) (1-λ)f(x2)在工程上通常直接检查 Hessian 矩阵是否半正定。对于二次型目标函数Hessian 是常数矩阵特征值非负即凸对于一般光滑函数则需要在迭代点附近采样近似估计 Hessian 并检查特征值符号。一维搜索是整个实验的地基因为多维下降法本质上也是反复调用一维搜索来确定步长。黄金分割法不需要函数可导只依赖函数值的大小比较适用范围最宽。以下实现选取区间(a, b)内两个内插点c和d每次迭代丢弃较差一侧的子区间。# golden_section.py def golden_section(f, a, b, tol1e-6): # 黄金分割比用来在两个内插点之间保持固定收缩率 phi (5 ** 0.5 - 1) / 2 c b - phi * (b - a) d a phi * (b - a) while b - a tol: if f(c) f(d): b d # 极小值在 [a, d] 内 else: a c # 极小值在 [c, b] 内 c b - phi * (b - a) d a phi * (b - a) return (a b) / 2每轮迭代区间缩短为原来的 0.618 倍这比二分法的 0.5 慢但优势是完全不依赖导数信息对非光滑目标函数也稳定。实验里如果遇到目标函数带有绝对值项或分段线性项梯度不存在的位置会让梯度下降直接崩溃此时黄金分割法是唯一能保证收敛的选择。要注意tol控制的是区间宽度而不是函数值误差写实验报告时应该把这两者分开记录。黄金分割法的内插点复用逻辑经常被写错更新区间后新的 c 或 d 其中一个是上一轮保留下来的如果重新计算全部两个点计算量会增加但精度不会提高。二分法版本的收敛速度更快但不是针对函数值而是针对一维函数导数的符号变化。它的前提是步长对应的导数值在区间两端异号这个前提在函数单调区间内才成立。实验对比章节里通常建议两种方法各跑一组数据基准测试项目包括迭代次数、剩余区间宽度和最终函数值误差。3.2 多维场景下的梯度下降参数整定多维无约束优化的实验目标通常是等高线图上的收敛路径可视化。梯度下降的实现非常短难点在于学习率选择、终止条件和迭代日志设计。# grad_descent.py import numpy as np def grad_descent(theta0, grad_fn, lr0.01, max_iter1000, tol1e-6): theta np.array(theta0, dtypefloat) for i in range(max_iter): g grad_fn(theta) g_norm np.linalg.norm(g) if g_norm tol: # 梯度模长小于阈值即停止 break theta - lr * g # 沿负梯度方向更新 # 实际实验中在这里记录 theta、g_norm 和 f(theta)用于画收敛曲线 return theta这里的lr固定会导致两个问题学习率过大时迭代会在极小值附近来回震荡g_norm不降反升学习率过小时收敛速度慢到实验报告里只能画出一条近乎水平的价格曲线。我更推荐实验里先跑三组不同量级的 lr比如 0.1、0.01、0.001看g_norm的变化曲线选那条稳定下降且没有锯齿的。终止条件也不应该只依靠g_norm更严谨的做法是同时检查相邻两轮目标函数值的相对变化量当abs(f_new - f_old) / abs(f_old)小于某个阈值时停止这样能避免梯度接近零但目标函数仍在缓慢变化的情况。方法是否使用 Hessian收敛速度单步计算成本适用场景梯度下降否线性收敛低大规模参数调优牛顿法是二阶收敛高需存储并求逆 Hessian小型高精度问题拟牛顿 BFGS近似 Hessian超线性中等中小规模光滑优化L-BFGS有限内存 Hessian超线性低高维大规模优化牛顿法的引入时机取决于 Hessian 的可靠性。如果目标函数光滑且维数不高牛顿法的步长理论上远优于梯度下降的固定步长但 Hessian 出现半正定缺失时牛顿方向可能不是下降方向。拟牛顿法用 BFGS 公式逐步逼近 Hessian 的逆规避了显式求逆的计算量是 sklearn 等库底层最常配的默认优化器。实验报告里如果写成“牛顿法更快”而不说明 Hessian 的修正策略评阅人通常一眼就看出来是套结论。3.3 从目标函数形式反推所需优化器无约束实验的任务往往不止一个目标函数而是给一组函数家族让你对比。我的经验是先对函数做简单分类二次型函数优先用牛顿法因为 Hessian 是常数矩阵一次迭代就能收敛非二次光滑函数用拟牛顿大规模参数问题用 L-BFGS。分类依据来自一个核心事实梯度下降只用了目标函数的一阶信息收敛速度受 Hessian 条件数影响极大。条件数大时等高线呈狭长椭圆状梯度方向几乎指向椭圆短轴收敛路径会呈 Z 字形。这种情况下即使调小学习率也只是让 Z 字变密并没有改变路径本质。更聪明的做法是引入动量项让当前更新方向带有历史梯度的惯性抑制短轴方向的振荡。实验报告中最有价值的内容是记录不同起始点下优化器最终是否收敛到同一个极小值。凸函数的局部最优即全局最优这一性质决定了从任何起点出发梯度类方法都应该收敛到同一解。如果实验中出现了不同终点那大概率是数值精度问题或代码 bug而不是理论的反例。这一步验证值得专门写进报告的结论部分它能把“我跑了算法”升级成“我验证了算法的凸性假设”。4. 拉格朗日对偶与惩罚法Lab2 有约束优化实验的落地路径4.1 约束类型分类与拉格朗日乘子的工程意义Lab2 把问题维度从自由空间拉回到可行域内所有算法选择的出发点都变成“如何让迭代点不违反约束”。约束问题标准形式是min f(x)加上等式约束h_i(x)0和不等式约束g_j(x)≤0。拉格朗日乘子的引入把这组约束编码进了目标函数L(x, λ, μ) f(x) Σλ_i h_i(x) Σμ_j g_j(x)。这里的 λ 和 μ 在最优解处有明确含义它们量化了约束边界对目标函数值的边际影响在做资源分配实验时乘子值等于该资源的影子价格。工程上处理约束问题一般不直接求解 KKT 方程组而是在原问题和对偶问题之间交替迭代。对偶问题的优势是它通常变成无约束问题且对偶函数总是凹函数无论原问题是否凸。但在实验实现时要注意强对偶条件的边界如果 Slater 条件不满足对偶间隙不为零直接落到对偶解还不能宣布原问题解决。实验说明书里常出现的罚函数法就是对这一过程的数值逼近。4.2 惩罚函数法实现与参数敏感性惩罚函数法的思路最简单直接把违反约束的程度转换成目标函数的额外代价然后交给无约束优化器处理。外部惩罚法的典型形式是f(x) ρ * (max(0, g(x))² h(x)²)惩罚系数 ρ 从较小值逐步增大。# penalty_method.py import numpy as np from scipy.optimize import minimize def f(x): return (x[0] - 2) ** 2 (x[1] 1) ** 2 def g(x): # 不等式约束x[0] x[1] - 1 0 return x[0] x[1] - 1 def penalized_objective(x, rho): # 外点罚函数只惩罚违反约束的部分 return f(x) rho * max(0, g(x)) ** 2 rho 1.0 for _ in range(10): res minimize(penalized_objective, x0[0.0, 0.0], args(rho,), methodBFGS) rho * 10 # 逐轮增大惩罚权重迫使解向可行域内部移动 print(res.x, f(res.x), g(res.x))这段代码每轮把rho提高一个数量级用上一轮的解作为当前轮的初值本质上是一种续跑策略。初始rho太小约束会被当不存在rho增长过快会让目标函数梯度被惩罚项梯度支配导致优化器在可行域边界抖动。报告里建议专门画一张rho与约束违反量的关系表观察约束何时趋近于零。罚函数法最大的坑在于最终解是近似可行解工程验收时需要用绝对容差去判断是否真正满足约束。方法约束类型实现复杂度收敛类型主要限制外部罚函数法等式与不等式低逼近可行解惩罚系数无限增大会引入病态 Hessian内部罚函数法不等式为主中从内部逼近边界初始点必须在可行域内部增广拉格朗日法等式为主中高强对偶下精确收敛乘子更新规则需额外推导内点法线性或凸约束高多项式时间内收敛需要预处理与势函数维护内部罚函数法禁止迭代点穿越约束边界它的惩罚项在边界处趋向无穷大所以初始点必须在可行域内部。这个前提条件在实际代码里很容易被忽视一旦初始点落在边界外侧目标函数值直接变成无穷大优化器当场报错。增广拉格朗日法则在罚函数基础上加入乘子项可以通过乘子更新让解精确满足等式约束而不是像纯罚函数那样不断增大惩罚系数。4.3 内点法实验的核心迭代逻辑内点法在实验课程里通常只是概念讲解但如果高级实验要求复现核心逻辑可以拆成三步把不等式约束转成对数壁垒项-t * Σlog(-g_j(x))再通过牛顿法求解带壁垒项的 KKT 条件最后更新壁垒参数 t 并重复直到满足对偶间隙要求。参数 t 控制了壁垒项的强度t 越小壁垒作用越强迭代点离约束边界越远t 越来越大时壁垒逐渐消失迭代点靠向真正的边界解。用最优性条件解读对偶残差、中心性残差和原始可行残差三者在每个内点迭代步内被同时压小。工程实现对新手极不友好的一点是阶梯式障碍牛顿步的步长选择必须保证迭代后的点仍然严格在可行域内部所以通常需要沿着牛顿方向做线搜索缩小步长以避免越界。实验报告里如果只写了一版内点法结果而没有记录步长收缩过程基本等于没做数值验证。这个细节也是评阅时判断学生是否真正跑通代码的关键点之一。用 SciPy 的 SLSQP 求解带约束的非线性问题能避开手工写内点法全部细节但也可以作为基准去验证自己手写内点法代码的正确性。最标准的对照测试是同一目标函数和约束分别用内点法、SLSQP 和惩罚函数法求解三种方法应该收敛到同一目标函数值偏差只在约束处理容差级别。如果三种方法差值超出 1e-6 量级几乎可以断定有一版代码存在逻辑问题。5. 从实验报告反推参数收敛曲线与容差验证的实用技巧5.1 用迭代日志重画收敛判定线实验报告里经常只放最终损失曲线但这恰恰丢失了最重要的信息算法在第几步停止为什么在那一轮停止。更实用的做法是改造成带日志的循环把每次迭代的目标函数值、梯度范数和参数更新量分别落盘成列表。回到第一种方法定位第一次满足终止条件的迭代序号对照该轮的梯度范数你会发现手动改过阈值之后算法往往会提前或延后数轮停住。收敛曲线的横坐标一定要写迭代次数而不是时间因为这个实验的核心比较对象是算法收敛步数不是墙钟时间。# convergence_log.py def run_with_logs(optimize_fn, theta0, **kwargs): log [] for state in optimize_fn(theta0, **kwargs): # 约定 optimize_fn 每轮产出 (iter, fval, grad_norm, step_size) log.append(state) return log将日志转成 DataFrame 以后可以按下面的标准去检查梯度范数是否单调下降目标函数值是否出现回升步长如果来自线搜索回落规律是否符合预期。这三类检查能帮你快速判断算法收敛的性质而不是只看到包装的最终结果。5.2 容差设定过松导致的假收敛实验报告里最常见的假收敛发生在停止阈值过大时。想象梯度范数阈值设成 1e-3而目标函数在极小值附近相当平缓梯度值本来就在 1e-4 量级这时候算法会认为已经收敛实际离最优解还很远。验证方法是拿两组不同容差去跑同一个算例对比最终目标函数差值和达到停止条件的迭代次数。如果容差从 1e-4 改到 1e-6目标函数值变化超过目标量级的 5%就说明之前的结果存在系统性偏差。另一个容易被忽略的点是要观察收敛时步长的绝对值如果步长小于数值精度后续迭代没有任何意义应该人工终止。5.3 里程碑式回归验证把整个压缩包里两个实验报告当作一次完整项目的交付物可以建立三条回归线无约束部分验证梯度下降、牛顿法、拟牛顿法在同一目标函数上的轨道重合性有约束部分验证惩罚法、增广拉格朗日内点法与 SLSQP 在相同约束条件下的目标值一致性跨实验部分验证拉格朗日乘子与灵敏度分析的结论对齐性。三者都通过后这份实验报告才不是一份演示文档而是一份可以交付给后续研究直接复用的实验基座。本文还有配套的精品资源点击获取