三次插值法：优化设计中的高效一维搜索与收敛加速指南-北京尧图网络

简介基于三次插值法求解函数极值的MATLAB代码包面向数值分析、优化设计方向的学生与工程师核心功能是通过三个已知数据点构造三次插值多项式逼近目标函数曲线再对插值多项式的导数求根进而定位候选极值点并通过二阶导数符号判断极大值或极小值。压缩包共包含4个m脚本文件整体大小仅1KB代码结构清晰主程序负责流程控制目标函数、导数计算与搜索区间设置分别由独立脚本完成便于替换目标函数后直接使用。已有355人浏览学习。虽然体积小巧但完整覆盖了从函数定义、导数计算、三次插值构造到极值点搜索与类型判别的标准流程适合数值方法与优化设计初学者对照学习也可作为MATLAB中函数逼近与寻优的参考模板迁移到实际工程参数优化场景中。1. 三次插值法在优化设计里的位置极值搜索的“最后一步”为什么值得单独抠在优化设计里求极值常常卡在一维搜索上方向已经定了步长怎么选才能让目标函数下降最多。三次插值法就是用两个点的函数值和导数值构造三次多项式通过求这个多项式的极值点来逼近原问题最优点的一种快速一维搜索方法。它解决的不是“能不能找到极值”而是“要多少次迭代才能找到极值”。对结构优化、参数标定这类需要高频线搜索的场景三次插值法能把迭代次数压到个位数比黄金分割和二次插值明显更省。这篇文章写给手里有梯度、目标函数光滑想把优化设计收敛速度再提一截的工程师。以下全部基于我实际调线搜索器的经验包括那些不得不向玄学低头的时刻。2. 从二次插值到三次插值极值搜索效率差在哪一个一维搜索方法快不快看它每轮用了多少信息以及这些信息怎么组合。黄金分割法每轮只用一个函数值然后按固定比例收缩区间二次插值法用三个函数值拟合抛物线三次插值法更进一步用两个点的函数值和导数值凑出四个条件去构造一条三次曲线。信息量越多逼近真实极值点的能力越强。但信息量多不代表没有麻烦三次多项式会出现多余的驻点、分母为零、新点越界等问题而这些恰好是工程里最容易翻车的环节。2.1 二次插值抛物线法为何不适合“最后一公里”二次插值法也叫抛物线法是优化设计教科书里常见的一维搜索手段。给定区间内三个点计算函数值用这三个点唯一确定一条抛物线再把抛物线顶点的横坐标当作新的步长估计。它最大的优势是实现简单连导数都不用求。但劣势也正在这里它只用函数值相当于把目标函数局部强行看成抛物线。一旦目标函数在这个区间不是近似二次型抛物线顶点的位置就会偏离真实极值点尤其是三点间距严重不对称时新点可能偏向区间的一端导致下一轮几乎不更新。实际问题里连续函数在极值点附近通常可以用二次函数近似但“附近”的范围有多宽二次插值法只有在区间足够窄时才表现出超线性收敛。而在优化设计刚开始时初始区间往往很宽函数形态可能包含拐点或噪声这时抛物线顶点连方向都容易给错。另一个更直接的短板是二次插值完全丢掉了导数信息。在优化设计里只要用的是带梯度的算法如 SQP、内点法或者伴随敏感性分析梯度本来就是现成的。放着 g0 和 g1 不用只拿函数值去拟合抛物线相当于你知道当前点是上坡还是下坡却偏要猜坡顶在哪。所以我个人的习惯是没有导数或者导数噪声大到不可信才退回二次插值或黄金分割只要能算梯度直接上三次插值。2.2 三次插值法的四个边界条件从 f, f 构造三次多项式三次插值法的数学基础很朴素用两个端点的函数值和导数值构造一个三次多项式 p(x)让 p 在这两个位置上的取值和斜率与原目标函数完全一致。假设左侧点 x0、右侧点 x1令 h x1 - x0并记 t x - x0则三次多项式可以写成p(t) A * t^3 B * t^2 C * t D四个边界条件是p(0) f0 f(x0) p(h) f1 f(x1) p(0) g0 g(x0) p(h) g1 g(x1)分别代入后可以解出系数。D 和 C 是直接得出来的D f0 C g0A 和 B 需要消元。由 p(h) 得到 Ah^3 Bh^2 Ch D f1再由 p(h) 得到 3Ah^2 2B*h C g1。把 D、C 代进去解这个二元一次方程组A [h * (g0 g1) - 2 * (f1 - f0)] / h^3 B [g1 - g0 - 3 * A * h^2] / (2 * h)到这里三次多项式的系数就完全确定了。但这只是第一步我们要找的是这个多项式的极小点而不是随便一个驻点。2.3 求导数方程的根x_new 的选择与收敛条件对 p(t) 求导得到 p(t) 3At^2 2Bt C这是个二次方程理论上在区间内可能有两个根。其中一个对应局部极大另一个对应局部极小我们要选的是那个让 p(t) 6At 2*B 0 的根。手工求两个根再判断区间很啰嗦实际工程实现里更常用一个化简后的公式直接给出新点估计z 3 * (f0 - f1) / h g0 g1 w sqrt(z^2 - g0 * g1) x_new x1 - h * (g1 w - z) / (g1 - g0 2 * w)这个公式在不少优化库的线搜索器里都能看到本质是把两次求根、二阶导符号判断、排除多余驻点这几件事一次做完。使用它的前提是区间端点满足 g0 0 g1也就是左端函数在下降、右端函数在上升这样区间内才有极小点。如果用户传入的区间刚好相反最简单的处理是交换 x0 和 x1因为很多时候只是左右端点顺序搞反了。算出 x_new 后要在新点处计算 g_new g(x_new)。如果 g_new 0说明极小点还在 x_new 右侧把 x_new 更新为新的左端点如果 g_new 0把 x_new 更新为新的右端点如果 g_new 接近 0就找到了极值点。这个更新逻辑和二分法类似但区间收缩不是等比的每次收缩量由三次多项式决定通常几步就能把区间压得很小。收敛条件建议设双重判据一是梯度绝对值小于 tol二是区间宽度小于 xtol。梯度判据在平坦函数上很挑因为很多函数在极值点附近梯度变化很慢绝对值一直停在 1e-8 以上位置判据能识别“已经动不了了”的情况直接把当前最优位置返回。后面第3章的代码里两条判据会同时放进去。这里还要提一个数值尺度的问题。计算 z 时包含 (f0 - f1)/h如果 f 的量级是 1e6 而导数的量级是 1e-3z 的舍入误差会彻底盖过梯度信息。我在实际优化过重量、温度这类不同量纲的目标时都先做变量归一化或者至少保证 f 和 g 在同一个数量级附近否则 w 和分母都会失真迭代几步就开始乱跳。3. 用 Python 跑通三次插值法一维搜索的完整代码与参数说明理论知识看一百遍不如在桌面写一个能跑的例子。这一章我会用一个单峰函数演示三次插值法的最小可用实现。目标函数选 f(x)exp(x)-3*x它的极小值点解析解是 x ln(3)能直接对照结果不存在“不知道正确答案”的问题。3.1 目标函数与梯度一个能验证到 ln3 的例子这个函数本身很简单但很适合用来验证线搜索器。它在 x0 处导数为 1-3-2下降在 x2 处导数为 7.389-34.389上升。让初始区间取 [0, 2]天然满足三次插值法要求的左负右正。如果换成更复杂的优化设计目标函数可能是仿真器返回的响应面但接口形式完全一样只要给我一个输入 x返回函数值和梯度。下面的代码只依赖 Python 标准库不用 numpy 也能跑通import math def f_obj(x): 目标函数exp(x) - 3*x极值点 x ln(3) return math.exp(x) - 3.0 * x def g_obj(x): 目标函数的一阶导数 return math.exp(x) - 3.0 def cubic_search(f, g, x0, x1, tol1e-8, xtol1e-10, max_iter50): 三次插值法一维搜索 f: 目标函数 g: 目标函数梯度 x0, x1: 区间端点要求极小点位于区间内 tol: 梯度收敛阈值 xtol: 区间宽度收敛阈值 max_iter: 最大迭代次数 f0 f(x0) f1 f(x1) g0 g(x0) g1 g(x1) # 自动整理区间方向保证左端导数为负右端导数为正 if g0 0 and g1 0: x0, x1 x1, x0 f0, f1 f1, f0 g0, g1 g1, g0 if not (g0 0 and g1 0): raise ValueError(区间两端需满足 f(x0)0f(x1)) # 保存历史最优值点防止极端情况下的偶发错误点污染最终结果 best_x (x0 x1) / 2.0 best_f min(f0, f1) for i in range(max_iter): h x1 - x0 if abs(h) xtol: break z 3.0 * (f0 - f1) / h g0 g1 disc z * z - g0 * g1 w math.sqrt(disc) if disc 0 else 0.0 denom g1 - g0 2.0 * w if abs(denom) 1e-15: # 分母退化三次多项式在该区间没有可靠极值点退化为二分 x_new (x0 x1) / 2.0 else: x_new x1 - h * (g1 w - z) / denom # 强制新点落在区间内部离端点 10% 的位置至少保留一点空间 margin 0.1 * h x_new min(max(x_new, x0 margin), x1 - margin) f_new f(x_new) g_new g(x_new) if f_new best_f: best_x x_new best_f f_new # 收缩区间看新点的导数符号 if g_new 0: x0, f0, g0 x_new, f_new, g_new else: x1, f1, g1 x_new, f_new, g_new # 双重收敛判断 if abs(g_new) tol or abs(x1 - x0) xtol: break if i % 10 0: print(f迭代 {i:2d} x{x_new:.10f} g{g_new:.3e} h{x1-x0:.3e}) return best_x x_opt cubic_search(f_obj, g_obj, 0.0, 2.0) print(f最优 x {x_opt:.12f}) print(fln(3) {math.log(3.0):.12f}) print(f最小 f {f_obj(x_opt):.12f})3.2 迭代流程区间收缩里每一步在做什么这段代码的关键逻辑在三个地方。首先是自动整理区间方向。真实需求里用户不会在意端点顺序只要传入一个包含极小点的区间就行所以我在函数开头加了交换逻辑让左端导数是负、右端导数是正。这个交换看起来简单很多粗糙实现却漏掉了结果就是直接报错或者迭代出负数步长。其次是分母退化处理。denom 如果接近零标准公式会给出一个无穷远点这时候三次多项式在整个区间上可能没有一个内点的驻点继续算下去没有任何意义。我选择退化为中点半分相当于动能降到最低但至少保存了区间信息。这个分支在简单函数上几乎不会触发但一旦遇到仿真黑盒几乎必然会发生。很多开源的线搜索器不做这个保护就是留着一个暗坑。最后是 best_x 的维护。由于我们强制把新点约束在区间内部理论上每轮都应该比上一轮好但数值误差和强制收缩可能让新点的函数值不如历史最优。在所有优化算法里保留历史最优都是一个不费成本的“后悔药”最后返回它能避免偶发的一次坏点毁掉整个线搜索。3.3 关键参数怎么给容差、最大迭代与初始区间参数设置不是玄学但要配合目标函数的尺度来调。tol 默认给 1e-8适合梯度量级在 1e-2 到 1e2 之间的普通问题。如果梯度本身就小比如目标函数乘以 1e-61e-8 就太严格了永远达不到这时按梯度量级的 1/1000 去给更实际。xtol 则看你对步长精度的要求物理参数通常不需要 1e-10 的精度给 1e-6 就好还能省两次迭代。max_iter50 在我的经验里绰绰有余因为三次插值法对接近二次形态的局部区间收敛非常快。但如果目标函数是带噪声的黑盒模拟器50 轮可能不够因为每一步的新点可能都不稳定区间收缩很慢。那时我通常把 max_iter 提到 100并配合函数值缓存来压制噪声影响这一点在第 5 章会详细讲。初始区间是另一个容易出错的地方。三次插值法要求区间两端满足左负右正这是保证区间内含极小点的前提。如果你只有两个点并不知道极小点是不是在中间可以先跑一小段黄金分割法把区间括出来再交给三次插值法。这个组合是我在仿真优化里最常用的姿势前面用黄金分割收粗后面用三次插值精收。4. 三次插值法的适用边界黑盒目标函数与梯度噪声下还能用吗三次插值法对函数形态和梯度质量的要求都不低。很多工程场景里目标函数是仿真器输出的一个数没有解析梯度甚至函数本身都带随机噪声。这一章专门说清楚什么条件下三次插值法值得用什么条件下应该果断换方法。4.1 没有解析梯度有限差分梯度与步长设置没有解析梯度时最常见的做法是中心差分。方向导数可以用下面的公式估算g_cal (f(x eps) - f(x - eps)) / (2 * eps)在一维线搜索里x 就是步长 αf(α) 是沿着搜索方向的目标函数值。eps 的选择直接决定梯度质量。过小会撞上浮点舍入误差尤其 f 量级很大时两个大数相减会直接损失有效数字过大则差分结果包含太多高阶分量和真实梯度明显偏离。我通常先按 eps max(1e-6, sqrt(eps_machine) * abs(x)) 起步再根据收敛行为放大到 1e-4 或 1e-3。对噪声显著的仿真黑盒反而要把 eps 调大取 1e-3 甚至 1e-2因为完全忽略噪声里的小尺度抖动反而更容易得到一个稳定的平均梯度。注意中心差分的代价是每算一个梯度要两次函数值。用三次插值法时每轮需要新点处的梯度等于每轮额外多两次函数评估。如果函数每次评估要跑一次有限元或 CFD这个成本就很可观。这时我会考虑用少量样本先拟合一个代理模型在代理模型上算梯度和三次插值而不是直接对黑盒差分。4.2 三次插值与黄金分割、二次插值的对比选型边界一张对比表能说清楚它们的差异方法所需信息单轮函数评估成本收敛特征最适合的场景黄金分割法函数值1 次线性收敛区间稳定缩小导数不可用、区间可包住极值、函数不光滑二次插值法三点函数值3 次初始每轮 1 次超线性但区间大时易振荡导数不可用、函数光滑但计算便宜三次插值法两点函数值和导数值每轮 f 和 g 各一次超线性迭代少梯度可得、函数光滑、计算成本高有限差分三次插值函数值近似梯度每轮 1 次 f 2 次差分评估取决于差分步长黑盒但函数噪声可控经验判断是这样如果函数计算一次要十秒以上而导数能伴随算出来三次插值法几乎是必选。SQP、内点法这类外层优化算法本身已经提供了梯度和搜索方向线搜索器再不用导数就太亏了。如果函数不光滑比如目标是带罚函数或绝对值项的结果黄金分割法更稳因为三次插值碰到导数跳变会直接误判极小值位置。4.3 在多维优化设计里做线搜索方向与步长的接力多维优化里的线搜索本质上是在当前设计点 x_k 处给一个方向 d_k把问题化为单变量函数 φ(α) f(x_k α * d_k) 的极小值问题。α 是步长。φ(α) 可由链式法则得到如果外层算法能提供梯度φ(α) ∇f(x_k α * d_k)^T d_k。这个式子直接把多维问题拉回一维因此前面所有公式里的 f、g 都换成 φ 和 φ。在实现时我习惯把线搜索器设计成只关心一维状态不关心你的目标函数原来是几维。这样线搜索可以复用。方向 d_k 的质量也会影响三次插值的表现如果 d_k 是负梯度目标函数在 α 很小时可能接近线性如果 d_k 是拟牛顿方向φ(α) 在 α1 附近很可能已经接近二次形态三次插值会很快收敛到好的步长。这也是为什么很多拟牛顿算法里一步三次插值线搜索就够用了。需要警惕的是每一步线搜索都要用到 ϕ 和 ϕ 的关系。如果外层优化算法给你的梯度有噪声差的线搜索器会把噪声放大到步长选择里让整个优化路线变得歪歪扭扭。这种情况下我会在线搜索之前先把梯度做一步平滑或者把三个连续步长的函数值做二次拟合后再交给三次插值。5. 三次插值法避坑指南5 个现场翻车案例与排查方法做过几年优化器的人都知道线搜索是充满暗坑的地方。这里整理 5 个最常见的翻车案例每一条都是我或者同事调坏过的真实问题。现象、原因、解决三步拆开写。5.1 极值点飞出区间根的选择逻辑没写对现象新点 x_new 算出来比区间端点还大或者跑到区间另一端导致区间不但没收缩反而被替换成一个更宽的范围。原因三次多项式的导数是二次方程两个根中只有一个是极小点。如果实现时直接用通用的二次求根公式然后随手取了一个根很容易取到极大点。另一个原因是端点的函数值差异太大标准公式里的 w 失去意义计算出的 x_new 自然越界。解决在代码里对新点做硬性保护让 x_new 必须落在 [x0 0.1h, x1 - 0.1h] 之间。这个技巧在我给的第 3 章代码里已经埋进去了。之前我有一版代码因为没做这个保护在目标函数是“应力约束罚函数”时三次插值给出的步长经常跨越整个变量边界把设计点推到铁皮模型之外后面所有计算全部崩掉。加了边界保护后即使多项式有问题区间也只会收缩不会爆炸。5.2 初始区间两端导数不满足“左负右正”现象程序报错说“区间两端需满足 f(x0)0f(x1)”或者明明程序没报错但迭代几轮后返回的 x 根本不是极小点。原因调用者随便给了两个点假设极小点在中间但实际上区间可能完全在极小点的左侧或右侧。比如目标函数单调两个端点导数为负区间内没有驻点三次插值法天然没法工作。解决做两件事。第一在代码里自动交换端点处理“顺序反了”的情况这能救回一半的场景。第二如果交换后仍不满足左负右正就先用一个扫描程序从粗网格里找极值的大致范围找到后再调用三次插值。另一个办法是用黄金分割法先跑 10 轮把区间括住再交棒给三次插值。我现在的流程里总是先跑一轮“括区间”函数再决定用哪种线搜索彻底告别“假设区间有效”的脆皮代码。5.3 有限差分梯度噪声大差分步长不是玄学现象迭代开始一两轮还挺正常后面 x_new 开始来回跳函数值并不持续下降甚至最后停在明显不是极值点的地方。原因有限差分步长选得太小或者目标函数本身有随机噪声。差分步长太小时两个相近函数值的小数部分完全被舍入误差污染算出的梯度符号都可能反。噪声则是另一个维度的问题如果仿真器每次调用因为线程调度或随机种子得到不同结果那么差分算出的梯度完全是来回收敛噪声三次插值法就会像喝醉一样乱走。解决对步长我用公式 eps max(1e-3, (abs(f))^(1/3)) 做保底再根据收敛日志下调。因为三次插值本意是找一个近似平滑的局部模型容许差分梯度有一点偏移不像牛顿法对 Hessian 那么敏感。对噪声先把目标函数在同一个点重复评估 3 到 5 次取平均或者对仿真器固定随机种子保证函数值是确定性的。如果噪声太大无法消除就不要用三次插值换回黄金分割法更稳黄金分割只比大小噪声只要不改变单调性就不会出大错。5.4 平坦区域迭代停滞终止条件要补一个位置判据现象程序跑满 max_iter 才退出但返回的 x 和初始值相差很小。画函数图发现整个区间像一条平线各处梯度绝对值都低于 1e-4但继续缩小梯度阈值仍然不动。原因三次插值法依赖导数符号变化来收缩区间。如果函数在极值点附近非常平坦梯度绝对值一直很小但符号可能因为数值误差来回变导致区间两端不断交换位置区间宽度也缩小到一个死区无法进一步收敛。解决终止条件必须同时看梯度和区间宽度。我在第 3 章代码里用的abs(g_new) tol or abs(x1-x0) xtol就是专门对这种情况的双保险。另外当检测到连续 5 轮区间宽度下降不到 10% 时直接接受当前 best_x比死等梯度容差强。平坦问题里的梯度容差纯粹是心理安慰位置容差才是真正让程序停止的判据。5.5 黑盒函数不“黑”但不确定缓存与重复计算问题现象同样的 x两次调用 f(x) 返回不同的函数值三次插值的多项式系数一会儿大一会儿小导致最终极值点完全随机。原因仿真优化里的“黑盒”根本不是黑盒而是不确定盒。有限元软件在不同核数下做并行结果有微小波动CFD 迭代未完全收敛就停了或者目标函数里有随机蒙特卡洛采样。梯度差分时不同的 x±eps 对应不同的随机种子算出来的梯度方向纯粹是伪随机。解决第一对所有评估点做永久缓存字典的键是浮点转成十六进制后的 bit 表示避免同一个 x 重复计算。第二如果条件允许固定随机种子让函数变成严格确定性。第三实在无法固定就在每个评估点调用多次求平均。我在优化一个注塑工艺参数时为了让三次插值法正常工作把每一步的目标函数固定到平均 5 次仿真结果最终收敛曲线才稳定。这个代价换来的是线搜索不再随机漂移整体反而节省了时间。6. 验证与进阶让三次插值法在你的优化流程里真正落地线搜索器改完以后不要直接塞进大优化工程先做小规模验证。我给自己定了一个固定流程用两条曲线验证再配合函数值缓存和预搜索确保它在真实业务里不出幺蛾子。6.1 三条收敛曲线梯度、步长、函数值一起看跑完一次线搜索我会把每次迭代的 x、g_new、f_new 打出来然后画三条曲线函数值下降路径、梯度绝对值随迭代变化、区间宽度变化。三者要一起看只看函数值会掩盖停滞只看梯度会忽略区间收缩异常。正确的形态是函数值单调下降或近乎单调下降梯度绝对值快速趋近零区间宽度指数级收缩。如果函数值下降但梯度绝对值上升说明多项式选错根了如果区间没收缩而梯度也没到容差说明陷入了平坦区。6.2 两个落地技巧函数值缓存与区间预搜索无论是不是黑盒我都给线搜索器配一个全局缓存。因为外层优化算法会在多个地方调用同一个点比如差分梯度时 f(xeps) 和 f(x-eps) 很有可能是之前某个 α 计算过了。缓存命中一次相当于省一次昂贵仿真。第二个技巧是区间预搜索。三次插值法需要一个可靠的初始区间最简单的做法是先按等比数列尝试步长 α0.1, 0.3, 1.0, 3.0直到发现目标函数从下降到上升取相邻两个点作为区间。这个过程会多花几次函数评估但能避免大量无效的迭代总体仍然划算。6.3 我踩过的最后一个坑保护点在区间内很多年前我第一次手搓三次插值法觉得标准公式高不可攀照着论文推导实现后直接用生产数据跑结果步长飞出边界把整个优化方向带偏。后来在一行代码里加了边界限制 x_new min(max(x_new, x00.1*x1-x0)), x1-0.1*x1-x0))问题立刻消失。从那时候起我所有优化器里的线搜索都保留“强制保护半径”并且保留历史最优点作为返回结果。这个习惯救过我太多次现在连给别人写插件都会不自觉地带上它。如果你只能从这篇文章带走一句话那就是三次插值法本身不玄真正玄的是你给它的区间和导数先把这两个稳住再谈收敛速度。希望帮到你。本文还有配套的精品资源点击获取

三次插值法：优化设计中的高效一维搜索与收敛加速指南

相关推荐

Ollama本地部署AI模型：从安装到优化的完整指南

DPO技术解析：大模型对齐优化的新范式

pstack-claude：用本地大模型解析Linux进程栈跟踪

更多资讯

风电并网仿真效率提升：等效建模与自适应算法解析

GPS广播星历计算卫星位置、速度与钟差：从RINEX到ECEF的完整Python实现

Redis集群模式下Lua脚本跨槽问题解决方案

t3code代码生成工具实战：从设计思路到落地避坑指南

8款高效论文写作工具全测评与组合使用指南

SG2地震波形解析：MATLAB与Python端序处理与物理量校准

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？