最优化理论复习--使用导数的最优化方法

发布时间：2024年01月10日

文章目录

上一篇

最优化理论复习–最优性条件（二）

最速下降法

考虑无约束问题 m i n f ( x ) , x ∈ R n min f(x), x\in R^n minf(x),x∈Rn, 其中 f ( x ) f(x) f(x) 具有一阶连续偏导数（梯度下降法）
策略：从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点。

下降方向：负梯度方向是最速下降方向
d = ? ▽ f ( x ) ∣ ∣ ▽ f ( x ) ∣ ∣ d = -\frac{\bigtriangledown f(x)}{||\bigtriangledown f(x)||} d=?∣∣▽f(x)∣∣▽f(x)?
注： 在不同的尺度下最速下降方向是不同的

最速下降法的迭代公式：
x k + 1 = x k + λ k d k x_{k + 1} = x_{k} + \lambda_k d_{k} xk+1?=xk?+λk?dk?

  • d k d_{k} dk? 为搜索方向为 ? ▽ f ( x k ) - \bigtriangledown f(x_{k}) ?▽f(xk?)
  • λ k \lambda_k λk?为一维搜索步长，满足 f ( x k + λ k d k ) = min ? λ ≥ 0 f ( x k + λ d k ) f(x_k + \lambda_k d_k) = \min\limits_{\lambda \geq 0} f(x_k + \lambda d_k) f(xk?+λk?dk?)=λ≥0min?f(xk?+λdk?)

算法步骤：

  1. 给定初始点 x k ∈ E n x_k \in E^n xk?∈En, 允许误差 ? > 0 , k = 1 \epsilon > 0, k = 1 ?>0,k=1
  2. 计算搜索方向 d = ? ▽ f ( x k ) d = - \bigtriangledown f(x_k) d=?▽f(xk?)
  3. 若 ∣ ∣ d k ∣ ∣ ≤ ? ||d_k|| \leq \epsilon ∣∣dk?∣∣≤?, 停止， 从 x k x_k xk? 出发，沿 d k d_k dk? 进行一维搜索， 求 λ k \lambda_k λk?, 使得 f ( x k + λ k d k ) = min ? λ k ≥ 0 f ( x k + λ d k ) f(x_k + \lambda_k d_k) = \min\limits_{\lambda_k \geq 0} f(x_k + \lambda d_k) f(xk?+λk?dk?)=λk?≥0min?f(xk?+λdk?)
  4. 令 x k + 1 = x k + λ k d k , k = k + 1 x_{k +1} = x_k + \lambda_k d_k, k = k + 1 xk+1?=xk?+λk?dk?,k=k+1, 转2

在这里插入图片描述
最速下降法的收敛性是线性收敛的。
条件数越小，收敛越快；条件数越大，收敛越慢
最速下降法存在锯齿现象，因为相邻的两个搜索方向是正交的
在这里插入图片描述

牛顿法

设 f ( x ) f(x) f(x) 是二次可微函数， x ∈ R n x \in R^n x∈Rn, 又设 x k x_k xk? 是 f ( x ) f(x) f(x) 的极小点的一个估计， 将 f ( x ) f(x) f(x) 在 x k x_k xk? 点泰勒展开，二阶近似
f ( x ) = f ( x k ) + ▽ f ( x k ) T ( x ? x k ) + 1 2 ( x ? x k ) T ▽ 2 f ( x k ) ( x ? x k ) f(x) = f(x_k) + \bigtriangledown f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T \bigtriangledown^2 f(x_k) (x - x_k) f(x)=f(xk?)+▽f(xk?)T(x?xk?)+21?(x?xk?)T▽2f(xk?)(x?xk?)
其中 ▽ 2 f ( x k ) 是 f ( x ) \bigtriangledown ^2 f(x_k) 是f(x) ▽2f(xk?)是f(x)在点 x k x_k xk? 处的海森矩阵

因此牛顿法的迭代公式为
x k + 1 = x k ? ▽ 2 f ( x k ) ? 1 ▽ f ( x k ) x_{k + 1} = x_k - \bigtriangledown^2 f(x_k)^{-1} \bigtriangledown f(x_k) xk+1?=xk??▽2f(xk?)?1▽f(xk?)

算法步骤：

  1. 给定初始点 x 0 x_0 x0?, 允许误差 ? > 0 , k = 1 \epsilon > 0, k = 1 ?>0,k=1
  2. 若 ∣ ∣ ▽ f ( x k ) ∣ ∣ ≤ ? ||\bigtriangledown f(x_k)|| \leq \epsilon ∣∣▽f(xk?)∣∣≤?, 停止， 得解 x k x_k xk? ,否则， 令 x k + 1 = x k ? ▽ 2 f ( x k ) ? 1 ▽ f ( x k ) , k = k + 1 x_{k + 1} = x_k - \bigtriangledown^2 f(x_k)^{-1} \bigtriangledown f(x_k), k = k + 1 xk+1?=xk??▽2f(xk?)?1▽f(xk?),k=k+1, 转2

在这里插入图片描述

牛顿法的收敛性是至少二阶收敛的

但是当初始点远离极小点时，牛顿法可能不收敛
因此在牛顿法的基础上增加了步长的概念

阻尼牛顿法
基本思想：增加沿牛顿方向一维搜索

迭代公式
x k + 1 = x k + λ k d k x_{k + 1} = x_k + \lambda_k d_k xk+1?=xk?+λk?dk?

  • d k = ? ▽ 2 f ( x k ) ? 1 ▽ f ( x k ) d_k = - \bigtriangledown^2 f(x_k)^{-1} \bigtriangledown f(x_k) dk?=?▽2f(xk?)?1▽f(xk?)
  • λ k = min ? λ f ( x k + λ d k ) \lambda_k = \min\limits_\lambda f(x_k + \lambda d_k) λk?=λmin?f(xk?+λdk?)

算法步骤：

  1. 给定初始点 x 0 ? > 0 , k = 1 x_0 \epsilon > 0, k = 1 x0??>0,k=1
  2. 计算 ▽ f ( x k ) , ▽ 2 f ( x k ) ? 1 \bigtriangledown f(x_k), \bigtriangledown^2 f(x_k) ^{-1} ▽f(xk?),▽2f(xk?)?1
  3. 若 ∣ ∣ ▽ f ( x k ) ∣ ∣ ≤ ? ||\bigtriangledown f(x_k)|| \leq \epsilon ∣∣▽f(xk?)∣∣≤?，停止，否则令 d k = ? ▽ 2 f ( x k ) ? 1 ▽ f ( x k ) d_k = - \bigtriangledown^2 f(x_k) ^{-1} \bigtriangledown f(x_k) dk?=?▽2f(xk?)?1▽f(xk?)
  4. 从 x k x_k xk?出发，沿方向 d k d_k dk? 作一维搜索求 λ k \lambda_k λk?，令 x k + 1 = x k + λ k d k x_{k + 1} = x_k + \lambda_k d_k xk+1?=xk?+λk?dk?
  5. k = k + 1，转2

二阶矩阵逆矩阵公式：

对 A = [ a b c d ? ] A = [ \begin{matrix} a & b \\ c & d \ \end{matrix} ] A=[ac?bd??], 则 ∣ A ∣ = a d ? b c |A| = ad - bc ∣A∣=ad?bc
当 a d ? b c =? 0 ad - bc \not = 0 ad?bc?=0时， A的逆矩阵为
A ? 1 = 1 ∣ A ∣ [ d ? b ? c a ? ] A^{-1} = \frac{1}{|A|}[ \begin{matrix} d & -b \\ -c & a \ \end{matrix} ] A?1=∣A∣1?[d?c??ba??]
行列式的倒数乘主对角线互换，副对角线添负号

在这里插入图片描述
为了解决 H e s s i a n Hessian Hessian矩阵不存在的情况，提出修正的牛顿法

方法是在 H e s s i a n Hessian Hessian矩阵的基础上加一个参数的单位矩阵是它化为正定矩阵
构造 G k G_k Gk?, I I I 为单位矩阵， ? k \epsilon_k ?k? 是一个适当的正数
G k = ▽ 2 f ( x k ) + ? k I G_k = \bigtriangledown^2 f(x_k) + \epsilon_k I Gk?=▽2f(xk?)+?k?I

算法步骤：

  1. 给定初始点 x 0 ? > 0 , k = 0 x_0 \epsilon > 0, k = 0 x0??>0,k=0
  2. 计算梯度 ▽ f ( x k ) \bigtriangledown f(x_k) ▽f(xk?), 若 ∣ ∣ ▽ f ( x k ) ∣ ∣ ≤ ? ||\bigtriangledown f(x_k)|| \leq \epsilon ∣∣▽f(xk?)∣∣≤?, 停止， 得到解 x k x_k xk? , 否则跳到3
  3. 计算 H e s s i a n 矩 阵 ▽ 2 f ( x k ) Hessian矩阵 \bigtriangledown^2 f(x_k) Hessian矩阵▽2f(xk?), 求修正后的矩阵 G k = ▽ 2 f ( x k ) + θ I G_k = \bigtriangledown^2 f(x_k) + \theta I Gk?=▽2f(xk?)+θI 计算修正牛顿方向 d k = ? ( G k ) ? 1 ▽ f ( x k ) d_k = -(G_k)^{-1} \bigtriangledown f(x_k) dk?=?(Gk?)?1▽f(xk?)
  4. 从 x k x_k xk? 出发， 沿方向 d k d_k dk? 作一维搜索，求步长 λ k \lambda_k λk?
    令 x k + 1 = x k + λ k d k x_{k + 1} = x_k + \lambda_k d_k xk+1?=xk?+λk?dk?, k = k + 1, 转2

下一篇

未完待续

文章来源:https://blog.csdn.net/m0_64372178/article/details/135372654
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章