最优化理论复习--使用导数的最优化方法
上一篇
最速下降法
考虑无约束问题
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?)
算法步骤：
- 给定初始点 x k ∈ E n x_k \in E^n xk?∈En, 允许误差 ? > 0 , k = 1 \epsilon > 0, k = 1 ?>0,k=1
- 计算搜索方向 d = ? ▽ f ( x k ) d = - \bigtriangledown f(x_k) d=?▽f(xk?)
- 若 ∣ ∣ 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?)
- 令 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?)
算法步骤：
- 给定初始点 x 0 x_0 x0?, 允许误差 ? > 0 , k = 1 \epsilon > 0, k = 1 ?>0,k=1
- 若 ∣ ∣ ▽ 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?)
算法步骤：
- 给定初始点 x 0 ? > 0 , k = 1 x_0 \epsilon > 0, k = 1 x0??>0,k=1
- 计算 ▽ f ( x k ) , ▽ 2 f ( x k ) ? 1 \bigtriangledown f(x_k), \bigtriangledown^2 f(x_k) ^{-1} ▽f(xk?),▽2f(xk?)?1
- 若 ∣ ∣ ▽ 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?)
- 从 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
二阶矩阵逆矩阵公式：
对
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
算法步骤：
- 给定初始点 x 0 ? > 0 , k = 0 x_0 \epsilon > 0, k = 0 x0??>0,k=0
- 计算梯度 ▽ 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
- 计算 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?)
- 从
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
下一篇
未完待续
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！