4_一维搜索法

第一章Matlab概述★搜索区间及其确定方法★对分法★Newton切线法★黄金分割法★抛物线插值法第四章一维搜索由第一章关于求解优化问题的迭代法知道，从已知迭代点出发按照基本迭代公式来求解最优化问题，其关键在于如何构造一个搜索方向和确定一个步长，使下一迭代点处的目标函数值下降，即．现在我们来讨论，当搜索方向已经确定的情况下，如何来确定步长？步长因子的选取有多种方法，如取步长为常数，但这样选取的步长并不最好，如何选取最好步长呢？实际计算通常采用一维搜索来确定最优步长．kkkkPtXX1第四章一维搜索对无约束最优化问题)(minXfnRX当已知迭代点和下降方向时，要确定适当的步长使比所下降，即相当于对于参变量的函数kXkPkt)(1kXf)(kkkPtXf)(kXft)()(kktPXft要在区间上选取使，即],0[ktt)()(1kkXfXf)0()()()(kkkkkXfPtXft上面的分析，实质上是单变量函数关于变量的一维搜索选取问题，故通常叫做一维搜索．按这种方法确定的步长又称为最优步长，这种方法的优点是，它使目标函数值在搜索方向上下降得最多．()ttkt第四章一维搜索)(1kkkPXlsX，为了简便起见，我们用记号表示从点出发沿方向对目标函数作直线搜索所得到的极小点是．kXkP)(Xf1kX（4.1）在目标函数确定的条件下（4.1）等价于如下两式：kkkktkktkkkPtXXttPXfPtXf1)(min)(min)()(Xf原因：作直线搜索，搜索方向和梯度方向刚好正交。若从出发，沿方向进行一维搜索得极小点，则该点处的梯度方向与搜索方向之间应满足kXkkkkPtXX1)(1kXfkP0)(1kTkPXf(4.2)第四章一维搜索4.1搜索区间及其确定方法下面引入如下的搜索区间概念.定义4.1设，并且])0[)(0[max**11tttRR，，，：)(min)(max0*tttt若存在闭区间使，则称是问题（4.3）的搜索区间．])0[])([0[][maxtbaba，，，，][*bat，][ba，设一维最优化问题为)(minmax0ttt（4.3）简言之，一个一维最优化问题的搜索区间，就是包含该问题最优解的一个闭区间．通常，在进行一维搜索时，一般要先确定出问题的一个搜索区间，然后在此区间中进行搜索求解．第四章一维搜索下面介绍确定问题搜索区间的法—加步探索法先选定一个初始点和初始步长．然后，沿着轴的正方向探索前进一个步长，得到新点．若目标函数在新点处的值是下降了，即)()(000tht)()(000tht则下一步就从新点出发加大步长，再向前探索．若目标函数在新点处的函数值上升，即00ht则下一步仍以为出发点以原步长开始向轴的负方向同样探索．当达到目标函数上升的点时，就停止探索，这时便得到一个搜索区间．0t第四章一维搜索加步探索法算法的计算步骤：(1)选取初始数据．选取初始点，计算．给出初始步长，加步系数，令．])0[)(0[max00ttt，或，)(00t00h10k(2)比较目标函数值．令，计算，若，转(3)．否则转(4)．kkkhtt1)(11kktkk1(3)加大探索步长．令，同时，令，转(2)．kkhh1,ktt,1kktt1kk（4）反向探索．若，转换探索方向，令，转（2）．否则，停止迭代，令输出．0k1ktt,kkhh11min{}max{}kkattbtt，，，第四章一维搜索注意：在加步探索法中，一般建议．若能估计问题的最优解的大体位置的话，初始点要尽量取接近于问题的最优解．在具体运用加步探索法时，有时还要考虑一些细节问题．例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理．2第四章一维搜索单谷区间与单谷函数定义4.2设，闭区间．若存在点，使得在上严格递减，在上严格递增，则称是函数的单谷区间，是上单谷函数．11RR：1][Rba，][*bat，)(t][*ta，][*bt，][ba，)(t)(t][ba，对单谷区间和单谷函数的理解（1）图形特征；（2）连续形；（3）单谷区间一定是搜索区间。第四章一维搜索单谷区间和单谷函数有如下有用的性质：定理4.1设是的单谷区间，任取并且．（1）若有，则是的单谷区间．（2）若有，则是的单谷区间．证明略][11baRR，，：)(t][21batt，，12tt)()(12tt][1ta，)()(12tt][2bt，)(t)(t定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间．换句话说，利用这个定理可以把搜索区间无限缩小，从而求出极小点．以下介绍的几种，一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解．第四章一维搜索4.2对分法基本原理min()t)(mintbta确定一个有限搜索区间][ba，设在已获得的搜索区间内具有连续的一阶导数．11RR：][ba，因为可导连续有最小值令，总可求得极小点．0)(t*t不妨设在上是单减函数；在上是单增函数．则)(t)(*ta，)(*bt，当时，，故；)(*tat，0)(t0)(a当时，，故；)(*btt，0)(t0)(b第四章一维搜索迭代步骤已知，表达式，终止限．)(t)(t(1)确定初始搜索区间，要求．],[ba'()0'()0ab，(2)计算的中点．],[ba)(21bac(3)若，则，转(4)；若，则，转(5)；若，则，转(4)．0)(cca0)(cct*0)(ccb(4)若，则，转(5)；否则转(2)．||ba)(21*bat(5)打印，结束．*t说明：由于每次迭代都取区间中点，使区间长度缩短一半，故名曰对分法或二分法。第四章一维搜索4.3Newton切线法基本原理设在已获得的搜索区间内具有连续二阶导数，求11:RR][ba，)(mintbta同理，因为在上可微，故在上有最小值，令．)(t][ba，)(t][ba，0)(t不妨设在区间中经过k次迭代已求得方程的一个近似根．过作曲线的切线，其方程是][ba，0)(tkt))(,(kktt)(ty))(()(kkktttty（4.4）然后用这条切线与横轴交点的横坐标作为根的新的近似,令可解出1kt0y)()(1kkkktttt—Newton切线法迭代公式第四章一维搜索迭代步骤已知，表达式，终止限．)(t)(t(1)确定初始搜索区间，要求．],[ba'()0'()0ab，(2)选定．0t(3)计算.000'()/()tttt(4)若，则，转（3）；否则转（5）．||0tttt0(5)打印，结束．()tt，第四章一维搜索有关说明如果初始点选得适当，Newton切线法收敛速度很快，通常只需几次迭代就可以得到满足一般精度要求的结果，但其也有缺点．第三，即使曲线比较正常，初始点的选取也必须适当．第二，当曲线有较复杂的弯曲时，这种方法也往往失效．第一，需要求二阶导数．若是多维优化，还要涉及Hesse矩阵．第四章一维搜索4.4黄金分割法基本原理所谓黄金分割就是将一线段分为二段时，要求整段长L与较长段x的比值正好等于较长段x与较短段L-x的比值，即xLxxL于是有，解出其正根022LLxxLLx618.0215用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段．如此继续下去可将单谷区间无限缩小．][ba，21tt，][ba，第四章一维搜索迭代步骤根据黄金分割的思想，在上选取二点将区间长度进行黄金分割，即][ba，21tt，ab)(618.01abat)(382.02abat计算与的值，并根据与的值的大小关系分情况讨论：)(1t)(2t)(1t)(2t（1）若，说明是好点，于是把区间划掉，保留，置新的区间；)()(21tt1t][2ta，][2bt，][][211btba，，（2）若，说明是好点，于是把区间划掉，保留，置新的区间；)()(21tt2t][1bt，][1ta，][][111taba，，（3）若，则应具体分析，看极小点可能在哪一边再决定取舍．在一般情况下，可同时划掉和，仅保留中间的，置新的区间．)()(21tt][2ta，][1bt，][12tt，][][1211ttba，，第四章一维搜索接下来是在留下的区间内找好点．重复上面的步骤，直到搜索区间小于给定的允许误差为止．这样就得到黄金分割法迭代算法：][11ba，][iiba，0已知，常数0.382，终止限．)(t(1)确定的初始搜索区间．)(t][ba，(2)计算．)()(222tabat，(3)计算．1211()tabtt，(4)若，则打印，结束；否则转(5)．||21tt221*ttt(5)判别是否满足：若满足，则置2112122，，ttta然后转(3)；否则，置)()(22221211tabttttb，，，，然后转(4)．第四章一维搜索说明：黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点．该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛．第四章一维搜索4.5抛物线插值法基本原理考虑一维搜索问题)(min21tttt假设是定义在区间上的单谷函数．首先用试探法在上找一点，使之满足)(t][21tt，][21tt，0t)()()()(0201tttt，通过目标函数曲线上的三个点))(())(())((220011tttttt，，，，，作它的二次拟合曲线2210)(tataatP第四章一维搜索由于上述三个点既是目标函数曲线上的点，又是二次拟合曲线上的点，故有方程组)(t)(tP．，，)()()()()()(222221020202010012121101ttataatPttataatPttataatP（4.5）将方程组（4.5）中的消去，得0a22110210102210220202()()()()()()()()attattttattatttt，．（4.6）从方程组（4.6）可解出待定系数))()(()()()()()()(1220012202102122122201ttttttttttttttta))()(()()()()()()(1220012010121202ttttttttttttttta（4.7）（4.8）第四章一维搜索对于二次拟合函数，我们很容易求得它的极小值点．令，即，从中解出2210)(tataatP0)(dttdP0221taa212aat（4.9）将式（4.7）与式（4.8）代入式（4.9）得．)()()()()()()()()()()()(21220101212022021021221222021ttttttttttttttttttaat（4.10）用区间上二次拟合函数的这个极小值点作为目标函数在该区间极小值点的一个估计值．若和已充分接近，即成立时,就可被看作是在区间内近似最优解；否则应缩短区间，按照值保持两头大、中间小的原则构成新的三点，继续上述过程，直至终止条件成立为止．],[21