组合优化与凸优化实验指南：从梯度下降到拉格朗日对偶的实践路径

简介：哈工大组合优化与凸优化研究生课程实验资料包，面向修读该课程的研究生以及希望系统入门优化领域的算法工程师。资料以动手实验为主线，配合详尽的实验报告和说明书，帮助读者将拉格朗日对偶、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-1，graph[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 False

is_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, tol=1e-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, lr=0.01, max_iter=1000, tol=1e-6): theta = np.array(theta0, dtype=float) 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 的逆，规避了显式求逆的计算量，是 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,), method="BFGS") rho *= 10 # 逐轮增大惩罚权重，迫使解向可行域内部移动 print(res.x, f(res.x), g(res.x))

这段代码每轮把rho提高一个数量级，用上一轮的解作为当前轮的初值，本质上是一种续跑策略。初始rho太小，约束会被当不存在；rho增长过快，会让目标函数梯度被惩罚项梯度支配，导致优化器在可行域边界抖动。报告里建议专门画一张rho与约束违反量的关系表，观察约束何时趋近于零。罚函数法最大的坑在于最终解是近似可行解，工程验收时需要用绝对容差去判断是否真正满足约束。

内部罚函数法禁止迭代点穿越约束边界，它的惩罚项在边界处趋向无穷大，所以初始点必须在可行域内部。这个前提条件在实际代码里很容易被忽视，一旦初始点落在边界外侧，目标函数值直接变成无穷大，优化器当场报错。增广拉格朗日法则在罚函数基础上加入乘子项，可以通过乘子更新让解精确满足等式约束，而不是像纯罚函数那样不断增大惩罚系数。

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 在相同约束条件下的目标值一致性；跨实验部分验证拉格朗日乘子与灵敏度分析的结论对齐性。三者都通过后，这份实验报告才不是一份演示文档，而是一份可以交付给后续研究直接复用的实验基座。

本文还有配套的精品资源，点击获取