第八章单变量函数的寻优方法选编.ppt

第 八 章;黄金分割法（0.618法） Step0 给定容许最终不确定区间长度为l 0，初始区间[a1,b1 ],令k=1,进入Step1 Step1 若 bk- akl,则停算,极小点x*? [ ak,bk ] 否则计算 f 在 uk=ak+0.382(bk-ak) vk=ak+0.618(bk-ak) 的值。;a1;a1;Step2 若f(uk)f(vk),则令 ak+1 = uk和bk+1= bk 否则令 ak+1 = ak和bk+1= vk Step3 令k+1 ? k,转Step1;8.1 黄金分割法; 定义：设φ： [α, β] →R， ?λ* ∈[α, β] 是φ在[α, β] 上的极小点 ，若对任意λ1 ,λ2, α≤ λ1 λ2 ≤β满足： 1o 若λ2 ≤ λ* ，则φ(λ1) φ(λ2); 2o 若λ1 ≥λ* ，则φ(λ1) φ(λ2). 则称φ(λ)在[α, β] 上强单峰。 ; 若对任意λ1 ,λ2, α≤ λ1 λ2 ≤β满足： 1o 若λ2 ≤ λ* ，则φ(λ1) φ(λ2); 2o 若λ1 ≥λ* ，则φ(λ1) φ(λ2). 则称φ(λ)在[α, β] 上强单峰。 若只有当φ(λ1) ≠φ(λ* )， φ(λ2) ≠φ(λ* )时，上述1o, 2o 式才成立，则称φ(λ)在[α, β] 上单峰。; 定理：设Ф：R→R 在[α，β ]上单峰，α≤λ＜μ≤ β 。那么 1°若Ф(λ)≥ Ф(μ)，则Ф(ρ)≥Ф(μ)， ? ρ ∈[α，λ]；如左下图 2°若Ф(λ)＜ Ф(μ)，则Ф(ρ)≥Ф(λ)， ? ρ ∈[μ ， β]；如右下图; Proof. 1°反证：设 λ* ∈[α,β]为极小点，γ∈[α,λ]及γ﹤λ﹤λ*，使ф (γ)ф (μ )ф (λ)， 若λ* ∈[λ ,β]，由定义ф (γ)ф (λ)，矛盾（假设）； 若λ* ∈[α ,λ），由定义及μ λ ≥λ*， ф(μ )ф (λ), 矛盾（条件）； 于是结论成立。 2 °的证明类似（略）。 注：上述定理为缩短区间的算法提供了理论根据。;2、黄金分割法（0.618 法） 通过上述定理，选二点λμ ,比较ф (λ) 与ф (μ ),可去掉[α ,λ]或者[μ ,β].考虑条件： 1°对称： λ- α= β- μ ……① （使“坏”的情况去掉，区间长度不小于“好”的情况） 2°保持缩减比 t=(保留的区间长度／原区间长度) 不变。 （使每次保留下来的节点， λ或 μ，在下一次的比较中成为一个相应比例位置的节点 ）。 推导缩减比 t : 如图设第一次保留[α, μ] (去掉[μ, β]),那么第二次保留的长度为[α, λ],则;2、黄金分割法（0.618 法）（续） 整理② ： μ =α +t(β -α ) λ = α +t(μ -α ) 结合①式：t2+t-1=0 故 t≈0.618 注意 上式有 t2=1-t , 故有 μ =α +t(β -α ) λ = α + （1-t）(β -α ) （算法框图见下页）;黄金分割法（0.618 法）（算法）;8.2牛顿法;一、牛顿法（Newton）基本原理; 用qk(λ)作为ф(λ)的近似，当ф″(λk) 0时，其驻点为极小点： q′k(λ)= ф′(λk) +ф″(λk)(λ- λk )=0 得到： λk +1=λk –ф’(λk) /ф’’(λk) 取λk +1为新的迭代点。 以上过程即Newton法。 特点：二阶、局部收敛。 （算法框图见下页）;Newton法算法框图：;二、牛顿法（Newton）例题 Ex. 求 min ф(λ)= arctan t d t 解： ф′ (λ) =arctan λ , ф″(λ)=1／(1+ λ2) 迭代公式： λk +1= λk - (1+ λ2) arctan λk 取λ1= 1，计算结果： k λk