12-核心概念-迭代算法

知识点：迭代算法

知识点概述

迭代算法是求解最优化问题的主要方法，它从一个初始点出发，按照特定规则生成一系列点，希望该序列能收敛到问题的最优解。

教材原文

…实际问题往往是没有办法显式求解的，因此常采用迭代算法。 迭代算法的基本思想是：从一个初始点 $x^0$ 出发，按照某种给定的规则进行迭代，得到一个序列 {x^k} 。如果迭代在有限步内终止，那么希望最后一个点就是优化问题的解。如果迭代点列是无穷集合，那么希望该序列的极限点（或者聚点）则为优化问题的解。

详细解释

• 基本思想: “从当前点出发，寻找一个更好的点”。这个过程不断重复，直到满足某个停止条件。
• 核心步骤:
  1. 初始化: 选择一个初始点 $x^0$。
  2. 迭代: 在第 $k$ 步，根据当前点 $x^k$ 和特定规则（如利用梯度信息）计算下一个点 $x^{k+1}$。
  3. 终止: 检查是否满足停止准则（如梯度足够小、函数值变化不大或达到最大迭代次数）。若满足则停止，否则返回步骤2。
• 停止准则:
  • 最优性条件: 梯度范数小于阈值（$\Vert \nabla f(x^k)\Vert \le \epsilon$）。
  • 函数值/点列变化: 相邻两次迭代的目标函数值或点的位置变化足够小。
  • 资源限制: 达到预设的最大迭代次数或计算时间。

学习要点

• 理解迭代是求解复杂优化问题的基本范式。
• 掌握迭代算法的“初始化-迭代-终止”三步流程。
• 了解常用的算法停止准则及其含义。

实践应用

• 梯度下降法: $x^{k+1}=x^k-{\alpha }_k\nabla f(x^k)$，沿着梯度反方向更新。
• 牛顿法: $x^{k+1}=x^k-[{\nabla }^{2}f(x^k){]}^{-1}\nabla f(x^k)$，利用二阶信息进行更新。

关联知识点

• 前置知识: 11-核心概念-全局和局部最优解
• 后续知识: 13-核心概念-算法收敛速度, 57-理论方法-梯度下降法, 60-理论方法-牛顿法
• 相关知识: 无