全局最优化算法.pdf

《全局最优化算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全局最优化算法沈云中同济大学测量系E-mail:yzshen@mail.tongji.edu.cn提要•概述•局部最优算法•区间数学理论•全局最优算法•带约束全局最优算法概述•最优化模型函数模型：min:f(x)点集范围：x∈X•对于凸函数和凸集，只存在唯一的极值点其局部最优点就是全局最优点•非凸函数或点集，存在多个极值点其极值点与初值有关全局最优就是要寻找最大或最小的极值点凸集与凸函数凸集：如果集S中任何两点间的连线都属于S，则称S为凸集。n凸函数：设S⊂R是非空凸集，f:SaR，如果对任意的α∈(0,1)有121212f(αx+(1−α)x)≤αf(x)+(1−

2、α)f(x)，∀x,x∈S则称f是S上的凸函数，或f在S上是凸的。如果对于任意的α∈(0,1)有121212f(αx+(1−α)x)<αf(x)+(1−α)f(x)，x≠x则称f是S上的严格凸函数，或f在S上是严格凸的。带约束的优化•带约束的优化模型Tg(x)=(g(x),...,g(x))1pTh(x)=(h(x),...,h(x))，1qnpnq其中，g:RaR,h:RaR，那么⎧minf(x)⎪⎨s.t.g(x)≤0或者minf(x)x∈X⎪⎩h(x)≤0定理：非线性优化模型，也称非线性规划(MP)，若ng(x),i=1,,,...,p，皆为R上的凸函数，h(

3、x),j=1,,,...,q皆ij为线性函数，并且f是X上的凸函数，则(MP)是凸规划。定理：凸规划的任一局部最优解都是它的整体最优解。局部最优点•局部最优点：**定义：对于非线性规划(MP)，若x∈X，并且存在x的一个*{n*}领域N(x)={x∈Rx−x<δ}(δ>0,δ∈R)，使δ**f(x)≤f(x),∀x∈Nδ(x)IX，**则称x是(MP)的局部最优解或局部极小点，称f(x)是(MP)的局部最优值或局部极小点。如果有***f(x)

4、最优值或严格局部极小点。无约束局部最优解定理nnn定理1：设f:RaR在点x∈R处可微。若存在p∈R，使T∇f(x)p<0，则向量p是f在点x处的下降方向。nn*定理2：设f:RaR在点x∈R处可微。若x是(UMP)的局部最*优解，则∇f(x)=0nn2*定理3：设f:RaR在点x∈R处的Hesse矩阵∇f(x)存在。若*2**∇f(x)=0，并且∇f(x)正定，则x是(UMP)的局部最优解。n*nn定理4：设f:RaR，x∈R，f是R上得可微凸函数。若有**∇f(x)=0，则x是(UMP)的整体最优解。无约束局部最优算法•最速下降法控制误差ε＞0,初始点x(k=0

5、),迭代步骤：k①：计算▽f(x)k②：若

6、

7、▽f(x)

8、

9、≤ε,则取x*=x,停；kk否则,令p=-▽f(x),用一维搜索法求λ,kkk使得f(x+λp)=min{f(x+λp)

10、λ≥0}.kkkkk③：令x=x+λp,k=k+1,+1,转向①k+1kkk优点：整体收敛性,计算量小,初始点要求不高缺点：收敛速度慢无约束局部最优算法•BFGS拟牛顿算法（Boryden-Fletcher-Goldfarb-Shanno）(1kk+)()xxd=+αkk()kdHx=−∇f()kkTTTHEp=()−−ρρqH()Eqpp+ρpkk+1kkkkkkkkkHE=01(()

11、()kk+1)()ρ=pxxkTpxx=−qpkkk(()kk+1)(()qx=∇∇∇ff()()−∇xk()k迭代停止条件：∇0；000第2步计算∇f(x)，若∇f

12、(x)≤ε，停止迭代，输出x；否则，进行第3步；00第3步取p=−∇f(x)，令k:=0；kkkkk+1kk第4步进行一维搜索求t使得f(x+tp)=minf(x+tp)，令x=x+tp；kkkt≥0k+1k+1k+1第5步计算∇f(x)，若∇f(x)≤ε，停止迭代，输出x；否则，进行第6步；0n第6步若k+1=n，令x:=x，转第3步；否则进行第7步；2k+1∇f(x)k+1k+1k第7步用F-R公式取p=−∇f(x)+λp，其中λ=。令k:=k+1，kk2k∇f(x)转第4步。带约束局部最优化解定理•K-T条件⎧⎪ngi(x)≤0,i=1,...,p⎫⎪X=