清华大学运筹学课件非线性规划_2

《清华大学运筹学课件非线性规划_2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、直线搜索问题条件：已知和可行下降方向nX0DR精确搜索：求解单变量优化问题min()tfXt(D)0s.t.XtD0t0非精确搜索：找到一个tˆ0满足Xt0ˆˆˆD,()(t0)t0，并且不能太小tˆ其中0，由于D是下降方向，所以(0)0精确搜索的基本途经1）确定初始区间用试探法确定一个单谷区间()t可用步长加倍或减倍的方法2）逐步压缩区间按照一定规则在上述区间内选点，通过计算并比较这些点上的函数值逐步缩小包含局部最优解的区间直至区间长度小于给定阈值区间压缩原理已知闭区间[,]ab是单谷

2、区间，在其内部任取两点ab11，计算(),()ab11，如果()()ab11，局部最优解在区间[,]ab1，否则局部最优解在区间[,]ab，两种情况均能压缩区间1()t()tttaabbaabb1111第一种情况第二种情况精确搜索的0.618法的原理基本想法：每计算一个函数值能将区间压缩一个固定比值cta1t2batttb312tacba2batabttacta221212c510.6181cc2在单谷区间a,b搜索局部最优解的0.618法1）确定误差阈值及满足n

3、1的0.618ban2）令aa,bb003）对于k1,2,,n依次完成以下运算a）令tkak10.618bk1ak1（只需算一个）tbkk110.618bakk1b）计算tk和tk中未知的数值c）比较tk和tk的大小确定ak,bk4）取所求局部最优解为0.5abnn斐波那契（Fibonacci）法（最优选点方法）用Fn表示利用n点函数值能将其压缩为一个单位长度的最大初始区间长度，即，通过计算n点函数值，可以把长度为Fn的初始区间压缩为单位长度区间，但只要

4、初始区间长度大于F就不能做到这一点n压缩区间至少需要计算两点函数值，所以FF101当n2时，由于两个分点可以任意接近中点，如下面的t1和t2所示，所以能将两个单位的区间压缩为一个单位的区间，即F22t1t2112前三个数的关系F1,FFF1,F01210一般情况下，F,F,F必须满足下图所示关系nn1n2tta12bFFn1n1Fn()tt12()()tt()12at3t1t2bat1t2t3bFn2Fn2Fn2Fn2Fn1Fn1bttaF12n1FFF,nnn12babaF

5、n如何确定分点数n？假设初始区间是a,b，容许误差是0将视为一个单位的长度，则在a,b中一共有ba个单位长度，只要取n为满足baFn的最小整数，通过计算n个分点的函数值，一定能将包含最优解的区间压缩为不大于一个单位的长度，即小于或等于在单谷区间a,b搜索局部最优解的斐波那契法11）确定误差阈值以及满足Fnba的n2）令aa,bb003）对于k1,2,,n1依次完成以下运算（只需算一个）a）令tkak1FnkFnk1bk1ak1tbkk11FFnknk

6、bak1k1b）计算tk和tk中未知的数值c）比较tk和tk的大小确定ak,bk4）取所求局部最优解为0.5abn1n10.618法和斐波那契法的关系FFnn2由FFF可得1nn1n2FFn1n1Fn1在上面右式令n并定义Flim*nFn12可得1F*等价于F*F*10F*1解二次方程得正数解F510.618*2所以0.618法实际上就是用斐波那契法中分数数列的极限代替每个分数值所得到的方法利用导数的精确搜索算法（区间对分法）如右图，单

7、谷区间[,]ab一定()t满足()0,()0abtatb*取，ta0.5b若()0t，()t将区间压缩为[,]at，否则将区间压缩为[,]tbabtt*这种方法区间压缩比等于0.5，比仅计算函数值的最好方法斐波那契法好，实际效果取决于导数计算量利用二阶导数的精确搜索算法（Newton法）()t()tatatt*t1bt*t2t1b如上左图，在b点用切线近似()t，求该切线的零点切线方程：gt()()b()(btb)如上所示()bgt()0tb11单谷区间()b()

8、t一定收敛t1再在1点重复上述过程tt21()t1非精确搜索的Goldstein法原理(0)0,0mm112()tgt()