多元函数无约束优化问题

$$ \min \{f(x)|x\in \mathbb R^n\} $$

线搜索：走向量，取最优步长

线搜索

搜索方向：

$$ \boldsymbol x_{k+1}=\boldsymbol x_k+\alpha _k\boldsymbol p_k. $$

• 下降性质descent property $p_k^T\nabla f(x_k)<0$ - p_k
  • 梯度方向
  • 共轭梯度方向
  • 牛顿方向 牛顿方法
  • 拟牛顿方向 拟牛顿方法
• 步长 $\alpha_k$

  • 精确步长 exact stepsize ：$\alpha_k=\argmin_{\alpha\ge0}f(x_k+\alpha p_k) = \phi(\alpha)$

    • 仅 \phi (\alpha)是二次函数有精确步长表达式。

  • 非精确步长：

    • 使用一维优化问题 方法

    <aside>

    merit_fn 非精确步长需要额外的下降判据

    </aside>

    • Armijo：Armijo规则→回溯线搜索 (backtracking line search 试误法) ｜ 利用原点信息

      

      以$x_{k+1}=x_k+\alpha P_k$方向搜索下一个可行点，以Armijo准则保证下降（$\alpha<=\beta\alpha$ 以搜索$\alpha$取值，$P_k$为线搜索方向。）

      有时候严格下降并非最合适的迭代准则

      • 插值拟合缩放

        替代 $\beta$乘积缩放（回溯 backtrack）

      • 非单调（nonmonotone）Armijo

      • safeguard

        机器精度问题：最小步长，最大回溯次数

    • Goldstein ｜ 两条线之间

      

    • Wolfe:曲率条件(curvature condition):，来避免曲线下降不充分的问题。 ｜ 剔除导数值小于原点处的点

      加入曲率条件（Wolfe / Strong Wolfe）：提高“准确度”（步长更接近合理尺度）

      Armijo 容易把 α 缩得很小（尤其在病态问题、非线性强、方向质量一般时），导致进展慢。Wolfe 在 Armijo 基础上加曲率条件：

      

      对拟牛顿（BFGS/L-BFGS）尤为重要：Strong Wolfe 能更好维护正定性和实际收敛表现。

      $$ |\nabla f(x_k+\alpha p_k)^Tp_k|\le c_2|\nabla f(x_k)^Tp_k| $$

      如果你关心稳定 + 收敛速度，优先用 Strong Wolfe（常见取

      c1=10−4,c2=0.9c_1=10^{-4}, c_2=0.9

      c1=10−4,c2=0.9）。

    ---

    收敛性分析：梯度 Lipschitz 连续，

    $$ \sum \cos ^2\theta \lVert \nabla f(x)\lVert <+\infty. $$

梯度方法

梯度方法