最速下降法与牛顿法及其区别
-
精品文档
最速下降法与牛顿法及其区别
摘要：
无约束优化方法是优化技术中极为重要和基本内容之一。
它不仅
可以直接用来求解无
约束优化问题，
而且很多约束优化问题也常
将其转化为无约束优化问题，
然后用无约束优化
方法来求解。<
/p>
最速下降法和牛顿法是比较常见的求解无约束问题的最优化方法，
这两种算法
作为基本算法，
在最优化方法中占有重要的地位。<
/p>
其中最速下降法又称梯度法，
其优点是工
作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率低。牛顿法的优点是收敛速
度快；缺点是对初始点要求严格，方向构造困难，计算复杂且占用内存较大。同时，这两种
算法的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设
< br>计和产品优化设计等方面都有着重要的应用。
因此，
研究
最速下降法和牛顿法的原理及其算
法对我们有着及其重要的意义。
关键字：
无约束优化
最速下降法
牛顿法
Abstract:
unconstrained
optimization
method
is
to
optimize
the
technology
is
extremely
important
and
basic
content
of.
It
not
only
can
be
directly
used
to
solve
unconstrained
optimization problems, and a lot of
constrained optimization problems are often
transformed into
unconstrained
optimization
problem,
and
then
use
the
unconstrained
optimization
methods
to
solve.
The
steepest
descent
method
and
Newton-Raphson
method
is
relatively
common
in
the
unconstrained problem optimization
method, these two kinds of algorithm as the basic
algorithm,
the
optimization
method
plays
an
important
role
in.
One
of
the
steepest
descent
method
also
known
as
gradient
method,
its
advantages
are
less
workload,
storage
variable
is
less,
the
initial
requirements is not high; drawback is
the slow convergence, low efficiency. Newtonian
method
has the advantages of fast
convergence speed; drawback is the initial point
of strict construction
difficulties,
directions, complicated calculation and larger
memory. At the same time, these two
kinds
of
algorithm
theory
and
methods
into
many
aspects,
especially
in
the
military,
economic,
management, production process
automation, engineering design and product
optimization design
has important
applications. Therefore, to study the steepest
descent method and Newton-Raphson
method principle and algorithm for us
with its important significance.
Keywords:
unconstrained
optimization steepest descent method
.
精品文档
一、算法的基本原理
1.1
最速下降法的基本原理
在基本迭代公
式
X
k
1<
/p>
X
k
t
k
P
k
中，
每次迭代搜索方向
P
k
取为目标函数
f
(
< br>X
)
的负梯
度方向，即
P
k
f
(
X
k
)
，而每次迭代的步长
t
k<
/p>
取为最优步长，由此确定的算法称为最速
下降法。
为了求解问题
min
f
(
X
)
，假定我们
已经迭代了
k
次，获得了第
k
个迭代点
X
k
。现在<
/p>
从
X
k
出发，可
选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方
向
)
进行搜索应该是有利的，至少在
X
k
邻近的范围内是这样。因此，去搜索方向为
P
k
f
(
X
k
)
.
为了使目标函数在搜索方向上获得最多的下
降，沿
P
k
进行一维搜索，由此得到第
k
1
个跌带
点，即
X
k
1
X
k<
/p>
t
k
f
(
X
k
)
，
其中步长因子
t
k
按下式确定
f
(
X
k
t
k
f
(
X
k
))
m
in
f
(
X
k
< br>
t
k
f
(
X
k
)
)
，
X
k
1
ls
(
X
k
,
f
(
X
k
))
.
（
1
）
显然，令
k
0<
/p>
,
1
,
2
,
就可以得到一个点列
X
0
,
X
1
,
X
2
,<
/p>
,
其中
X
0
是初始点，由计算
者任意选定。当
f
(
X
)
满足一定的条件时，由式（
1
）所产生的点列
{
X
k
}
必收敛于
f
(
X
)
的
极小点。
下面为书写方便，记
g
(
< br>X
)
f
(
X
)
。
因此
g
k
g
(
X
k
)
f
(
X
k
)
.
1.2
牛顿法的基本原理
设最优化问题为
min
f
(
X
)
，其中
f
:
R
R
二阶可导，
Hesse
矩阵
f
(
X
)
正定。
不妨设经过
k
次迭代已获点
X
k
，现将
f
(
X
)
在
X
X
k
处展成二阶泰勒公式，于是有
n
1
2
1
f
(
X
< br>)
Q
(
X
)
f
(
X
k
)
f
(
X
k
)
T
(
X
X
k
< br>)
(
X
X
k
)
T
2
f
(
X
k
)(
X
X
k
)
2
.
精品文档
显然
Q
(
X
)
是
二次函数，
特别由假设知
Q
(
X
)
还是正定二次函数，
所以
Q
(
X
)
是凸函数
且存在唯一全局极小点。为求此极小点，令
Q
(
X
)
f
< br>(
X
k
)
2
f
(
X
k
)(
X<
/p>
X
k
)
0
即可解得
X
X
k
[<
/p>
2
f
(
X
k
)]
1
f
(
X
k
)
，
< br>
亦即
2
1
X
k
1
X
k
[
f
(
X
k
)]
f
(
X
k
)
。
（
2
）
对照基本迭代公式
X
k
1
X
k
t
k
P
k
易知
，式（
2
）中的搜索方向
2
1
P
k
[
f
(
X
k
)]
f
(
X
k
)
，
（
3
）
步长因子
t
k
<
/p>
1
。换句话说从点
X
k
出发沿搜索方向
P
k
[
2
f
(
X
k
)]
1
f
(
X
k
)
并取步
长
t
k
1<
/p>
即可得
Q
(
X<
/p>
)
的极小点
X
k
1
。因此，
P
k
[
2
f
(
X
k
)]
1
f
(
X
k
)
是直指点
X
k
< br>处近似二次函数
Q
(
X
)
的极小点的方向。此时称
< br>P
k
[
2
f
(
X
k
)]
<
/p>
1
f
(
X
k
)
为从点
X
k
出发的
Nowton
方向。
从初始点开始，
每一轮从当前迭代点出发，
沿
Nowton
方向并取步长
t
k
1
的算法称为牛顿法。
二、算法的迭代步骤及流程图
2.1
最速下降法迭代步骤
已知目标函数<
/p>
f
(
X
)
及其梯度
g
(
X
)
，终止限
1<
/p>
,
2
和
3
.
（
1
）选定初始点
X
0<
/p>
，计算
f
0
<
/p>
f
(
X
0
),
g
0
g
(
X
0
)
；置
k
0
.
（
2
< br>）作直线搜索：
X
k
1
ls
(
X
k
,
g
k
)
；计算
f
k
1
f
(
X
k
1
),
g
k
1
g
(
X
k
1
)
.
.
精品文档
用终止准则检验是否满足：
若满足，
则打印最优解
(
X
k
1
,
f
(
X
k
1
))
，
结束；
否则，
< br>置
k
k
1
，
转（
2
）
（
3<
/p>
）最速下降法算法流程图如图所示
.
开始
选定
X
0
f
0
f
(
X
0
)
g
0
g
(
X
< br>0
)
X
ls
(
X
0
,
g
0
)<
/p>
f
f
(
X
0
)
g
g
(
X
0
)
终止准则满足？
N
Y
X
,
f
结束
f
f
0
g
0
g
X
0
X
2.2
牛顿法迭代步骤
已知目标函数
f
(
X
)
及其梯度
g
< br>(
X
)
，
Hesse
矩阵
G
(
X
)
，终止限
.
（
1
）选定初始点
X
0
；计算
f
0
f
(
X
0
),
g
o
g
(
X
0
)
；置
< br>k
0
.
2
（
2
）计算
G
k
f
(
X
k
)<
/p>
.
.