算法映射、收敛性与收敛速度

“目标值一直下降”并不自动等于“迭代点收敛到最优解”。收敛分析必须回答：点列是否有极限点，极限点是否满足停止条件，整个序列是否会在多个点之间游走。

算法映射

把一次迭代写成集合值映射

x^{(k+1)}\in M(x^{(k)}).

允许集合值，是因为线搜索、并列方向或子问题可能有多个解。固定点 $x\in M(x)$ 通常对应算法的停止状态。

若

x^{(k)}\to x,\qquad y^{(k)}\to y,\qquad y^{(k)}\in M(x^{(k)})

能推出 $y\in M(x)$ ，称 $M$ 在 $x$ 处闭。它保证“迭代关系在取极限后仍成立”，避免极限点从算法规则中漏掉。

连续单值映射当然闭，但集合值映射的闭性比连续性更合适。精确一维搜索的解映射常需借助目标连续性与步长有界性证明闭。

若存在连续函数 $Z$ ，使得在非解点

Z(y)<Z(x),\qquad \forall y\in M(x),

而在解集上不增加，那么 $Z$ 是下降函数。多数无约束算法直接取 $Z=f$ 。

结合迭代始终留在紧集、算法映射在非解点外闭，可用 Zangwill 型框架推出：任意聚点都属于解集，或算法有限步进入解集。

$f(x_k)$ 单调有下界，只能推出函数值收敛。不同点可能有相同函数值， $x_k$ 仍可能不收敛。还需紧性保证存在聚点，闭性与充分下降保证聚点满足驻点条件；若驻点唯一，才容易进一步得到整个点列收敛。

若 $x_k\to x^*$ ，令误差 $e_k=\lVert x_k-x^*\rVert$ ：

Newton 法在 Hessian 非奇异、初值足够近等条件下二次收敛；最速下降对良态强凸二次函数通常线性收敛；拟 Newton 常达到超线性。

不要用目标误差和点误差的比值混写。某些教材定义基于 $|f(x_k)-f^*|$ ，答题时要说明所用口径。

常见准则：

\lVert\nabla f(x_k)\rVert\le\varepsilon,

\frac{\lVert x_{k+1}-x_k\rVert}{1+\lVert x_k\rVert}\le\varepsilon,

或相对目标变化足够小。单独用步长小可能误把线搜索失败当作收敛，最好组合梯度或 KKT 残差。