组合优化与凸优化课程实验指南：算法实现与报告写作全解析

简介：哈工大组合优化与凸优化研究生课程实验资料包，面向需要系统理解离散优化与凸优化理论的研究生和工程人员，通过动手实验掌握动态规划、贪心、梯度下降、内点法等经典算法。压缩包共262个文件，约47.1MB，包含128个bmp和100个png图像用于实验结果可视化与数据集展示，12个Python脚本及对应pyc文件用于算法实现，配套xml/iml工程配置、mat数据文件和all-data数据集，结构完整便于复现。实验覆盖无约束优化与有约束优化两大主题，从一维搜索、梯度下降到线性规划、惩罚函数与内点法，实验报告详细记录问题背景、求解步骤与结果分析，说明书则给出清晰的操作指引。资源提供全套实验代码、可视化图表和撰写规范的报告，适合研究生课程学习、期末复习或优化算法入门参考。目前已有294人学习下载。

1. 组合优化与凸优化研究生课程实验，这个包应该怎么读

一个命名规规矩矩的包：“哈工大组合优化与凸优化研究生课程实验内含实验报告和说明书.zip”，本质上不是一份现成的答案，而是一套需要你还原出完整实验流程的素材。组合优化和凸优化是两类不同的数学优化体系：前者面对离散决策变量，后者面对连续可微目标；课程实验往往要求你在同一个报告里既有理论推导，又有可复现代码，还要把实验结果组织成说明书。我接下来按常见实验设计把整个包拆开，告诉你每一部分该用什么算法实现、报告怎么写、最终怎么打包成一个能直接交的ZIP。适合正在做这门课实验的研究生，也适合把这类问题当面试准备的工程师。

2. 组合优化实验：从建模到分支定界的落地写法

2.1 先判断问题的难度：P、NP-hard还是可近似

组合优化实验几乎不会让你从零发明算法，而是让你在几个经典模型里选一个：TSP、背包、指派、最大割。课程实验对应的通常是一个离散优化问题，以0-1背包最典型，因为状态空间清晰且便于验证最优解。我在动手前会先做两件事：一是把问题写成整数规划或0-1规划的数学形式，二是判断规模。比如给定物品数n和背包容量C，价值为v、重量为w，这类问题当n越过40时，暴力枚举就非常吃力，必须用分支定界或动态规划。

分支定界的思想是：把原始问题的解空间分成子集，用松弛问题的解作界，剪掉不可能优于当前最优解的分支。对于最大化背包问题，上界可以用连续背包松弛来计算——把剩余容量按价值密度从高到低装满。这个上界越紧，剪枝效率越高。

2.2 用Python写一个背包问题的分支定界骨架

下面这版代码不是最优工程实现，而是用于课程实验展示算法逻辑的最小骨架：

import heapq def bound(i, n, w, v, cap, cur_v, cur_w): """计算从第i个物品开始可能达到的价值上界""" if cur_w >= cap: return 0 total_v = cur_v remain = cap - cur_w j = i while j < n and w[j] <= remain: remain -= w[j] total_v += v[j] j += 1 if j < n: total_v += v[j] * remain / w[j] return total_v def knapsack_branch_bound(n, w, v, cap): # 按价值密度降序排序 items = sorted(range(n), key=lambda idx: -v[idx] / w[idx]) w = [w[i] for i in items] v = [v[i] for i in items] best = 0 best_sol = [0] * n # 使用最大堆，因为heapq是最小堆，取负值 heap = [] heapq.heappush(heap, (0, 0, 0, 0, [])) # (-cur_v, level, cur_v, cur_w, path) while heap: neg_v, level, cur_v, cur_w, path = heapq.heappop(heap) if level == n: continue # 选择当前物品 if cur_w + w[level] <= cap: new_v = cur_v + v[level] new_path = path + [1] if new_v > best: best = new_v best_sol = new_path + [0] * (n - level - 1) if level + 1 < n and bound(level + 1, n, w, v, cap, new_v, cur_w + w[level]) > best: heapq.heappush(heap, (-new_v, level + 1, new_v, cur_w + w[level], new_path)) # 不选当前物品 new_v = cur_v new_path = path + [0] if level + 1 < n and bound(level + 1, n, w, v, cap, new_v, cur_w) > best: heapq.heappush(heap, (-new_v, level + 1, new_v, cur_w, new_path)) return best, best_sol

这段代码的bound函数是整个分支定界的核心：它把剩余容量按价值密度连续填充，得到当前分支的价值上界。只有当上界超过当前已知最优解时才入堆，否则直接剪枝。参数n、w、v、cap分别对应物品数、重量列表、价值列表和背包容量；堆里存储的二元组把cur_v取负，是为了借用heapq实现最大堆。注意排序后返回的解对应的是排序后的物品顺序，实验报告里需要再做一次映射回原顺序。

2.3 参数选择和启发式算法的边界

分支定界适合n在几十到几百之间的问题，一旦物品数超过三四百，上界可能不够紧，队列会膨胀到内存吃紧。这时实验通常会允许你换用启发式算法。模拟退火、遗传算法这类方法不保证最优，但能在秒级给出不错的结果。我一般用两个指标来选：问题规模是否超过分支定界的可解上限，以及是否要求最优解。课程实验要求的往往是最优解或指定gap，所以优先分支定界或动态规划，不要一开始就上启发式。

下面这张表总结了组合优化实验中常见的算法定位，写报告时可以对照：

写报告时，通常要给出至少一个精确算法和一个启发式算法的对比，这样才能体现对组合优化“可解性”的理解。很多同学只贴结果不放剪枝过程，分数上不去，原因就在这里。

2.4 组合优化实验的自测指标

实验报告里不能只说“运行成功”。你需要记录三组数值：最优解与已知下界的差距、运行时长、内存占用。对于随机生成的数据，可以先用小的n验证算法能找到穷举最优，再放大规模记录时间曲线。把时间-规模数据画成对数坐标图，几乎能直接看出算法是否指数增长。这个图比几十页推导更有说服力。

3. 凸优化实验：梯度下降、牛顿法与对偶的代码路径

3.1 凸函数判定与实验目标设计

凸优化实验的第一步不是写代码，而是先确认目标函数是凸的。你拿到实验题时，可能给的是一个带约束的二次规划或最小二乘问题。要验证凸性，最可靠的方法是检查定义域内Hessian矩阵是否半正定。对不可导函数，则用定义式对任意两点判断。课程实验很多是线性回归或逻辑回归损失函数，天然凸，但不要跳过判定，因为报告需要你写这一句。

我一般会在代码里先做一个Hessian计算：

import numpy as np def hessian_check(X, y, theta): """线性回归目标函数的Hessian，应为半正定""" m = len(y) H = (X.T @ X) / m # 检查所有特征值是否大于等于0 eigvals = np.linalg.eigvalsh(H) return H, eigvals X = np.random.randn(50, 5) y = np.random.randn(50) H, eigvals = hessian_check(X, y, None) print("最小特征值:", eigvals.min())

这里的X是设计矩阵，y是观测向量。线性回归目标函数为 ||y - X theta||^2 / (2m)，其Hessian是(X^T X)/m，只要样本数足够且特征不共线，特征值非负。注意这里为什么除以m：目的是让目标函数和梯度量级不随数据量增长，实验里很多收敛问题都源于忘记归一化。

3.2 梯度下降和牛顿法的参数怎么设

凸优化的核心实验通常比较三种一阶/二阶优化器：普通梯度下降、带动量的梯度下降、牛顿法。下面是一个收敛对比的最小实现：

def gradient_descent(X, y, lr=0.1, iter_max=200, tol=1e-6): m, n = X.shape theta = np.zeros(n) history = [] for _ in range(iter_max): grad = (X.T @ (X @ theta - y)) / m theta -= lr * grad history.append(np.linalg.norm(grad)) if history[-1] < tol: break return theta, history def newton_method(X, y, iter_max=50, tol=1e-8): m, n = X.shape H = (X.T @ X) / m theta = np.zeros(n) history = [] for _ in range(iter_max): grad = (X.T @ (X @ theta - y)) / m delta = np.linalg.solve(H, grad) theta -= delta history.append(np.linalg.norm(grad)) if history[-1] < tol: break return theta, history

这里的lr是学习率，tol是梯度范数的终止阈值。普通梯度下降对学习率非常敏感，lr太大会震荡，太小则收敛慢。牛顿法直接求解线性系统，相当于用曲率缩放梯度，所以不需要学习率，但代价是每次迭代需要解一个n乘n线性方程组，特征多时计算量很大。你可以把两者跑在同一份数据上，画出梯度范数随迭代次数的下降曲线，然后检查实验报告里的收敛对比表。

下面是参数的一个经验范围：

3.3 约束优化：从拉格朗日对偶到KKT条件的验证

组合优化和凸优化在约束处理上思路不同。凸优化实验会给出一个带约束的线性规划或二次规划，要求你写出拉格朗日函数，并用对偶问题求最优解。一个最小例子是：

最小化 0.5 x^2，约束 x >= 1。

拉格朗日函数 L(x, lambda) = 0.5x^2 - lambda*(x-1)，lambda >= 0。对x求导得到 x = lambda，代入原问题得到对偶函数 g(lambda) = -0.5lambda^2 + lambda。最大化这个凹函数，得到lambda = 1，所以x = 1。这个解满足原问题的约束，且互补松弛条件 lambda*(x-1)=0成立。

代码里验证KKT只需要几步：

import numpy as np def check_kkt(x, grad_f, grad_h, lam): # 稳定性：梯度加上约束梯度的线性组合应为0 print("stationarity:", np.dot(grad_f(x) + lam * grad_h(x), grad_f(x) + lam * grad_h(x))) print("primal feasible:", x - 1 >= 0) print("dual feasible:", lam >= 0) print("complementary:", lam * (x - 1))

实际参数x=1, lambda=1，四个条件全满足。需要注意的是，对于非凸问题KKT是必要条件而非充分条件；报告里要写明约束规格（如Slater条件）以保证对偶强对偶性成立。

3.4 数值稳定性与收敛判定的坑

凸优化实验最常见的失败是目标值变成NaN。原因一般是学习率过大、数据未归一化或Hessian奇异。遇到这种情况，先检查特征值，再把学习率降到0.01重跑。另一个容易被忽略的参数是停止条件：用梯度范数比用目标函数变化更可靠，因为目标值可能在很平的区域缓慢变化，而梯度范数能更直接反映是否到达平稳点。

在写报告时，把三种方法的目标函数下降曲线画在同一张图上，横轴用迭代次数，纵轴用log10(目标值-最优值)。如果牛顿法曲线是直线且很快贴到0，说明二阶收敛；梯度下降则呈线性收敛。这个区分是实验的高分点。

4. 实验报告与说明书的写作规范：让审阅者一眼看到工作量

4.1 报告结构的四段式与分值布局

实验报告不能是代码附件的说明文档。组合优化与凸优化课程实验的评分者一般会先看报告能否独立回答问题，再看代码能否复现。我建议采用四段式：问题建模、方法设计、数值实验、结论分析。问题建模写清楚决策变量、目标函数和约束；方法设计写出算法伪代码和复杂度；数值实验放结果表格和曲线；结论分析写实验中发现的异常和尝试过的改进。

常见实验报告包括需求分析、概要设计、详细设计、测试报告等。对于算法类课程，不必写软件工程那套东西，而是要把重点放在算法正确性、效率和实验覆盖度上。报告的长度不是越多越好，能用一张表说清数据分布就不用堆代码。

4.2 说明书里必须写清的三件事

说明书是独立于报告之外的文本，通常放在ZIP的根目录。它要回答三个问题：用什么环境跑、按什么顺序跑、结果输出在哪里。我一般会在说明书写一个最小可复现步骤，例：

python -m venv venv source venv/bin/activate pip install -r requirements.txt python run_combination.py python run_convex.py python plot_convergence.py

然后说明每个脚本输出到哪个目录。这个可复现性往往被忽视，但实验报告中只要有一处“在我的机器上能跑”以外的事实，就能让审阅者信任。dependency-free的matlab脚本也要写清版本号，比如R2023a，因为不同版本的优化工具箱接口有差异。

4.3 实验数据与图表怎么放

实验报告内的表格格式可以这样组织：

每个数据点最好连随机种子都记录，方便别人复现。图不要截控制台输出，而是用Matplotlib生成带数据标签和参数说明的曲线。图题写清坐标轴含义，例如“测试集误差随学习率变化”，不要写“结果图”这种无法检索的名称。

4.4 附录：把推导过程和失败实验也收进去

满分报告几乎都有一个好附录。附录放两类内容：一是凸优化中KKT条件、对偶间隙等关键公式的完整推导；二是实验过程中失败算法的时间对比，比如固定学习率导致发散的学习曲线。失败记录能说明你对算法收敛性的理解，而不是只展示成功结果。ZIP包里报告和说明书区分开来，报告面向“做了什么”，说明书面向“怎么复现”。

5. 把实验包打成干净的ZIP：压缩参数、目录结构与校验

5.1 压缩参数怎么选

实验报告、说明书、源码和结果截图整理好后，最终用zip打包。建议使用-9获得更小的体积，但如果目录里有大量图像，-9耗时会更长。我一般这样做：

zip -r -9 组合优化与凸优化课程实验.zip report.pdf README.md src/ figures/

这个命令把report.pdf、README.md、src目录和figures目录递归打包。-r是递归目录的必需参数，-9表示最高压缩比。如果还需要保留Unix权限，可以加--symlinks，但Windows解压时通常不需要。

5.2 目录结构与README的写法

一个清楚的包应该有可检索的入口：

组合优化与凸优化课程实验/ ├── README.md ├── 实验报告.pdf ├── 说明书.md └── src/ ├── combination_branch_bound.py └── convex_optimization.py

README写三件事：实验概述、环境依赖、脚本入口。说明书在此基础上补上参数设置和输出路径。文件名避免final_final.py这类无法区分的命名，用版本或日期区分。

5.3 用校验和确认ZIP完整

交付前用SHA-256记录文件摘要，再用解压测试确认内部CRC正确：

sha256sum 组合优化与凸优化课程实验.zip unzip -t 组合优化与凸优化课程实验.zip

第一条命令输出唯一校验值，第二条命令逐个测试ZIP内部记录的CRC。返回没有错误，说明这个包可以交给审阅者；把校验值写进说明书，后续换机器也能验证文件未被改动。

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