简介最优化方法课程设计报告围绕单纯形算法、黄金分割法、最速下降法与惩罚函数法四种经典最优化方法展开。报告面向学习运筹学、最优化方法及数值计算课程的本专科生以完整课程设计为框架先在摘要中概述最优化理论的价值与MATLAB工具的应用再逐一阐述各方法的基本思路、算法流程图、MATLAB源程序及应用举例可帮助读者对照实现并掌握从线性规划到非线性约束优化的核心步骤。压缩包内为1个doc格式文档共419KB结构完整分为摘要、单纯形算法、黄金分割法、最速下降法、惩罚函数法、自我总结及参考文献七个模块每个算法专题都配有流程图、可运行的示例代码和数值算例便于按需查阅和修改复用。已有163人浏览学习适合作为最优化课程设计、期末复习或相关竞赛的参考资料。1. 最优化实验报告先定口径模型、算法与停止准则写实验报告时最常见的错误是一上来就贴代码、堆收敛图。真正做报告的第一步是把“实验口径”定清楚你要在什么目标函数上比较哪些算法用什么判据断定迭代已经收敛实验环境怎样固定。否则同一套最优化代码跑出不同结果接下来的一切对比都失去意义。这篇内容按最优化方法课程里最常见的实验形式来讲用可复现的随机二次函数作为测试床对比梯度下降与牛顿法在收敛速度、参数敏感性和数值稳定性上的差异最后能产出一份带表格、收敛曲线和可复现配置的实验报告。2. 从最优化问题建模到实验报告的骨架目标函数、记录字段与收敛判据2.1 实验报告先要有可复现的最优化问题二次模型为例最优化实验最怕目标函数不可控同一个函数不同维度、不同条件数跑出来的行为完全不同。我一般会把实验对象固定为一个带岭参数的随机二次函数min_x f(x) 1/2 x^T A x - b^T x其中A是正定对称矩阵条件数由cond参数控制。选择二次函数有三个好处梯度有解析式A x - bHessian 就是A最优解可以精确验证调整条件数就能模拟“好解”和“难解”的问题算法脚本写起来最短便于把精力放在实验设计上。在这个建模阶段需要确定的参数有四个维度n、条件数cond、随机种子seed、起始点x0。这四个参数会写进实验报告的“实验设置”一节确保别人照着跑能得到同样的数值。常见的做法是用np.random.default_rng(seed)固定噪声再用 QR 分解构造正交矩阵乘以对角阵import numpy as np def make_quadratic(n, cond, seed0): rng np.random.default_rng(seed) Q, _ np.linalg.qr(rng.normal(size(n, n))) diag np.geomspace(cond, 1.0, n) A Q np.diag(diag) Q.T b rng.normal(sizen) return A, bnp.geomspace(cond, 1.0, n)把特征值从cond对数均匀地降到 1构造出来的矩阵条件数大约等于cond。注意Q np.diag(diag) Q.T保证对称正定实际打印np.linalg.cond(A)时可能略有偏差报告里写实际打印值即可。2.2 停止准则怎么定迭代次数、梯度范数与相对变化实验报告里的收敛定义必须落到具体判据上。常见的有三种梯度范数小于tol、目标函数相对变化小于tol、迭代次数达到上限。三者不是替代关系而是同时满足或至少显式记录哪种先触发def check_stop(x_old, x_new, g, f_old, f_new, tol): grad_norm np.linalg.norm(g, np.inf) rel_change np.abs(f_new - f_old) / (1 np.abs(f_old)) return grad_norm tol, rel_change tol我建议在实验报告里把停止判据写明为“梯度无穷范数小于1e-6同时目标函数相对变化小于1e-8”而不是只写“收敛”。原因很实际对条件数大的问题目标函数下降已经很慢但梯度范数仍然偏大只看目标函数相对变化又会提前停止。两个条件组合起来结论更稳。之所以用无穷范数而不是二范数是因为inf范数对应梯度分量的最大值能直接反映“是否每个变量都稳定下来了”二范数会把所有分量平方求和个别分量残留大时也可能被整体数值掩盖。2.3 把记录字段定义好实验报告才不会缺数据迭代过程中需要记录的不只是“最终答案”。一份能复现的实验报告至少要在每次迭代保存这些字段同时把最后几行输出到报告附录里字段含义示例it迭代次数127f当前目标函数值-3.25e-2grad_inf梯度无穷范数停止主判据9.3e-7alpha本次实际使用的步长0.03125x_norm解的范数用于观察发散2.1e-2elapsed累计时间秒0.008定义好字段之后再写算法循环代码和报告的对应关系会非常直接。实际脚本里可以用trace.append((it, f, grad_inf, alpha, ...))的方式累积而不需要在报告阶段重新跑一遍。这也是用二次函数做实验的好处你能预先知道最优解梯度范数是否真的趋近于 0 一目了然。3. 用梯度下降与牛顿法跑通最优化对比实验代码、参数与运行日志3.1 直接在本地跑通的最小 Python 代码确定了目标函数和记录字段之后最优化实验报告的核心就是算法对比脚本。下面这段是完整的最小实现包含固定步长梯度下降、带回溯线搜索的梯度下降和牛顿法。import numpy as np def f(x, A, b): return 0.5 * x A x - b x def grad(x, A, b): return A x - b def backtracking(x, p, A, b, alpha1.0, rho0.5, c1e-4): fx f(x, A, b) slope np.dot(grad(x, A, b), p) while f(x alpha * p, A, b) fx c * alpha * slope: alpha * rho return alpha def run_gradient_descent(x0, A, b, tol1e-6, max_iter10000): x x0.copy() trace [] for it in range(max_iter): g grad(x, A, b) p -g alpha backtracking(x, p, A, b) x x alpha * p trace.append((it 1, f(x, A, b), np.linalg.norm(g, np.inf), alpha)) if np.linalg.norm(g, np.inf) tol: break return x, trace def run_newton(x0, A, b, tol1e-8, max_iter50): x x0.copy() trace [] for it in range(max_iter): g grad(x, A, b) d np.linalg.solve(A, -g) alpha backtracking(x, d, A, b) x x alpha * d trace.append((it 1, f(x, A, b), np.linalg.norm(g, np.inf), alpha)) if np.linalg.norm(g, np.inf) tol: break return x, trace逻辑说明backtracking返回满足 Armijo 条件的步长初始步长设为 1。run_gradient_descent的搜索方向是负梯度p -grun_newton先解线性方程A d -g得到牛顿方向再在线搜索中使用这个方向更新。Armijo 条件写作f(x alpha * p) f(x) c * alpha * grad(x)^T p其中slope是方向导数因为p是下降方向所以为负。参数说明tol是主停止判据max_iter防止不收敛时死循环c1e-4是 Armijo 条件中可接受的下降比例太大容易过早停止太小则退化成精确线搜索rho0.5是步长衰减因子调成 0.8 会让步长更细腻但会增加函数求值次数。3.2 步长参数与 dtype 精度对最优化实验的影响固定步长梯度下降最容易踩的坑是把alpha设成一个看着合理但实际过大的值。以条件数 10 的 10 维问题为例步长 0.9 时目标函数序列会出现来回震荡迭代次数反而变多把 alpha 降到 0.1 后行为才稳定。原因是最小二乘型问题的收敛步长受限于最大特征值步长超过2 / lambda_max时最速下降方向上的分量会过冲。另一个容易被忽略的是float64与float32的差别。最优化实验默认用双精度但如果你在报告里提到“计算时间”必须说明硬件和精度否则不同机器上的耗时没有可比性。我的建议是实验脚本里统一使用np.float64并且在报告开头的“环境”小节写下 numpy 版本和 CPU 型号这属于实验口径的一部分。3.3 从运行日志到实验报告表格跑完算法后把两个算法的 trace 整理成一张对比表需要统计的指标包括达到tol所需迭代次数、最终目标函数值、最终梯度无穷范数、最后一次迭代的步长、总耗时。下面这段代码输出可直接粘贴到报告里x0 np.zeros(10) A, b make_quadratic(10, cond10, seed1) x_gd, trace_gd run_gradient_descent(x0, A, b) x_nt, trace_nt run_newton(x0, A, b) for name, trace in [(GD, trace_gd), (Newton, trace_nt)]: last trace[-1] print(f{name}: iters{last[0]} f{last[1]:.8e} grad{last[2]:.8e})对条件数 10、维度 10、起点为全零的问题典型结果是带线搜索的梯度下降用不到 100 次迭代达到1e-6牛顿法通常 3 到 6 步就达到1e-8。这种差别本身就构成实验报告里最有说服力的部分——算法对比不能只看“谁跑得快”要看迭代次数这个与实现无关的指标。算法迭代次数最终 f最终 grad_infalpha梯度下降回溯线搜索87-1.234e-028.1e-070.25牛顿法回溯线搜索4-1.235e-022.0e-121.0注意上表是示例数据实际数值随seed和cond变化。报告里最好把“数据生成参数”和“结果表”放在同一页别人不用翻代码就能看出变量的对应关系。4. 最优化实验报告里的收敛性验证、数值稳定性排错与参数表设计4.1 条件数变大时最优化实验的结果怎么漂移最优化实验报告如果只跑一个条件数写不出深度。常见做法是设计一组条件数扫描观察迭代次数随cond增大的变化for cond in [1, 10, 100, 1000, 10000]: A, b make_quadratic(10, condcond, seed1) x0 np.zeros(10) _, trace_gd run_gradient_descent(x0, A, b, tol1e-8) _, trace_nt run_newton(x0, A, b, tol1e-10) print(fcond{cond:6d} GD{len(trace_gd):6d} Newton{len(trace_nt):3d})这里把tol提高是为了让梯度下降的迭代次数差异更明显。实际跑下来条件数从 1 涨到 10000 时梯度下降的迭代次数可能从几十次涨到几万次而牛顿法的迭代次数几乎不随条件数变化只有数值上能否精确解线性方程的问题。这个对比直接支撑报告结论“对于正定二次问题牛顿法具有二次收敛性受条件数影响小”。不过报告里不能只贴结果表要把原因写出来梯度下降的收敛速率上界是(cond - 1)/(cond 1)条件数越大每一轮能消掉的误差比例越接近 1牛顿法因为把 Hessian 纳入计算相当于对几何做了一次仿射变换把椭圆等高线变成圆所以条件数不再直接决定迭代步数。这一段在最优化理论与算法课程报告里是重要的得分点也是实际工作中判断该不该换算法的依据。4.2 Hessian 不正定、线搜索失败与数值奇异性怎么排查最优化实验的另一个主题是“算法什么时候失效”。用二次函数作为实验对象时最常见的三类现象第一纯牛顿法在负曲率方向上步长过冲。解决方法是保留回溯线搜索让步长自动缩小如果alpha在连续几十次迭代里都衰减到接近机器精度基本可以判断 Hessian 在当前位置不正定报告中要记录这个现象。第二用np.linalg.solve解线性方程组时出现LinAlgError: Matrix is singular。出现这个异常先检查A是否真的正定打印np.linalg.eigvalsh(A)看最小特征值是否接近 0。二次函数实验里更常见的起因是把A构造成了半正定矩阵比如对角线上有 0此时需要加一个小的岭项A 1e-8 * I。第三回溯线搜索死循环表现为运行时间异常长。排查时在while循环里打印alpha和 Armijo 不等式两侧的值如果alpha已经小于1e-12但条件仍不满足说明初始步长太小或c设得太大。我一般会把c1e-4、rho0.5作为默认值这两个参数很少需要同时调整。4.3 收敛图的画法与实验报告参数表设计实验报告里收敛图比表格更能说明问题。每步记录两个量即可迭代次数、目标函数值。画图时纵轴用对数刻度能同时容纳从1e0到1e-10的下降import matplotlib.pyplot as plt def plot_convergence(trace_gd, trace_nt, filename): plt.figure(figsize(6, 4)) plt.semilogy([t[0] for t in trace_gd], [abs(t[1]) for t in trace_gd], labelGD) plt.semilogy([t[0] for t in trace_nt], [abs(t[1]) for t in trace_nt], labelNewton) plt.xlabel(iteration) plt.ylabel(|f(x_k)|) plt.legend() plt.grid(True, whichboth, ls--, alpha0.4) plt.savefig(filename, dpi150)semilogy的纵轴是目标函数的绝对值因为目标函数可能为负直接画f(x)会看不到下降过程。图上叠加网格线方便直接读出某个迭代次数对应的函数值。报告里通常还会附一张“参数表”把实验中的所有选型列清楚算法名称、线搜索方式、停止准则、容差、最大迭代次数、随机种子。如果参数表里设置了tol1e-8但max_iter1000而实验实际跑了 5000 次迭代这属于实验口径不一致。让复现的人先看参数表再对照运行结果任何不一致都会被立即发现。这就是从“代码能跑”到“报告可信”的分界线。5. 最优化实验的收尾技巧数值梯度检验与可复现实验配置5.1 解析梯度 vs 数值梯度如果实验不限于二次函数极容易在计算梯度时写错一两个符号。最稳妥的收尾技巧是数值梯度检验def numeric_grad(x, A, b, eps1e-6): g np.zeros_like(x) for i in range(x.size): e np.zeros_like(x) e[i] eps g[i] (f(x e, A, b) - f(x - e, A, b)) / (2 * eps) return g x np.random.default_rng(0).normal(size10) rel_err np.linalg.norm(grad(x, A, b) - numeric_grad(x, A, b)) / np.linalg.norm(grad(x, A, b)) print(frel_err{rel_err:.2e})rel_err在1e-8附近说明解析梯度正确如果只有1e-4或更差先检查中心差分步长是否太小再把eps提高到1e-5试一次。超过1e-3可以直接判断梯度公式写错了。这个检验放在实验报告附录里评审人看到rel_err 1e-8就不用再人工核对求导过程。5.2 随机种子与参数文件让实验可复现实验配置里的每个随机因素都要显式固定。np.random.default_rng(seed)比全局np.random.seed更推荐前者不会影响其他库的随机状态。把seed、n、cond、tol这些参数集中在一个字典里运行结果自动落到带数值标签的输出目录这样实验报告里所有数值都能回溯到同一组配置。5.3 报告末尾的敏感度小表最后一节不写宽泛结论而是放一张“参数敏感性”小表让读者能直接看到哪些配置对实验结果影响最大固定cond100把seed从 0 换成 1、2、3梯度下降的迭代次数差异通常在 10% 以内把cond从 100 换成 1000迭代次数往往直接翻倍。这个对照比任何文字描述都更能说明影响实验结果的因素。生成时用一行循环重跑数遍即可不必重新展开整篇分析。最后记得把配置字典和trace同时用np.savez或json.dump存下来报告附件里带上这两个文件整个实验闭环就完整了。本文还有配套的精品资源点击获取
