AI 与工程数学 / 系统课时

根据问题结构选择优化算法

根据问题结构选择优化算法

面对一个新的优化问题,最重要的不是先挑“最快”的算法,而是先确认能否计算导数、目标是否凸、变量规模多大,以及 Hessian 是否可得。本节把这些结构信息整理成一条可执行的选择路径,并解释梯度法、牛顿法、拟牛顿法和无导数方法各自适合什么问题。

学习目标

  • 能根据可导性、凸性、维度和 Hessian 条件快速缩小算法范围
  • 能区分梯度法、牛顿法、拟牛顿法与无导数方法的主要成本和适用场景
  • 能理解“算法能运行”与“能够稳定找到全局最优”之间的区别

先看问题能提供什么信息

算法选择首先取决于你能从目标函数得到什么。设无约束问题为 min⁡xf(x)\min_x f(x)。如果可以稳定计算梯度 ∇f(x)\nabla f(x),就已经具备使用梯度类方法的基础;如果还能得到 Hessian ∇2f(x)\nabla^2 f(x),则可以进一步考虑牛顿法。

但“能算 Hessian”还不够。一个 nn 维问题的 Hessian 是 n×nn\times n 矩阵,存储、构造和求解线性方程组的代价都会随维度快速增加。因此,高维问题即使理论上存在 Hessian,也不一定值得显式使用。

凸性回答的是另一个问题:找到一个局部极小点后,能否把它当成全局最优点。 对凸目标,任何局部最优都是全局最优;非凸问题则可能存在多个局部极小点和鞍点,同一个算法从不同初值出发可能得到不同结果。

根据问题结构选择优化算法的决策路径

四类方法怎么取舍

梯度法每一步只依赖一阶导数,单步成本低、内存占用小,最适合变量很多的问题。代价是对条件数较差的问题可能收敛很慢,而且步长选择会直接影响稳定性。

牛顿法利用 Hessian 描述局部曲率,通过求解 ∇2f(xk)pk=−∇f(xk)\nabla^2 f(x_k)p_k=-\nabla f(x_k) 得到搜索方向。在靠近非退化极小点时通常收敛很快,但每一步需要构造或处理 Hessian,并求解线性方程组,因此更适合中低维且二阶信息可靠的问题。

拟牛顿法不直接计算真实 Hessian,而是根据连续迭代中的梯度变化近似曲率。BFGS 常用于中等规模问题;维度很大时,可以使用只保留少量历史信息的 L-BFGS。它通常比普通梯度法更省迭代次数,又避免了牛顿法完整 Hessian 的高成本。

无导数方法适用于梯度不存在、难以推导、噪声很大,或者目标函数只能通过仿真和外部程序得到的情况。它们不依赖解析梯度,但函数评估次数往往更多,因此在高维问题上通常不占优势。

把判断规则写成可执行检查

下面的程序把常见判断压缩成一个简单选择器。它不是通用优化库,而是把本节的决策原则变成可运行的检查逻辑。

python
def choose_method(differentiable: bool, dimension: int, hessian_available: bool) -> str:
    # 无法稳定获得梯度时,优先考虑不依赖导数的方法。
    if not differentiable:
        return "derivative-free"

    # Hessian 可得且规模不大时,二阶信息通常值得利用。
    if hessian_available and dimension <= 200:
        return "Newton"

    # 中等规模问题可用 BFGS,大规模问题更适合低内存的一阶或 L-BFGS 方法。
    if dimension <= 5000:
        return "BFGS"
    return "gradient or L-BFGS"


def main() -> None:
    cases = [
        (True, 50, True),
        (True, 1000, False),
        (True, 100000, False),
        (False, 8, False),
    ]

    for case in cases:
        print(case, "->", choose_method(*case))


if __name__ == "__main__":
    main()

预期输出:

text
(True, 50, True) -> Newton
(True, 1000, False) -> BFGS
(True, 100000, False) -> gradient or L-BFGS
(False, 8, False) -> derivative-free

这些阈值只是用于演示决策逻辑,并不是数学上的固定边界。实际工程中,变量虽然只有几百个,但如果 Hessian 构造一次就需要昂贵仿真,仍然可能更适合拟牛顿法;反过来,具有稀疏 Hessian 的大规模问题也可能高效使用专门的二阶方法。

选择之后还要检查什么

算法确定后,还要检查目标函数的缩放、初始点和停止条件。不同变量量级相差几个数量级时,梯度方向和 Hessian 条件数可能明显恶化,先做尺度归一化往往比盲目更换算法有效。

对非凸问题,不要把一次收敛结果自动当成全局最优。可以使用多个初始点重复求解,并比较最终目标值;若算法在不同初值下频繁落到不同解,应把它视为问题结构的一部分,而不是简单归因于“算法失效”。

实际选择时可以遵循一个稳定顺序:先判断导数是否可靠,再看维度与二阶信息成本,最后用凸性判断结果的可信程度。这样做比根据算法名气或单次基准速度选方法更可靠。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

根据问题结构选择优化算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通