第7章：牛顿法、内点法与非光滑优化

牛顿方向

在 x 附近用二阶模型 $f(x)+g^Td+\tfrac12d^THd$。若 Hessian 正定，模型最小点满足 $Hd=-g$，得到牛顿方向。

对严格凸二次函数，精确线性求解和全步长可一步到最优点；对一般函数，只在解附近且满足 Hessian 等正则条件时才有局部二次收敛。远离解时通常需要线搜索、阻尼或信赖域。

实际算法解线性系统，不显式形成 $H^{-1}$。大型问题还要考虑 Hessian 存储、稀疏性与近似求解。

线搜索

Armijo 条件要求

$$f(x+\alpha d)\le f(x)+c\alpha\nabla f(x)^Td,\quad0<c<1.$$

若 d 是下降方向，可以从候选步长开始不断缩小，寻找足够下降。它控制函数值变化，不能把非凸问题变成凸问题，也不保证找到全局极小值。

对数障碍与中心路径

对 $f_i(x)<0$ 的严格内部，用

$$\min_x\ t f_0(x)-\sum_i\log(-f_i(x)),\quad Ax=b$$

近似原约束问题。增大 t 减少障碍相对影响，解沿中心路径接近边界最优点。适当条件和精确中心点下，可构造对偶变量并得到约为 $m/t$ 的对偶间隙界。

障碍函数只在严格可行内部有定义，起点不满足约束时需要可行性阶段或其他内点形式。它不是把违反约束的点简单罚一个大数。

次梯度方法

非光滑凸函数可采用 $x_{k+1}=\Pi_C(x_k-\alpha_k g_k)$，$g_k\in\partial f(x_k)$。次梯度给全局下界，却未必是局部下降方向，因此每一步函数值可能上升。

在有界次梯度和适当距离界、步长条件下，可得到最佳或平均迭代的 $O(1/\sqrt k)$ 量级界。不能直接套用光滑梯度法的下降引理或线性收敛结论。

练习

1. 对正定二次函数证明牛顿法一步到解。
2. 为什么对数障碍不能直接从不可行点计算？
3. 以 $|x|$ 为例说明固定步长次梯度法可能在零点附近往复。