【课件】运筹学与最优化方法(华南理工)第4章(07-1)

第三章无约束最优化方法3.1常用的搜索算法结构一、收敛性概念：考虑（fs）设迭代算法产生点列{x(k)}S.1.理想的收敛性：设x*∈S是g.opt.当x*∈{x(k)}或x(k)≠x*，k，满足时，称算法收敛到最优解x*。*)(limxxkk3.1常用的搜索算法结构由于非线性规划问题的复杂性，实用中建立下列收敛性概念：2.实用收敛性：定义解集S*={x|x具有某种性质}例：S*={x|x---g.opt}S*={x|x---l.opt}S*={x|f(x)=0}S*={x|f(x)≤β}(β为给定的实数，称为阈值)3.1常用的搜索算法结构一、收敛性概念：考虑（fs）2.实用收敛性（续）▲收敛性：设解集S*≠，{x(k)}为算法产生的点列。下列情况之一时，称算法收敛：1°x(k)∈S*;2°x(k)S*，k，{X(k)}任意极限点∈S*。▲全局收敛：对任意初始点x(1),算法均收敛。局部收敛：当x(1)充分接近解x*时，算法才收敛。(P42例)3.1常用的搜索算法结构二、收敛速度设算法产生点列{x(k)},收敛到解x*,且x(k)≠x*，k，1.线性收敛：当k充分大时成立。2.超线性收敛：3.二阶收敛：﹥0，是使当k充分大时有0||||||||lim*)(*)1(xxxxkkk2*)(*)1(||||||||xxxxkk1||||||||*)(*)1(xxxxkk3.1常用的搜索算法结构二、收敛速度（续）定理：设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*，k，那么证明只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||，除以||x(k)–x*||并令k→∞，利用超线性收敛定义可得结果。1||||||||lim*)()1(xxxxk(k)kk3.1常用的搜索算法结构三、二次终结性▲一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。▲二次终结性=共轭方向+精确一维搜索。▲共轭方向·定义：设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),则向量组d(1),d(2),…,d(m)称为关于A的共轭向量组3.1常用的搜索算法结构四、下降算法模型考虑（fs）常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。△下降方向：设∈S，d∈Rn,d≠0,若存在，使，称d为在点的下降方向。minf(x)s.t.x∈S_x0),0(),()(__xfdxf_x3.1常用的搜索算法结构四、下降算法模型（续）△可行方向：设∈S，d∈Rn,d≠0,若存在，使，称d为点的可行方向。同时满足上述两个性质的方向称下降可行方向。_x_x0),0(,_Sdx3.1常用的搜索算法结构模型算法线性搜索求，得到新点使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)k)()()()1(kkkkdxx是否满足停机条件？停k=k+1yesno3.2一维搜索一元函数求极小及线性搜索均为一维搜索。常用于求：minf(x(k)+d(k))=φ(λ)s.t.λ∈SS有3种情况（-∞，+∞）或（0，+∞）或[a,b]一、平均法(二分法)λ∈[a,b],(P43)3.2一维搜索二、缩小区间的精确一维搜索：考虑问题(P)minφ(λ)s.t.λ∈[α,β]φ(λ):R→R1、不确定区间及单峰函数△不确定区间：[α,β]含φ(λ)的最小点，但不知其位置3.2一维搜索二、缩小区间的精确一维搜索（续）若对任意λ1,λ2,α≤λ1λ2≤β满足：1º若λ2≤λ*，则φ(λ1)φ(λ2);2º若λ1≥λ*，则φ(λ1)φ(λ2).则称φ(λ)在[α,β]上强单峰。若只有当φ(λ1)≠φ(λ*)，φ(λ2)≠φ(λ*)时，上述1º,2º式才成立，则称φ(λ)在[α,β]上单峰。αλ*λ1λ2β强单峰αλ*β单峰3.2一维搜索二、缩小区间的精确一维搜索（续）2、黄金分割法（0.618法）通过上述定理，选二点λμ,比较ф(λ)与ф(μ),可去掉[α,λ]或者[μ,β].考虑条件：1°对称：λ-α=β-μ……①（使“坏”的情况去掉，区间长度不小于“好”的情况）2°保持缩减比t=(保留的区间长度／原区间长度)不变。（使每次保留下来的节点，λ或μ，在下一次的比较中成为一个相应比例位置的节点）。推导缩减比t:如图设第一次保留[α,μ](去掉[μ,β]),那么第二次保留的长度为[α,λ],则αλμβ)2(t3.2一维搜索二、缩小区间的精确一维搜索2、黄金分割法（0.618法）（续）整理②：μ=α+t(β-α)λ=α+t(μ-α)结合①式：t2+t-1=0故t≈0.618注意上式有t2=1-t,故有μ=α+t(β-α)λ=α+（1-t）(β-α)（算法框图见下页）)(251舍去负值t3.2一维搜索二、缩小区间的精确一维搜索之黄金分割法（0.618法）（算法）初始[α,β],ε02/)15(tλ=α+（1-t）(β-α)μ=α+t(β-α)β-αε?STOP;λ*=(α+β)/2yesФ（λ）-Ф（μ）0?Noα=λ,λ=μμ=α+t(β-α)yesβ=μ,μ=λλ=α+（1-t）(β-α)Noαλμβμβαλμβαλ3.2一维搜索三、牛顿法（Newton）和插值法1、Newton法：对ф在λk点展开：ф(λ)=ф(λk)+ф’(λk)(λ-λk)+(1/2)ф’’(λk)(λ-λk)2+o(λ-λk)2取二次式（略去高阶项）：qk(λ)=ф(λk)+ф’(λk)(λ-λk)+(1/2)ф’’(λk)(λ-λk)23.2一维搜索二、牛顿法（Newton）和插值法1、Newton法：（续）用qk(λ)作为ф(λ)的近似，当ф″(λk)0时，其驻点为极小点：q′k(λ)=ф′(λk)+ф″(λk)(λ-λk)=0得λk+1=λk–ф’(λk)/ф’’(λk)取λk+1为新的迭代点。以上过程即Newton法。特点：二阶、局部收敛。（算法框图见下页）3.2一维搜索Newton法算法框图：初始λ1,ε1,ε20k=1︱ф′(λk)︱ε1?停；解λkyNф″(λk)0?N停，失败Yλk+1=λk-ф′(λk)／ф″(λk)|λk+1-λk|ε2YNk=k+13.2一维搜索二、牛顿法（Newton）和插值法1、Newton法：（续）Ex.求minф(λ)=arctantdt解：ф′(λ)=arctanλ,ф″(λ)=1／(1+λ2)迭代公式：λk+1=λk-(1+λ2)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，计算结果如下：03.2一维搜索二、牛顿法（Newton）和插值法1、Newton法：（续）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)3.2一维搜索二、牛顿法（Newton）和插值法2、插值法：（续）设二次插值多项式：aλ2+bλ+c=ф(λ)aλ12+bλ1+c=ф(λ1)aλ22+bλ2+c=ф(λ2)aλ32+bλ3+c=ф(λ3)解得a,b))()(()()()()()()(133221213132321a))()(()()()()()()(133221221231232232221bab23.2一维搜索三、不精确一维搜索：minf(x)考虑从x(k)点出发，沿方向d(k)寻找新迭代点：x(k)+λkd(k)要求:1°f(x(k)+λkd(k))f(x(k));2°λk0不能太小。总体希望收敛快，每一步不要求达到精确最小，速度快，虽然步数增加，则整个收敛达到快速。一个实用方法：为了方便，省去上标：设f:Rn→R。在x取方向d,有▽fT(x)d0(即d为下降方向)求λ使1°f(x+λd)≤f(x)+αλ▽fT(x)d2°▽fT(x+λd)d≥β▽fT(x)d其中α∈（0，1／2），β∈（α，1）为取定参数。实际中常取α=0.1,β=0.7附近。