梯度法、Newton 法和约束候选怎样可靠核验？¶

先备知识¶

掌握梯度、Hessian、下降方向、乘子必要条件与数值停止语义。

学习目标¶

1. 运行并解释梯度下降和 Newton 优化；2. 读取失败原因；3. 只核验候选条件而不宣称最优。

牵引问题¶

计算程序怎样既给出可复查结果，又不把“小梯度”或乘子残差小误报为全局最优？

探索与猜想¶

负梯度给局部最速下降方向，回溯线搜索控制实际下降。Newton 步解 \(H_ks_k=-\nabla f_k\)，但 Hessian 奇异或不定时未必给下降方向。

概念与理论¶

七步计算单元¶

1. 问题来源： 明确目标、定义域、尺度、约束和初值。
2. 数学转化： 推导梯度、Hessian、约束 Jacobian 与乘子残差。
3. 算法思想： 梯度法配回溯；Newton 法解线性系统并检查正定和下降性。
4. 误差与适用条件： 停止阈值不是最优值误差证书；约束候选还需正则性和分类。
5. 伪代码： 计算方向，拒绝病态状态，接受有限下降点，记录轨迹与原因。
6. Python： 复用 mathbook_examples.optimization 中的三个公开函数。
7. 结果解释： 报告点、目标、梯度或残差、步长、Hessian 状态、原因和轨迹。

状态边界¶

实现显式报告 gradient、step、non_descent_direction、singular_hessian、 indefinite_hessian、nonfinite_value 与 max_iterations。其中前两者只是停止信号。 等式候选核验返回驻点残差与约束残差，不声明候选点最优。

from mathbook_examples.optimization import gradient_descent, newton_optimize

f = lambda p: 0.5 * (p[0] ** 2 + 4 * p[1] ** 2)
g = lambda p: (p[0], 4 * p[1])
H = lambda p: ((1.0, 0.0), (0.0, 4.0))
print(gradient_descent(f, g, (2.0, -1.0)).reason)
print(newton_optimize(f, g, H, (2.0, -1.0)).reason)

本实现不返回 optimal 状态；converged 只表示文档化停止信号触发。

例题与迁移¶

例 1：正定二次函数¶

Newton 法一步到驻点，梯度法通过回溯逐步下降；全局最优性来自正定二次理论，不来自状态字符串。

例 2：约束候选¶

对 \(x^2+y^2\) 且 \(x+y=1\)，核验 \((1/2,1/2)\)、\(\lambda=-1\) 时驻点和约束残差均为零； 这只验证必要方程，还需理论分类。

即时检验与回望¶

即时检验 1¶

Hessian 不定时为何拒绝纯 Newton 优化步？

即时检验 2¶

约束与驻点残差为零是否自动证明全局最优？

常见误区与后续¶

• 梯度小可能来自尺度或平坦区。
• max_iterations 只是预算耗尽。
• 代码不覆盖不等式约束，也不建立一般 KKT 理论。

习题与答案¶

习题 1¶

负梯度为何是下降方向？

习题 2¶

回溯线搜索检查什么？

习题 3¶

Newton 步为何解线性系统？

习题 4¶

singular_hessian 表示什么？

习题 5¶

indefinite_hessian 表示什么？

习题 6¶

non_descent_direction 表示什么？

习题 7¶

gradient 停止是否是距离最优点证书？

习题 8¶

为什么保留轨迹？

习题 9¶

约束候选核验的两个残差是什么？

习题 10¶

残差小为何仍需正则性检查？

习题 11¶

Newton 一步到驻点能否证明全局最优？

习题 12¶

非有限候选为何不加入轨迹？

习题 13¶

本计算单元对“收敛”的定义是什么？

延伸：尺度¶

变量重新缩放会怎样影响停止阈值？