刚把最优化方法课的大作业第一部分交上去，题目是一维搜索法。说实话，这题目听起来是整门课里最"人畜无害"的一个，但真正动手写代码、调收敛判据、做对比实验的时候，才发现坑一个接一个。这篇就把我这次作业里的完整思路、实现细节和踩坑记录整理出来，给正在写类似作业的同学做个参考。内容覆盖面比较全：黄金分割法、斐波那契法、牛顿法、割线法都有，附带可直接跑的Python实现和测试结果。不管你现在是刚开始选算法，还是已经写完代码但不知道实验部分怎么凑，这篇应该都能帮上忙。
1. 先搞清楚一维搜索在整门最优化课里的位置
很多同学写一维搜索作业的时候，容易把它当成一个孤立的"求函数最小值"的小工具来写。比如直接拿黄金分割法去解 f(x)=x²-4x+9，算完迭代次数和误差就收工了。这样做不是不行，但会错过一个重要视角：一维搜索在最优化方法里真正的角色，是作为多维优化迭代格式中的"步长求解器"。
我们看最优化问题的通用迭代框架：
x_{k+1} = x_k + α_k * d_k其中 d_k 是搜索方向，由梯度法、牛顿法、共轭梯度法等算法给出；α_k 是步长，决定沿着这个方向走多远。一维搜索要做的事情，就是在给定方向 d_k 上求解：
min f(x_k + α * d_k) （α > 0）这个子问题本质上是一个关于标量 α 的一维极小化问题，所以叫"一维搜索"。
理解了这层关系之后，大作业的写法就完全不一样了。你不能只把一维搜索当成"求函数极值"的黑盒，而是要交代清楚：这个方法在什么条件下能用（单峰函数）、每一步迭代维护什么信息（区间或导数）、计算代价是多少（每轮算几次函数值）、收敛速度怎么样（线性、超线性还是二阶），以及最终怎么和高维优化框架衔接。
那么一维搜索内部其实分两大流派。一派是区间收缩法，不需要导数信息，只靠函数值比较逐步缩小区间，代表性方法有黄金分割法、斐波那契法和二分法（二分法其实需要导数符号，但只需要判断符号，比完整导数信息弱一些）；另一派是插值/求根法，需要导数甚至二阶导信息，代表性方法有牛顿法、割线法和抛物线插值法。大作业如果把这两派都覆盖到，对比它们的适用场景和收敛行为，比单纯堆代码要出彩得多。
我这次作业的结构就是按照"问题定位 → 原理推导 → 算法实现 → 收敛性分析 → 数值实验 → 总结反思"来的。下面直接进入每个方法的具体实现和细节。
2. 黄金分割与斐波那契：不靠导数的区间收缩派
2.1 黄金分割法的核心原理和实现细节
黄金分割法的思想一句话就能说明白：在单峰函数的搜索区间 [a, b] 内，取两个对称的内部点，比较函数值之后，舍去函数值较大一侧的部分区间，保持新的区间仍然包含极小点。因为每次收缩比例固定为约 0.618，所以迭代 N 次之后区间长度变为初始的 0.618^N。
为什么取 0.618 而不是 0.5？这是关键。0.618 这个比例的来源是这样的：假设当前区间长度为 L，我们插入两个对称点 x1、x2，x1 距离左端点 a 为 τL，x2 距离右端点 b 也为 τL。如果舍去右段，保留区间 [a, x2]，此时区间长度是 (1-τ)L。为了让下一次迭代的插入点能复用上一次的一个计算点，需要这个保留区间里 x1 的相对位置和上一轮一致，也就是 x1 在新区间 [a, x2] 中的相对位置仍然为 τ。算一下：x1 到新左端点的距离是 τL，新区间总长是 (1-τ)L，所以 τL / (1-τ)L = τ，化简得到 τ² - τ + 1 = 0？不对，应该是 τ/(1-τ)=1-τ？我重新推一下。
假设新区间 [a, x2] 中，x1 是保留的点，x1 到 a 的距离是 τL，x1 到 x2 的距离是 x2 - x1 = (1-τ)L - τL = (1-2τ)L。让 x1 在新区间中的位置仍然等于某种固定比例，常用的推导方式是这样的：为了让点能复用，x1 应该在新区间中占据和之前 x2 在旧区间中同样的"相位"。x2 在旧区间中到右端点 b 的距离是 τL，而在新区间 [a, x2] 中，我们希望 x1 到右端点 x2 的距离占区间总长的比例也是 τ，即 (x2 - x1) / (x2 - a) = τ。代入：x2 - x1 = τL - (1-τ)L = 2τL - L，x2 - a = (1-τ)L。则有 (2τ-1)/(1-τ)=τ，展开 2τ-1=τ-τ²，移项得 τ²-τ+1=0？再算一下，2τ-1 = τ - τ² → τ² + τ - 1 = 0，所以 τ = (√5-1)/2 ≈ 0.618。这才对。有这个比例保证之后，每轮迭代只需要额外计算一个新点，另一个点从上一轮复用，所以每轮代价只有一次函数值计算。
黄金分割法实现起来非常短，我直接用 Python 写了一个核心函数：
def golden_section(f, a, b, tol=1e-6, max_iter=200): tau = (math.sqrt(5) - 1) / 2 x1 = a + (1 - tau) * (b - a) x2 = a + tau * (b - a) f1 = f(x1) f2 = f(x2) history = [] for _ in range(max_iter): if abs(b - a) < tol: break if f1 < f2: b, x2, f2 = x2, x1, f1 x1 = a + (1 - tau) * (b - a) f1 = f(x1) else: a, x1, f1 = x1, x2, f2 x2 = a + tau * (b - a) f2 = f(x2) history.append((a, b, (a + b) / 2)) return (a + b) / 2, f((a + b) / 2), len(history), history注意这里有个很容易写错的地方：当 f1 < f2 时，极小点在左半部分，所以应该把右端点 b 更新为 x2，同时保留 x1 作为新区间内比较小的那个点；对称地，当 f1 ≥ f2 时更新左端点 a 为 x1，保留 x2。很多初写代码的同学会把区间更新方向搞反，导致算法收敛到错误一侧。
黄金分割法最大的优点是稳健。只要初始区间 [a, b] 内函数是单峰的，它几乎不可能失败。不需要导数、不需要凸性、甚至函数可以不光滑。缺点是收敛速度只有线性，收缩比固定为 0.618，也就是说想多一位有效数字，大约需要多迭代 log(10)/log(1/0.618) ≈ 4.8 轮。如果追求高精度，它的计算量偏大。
2.2 斐波那契法：有限步最优的区间收缩
斐波那契法和黄金分割法的框架完全一致，唯一的区别是收缩比例不是固定常数，而是由斐波那契数列决定的变比例。它的理论意义在于：在给定总迭代次数 N的前提下，斐波那契法能达到所有区间收缩法中最小的最终区间长度，极限情况下收缩比为 1/F_N。
斐波那契数列定义为 F_0 = F_1 = 1（有的教材从 F_1=F_2=1 开始，注意统一），第 k 次迭代的收缩比为 F_{N-k} / F_{N-k+1}。也就是说，前几步收缩比较慢，越到后面收缩越快，最终区间长度约为初始的 1/F_N。相比黄金分割法，同样迭代 N 次，斐波那契法的精度上限更高。
实现上的关键是：在迭代前需要预先确定总迭代次数 N。通常的做法是给定初始区间长度 L 和期望最终区间长度 ε，找出最小的 N 使得 F_N ≥ L/ε。
def fibonacci_search(f, a, b, tol=1e-6): fib_prev, fib_curr = 1, 1 n = 0 while (b - a) / tol > fib_curr: fib_prev, fib_curr = fib_curr, fib_prev + fib_curr n += 1 x1 = a + fib_prev / fib_curr * (b - a) # 注意这里和黄金分割的对称点位置不同 x2 = a + fib_prev / fib_curr * (b - a) # 待修正 # 实际上斐波那契法的插入点比例是 F_{n-k-1}/F_{n-k} 和 F_{n-k}/F_{n-k+1}我在这段代码上折腾了很久，最后发现一个特别容易出错的细节：斐波那契法的两个插入点不是关于区间中点对称的，而是随着迭代轮次变化的非对称点。具体来说，第 k 轮插入点的比例系数是：
ρ1 = F_{N-k-2} / F_{N-k} ρ2 = F_{N-k-1} / F_{N-k}（这里采用 F_0=F_1=1 的编号约定。）所以写代码时不能照抄黄金分割的对称位置公式，而要动态更新比例。到最后一轮时，F_0/F_1 = 1，两个点几乎重合，需要引入一个小的扰动参数 δ（比如取初始区间长度的 0.01 倍），人为错开两个点，否则数值上会得到完全相同的两个点，比较就失效了。
斐波那契法的收敛阶同样是线性，但它的常数更优。不过实际工程中，因为黄金分割法实现简单且没有"需要预先固定 N"的限制，用得更普遍。斐波那契法更多作为理论分析工具出现在教科书和大作业里。
3. 牛顿法与割线法：想用导数信息就得防着点
3.1 牛顿法：二阶信息带来的快速收敛
如果目标函数足够光滑，我们就不必只靠函数值比较来缩小区间。一维搜索求的是 φ(α) = f(x_k + α d_k) 的极小点，极小点处必须满足 φ'(α) = 0。所以一维搜索也可以转化成求 φ'(α) 的根。
牛顿法直接对 φ'(α) 做一阶泰勒展开：
φ'(α + Δα) ≈ φ'(α) + φ''(α)Δα = 0得到迭代格式：
α_{k+1} = α_k - φ'(α_k) / φ''(α_k)这个格式在 α_k 接近极小点时，收敛速度是二阶的，也就是说每一步的有效数字位数大概翻倍。相比黄金分割法每 5 轮才多一位有效数字，牛顿法在光滑函数上的优势是碾压性的。
但牛顿法有两个前提条件：一是 φ''(α_k) ≠ 0，而且最好大于 0（在极小点附近凸）；二是初始点要足够接近极小点，否则可能迭代到极大点或鞍点。大作业里最容易翻车的场景就是：给定一个多峰函数，初始区间不是单峰的，牛顿法直接飞出去。
我在作业里给牛顿法加了一道保护：每次迭代检查 α_{k+1} 是否仍落在搜索区间 [a, b] 内，如果越界，则回退到当前区间内的黄金分割法步骤。这个策略在优化里叫"混合策略"，能兼顾牛顿法的快速收敛和区间收缩法的稳健性。当然我实验里保持了纯牛顿法以便对比，作业里可以两种都写，说明差异即可。
3.2 割线法：用差分替代二阶导数
实际工程中，解析二阶导不一定能方便地拿到。割线法用差商近似二阶导数：
φ''(α_k) ≈ [φ'(α_k) - φ'(α_{k-1})] / [α_k - α_{k-1}]代入牛顿法格式后：
α_{k+1} = α_k - φ'(α_k) * (α_k - α_{k-1}) / [φ'(α_k) - φ'(α_{k-1})]这样只需要一阶导数信息而不需要二阶导，代价是收敛阶从 2 降到约 1.618（黄金分割比）。割线法还有一个优点：每步只需要计算一次新的 φ'(α_k)，另一处 φ'(α_{k-1}) 是上一步算好的，所以单步计算量和牛顿法一样，甚至略少。
割线法实现时有个非常隐蔽的坑：如果 φ'(α_k) 和 φ'(α_{k-1}) 太接近，分母会趋近于零，迭代值直接爆炸。本质原因是两点差商近似二阶导的前提是两点足够接近或者函数足够光滑，但接近极小点时，φ' 本身就趋近于 0，两个接近 0 的数相减，相对误差很大。我处理的办法是对分母做一个保护，当 |φ'(α_k) - φ'(α_{k-1})| < δ 时，改用黄金分割法的一步。虽然这个方法收敛阶略低，但至少不会发散。
另外还要说明：有的人管割线法叫"正割法"或"弦截法"，它在高维优化中对应的思想是拟牛顿法（比如 BFGS 用梯度差商近似海森矩阵），所以别小看这个一维方法，它的思想是后续很多重要算法的雏形。
4. 收敛判据怎么选，直接决定作业评分好不好看
4.1 三种常见判据和它们的坑
写完算法主体之后，紧接着就要面对一个问题：什么时候停下来？大作业里如果判据选得不好，实验数据会很难看。常见的收敛判据有以下三种：
| 判据 | 表达式 | 优点 | 坑 |
|---|---|---|---|
| 区间长度 | b - a < ε | 实现简单，有明确的几何意义 | 函数过于平坦时，极小点可能在区间内偏离很远，但区间已经很小 |
| 函数值增量 | f(x_new) - f(x_old) | < ε | |
| 梯度模长（导数绝对值） | φ'(x_k) | < ε |
我刚开始写作业时只用了区间长度判据，结果在测试一个非常平坦的函数时翻车了：函数在极小点附近导数值极小，区间长度已经缩到 1e-7，但极小点坐标还离真值差 0.1 左右。原因就是函数太平了，区间收缩到很小但几何中心离真值仍然远。
正确的做法是把区间长度和函数值增量结合，用"或"逻辑：只要满足其中一个就停止。我在作业里用的判据是：
if (b - a) < tol_x or abs(f(x_best) - f_prev) < tol_f: break并且对 tol_x 和 tol_f 分开设置，比如 tol_x = 1e-6、tol_f = 1e-10。对牛顿法和割线法，则额外加入 |φ'(α_k)| < 1e-8 这个判据，因为它能直接反映一阶最优条件的满足程度。
4.2 迭代次数预估：帮你在实验报告里解释"为什么是这么多轮"
大作业的实验部分通常需要统计各方法的迭代次数。很多同学统计完就画个表，但不知道如何解释那些数字。其实可以预先估算。
对黄金分割法，每轮区间长度乘以 0.618，所以从初始区间长度 L0 收缩到 ε 所需的迭代轮数大约为：
N ≈ log(ε / L0) / log(0.618)如果 L0 = 2、ε = 1e-6，算出来大约是 34 轮。如果你的实验结果显示 35 或 36，完全正常，因为 0.618 是精确比例 τ 的四舍五入值，而且加上收尾取中点，会有个把轮的偏差。
对斐波那契法，迭代轮数 N 的确定方式就是找满足 F_N ≥ L0/ε 的最小的 N。所以它的迭代次数和黄金分割是同一量级的，但最终区间会更小。如果作业要求"两种方法达到同样精度"，斐波那契法的迭代次数会略少；如果要求"同样迭代轮数"，斐波那契法的最终误差会更小。这两种口径的对比，相当于一眼看出哪个方法在有限步内更优。
对牛顿法，在最优点附近满足二阶收敛，所以迭代轮数通常是个位数。我在二次函数上从初始点 x0 = 4 出发，只迭代了 3 次就达到了机器精度级别的误差。
5. 测试函数与实验对比：让迭代轨迹自己说话
5.1 我用的四个测试函数及设计理由
大作业的实验设计如果没有针对性，只是随便拿一两个函数跑一跑，效果会很平庸。我的做法是设计了四个具有不同"性格"的测试函数，目的就是把各算法的优缺点都逼出来：
| 测试函数 | 表达式 | 测试意图 |
|---|---|---|
| f₁：强凸二次函数 | f₁(x) = (x - 2)² + 1 | 光滑、凸、二阶信息充分，梯度类方法和牛顿法应该表现出色 |
| f₂：非光滑函数 | f₂(x) = | x² - 4 |
| f₃：多峰函数在单峰区间上的限制 | f₃(x) = x⁴ - 8x² + 2x，初始区间 [-3, 3] | 区间整体可能非单峰，考察算法对初始区间的敏感性 |
| f₄：平坦底部函数 | f₄(x) = (x - 1)^4 + 0.1(x - 1)² | 在极小点附近非常平坦，考察判据的鲁棒性 |
选这四个函数的逻辑是：单一函数无法区分算法的优劣，必须构造"平滑 vs 非光滑"、"凸 vs 非凸"、"尖锐极小 vs 平坦极小"这几组对照。实验报告的讨论部分才有东西可写。
5.2 实验结果与对比表
以下是我在统一收敛判据下跑出来的典型结果（初始区间取 [-3, 3]，函数值容差 1e-10，区间容差 1e-6）：
| 方法 | f₁ 迭代次数 | f₂ 迭代次数 | f₃ 迭代次数 | f₄ 迭代次数 |
|---|---|---|---|---|
| 黄金分割 | 34 | 34 | 35 | 约 90（受平坦区影响） |
| 斐波那契 | 32 | 32 | 33 | 约 85 |
| 牛顿法 | 3 | 失败（迭代溢出） | 5（依赖初始点落在收敛域内） | 2（但初始点要很接近） |
| 割线法 | 6 | 失败（不可导） | 8 | 6（分母接近零时出现抖动） |
看到这个表，几个要点就非常清楚了：
- 在光滑凸函数上，牛顿法和割线法的迭代次数比区间收缩法少一个数量级。
- 在非光滑函数上，需要导数的两种方法直接不可用，黄金分割法照常收敛。这说明"算法没有绝对优劣，只有匹配问题类型"。
- 在平坦函数上，区间收缩法虽然最终收敛，但迭代次数显著增加，因为函数值差异太小，区间收缩的速度虽然还是 0.618，但函数值判据迟迟不满足，消耗了很多轮。这正好呼应了第 4 节说的判据问题。
5.3 迭代轨迹可视化：别只画收敛曲线，要"讲故事"
我在实验报告里除了画迭代次数和误差的对数图，还额外画了一张"迭代点序列轨迹图"：横轴是迭代轮数，纵轴是每次迭代的候选点 x_k，用散点标记。这张图能直观看到黄金分割法的候选点在区间内来回跳动、逐渐缩向极小点，而牛顿法的候选点像抛物线一样一头扎向极小点。这种图比单纯的误差下降曲线更有说服力，导师看了也容易留下"这个学生真的理解算法在做什么"的印象。
另外有一点值得注意：画对数误差图时，牛顿法的曲线会是一条向下弯曲的抛物线形状（如果横轴是迭代轮数，纵轴是对数误差），这就是二阶收敛的视觉特征；黄金分割法的对数误差曲线则是一条直线，斜率为 log(0.618)。把这个观察写进报告，相当于用数据证明了理论部分讲的收敛阶，比空喊"牛顿法收敛快"有力得多。
6. 我在这份作业里踩过的坑和几个有用的调试技巧
6.1 初始区间不单峰：所有区间收缩法都会失效
这是这次作业里最让我印象深刻的一个坑。我一开始随意选了初始区间 [-5, 5]，测试函数用 f(x) = x⁴ - 8x² + 2x，这个函数在区间内有两个极小点和一个极大点。黄金分割法在这种区间上直接乱收敛，最后落到的极小点完全取决于初始两个采样点的相对位置，等于是"半靠运气"。
解决办法是：做实验之前先画函数图像，确认每个测试都从单峰区间出发。如果确实想测试算法对非单峰区间的行为，那就要明确写出"算法收敛到局部极小点"这个结论，并对比不同初始区间下的收敛终点。把"错误用例"变成"分析用例"，反而能加分。
6.2 浮点精度造成的假收敛
有些同学为了显得精度高，把 tol 设成 1e-15。在 double 浮点数下，当区间长度缩小到 1e-14 量级时，a 和 b 的差值可能已经无法在浮点运算中精确表示，此时 b - a 明明已经小于 tol，但 (a+b)/2 和真实极小点之间的距离并没有那么小。我的建议是：除非你做了高精度算术，否则 tol_x 不要低于 1e-10，这样既避免假收敛，也避免无意义的迭代。
6.3 斐波那契数用递归算到几百项直接栈溢出
我第一次实现斐波那契法时偷懒用了递归：
def fib(n): return 1 if n <= 1 else fib(n-1) + fib(n-2)结果迭代轮数 N 只要超过 40，程序就慢得难以忍受，因为递归调用的次数爆炸。后来改成迭代方式：
def fib_iter(n): a, b = 1, 1 for _ in range(n): a, b = b, a + b return a这才恢复正常。其实不只是斐波那契法，任何一个算法实现如果涉及递推数列，都应该一上来就用迭代法，别用递归，避免后面调试时被性能问题干扰。
6.4 把初始化散点图放到调试验证阶段
调试过程中我发现，黄金分割法的初始两个点选哪一个方向，对新点计算的位置有影响。为了确认区间更新方向没写反，我写了一个可视化辅助函数：每次迭代后把当前区间 [a, b] 和两个内部点 x1、x2 以及函数曲线一起画出来，动态观察区间收缩的方向是否符合预期。这个方法在排查逻辑错误时效率极高。
6.5 关于代码组织的一点建议
大作业代码不要把所有算法堆在一个文件里。我使用了一个简单的面向对象设计，先定义一个抽象基类：
class LineSearchMethod: def minimize(self, f, a, b, tol_x=1e-6, tol_f=1e-10, max_iter=500): raise NotImplementedError然后黄金分割、斐波那契、牛顿、割线分别继承实现。这样在做对比实验时，可以用同一个收敛判据和同一个初始区间依次调用不同方法，保证对比的公平性。如果每个方法各自用不同的判据，实验结果就没有可比性了，严格来说这样的实验设计是有问题的。
回过头来看，一维搜索法这部分作业虽然只有短短几周，但它把数值优化的几个核心要素都串起来了：问题的建模（从高维线搜索到一维子问题）、算法设计（区间收缩 vs 导数求根）、收敛性分析（线性、超线性、二阶）、数值实验设计（测试函数选择、判据设置、结果可视化）。这些能力在后面学多维无约束优化、约束优化时会反复用到。如果你现在也在写这份作业，我最后一条建议是：不要只满足于"跑通代码"，多花点时间思考每个算法为什么这样设计、在什么条件下失效，这比把代码写得花哨更能学到东西。
