工程优化+第3章-..

定理(必要条件)设(1)为D的一个内点;(2)在可微;(3)为的极值点;则。:nfDRR0fx()fxx第3章常用的一维搜索方法求无约束的某可微函数的最优解，根据一阶必要条件，可令函数的梯度等于零，由此求得驻点；然后用充分条件进行判别，求出所要的解:nfDRRn元函数min()nxRfx求解无约束优化问题xx()fx定理(充分条件)设(1)为D的一个内点;(2)在二次连续可微;(3);(4)正定;则为的严格局部极小点。:nfDRR2fx(*)0fx()fxx()fxxx第3章常用的一维搜索方法•对某些较简单的函数，这样做有时是可行的；•但对一般n元函数f(x)来说，由条件得到的是一个非线性方程组，解它相当困难。•对于不可微函数，当然谈不上使用这样的方法。•为此，常直接使用迭代法。()0fx0x10()()fxfxkx*x*lim0kkxx为了求函数f(x)的最优解，首先给定一个初始估计然后按某种规划(即算法)找出比更好的解对极小化问题，再按此种规则找出比更好的解,如此即可得到一个解的序列。若这个解序列有极限，即则称它收敛于x*。若算法是有效的，则它产生的解的序列将收敛于该问题的最优解。但由于计算机只能进行有限次迭代，一般很难得到准确解，而只能得到近似解。当达到满足的精度要求后，即可停止迭代。迭代法的基本思想0x1x1x2x理想的终止条件是()(*)fxfx或者*xx问题是x*未知停止迭代时要满足的条件称为终止条件。迭代法的终止条件实用的终止条件是根据相继两次迭代的结果11()(),,kkkkfxfxxx11()(),,()kkkkkkfxfxxxfxx()kfx（1）根据相继两次迭代的绝对误差（2）根据相继两次迭代的相对误差（3）根据目标函数梯度的模足够小迭代法的终止条件011**kkxxxx101设序列收敛于，若存在与迭代次数k无关的数时，称超线性收敛。时，称线性收敛或一阶收敛。成立，就称收敛的阶为，或者称阶收敛。迭代法的收敛速度kx*x和，使k从某个k0开始，都有kxkx当12当，且具有二阶收敛速度。kx当2时，称为二阶收敛，也可说迭代法的一般框架找初始点判断当前点是否满足终止条件找下一个迭代点最优解(a)找初始点(b)终止条件(c)迭代格式从当前点出发，按照某种规则找下一个迭代点注：迭代格式不同，对应着不同的算法是否循环迭代法的分类可行算法：所有迭代点都是可行点据迭代点的可行性不可行算法：至少有一个迭代点不是可行点初始点不好找11,()(),()(),,()()下降：根据目标函数的下降特性非单调下降算法：算法kkkkkkklkkfxfxkfxfxlfxfx每一迭代点的目标函数值都在下降整体下降，局部上升初始点任意选取迭代法的分类直接法：不需要导数信息根据是否计算目标函数和约束函数的导数：需要导数信息非直接法仅利用函数值，简单易用：迭代点沿某方向产生根据迭代点是否沿某个方向产生信赖域方法：迭代点在某区域内搜索产线搜索方法生利用导数信息，收敛性结果更强每次迭代沿某个方向搜索下个迭代点，最常见研究最多的方法每次迭代在某区域内搜索下个迭代点，近30年来发展起来的一类方法kx1kx1()()kkfxfxkkxxd1kkkkxxdkdk现假定已迭代到点，(见图6-5)，若从都不能使目标函数值下降，则是一局部极小点，迭代停止。若从出发至少存在一个方向可使目标函数值有所下降，可选定能使目标函数值下降的某方向，沿这个方向迈进适当的一步，得到下一个迭代点，并使。这相当于在射线上选定新点其中，称为搜索方向；称为步长或步长因子。图6-5线搜索迭代法的基本思想出发沿任何方向移动kxkxkdkx0x:0kkdkxλk1kx:1kk(1)选定某一初始点，并令(2)确定搜索方向(3)从出发，沿方向求步长，以产生下一个迭代点(4)检查得到的新点是否为极小点或近似极小点。，转回(2)继续进行迭代。在以上步骤中，选取搜索方向是最关键的一步，各种算法的区分，主要在于确定搜索方向的方法不同。若是，则停止迭代。否则，令线搜索迭代法的步骤kd1kx找初始点判断当前点是否满足终止条件下一个迭代点最优解(a)找初始点(b)终止条件(c)迭代格式找步长和下降方向，确定下一个迭代点不同的对应不同的算法是否循环线搜索迭代法的框架分析1λkkkkxxdλkkd1kxkd不同的对应不同的算法kd线搜索迭代法的框架分析（c）迭代格式：不同的对应不同的算法，各种算法的区分，主要在于确定搜索方向的方法不同。后面介绍各种算法时会给出一个明确的选取的方法。kdkd在确定了迭代方向后，下一步就要确定迭代步长，常见的方法有3种。λk(1)令它等于某一常数(例如令λ1k)，这样做不能保证目标函数值下降。(2)第二种称为可接受点算法，只要能使目标函数值下降，可任意选取步长。λ:min()kkkfxd()kkfxdλk求目标函数f(x)的极小：由于这项工作是求以为变量的一元函数的极小点，故常称这一过程为（精确）一维搜索或线搜索迭代法的框架分析----一维搜索λ（精确）线搜索或一维最优化，确定的步长为最佳步长。(3)第三种方法是基于沿搜索方向使目标函数值下降最多，即沿射线kkxxd在搜索方向上所得最优点处的梯度和该搜索方向正交。()fx1kx1λmin()kkkkkkkfxdxxd1T()0.kkfxd定理设目标函数具有一阶连续偏导数，规则产生则有（精确）一维搜索的一个重要性质按下述证明：构造函数，则得()()kkfxdλminλk即是函数的极小点，所以T+1Tλλ0(λ)(λ)(λ)().kkkkkkkk''fxddfxd()λk•精确的一维搜索(1)试探法：按某种方式找试探点，通过比较一系列试探点的函数值的大小确定极小点。(2)区间收缩法：用某种分割技术缩小最优解所在的区间（称为搜索区间）。(3)函数逼近法：用比较简单函数的极小值点近似代替原函数的极小值点。从几何上看是用比较简单的曲线近似代替原来的曲线，用简单曲线的极小值点代替原曲线的极小值点。Newton法、二次插值法、三次插值法常用的一维搜索方法“成功-失败”法二分法、0.618法•非精确的一维搜索：通过计算少量的函数值，得到一步长，使得后续迭代点满足，即使目标函数要“充分”下降。常用的一维搜索方法k1kkkkxxd1()()kkfxfx(1)Armiji-Goldstein准则()()(1),kkkTkkkkfxdfxgd10.2其中(2)Wolfe-Powell准则k要满足()()kkkTkkkkfxdfxgd01.其中k要满足()()kkkTkkkkfxdfxgd和1,(,1),TkTkkkgdgd和•“成功—失败”法•0.618法（黄金分割法）•二分法•牛顿法（Newton）和插值法•Armiji-Goldstein准则•Wolfe-Powell准则常用的一维搜索方法我们主要介绍下面几种方法常用的一维搜索方法对问题令：则：min()axbfx(),(),fxaxbFx否则min()min()axbxfxFx“成功—失败”法（进退法）步骤1：选取初始点x∈R,初始步长h0及精度ε0，步骤2：计算步骤3：若搜索成功,转步骤4；否则，搜索失败，转步骤5。步骤4：令x:=x+h,转步骤2。步骤5：判断若停止迭代，；否则令转步骤2。缺点：效率低。优点：可以求搜索区间。1().fx2().fxh21,12:,:2hh?hh，*xx,4hh注意：初始步长不能选得太小例1：设给定初始点为a及初始步长为h,求搜索区间[c,d]1)前进运算首先计算f(a),f(a+h),如果f(a)f(a+h),则步长加倍,计算f(a+3h).若f(a+h)=f(a+3h),则c=a,d=a+3h;否则将步长再加倍，并重复上面运算.2)后退运算如果f(a)f(a+h),则将步长缩为原来的1/4并改变符号，即将步长改为-h/4,如果f(a)f(a-h/4),则c=a-h/4,d=a+h;否则将步长加倍，并继续后退。注意:1.h选择要适当.(太大含多个单峰区间,太小迭代次数多)；2.f(x)单调时无结果,(加迭代次数限制)；“成功—失败”法（进退法）0.618法（黄金分割法）0.618法是求单峰函数极值的一种试探法，有的书上也称为区间收缩法。所谓的单峰函数是指只有一个峰值的函数。定义(单峰函数)：设f(x)是定义在[a,b]上的函数，若1）x*∈[a,b]是φ在[a,b]上的最小点，2）若对任意x1,x2,a≤x1x2≤b,满足：1º若x2≤x*，则f(x1)f(x2);2º若x1≥x*，则f(x1)f(x2).则称f(x)为[a,b]上的单峰函数。定理：设f：R→R在[a,b]上是单峰函数，a≤x1x2≤b。那么1°若f(x1)≥f(x2)，则x*∈[x1,b],如左下图2°若f(x1)f(x2)，则x*∈[a,x2],如右下图αx1x2bαx1x2b0.618法（黄金分割法）缩短区间的第一个原则---去坏留好原则证明：1°反证法：设x*∈[a,b]为最小点，若x*∈[a,x1]，由定义知f(x1)f(x2)，矛盾（假设）；2°若x*∈[x2,b]，由定义知f(x1)f(x2),矛盾（条件）；结论成立。注：上述定理为缩短区间的算法提供了理论根据。0.618法（黄金分割法）通过上述定理，选二点x1x2,比较f(x1)与f(x2),可去掉[a,x1]或者[x2,b].考虑条件：1°对称原则：x1–a=b-x2……①（使“坏”的情况去掉，区间长度不小于“好”的情况）2°保持缩减比原则t=(保留的区间长度／原区间长度)不变。（使每次保留下来的节点，x1或x2，在下一次的比较中成为一个相应比例位置的节点）。推导缩减比t:如图设第一次保留[a,x2](去掉[x2,b]),第二次保留的长度为[α,x1],则αx1x2b212(2)xxtbx0.618法（黄金分割法）整理②：x2=a+t(b-α)x1=a+t(x2-α)结合①式：t2+t–1=0故t≈0.618注意:上式有t2=1-t,故有x1=a+(1-t)(b-a)=a+0.382(b-a)x2=a+t(b-a)=a+0.618(b-a))(251舍去负值t0.618法（黄金分割法）（0.618法）（算法）初始[a,b],ε02/)15(tx1=α+（1-t）(b-α)x2=α+t(b-α)b-αε?STOP;x*=(α+b)/2yesf（x1）-f（x2）0?Noα=x1,x1=x2x2=α+t(b–α)yesb=x2,x2=x1x1=α+（1-t）(b-α)Noαx1x2bx2bαx1x2bαx1优点：不要求函数可微，且每次迭代只需计算一个函数值，计算量小，程序简单缺点：收敛速度慢。黄金分割法（0.618法）的优缺点0.618法（黄金分割法）课件下载邮箱邮箱名：[e-mail]密码：youhua123456