最优化理论与方法第四章(10月10日)课件

第四章优化算法的结构与一维搜索4.1常用的优化

算法结构设迭代算法产生点列{x(k)}S.1.理想的收敛性：设x*∈S是全局最优点(g.opt)。当x*∈{x(k)}或

x(k)≠x*，k，满足

时，称算法收敛到最优解x*一.算法收敛性问题

2.实用收敛性：定义解集

S*={x|x具有某种性质

}

例：S*={x|x---g.opt}

S*={x|x---l.opt}

S*={x|f(x)=0}

S*={x|f(x)≤β}(β为给定的实数，称为阈值)收敛性：设解集S*≠，{x(k)}为算法产生的迭代点列。下列情况之一成立时，称算法收敛：

1°x(k)∈S*;2°x(k)S*，k，{x(k)}任意极限点∈S*。全局收敛：对任意初始点x(0),算法均收敛。局部收敛：当x(0)

充分接近解x*时，算法收敛二.算法收敛速度一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。二次终结性=共轭方向+精确一维搜索。共轭方向定义：设An×n

对称正定，d(1),d(2)∈Rn,d(1)≠0，d(2)≠0，满足d(1)TAd(2)=0,称d(1),d(2)

关于矩阵A共轭。共轭向量组：d(1),d(2),…,d(m)∈Rn

均非零，满足d(i)TAd(j)=0,(i≠j).三、二次终结性当A=I(单位矩阵)时，d(1)TAd(2)=d(1)Td(2)=0，即正交关系。

d(1),d(2),…,d(m)

关于正定矩阵A两两共轭时，d(1),d(2),…,d(m)

线性无关。设d=1d(1)+2d(2)+…+md(m)=0，j=1,2,…,m，d(j)TAd=

jd(j)TAd(j)=0∵d(j)TAd(j)>0，故j=0，即线性无关。超线性收敛和二次终结性常用来讨论算法的优点。四、下降算法结构算法结构

线性搜索求新点使x(k+1)∈D初始x(1)∈D,k=1对x(k)点选择下降可行方向d(k)是否满足迭代结束条件？停k=k+1yesno4.2

一维搜索

精确一维搜索方法为单峰函数缩小搜索区间一般遵循的原则去坏留好.对称等比收缩等间隔分割法消去区间后,区间缩小为原来区间长度的2/30.618法（黄金分割法）等间隔分割法特点:算法简单,计算次数多,这是因为每分割一次要进行两次函数值计算,采用黄金分割法,则每次分割只需计算一次函数值收缩比0.618的由来?Fibonaoci法Fibonaoci数列Fibonaoci分数数列为整数序列前后两项之比性质:黄金分割法是Fibonacci法的简单形式Fibonacci数列中当迭代后的区间长度与迭代前的区间长度之比为例1:Fibonacci法求解牛顿法（Newton）和插值法Newton法算法框图：初始λ1,ε1,ε2>0k=1︱ф′(λk)

︱<ε1?停；解λk

yNф″(λk)>0?N停，失败Yλk

+1=λk-ф′(λk)／ф″(λk)|λk

+1-λk

|<ε2

YNk=k+1

例2:求minф(λ)=arctantdt

解：

ф′(λ)=arctanλ,ф″(λ)=1／(1+λ2)

迭代公式：λk

+1=λk-(1+λk2)arctanλk

取λ1=1，计算结果：

k

λk

ф′(λk)1／ф″(λk)110.785422-0.5708-0.51871.325830.1169-0.11641.01374-0.001095-0.001095λ4≈λ*=0

取λ1=2，计算结果如下：k

λk

ф′(λk)1／ф″(λk)121.107152-3.5357-1.295213.50313.95不收敛。2、插值法：用ф(λ)在2个或3个点的函数值或导数值，构造2次或3次多项式作为ф(λ)的近似值，以这多项式的极小点为新的迭代点。

3点2次，2点2次，4点3次，3点3次，2点3次等以3点2次为例：取λ1，λ

2，λ3，求出ф(λ1)，ф(λ2)，ф(λ3)（目标函数值满足两头大，中间小）

设二次插值多项式：aλ2+bλ+c=ф(λ)

aλ12+bλ1+c=ф(λ1)aλ22+bλ2+c=ф(λ2)aλ32+bλ3+c=ф(λ3)

解得a,b再从λ1，λ

2，λ3，中选择目标函数值最小的点及其左右两点，作新的插值，以此类推。写在最后成功的基础在于好的学习习惯Thefoundationofsuccessliesingoo