使用黄金分割法确定步长的牛顿法
巡山小妖精
869次浏览
2021年01月31日 02:27
最佳经验
本文由作者推荐
qq图标怎么隐藏-网上宣传
数学与计算科学学院
实
验
报
告
实验项目名称
使用黄金分割法确定步长的牛顿法
所属课程名称
最优化方法
实
验
类
型
算法编程
实
验
日
期
201
班
级
信
学
号
姓
名
成
绩
一、实验概述：
【实验目的】
(1)
掌握
Matlab
数值计算的基本方法；
(2)
掌握最速下降法；
(3)
掌握黄金分割法确定步长。
【实验原理】
1.
黄金分割法
:
一维搜索是解函数极小值的方法之一，
其解法思想为沿某一已知方向求目标函
数的极小值点。
一维搜索的解法很多，这里主要 采用黄金分割法（
0.618
法）
。该方
法用不变的区间缩短率
0. 618
代替斐波那契法每次不同的缩短率，
从而可以看成是
斐波那契法的近似，实现起 来比较容易，也易于人们所接受。
黄金分割法是用于一元函数
f(x)
在给 定初始区间
[a,b]
内搜索极小点
xmin
的
一种方法。它是优化 计算中的经典算法，以算法简单、收敛速度均匀、效果较好而
著称，是许多优化算法的基础，但它只适用 于一维区间上的凸函数，即只在单峰区
间内才能进行一维寻优，
其收敛效率较低。
其基 本原理是：
依照“去劣存优”原则、
对称原则、以及等比收缩原则来逐步缩小搜索区间。具体步 骤是：在区间
[a,b]
内
取点：
a1
，
a2
把
[a,b]
分为三段。
①
如果
f (a1)>f(a2)
，令
a=a1,a1=a2,a2=a+0.618*(b-a)
；
②
如果
f(a1)
b=a2
，
a2=a1,a1=b-0.618*(b-a)
；
如 果｜
(b-a)/b
｜和｜
(y1-y2)/y2
｜都大于收敛精度
ε
重新开始循环。
因为
[a,b]
为单峰区间，这样每次可将搜索 区间缩小
0.618
倍，处理后的区间
都将包含极小点的区间缩小，
然后在保 留下来的区间上作同样的处理，如此迭代下
去，将使搜索区
[a,b]
逐步缩小，直到 满足预先给定的精度时，即获得一维优化问
1
题的近似最优解。
插入点原理图如下：
算法流程图
:
2
图
1
2.
牛顿法：
设
f
x
是二次可微实函数，x
k
R
n
，
Hesse
矩阵
2
f
x
k
正定。在
x
k
附近用
二次
Taylor
展开近似
f
，
1
T
T
f
x
k
s
q
k
s
f
x
k
s
f
x
k
s
s
T
2
f
x
k
s
2
s
x
x
k
，
q
k
s
为
f
x
的二次近似。将上式右边极小化，便得：
2< br>x
k
1
x
k
< br>
f
x
k
f< br>
x
k
，
这就是牛顿法的迭代公式。
1
3
在这个公 式里，步长因子
k
1
。令
G
k
2
f
x
k
,
g
k
f
x
k
，则上式也可写
成：
1
x
k
1
x
k
G
k
g
k
显然，牛顿法也可以看成在椭球范数
G
下的最速下降法。
k
T
事实上，对于
f
x
k
s
f
x
k
g
k
s
，
T
g
k
s
的 解。该极小化问题依赖于所取的范数，当采取
l
2
范
s
k
是 极小化问题
min
s
R
n
s
数时，< br>s
k
g
k
，所得方法为最速下降法。当采用椭球 范数
G
k
时，
s
k
G
k
1
g
k
，所得方法即为牛顿法。
【实验环境】
Windows7
Matlab 7.0
二、实验内容：
【实验方案】
算例：
f
(
x
1
,
x
2
)
x
1
2
x
2
2
x
1x
2
10
x
1
4
x
2< br>
60
的极小值，
0.001
。
要求
: 1
、利用使用黄金分割法确定步长的牛顿法
编写一维搜索方法（含黄金分割法确定步长）
；
2
、在使用共轭梯度法梯度法进行搜索时可以调用一维搜索方法。
【实验过程】
1.
黄金分割法程序流程图
4
2.
牛顿法的改进算法：
给出初始点x
0
R
n
。第
k
步迭代为：
（
1
）令
G
k
G
k
v< br>k
I
，其中：
v
k
0
，如果
G
k
正定
v
k
0,
；否则。< br>
（
2
）计算
G
k
的
Cholesky分解，
G
k
L
k
D
k
L
T
k
。
（
3
）解
G
k
d
g
k
得
d
k
。
（
4
）令
x
k
1
x
k
d
k
【实验结论】
（结果）
_
_
_
5