无约束非线性规划：线搜索方法

这是什么

一篇标准的数值优化讲义：先定义问题与「全局极小/局部极小」的落差，再给判断局部极小的定理与泰勒展开工具，然后拆成「方向」与「步长」两大件逐一展开（梯度下降 vs 牛顿方向；精确线搜索 vs Wolfe 条件 vs 回溯算法），最后拼出完整线搜索算法并给终止条件。每个方法都配二次函数 Q 与 Rosenbrock 函数的迭代数字对比。

核心要点

问题与「能解到什么程度」

• 无约束问题：min f(x)，x ∈ Rⁿ，f 连续（实践要求 C¹ 或 C²）。有约束版：min f(x) 满足 gᵢ(x) ≤ bᵢ。
• 全局极小点（对一切 x，f(x*) ≤ f(x)）很难找；局部极小点（邻域内最小）也可能找不到；实际能做的是逼近到「足够接近」——这是本文算法达成什么的目标。

定义与工具

• C^m 函数：m 阶及以下偏导存在且连续。梯度 ∇f：各方向偏导组成的向量（= 高维的导数，指向上坡最快的方向）。海塞矩阵 ∇²f：所有二阶偏导组成的矩阵。
• 正定矩阵：对称且对任意非零 x 有 xᵀAx>0；半正定：≥0。
• 定理 1：f 是 C²。若 ∇f(x*)=0 且 ∇²f(x*) 半正定 → 局部极小点；∇²f(x*) 正定 → 强局部极小点。但——求 ∇f 的零点本身就是千古难题，定理不能直接当算法用。
• 定理 2（泰勒）：C¹：f(x+p)=f(x)+∇f(x+tp)ᵀp（某 t∈(0,1)）。C² 版加 ½pᵀ∇²f(x+tp)p。由此得到局部线性估值 f(x+p) ≈ f(x)+∇f(x)ᵀp（一维是切线/高维是超切面，p 足够小时误差小），以及含二阶项的更准估值。

线搜索框架与方向选择

• 迭代框架：若方向 p 满足 ∇f(x)ᵀp < 0（p 与梯度夹角 >90°，即下降方向），存在小 α>0 使 f(x+αp) < f(x)。于是 x_{k+1} = x_k + α_k·p_k 反复迭代。
• 梯度下降 / 最大下降：p = −∇f(x)。保证全局收敛（任意起点都会到局部极小）、只要 f 连续可导；缺点是收敛慢——路径与水平集垂直、常走出锯齿形。数字：二次函数 Q(x)=3x₁²+2x₁x₂+3x₂² 从三个起点 11–14 次迭代达误差 <0.00001；Rosenbrock 函数 R(x)=(1−x₁)²+100(x₂−x₁²)²（极小在 (1,1)，谷又弯又窄）从 (−0.5,1) 起用了 5491 次——梯度指向谷中央而不是下游，反复折返。
• 牛顿方向：p = −∇²f(x_k)⁻¹∇f(x_k)（最小化二次泰勒模型 m_k(p) 得来）。收敛更快——梯度下降误差 O(‖p‖²)、牛顿 O(‖p‖³)，方向「更有远见」。代价：需要 C²、海塞矩阵正定（通常要求起点离极小够近）；即使正定，p 也未必是下降方向；算海塞矩阵再求逆计算量大。实用组合：海塞正定时用牛顿、否则退回梯度下降（对称矩阵正定 ⟺ 特征值全 >0，Numpy 可判）。数字：二次函数一步到位（二次函数的二阶泰勒展开恰等于函数本身）；Rosenbrock 31 步（对 5491 步）。

步长选择

• 权衡：步太长跨过极小点，太短降不了多少。
• 精确（最大下降）步长：在射线 {x_k+αp_k} 上找 f 最小的 α。极值出现在梯度与 p 垂直处（∇f(x_k+αp_k)ᵀp_k=0，用高维链式法则）。零点不好求 → 找「足够好」就行。
• Wolfe 条件（两个不等式，参数 c₁∈(0,1)、c₂∈(c₁,1)）：
  • 足量衰减条件（=Armijo）：f(x_k+αp_k) ≤ f(x_k) + c₁·α·∇f(x_k)ᵀp_k——下降量与步长×方向导数成比例。c₁ 常用 10⁻⁴。
  • 曲率条件：∇f(x+αp_k)ᵀp_k ≥ c₂·∇f(x_k)ᵀp_k——落脚点要「足够平缓」（梯度接近 0 或反向），因为局部极值处梯度必为 0。c₂ 随方向算法调。
  • 同时满足两式的步长区间存在且不难找，但比较麻烦。
• 回溯算法（backtracking）：丢掉曲率条件，只保足量下降。α 从 ᾱ 起，while 不满足足量衰减就 α ← ρ·α（0<ρ<1）。输出 α 保证有足够下降；且不会太短——因为 α_k/ρ 已被证明是「过长」的步长。ᾱ=1 常用于梯度/牛顿方向。ρ 的权衡：接近 0 → 循环少但整体收敛慢；接近 1 → 相反；方向越精确 ρ 可设越大。对牛顿方向很好用；对拟牛顿/共轭梯度不太好（未来话题）。

完整算法与终止

• 拼装：每步「方向算法(f,x_k)」给 p_k →「步长算法」给 α_k → x_{k+1}=x_k+α_k p_k。
• 终止条件两个：迭代次数 K（算力标准）或函数误差 |f(x_k)−f(x_{k−1})| < ε（精度标准）；f(x*) 本身不可得，所以用相邻两次的差代替。两者可同时用。
• 文末给出「牛顿方向 + 回溯步长」的完整伪代码（海塞正定 → 牛顿方向，否则梯度方向），Python 实现放在研究模块（raw 未含代码本体）。

机制 / 论证

• 为什么只谈局部极小：全局极小对一般函数不可求；数值优化的现实目标是「逼近某个局部极小」，再靠多起点/启发式碰全局。原文直说「找出局部极小点我们可能也找不到，能做到的是足够接近」。
• 为什么方向与步长是两件事：方向决定往哪个山坡下走，步长决定走多远；两者独立出问题、可分别选算法再拼装——这是线搜索的模块化思想。
• 为什么梯度下降慢而牛顿快：梯度只用了函数的一阶信息（眼前最陡），牛顿用了二阶曲率信息（海塞矩阵含谷的形状），所以牛顿「看得远」、每步更准。Rosenbrock 的 5491 vs 31 步就是这个差别的量级证据——二阶导数里藏着谷的形状信息。
• 为什么回溯不会把步长折到零：p_k 是下降方向且 c₁<1，所以只要 α 足够小必满足足量下降；回溯折到第一个满足的 α，而 α/ρ 不满足 → α 不会比「该够用」的尺度短太多。
• 资产配置的落点（结语）：无约束 NLP 应用广，但更多应用在有约束问题——资产配置约束 Σwᵢ=1、wᵢ≥0、wᵢ≤1/3 会让问题更有趣也更难，需要专门算法（接第 35 篇与组合优化）。

可操作

• 最小化一个可微函数的标准流程：给定 f 与起点 x₀ → 每步算 ∇f（与 ∇²f）→ 海塞正定用 p=−H⁻¹∇f、否则 p=−∇f → 回溯定步长（ᾱ=1、c₁≈10⁻⁴、ρ∈(0,1) 如 0.5）→ 迭代到次数 K 或 |f(x_k)−f(x_{k−1})|<ε。
• 判断收敛的一个实用检查：对称矩阵是否正定用特征值（Numpy eigvals）——特征值全 >0 才走牛顿方向。
• 起步建议：先梯度下降（实现最简单、保证收敛）验证逻辑，再上牛顿/拟牛顿提速；复杂方向（拟牛顿、共轭梯度）文中预告未展开。
• 预判难度：函数有窄弯谷（如 Rosenbrock 型）时纯梯度下降会数千步——尽早换带二阶信息的方法。
• 量化用途链：本篇是第 35 篇（拉格朗日把约束问题转无约束后用它解）与第 23 篇（MPT 解析解之外、无解析解时）的数值底座；反向传播训练神经网络也属此类（量化课堂 ML 篇后续展开）。

术语

• 无约束 / 有约束优化：决策变量自由取值 / 受 gᵢ(x)≤bᵢ 限制。
• 全局极小点 / 局部极小点 / 强局部极小点：全局最小 / 邻域内最小（允许相等）/ 邻域内严格更小。
• 梯度 ∇f / 海塞矩阵 ∇²f：一阶偏导向量 / 二阶偏导矩阵。
• 线搜索：选下降方向 + 定步长、迭代逼近极小点的方法族。
• 梯度下降（最大下降）：p=−∇f 的方向选择。
• 牛顿方向：p=−(∇²f)⁻¹∇f，基于二阶泰勒模型。
• Wolfe 条件：足量衰减（Armijo）+ 曲率两个不等式，用来筛「够好」的步长。
• 回溯算法：从大步长开始按 ρ 收缩直到足量下降的步长算法。

不确定 / 待验证

• 收敛性证明（梯度下降为什么保证收敛、牛顿的局部收敛阶）文中只给结论不证明；「O(‖p‖²)/O(‖p‖³) 误差」是断言级别。
• Rosenbrock 的 5491 步、二次函数 11–14 步、牛顿 31 步是文中给的实验数字，误差阈值 0.00001 照录；Python 代码在研究模块，raw 未含实现，无法复算 [需要验证]。
• 混合策略「海塞正定时用牛顿否则梯度下降」的正确性与收敛保证文中只作建议，没有证明。
• 参数 c₁、c₂、ρ、ᾱ 的选值（10⁻⁴、0<ρ<1、ᾱ=1）是经验惯例，无理论最优。
• 拟牛顿、共轭梯度、约束问题的专用算法文中只预告，未展开（属于量化课堂后续/外部教材内容）。
• 导语提到反向传播训练神经网络，但本篇正文只讲一般无约束优化，未做神经网络的具体对接——留待 ML 批次。

相关

• 线搜索（无约束优化的迭代下降法） — 线搜索共享概念页（本篇方向/步长/终止的提炼）
• 数学规划简介 — 数学规划总纲与分类（本篇前置，postId=3293）
• 拉格朗日乘子 — 约束转无约束后调用本篇方法数值求解（第 35 篇）
• 数学规划（优化问题与分类） — 数学规划共享概念页（本篇是它的「无约束求解」件）
• MPT 模型的解析解（上） — 用到正定矩阵与二次型的推导（第 23 篇）
• 聚宽量化课堂（低频量化策略 43 篇） — 量化课堂 43 篇总览