企业官网建设流程全解析

简介：最优化算法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_0=0.5$ 出发向右，采样 $0.6$ 发现函数值更大，说明初始方向朝上坡走，极小点其实在左侧。此时不能继续向右，而要把方向反转，这就是“进退法”中“退”的含义。方向正确后，下一次探测点在新的方向上继续推进，如果 $f(x_3)$ 依然低于当前最优点 $f(x_2)$，说明还没走出山谷，于是把区间整体平移并加大步长，这就是“进”和“加速”。

2.2 为什么说凸函数才谈得上全局最优

单峰区间内可能有多个极小点，对应的是多峰情形。对于严格凸函数，任意局部极小都是全局最小，且极小点唯一，因此只要进退法成功返回一个单峰区间，区间内一定包含全局最优点。若目标函数不是凸函数，例如 $f(x)=x^4-10x^2+0.5x$，有两个局部极小和一个全局极小，从不同初值出发，进退法可能返回完全不同的区间。这不是算法 bug，而是信息不足：三点比较只能反映局部趋势，没有任何机制判断更远处是否存在更低的谷。所以在工程上，如果确认不了凸性，我会用多次随机初值、分别跑进退法，留下所有区间里使端点函数值更低的候选，再做二次精选。这些候选区间并不会保证全局最优，但它们能告诉你目标函数潜在的“谷”有多少个。

2.3 步长与终止条件决定搜索结果质量

步长选择对结果的影响可以用下表概括：

终止条件的细节也常被忽略。最简单的判据是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 时，h0=1会迭代很多轮，设置h0=50更合理。

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()的执行顺序是：

1. 调用func_value()计算左点与初始右点的函数值；
2. 如果右点函数值更大，说明极小点在左侧，将步长取反并交换x1/x2与y1/y2；
3. 在max_iter次循环内调用cal_y3()，检查y3 >= y2是否成立；
4. 成立则返回排序后的区间，否则把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, x0=0.0, h0=0.1, max_iter=200): 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, x0=0.5, h0=0.1) interval = opt.run() print("单峰区间:", interval)

输出：

单峰区间: [-0.2, 0.4]

结果解读：函数最小值点在x=0，进退法返回的区间把 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, "-", label="f(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:", label="init") else: plt.plot([a, b, c], [sample(a), sample(b), sample(c)], "o:", label=f"step {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 参数变化对结果的影响

下面用同一函数做几组参数试验，结果以定性趋势呈现：

可以看到，h0增大时返回区间明显变宽，但迭代轮数变少；h0减小时区间变窄，但若h0小到接近机器精度，例如h0=1e-12，sample(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，从x0=0出发，算法初始点已经在两个谷之间的峰上，方向判断依赖于两个采样点的大小关系，可能陷入左侧谷也可能落入右侧谷。而从x0=4出发，由于初始步长 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, tol=1e-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 方法一样，黄金分割法也依赖一个真实包含极值的区间，所以进退法的单峰性验证不能省。

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