简介最优化算法python实现系列首篇围绕进退法展开面向需要以Python实现一维凸优化问题的算法学习者和开发者也适合作为最优化课程的补充实验材料。PDF文档系统梳理了进退法的用途与适用条件说明它通过搜索函数值呈“高—低—高”的三点来获取包含极值的单峰区间并指出在非凸函数下通常只能得到局部最优帮助读者建立对优化算法的正确认知。文中给出完整的Python类实现涵盖初始化、函数值计算、步长比较与区间迭代等模块配合二次函数目标示例演示运行结果读者可直接复现或迁移到其他一维搜索场景。压缩包共1个文件类型为PDF大小仅55KB轻量便携适合快速入门或作为课程实验参考。已有2942人浏览学习适合数值优化、最优化方法相关方向的初学者收藏使用。1. 进退法为什么一维搜索要先框住极值假设你正在调试一个无约束优化任务目标函数在某个区间上的形状还不清楚直接把全域交给scipy.optimize.minimize_scalar并不安全因为大多数方法都依赖一个有界区间作为初值。进退法就是用来做这件事的它从任意一个点出发以固定步长探测如果发现方向反了就转头方向对了就加倍步长前进直到拿到一个“高-低-高”的三点组合从而返回一个包含极小点的单峰区间。比如目标函数是lambda x: x**2初始点取 0.5、初始步长取 0.1一次run()就能得到区间[-0.2, 0.4]。这个区间可以直接作为黄金分割法、抛物线插值或 scipy 有界优化的搜索范围。它不追求精确解而是解决“极值到底在哪个区间里”这个前置问题。适合正在学最优化算法、想手写一维搜索工具或者需要理解优化器内部预搜索过程的读者。2. 单峰区间与凸函数进退法的适用边界和步长选择2.1 “高-低-高”到底在描述什么一维单峰函数像一座山谷两侧函数值高于谷底且谷底唯一。进退法的目标是找到三个点 $x_1 x_2 x_3$使函数值满足 $f(x_1) f(x_2)$ 且 $f(x_3) f(x_2)$。满足这个条件的区间 $[x_1,x_3]$ 就是单峰区间。注意算法本身不需要求导只需要在少数几个采样点上计算函数值因此对于不可导但可采样的黑盒函数很友好。每次迭代只增加一个函数值计算内存占用是常数级这一点比梯度类方法更轻量。实际操作中第一次得到的三个点往往不满足这个条件。比如从 $x_00.5$ 出发向右采样 $0.6$ 发现函数值更大说明初始方向朝上坡走极小点其实在左侧。此时不能继续向右而要把方向反转这就是“进退法”中“退”的含义。方向正确后下一次探测点在新的方向上继续推进如果 $f(x_3)$ 依然低于当前最优点 $f(x_2)$说明还没走出山谷于是把区间整体平移并加大步长这就是“进”和“加速”。2.2 为什么说凸函数才谈得上全局最优单峰区间内可能有多个极小点对应的是多峰情形。对于严格凸函数任意局部极小都是全局最小且极小点唯一因此只要进退法成功返回一个单峰区间区间内一定包含全局最优点。若目标函数不是凸函数例如 $f(x)x^4-10x^20.5x$有两个局部极小和一个全局极小从不同初值出发进退法可能返回完全不同的区间。这不是算法 bug而是信息不足三点比较只能反映局部趋势没有任何机制判断更远处是否存在更低的谷。所以在工程上如果确认不了凸性我会用多次随机初值、分别跑进退法留下所有区间里使端点函数值更低的候选再做二次精选。这些候选区间并不会保证全局最优但它们能告诉你目标函数潜在的“谷”有多少个。2.3 步长与终止条件决定搜索结果质量步长选择对结果的影响可以用下表概括h0 与极值尺度关系迭代表现返回区间特点h0 过小每轮函数值变化很小可能触发浮点误差区间极窄后续优化器容易提前收敛h0 适当3~6 轮内出现高-低-高区间宽度与极值附近尺度相称h0 过大一步跨过极值落在另一侧山腰区间可能覆盖多个波峰单峰假设失效终止条件的细节也常被忽略。最简单的判据是if y3 y2: break但很多教材写的是y3 y2。二者差异在于当极值正好落在 $x_2$ 与 $x_3$ 中点时$y_3$ 可能与 $y_2$ 相等。如果只判断相等时算法会继续翻倍步长把区间越撑越大最终仍会返回一个过宽的区间改用则在相等时立刻停止因为这已经满足“高-低-高”的定义。下面给出我常用的循环骨架while True: 计算 x3 x2 h, y3 f(x3) if y3 y2: break x1 x2; y1 y2 x2 x3; y2 y3 h h * 2这里代替是针对对称函数和平台区的重要修改。同时在类实现中要加一个max_iter保护否则遇到单调函数或数值平台时会无限循环。初值方面我一般把h0设为变量典型尺度的 1/10 到 1/5变量范围在 0~1000 时h01会迭代很多轮设置h050更合理。3. 用 Python 实现进退法类结构、状态维护与主循环3.1 为什么选择用类封装而不是单函数进退法涉及三个探测点、三个函数值、一个步长和搜索轨迹如果全用局部变量在单个函数里反复赋值代码会变得难以追踪。用类封装的好处是每个方法只做一件事run()负责主循环func_value()负责采样cal_y3()负责推进get_interval()负责输出。这样在调试时可以逐方法调用查看某一时刻的x1/x2/x3也方便把搜索轨迹保存下来用于绘图。构造函数接受四个参数目标函数obj_func、初始点x0、初始步长h0和最大迭代次数max_iter。实例属性x1、x2、x3分别表示当前区间的左点、中间低点和下一个探测点y1、y2、y3是对应的函数值。h是动态步长初始等于h0方向修正后可能为负。trace列表记录每轮三个点的位置供第 4 章的可视化使用。3.2 类方法与搜索流程run()的执行顺序是调用func_value()计算左点与初始右点的函数值如果右点函数值更大说明极小点在左侧将步长取反并交换x1/x2与y1/y2在max_iter次循环内调用cal_y3()检查y3 y2是否成立成立则返回排序后的区间否则把x2提升为新的x1、把x3提升为新的x2步长翻倍继续探测。这样设计保证了每一步之后x2始终是当前三个点中函数值最低的点x1是它的左邻居或上一步的低点x3是新的疑似边界。交换操作的目的是让初始方向修正后x2能保留“当前最优点”这个语义简化后续逻辑。3.3 完整实现下面给出可直接运行的代码类名沿用了原博客中的advance_retreat_method方便对照class advance_retreat_method: 进退法搜索一维目标函数的单峰区间 参数 ---------- obj_func : callable 目标函数接受 float返回 float x0 : float, default 0 初始点 h0 : float, default 0.1 初始步长建议取变量典型尺度的 1/10 max_iter : int, default 200 最大迭代次数防止无界函数死循环 def __init__(self, obj_func, x00.0, h00.1, max_iter200): self.obj_func obj_func self.x0 x0 self.h0 h0 self.max_iter max_iter self.x1 x0 self.h h0 self.x2 x0 h0 self.x3 None self.y1 None self.y2 None self.y3 None # 搜索轨迹每项为 (x1, x2, x3) self.trace [] def func_value(self): 计算 x1 和 x2 的函数值 self.y1 self.obj_func(self.x1) self.y2 self.obj_func(self.x2) def _swap(self): 交换 x1/x2 与 y1/y2保证 x2 是当前最优点 self.x1, self.x2 self.x2, self.x1 self.y1, self.y2 self.y2, self.y1 def cal_y3(self): 沿当前方向计算探测点 x3 与函数值 y3 self.x3 self.x2 self.h self.y3 self.obj_func(self.x3) def get_interval(self): 返回排序后的单峰区间 [left, right] left, right sorted([self.x1, self.x3]) return [left, right] def run(self): self.func_value() # 若右点函数值更大说明极值在左侧反向搜索 if self.y2 self.y1: self.h -self.h self._swap() # 记录初始两个点 self.trace.append((self.x1, self.x2, None)) for _ in range(self.max_iter): self.cal_y3() self.trace.append((self.x1, self.x2, self.x3)) # 出现“高-低-高”停止 if self.y3 self.y2: break # 否则用 x2、x3 替换 x1、x2步长加倍 self.x1, self.y1 self.x2, self.y2 self.x2, self.y2 self.x3, self.y3 self.h self.h * 2 else: raise ValueError( 达到 max_iter 仍未找到单峰区间检查函数是否有界或减小 h0 ) return self.get_interval()这段代码中有几个细节值得展开。首先是_swap()之后x2变成了原来函数值较小的点x1变成了原来函数值较大的点这时h已被取反下一步的x3会落在x2的反方向也就是朝向真正的极值区。其次是trace里用None表示初始两个点因为还没有x3绘图时可以用这个标记区分初始状态和迭代状态。循环中的else子句是 Python 的for...else语法正常break退出时不会触发如果迭代满max_iter还没有停止说明函数在采样区间内单调下降或无限振荡此时抛出异常比返回一个错误区间更有价值。参数调整上h0的作用最直观。h0越小首次探测范围越小返回区间越窄但对浮点误差越敏感max_iter不需要调很大因为步长按 2 的幂增长20 次就能把区间扩大到初始范围的 100 万倍。真正需要检查的是x0是否落在平坦区域如果y1和y2完全相等比如常函数方向判断会失效类会在max_iter后报错。这种情况我会在调用前对obj_func做一次差分检查或者把h0放大到能跳出平台区的程度。4. 实战用 f(x)x^2 验证单峰区间并观察搜索轨迹4.1 最小可运行示例把上面类保存到advance_retreat.py然后运行sample lambda x: x**2 opt advance_retreat_method(sample, x00.5, h00.1) interval opt.run() print(单峰区间:, interval)输出单峰区间: [-0.2, 0.4]结果解读函数最小值点在x0进退法返回的区间把 0 包住了。左端点 -0.2 和右端点 0.4 并不对称因为迭代过程中步长是按 2 的幂衰减的最后一次x3从 0.2 跳到 -0.2恰好让三点满足高-低-高。这个区间精度不高但它是有界的、可用的。4.2 画出来看看搜索过程把trace里的点画到函数曲线上能直观看到三点如何移动。绘图代码import numpy as np import matplotlib.pyplot as plt xs np.linspace(-0.7, 0.9, 300) ys sample(xs) plt.plot(xs, ys, -, labelf(x)x^2) for i, (a, b, c) in enumerate(opt.trace): if c is None: plt.plot([a, b], [sample(a), sample(b)], o:, labelinit) else: plt.plot([a, b, c], [sample(a), sample(b), sample(c)], o:, labelfstep {i}) plt.xlabel(x) plt.ylabel(f(x)) plt.legend() plt.show()运行后可以看到初始两个点在 0.5 和 0.6随后方向转向左侧第二次迭代三个点为 0.6/0.5/0.4第三次为 0.5/0.4/0.2最后一次为 0.4/0.2/-0.2。由于y3在 -0.2 处等于 0.04正好与y2相等触发判停区间返回[-0.2, 0.4]。如果使用教材里的这一步不会停止算法会继续向右到 -1.0 附近区间变成[-1.0, 0.2]明显更宽。所以这个可视化案例也是验证终止条件差异的好素材。4.3 参数变化对结果的影响下面用同一函数做几组参数试验结果以定性趋势呈现初始点 x0初始步长 h0迭代轮数区间宽度趋势0.50.01较多很窄接近 0.020.50.13~4约 0.60.51.01~2超过 2.01.00.14~5约 0.8可以看到h0增大时返回区间明显变宽但迭代轮数变少h0减小时区间变窄但若h0小到接近机器精度例如h01e-12sample(0.5 1e-12)在普通 float 下几乎等于sample(0.5)方向判断会随机失效。工程上我会先估计极值附近的自然尺度再取它的 1/10 作为h0。如果完全没有先验信息就用np.ptp(xs) / 10这种动态估算。4.4 区间出来后还要做什么单峰区间的价值在于给精细搜索一个边界。拿区间直接交给scipy.optimize.minimize_scalar的bounded方法可以在几十次迭代内把极值点误差压到 1e-6 以下。如果不想引第三方库黄金分割法只需要几十行递归实现。无论用哪种区间越窄后续方法收敛越快因此把h0设置合适比事后对区间做二分更有意义。5. 从调试到扩展非凸函数、平台区与黄金分割5.1 非凸函数会产生什么现象把目标函数换成lambda x: x**4 - 10*x**2 0.5*x从x00出发算法初始点已经在两个谷之间的峰上方向判断依赖于两个采样点的大小关系可能陷入左侧谷也可能落入右侧谷。而从x04出发由于初始步长 0.1 无法感知远方的深谷区间只能圈住右侧局部极小。这说明进退法在非凸问题上只能提供“当前位置附近的单峰区间”不能承诺全局最优。如果业务场景确实存在多谷合理的做法是把初始点撒到变量范围的网格上每个小区间独立跑一次进退法再根据目标函数值挑选最优候选区间。5.2 平台区与浮点平坦区当y1和y2差值低于 float 判别阈值时方向判断不可靠。一个简单处理是在func_value()中增加校验if abs(self.y2 - self.y1) 1e-12: self.h self.h * 10 self.x2 self.x1 self.h这种方案会把探测范围扩大一个数量级使平台区被忽略。代价是可能跳过一个窄谷因此适合亮平坦区域。更稳健的做法是同时记录二阶差分但一般场景下放大步长已够用。若平台区出现在极值附近例如函数在最小值附近非常平缓则应该反过来缩小h0换取更好的数值分辨率。5.3 用黄金分割法紧跟着压缩区间拿到区间[a, b]后可以用黄金分割法继续压缩phi (5 ** 0.5 - 1) / 2 # 0.618 def golden_section(f, a, b, tol1e-6): c b - phi * (b - a) d a phi * (b - a) while abs(b - a) tol: if f(c) f(d): b d else: a c c b - phi * (b - a) d a phi * (b - a) return (a b) / 2 print(golden_section(sample, interval[0], interval[1]))这里的phi是黄金分割比每次迭代只计算一次新的函数值约 30 轮就能把宽度从 0.6 压缩到 1e-6。如果目标函数有噪音可以用抛物线插值替代如果不可导黄金分割法不需要导数仍然适用。注意和 scipy 的 bounded 方法一样黄金分割法也依赖一个真实包含极值的区间所以进退法的单峰性验证不能省。本文还有配套的精品资源点击获取