最优化-建模培训1(1)

《最优化-建模培训1(1)》由会员分享，可在线阅读，更多相关《最优化-建模培训1(1)（93页珍藏版）》请在装配图网上搜索。

1、无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标这是最简单的最优化问题，实际优化问题一般都比较复杂最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？2()2(2)(2)(2)fxaxxaxxxax

2、f2)2()(2)(6)0ax axaxax61,21()248fxxa()40afab 6ax xyzv(,)vf x y zxyz2(,)2()60 x y zyzxzxya)6222(),(2axyzxyzxyzzyxF2()02()02()0 xyzFyzyzFxzzxFxyxy ，2222(3)02(3)02(3)0 xyzayzxyzazxxyzaxy，zyx,zyx,xyazxayza222333x1x21x2x2121),(xxxxf1x2x405221 xx1200 xx，2121),(maxxxxxf1212254000 xxxx，12121212min()()01 2.(

3、)01 2()Tnnx xxinjnf x xxg x xxils th x xxjmmn，min()()0.()0XfG Xs tH X，Xmin()()01 2.()01 2()Xijf Xg Xils thXjmmn，11()()()()()()TTlmG Xg Xg XH Xh Xh X，|()01 2()01 2()ijDX g Xil h Xjmmn，；，*()min()()0.()0f Xf XG Xs tH X，*()f X*(,()Xf X*X121212min()()01 2.()01 2ijf xxg x xils th x xjm，22121212()|100TDx x

4、xxxx，12()tf x x，ct 21,xxc12()tf x x，LL12Txx，cct 21xx，21xx，222121)(xxxxf，2212221212min(2)(2)1.00 xxxxs txx，22T，*120 0TTXxx，kX1kXkPkt0X0X10 1 2kkkkXXt Pk，011()()()()kkf Xf Xf Xf X0 1 2kXD k，*X*lim|0kkXX0k*1*|lim|kkkXXqXXkX0q0,1qkX0,21q0,1qkX2kX|1kkXX1|)(|1kXf|)()(|1kkXfXf1|)(|1kXf|)()()(|11kkkXfXfXf)(

5、1kXf0X0kkPkt)()(kkkkXfPtXfkkkkPtXX11kX1kX)(1kXf1 kkNYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X0+t P)0，加步系数1，令k=00=(t0)，比较目标函数值tk+1=tk+hk,k+1=(tk+1)a=mint，tk+1b=maxt，tk+1结束NYNY k+1khk+1=hk,t=tk,tk=tk+1,k=k+1,k=k+1k=0hk=hk,k=k+1 在加步探索法中，一般建议 若能估计问题（4.3）的最优解的大体位置的话，初始点要尽量取接近于问题（4.3）的最优解.在具体运用上述加步探索法时，有时还要考

6、虑一些细节问题例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理2,由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念 定义定义4.2 设 闭区间 若存在点 使得 在 上严格递减，在 上严格递增，则称 是函数 的单谷区间单谷区间，是 上单谷函数单谷函数 11:,RR1,a bR,*bat()t*,a t()t*,tb,ba)(t)(t,ba 由定义4.2易知，一个区间是某函数的单谷区间意味着，在该区间中函数只有一个“凹谷”（极小值）例如，左图中的 是 的单谷区间，也即

7、是 上的单谷函数右图中的 不是 的单谷区间，即 不是 上的单谷函数,ba)(t)(t,ba,ba)(t)(t,ba 另外，从定义4.2还可知，某区间上的单谷函数在该区间上不一定是连续函数，而凸函数在所给区间上必然是单谷函数（如左图所示）由定义4.1和定义4.2知，函数的单谷区间总是相应问题（4.3）的一个搜索区间（如左图所示），但反之不然（如右图所示）单谷区间和单谷函数有如下有用的性质：定理4.1 设 是的单谷区间，任取 并且 （1）若有 ，则 是 的单谷区间（2）若有 ，则 是 的单谷区间定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间换句话说利用这个定理可以把搜索区间

8、无限缩小，从而求到极小点.以下介绍的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解,:11baRR,21batt12tt)()(12tt,1ta)(t)()(12tt,2bt)(t 求解一维最优化问题 一般可先确定它的一个有限搜索区间 ，把问题化为求解问题 ，然后通过不断缩短区间的长度，最后求得最优解min()t,ba)(mintbta 设 在已获得的搜索区间 内具有连续的一阶导数因为 在 上可微，故 在 上连续，由此知 在 上有最小值 令 ，总可求得极小点 不妨设 在 上是单减函数；在 上是单增函数所以 时，故 ；当 时，亦即 对分法的原理如图

9、 0)(t*t)(t),(*ta),(*bt*(,)ta t0)(t0)(a),(*btt0)(t0)(b11RR：,ba)(t,ba)(t,ba)(t,ba已知 ，表达式，终止限 (1)确定初始搜索区间 ，要求(2)计算 的中点 (3)若 ，则 ，转(4)；若 ，则 ，转(5)；若 ，则 ，转(4)(4)若 ，则 ，转(5)；否则转(2)(5)打印 ，停机)(t)(t,ba()0()0ab，,ba)(21bac0)(cca 0)(cct*0)(ccb|ba)(21*bat*tY开始确定a b,要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程

10、如图所示()0()0ab，0)(c()0c|ba 对分法每次迭代都取区间的中点 a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正好等于零，则该点就是极小点 因为每次迭代都使原区间缩短一半，所以称为对分法或二分法 设 在已获得的搜索区间 内具有连续二阶导数，求 因为 在 上可微，故 在 上有最小值，令 11:RR,ba)(mintbta)(t,ba)(t,ba0)(t 下面不妨设在区间 中经过 次迭代已求得方程 的一个近似根 过 作曲线 的切线,其方程是 然后用这条切线与横轴交点的横坐标 作为根的新的近似（如图）它可由

11、方程（4.4）在令 的解出来，即 这就是Newton切线法迭代公式 1kt0y)()(1kkkktttt 0)(t,bakkt)(,(kktt)(ty()()()4.4kkkytttt已知 ，表达式，终止限 (1)确定初始搜索区间 ，要求(2)选定 (3)计算 (4)若 ，则 ，转（3）；否则转（5）(5)打印 ，停机000()/()tttt|0tttt 0()tt，)(t)(t,ba()0()0ab，0t 000()/()tttt 输出*,t 开始 结束 0tt Y N 0tt*00,()ttt 选定 t0,确定a b,要求()0,()0ab Newton切线法的计算流程如图所示 这种方法一

12、旦用好，收敛速度是很高的如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点：第一，需要求二阶导数如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出的第二，当曲线 在 上有较复杂的弯曲时，这种方法也往往失效如图(a)所示的迭代：结果 跳出 .迭代或者发散，或者找到的根并不是我们想要的结果第三，即使曲线比较正常，在 中或者上凹或者下凹，初始点的选取也必须适当在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点否则都可能失败)(ty,ba012,ttt2t,ba,ba 要介绍黄金分割法有

13、必要回顾一下古老的黄金分割问题所谓黄金分割就是将一线段分为二段的方法这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段 的比值(如图)xL 于是 则 解得 由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍 因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割xLxxL022LLxxLLx618.0215 用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段如此继续下去可将单谷区间无限缩小 现在提出一

14、个问题，就在 上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间 选二点 等价于将区间长度 进行黄金分割，也就是将第一个搜索点 取在 的0.618处，第二个搜索点 取成 的对称点即 的0.382处（如图所示）,ba21,tt,baab 1t,ba2t1t,ba 即要求 接着计算 与 的值，并根据 与 的值的大小关系分情况讨论：（1）若 ,说明 是好点，于是把区间 划掉，保留 ，则 内有一保留点 ，置新的区间 ；（2）若 ，说明 是好点，于是应将 划 掉，保 留 ,则 内 有 保 留 点 ,置 新 的 区间 .)(618.01abat)(382.02abat)(1t)(

15、2t)(1t)(2t)()(21tt1t,2ta,2bt,2bt1t112,a btb)()(21tt2t,1bt,1ta,1ta2t111,a ba t(3)若 则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉 和 仅保留中间的 重置新的区间 接下来是在留下的区间 内找好点重复上面的步骤，直到搜索区间 小于给定的允许误差 为止。这样就得到黄金分割法迭代算法：12()(),tt,2ta,1bt,12tt1121,a btt,11ba,iiba0 已知 ，常数 0.382，终止限 (1)确定 的初始搜索区间 (2)计算 (3)计算 (4)若 ,则打印 ，停机；否则，转(5)

16、(5)判别是否满足 ：若满足，则置 ，然后转(3)；否则，置 ，然后转(4)(t)(t,ba)()(222tabat，1211()tabtt，221*ttt2122121at tt，11212222()()bt tttabat，|21tt*,t 开 始 确 定 a,b(51)/2 2()tba 22()12tabt 11()t 2212bttt*12()/2ttt*()t 结 束 N Y N Y 12tt 11212,attt222(),()tbat 12 黄金分割法算法流程如图所示12 黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点该方法适用于单谷区间上的任何函数，甚至可以是

17、不连续函数，因此这种算法属于直接法，适用相当广泛 考虑一维搜索问题 假设其中 是定义在区间 上的单峰函数首先用试探法在 上找一点 ，使之满足 )(min21tttt)(t,21tt,21tt0t)()()()(0201tttt，通过目标函数曲线上的三个点 作它的二次拟合曲线（如图所示）)(,(),(,(),(,(220011tttttt2210)(tataatP图4.14 由于上述三个点既是目标函数曲线 上的点，又是二次拟合曲线 上的点，故有方程组 将方程组（4.5）中的 消去，得 )(t)(tP2101 12 112001 02 002201 22 22()()()()4.5()()P ta

18、ata ttP taata ttP taata tt，0a22110210102210220202()()()()4.6()()()()a tta tttta tta tttt，从方程组（4.6）可解出待定系数 对于二次拟合函数 ，我们很容易求得它的极小值点令 即 ，从中解出 即为二次拟合函数 的极小值点22222202121010211002210212101022100221()()()()()()4.7()()()()()()()()()4.8()()()tttttttttatttttttttttttttatttttt2210)(tataatP0)(dttdP0221taa124.92a

19、ta)(tP 将式（4.7）与式（4.8）代入式（4.9）得 用区间 上二次拟合函数 的这个极小值点 作为目标函数 在该区间极小值点的一个估计值 若 和 已充分接近，即对给定的允许误差 使 成立时，就可被看作是 在区间 内近似最优解；否则应缩短区间，按照 值保持两头大、中间小的原则构成新的三点，继续上述过程，直至不等式（4.11）成立为止 22222202121010212021210102()()()()()()122()()()()()()tttttttttatattttttttt 4.10,21tt)(tPt)(tt0t00|4.11ttt)(t)(t,21tt 下面具体介绍缩短区间,构

20、成新三点的方法 由式（4.10）得到的点,在区间 内既可能在点 的左侧(即 ),又可能在 的右侧(即 ).分别对应这两种情形比较 和 的大小，又有 等三种情形，故共有如下六种情况（如图所示）：t,21tt0t0tt 0t0tt)(t)(0t000()(),()(),()()tttttt（1）对于图(a)的情况:因 ,所以相对 为说 是好点，故划掉区间 ,保留 为新区间，故置 保持不变；（2）对于图(b)的情况:因 ,所以相对 来说 是好点，故划掉 保留为 新区间，故置 与 保持不变；（3）对于图(c)的情况：因 所以相对 来说 是好点，故划掉 ,保留 为新区间，故置 保持不变；)()(0tt0

21、tt,20tt2020001()(),()(),ttttttttt，)()(0ttt0t,1tt,2tt1102()(),()(),ttttttt，0t2t0()(),tt0tt,01tt,20tt11()()tttt，1,t t（4）对于图(d)的情况:因 所以相对 来说 是好点，故划掉 保留 故置 ，与 保持不变（5）对于图(e)的情况：一般同时划掉 及 仅留中间的 ，故置（6）对于图(f)的情况：一般同时划掉 及 ，仅留中间的 ，故置0()(),ttt0t,2tt,1tt22()()tttt，0t1t,1tt,20tt,0tt,01tt,2tt,0tt121211202000,()(),

22、()(),()22tttttttttttttt121210102200,()(),()(),()22tttttttttttttt 开始 确定 t0,t1,t2,要求1020()(),()()tttt 按(4.10)计算t 1tt1()()tt 210tttt201()()()()tttt 110tttt101()()()()tttt 2tt2()()tt*,()ttt*,t 结束 Y Y Y Y N N N N 0tt 0tt 0()()tt 0()()tt 通过上述讨论,我们可直接给抛物线插值法的迭代流程图.抛物线插值法是多项式逼近法的一种所谓多项式逼近，是利用目标函数在若干点的函数值或导数值等信息，构成一个与目标函数相接近的低次插值多项式，用该多项式的最优解作为目标函数的近似最优解1用加步探索法确定一维最优化问题 的搜索区间，要求选取 2用对分法求解 已知初始单谷区间 ，按精度 计算3用Newton法求解 用第题求得的区间，按精度 计算12)(min30tttt21000，ht)3()(minttt53，ba1.012)(min30tttt01.0用黄金分割法求解 已知初始单谷区间 ，按精度 计算用抛物线插值法求解 已知初始单谷区间 )2()(minttt53，ba001.03728)(min23xxxxf001.020，ba演讲完毕，谢谢观看！