直接搜索数值解法演示文稿

直接搜索数值解法演示文稿当前1页，总共35页。优选直接搜索数值解法当前2页，总共35页。1绪论无约束最优化问题的经典解法中，都必须求其函数的导数。但是很多实际问题往往难以求出目标函数f(X)关于X的偏导数。这时就放弃求偏导的方法，而直接从分析目标函数f(X)的特征、信息出发，构造一种逐次使目标函数值下降（或上升）的搜索方法。当前3页，总共35页。1绪论

搜索方法是迭代算法中的一种。它由搜索方向S(k)和步长因子αk构成每一次迭代的修正量，为决定其算法的好坏的重要因素。各种算法的区别在于确定S(k)与αk的不同，尤其是搜索方向。当前4页，总共35页。1绪论搜索方法主要分成两类：（1）直接搜索法——只需要进行函数值的计算与比较来确定最优化的方向和步长。（2）间接搜索法——需要利用函数的一阶、二阶导数及偏导数矩阵来确定最优方向和最优步长。当前5页，总共35页。2进退法进退法的基本思想是，每次搜索都要改变搜索的步长。对于求极小值问题，如果在第K次迭代沿某方向搜索成功，则函数值一定下降，下一步仍可按该方向搜索，而且可大步向前搜索；如果在第K次迭代沿某方向搜索失败，则函数值上升，应退回原地，下一步便按其相反方向，即向后退小步搜索。当前6页，总共35页。2进退法进退法可用来搜索最优点和搜索最优区间。搜索最优点的具体过程：从某点x0出发，步长取为h,比较两点函数值。（1）若f(x0)>f(x0+h)，则搜索成功；于是，下一步取步长为2h;若第k步的步长为nh,并搜索成功，那么，第K＋1步的步长就是2nh。（2）若f(x0)≤f(x0+h)，则搜索失败；于是，退回到x0之后，再后退并按(nh)/4或(nh)/3步长搜索，直到步长小于ε，停止搜索。当前7页，总共35页。2进退法进退法的程序框图当前8页，总共35页。3黄金分割法3.1黄金分割法的特点和步骤黄金分割法的基本思路：通过不断缩小单峰区间的长度来搜索目标函数的极小点，且是按可行域全长的黄金点——0.618选取两个新点，更新区间，这种寻优方法比任意取两点的消去法效果更好，寻优区间缩短的速度更快。当前9页，总共35页。3黄金分割法当前10页，总共35页。3黄金分割法黄金分割法有如下特点：（1）每次选取的λ1、λ2两点为对称点；（2）舍去两端任一段后，保留下来的λ在新区间仍占有着相应的位置；（3）舍去两端任一段，新区间的长度为原区间长度的0.618倍。（4）迭代n次以后，区间长度成为0.618nL.当前11页，总共35页。3黄金分割法当前12页，总共35页。4二次插值法当前13页，总共35页。4二次插值法例：求f(x)=8x2-2x+7的极小点解：在寻优区间[0,2]中间取点1，即取xa=0,xb=1,xc=2则有：f(xa)=7,f(xb)=13,f(xc)=35按极小点公式有：验证：由df(x)/dx=0

有16x-2=0,x*=0.125当前14页，总共35页。4二次插值法当前15页，总共35页。4二次插值法例：求minf(x)=ex-5x解：1)先按从求函数导数获得极值的方法有：可得：λ*=0.6092)再按二次插值法求解取λa=0,λb=1,λc=2则有：f(0)=e-5=-2.282,f(1)=e2-10=-2.611,f(2)=5.086由此可计算出λ0=0.531而原函数的λ*=0.609，现用二次插值法一步迭代的结果为0.531，精度不高，还有11％的误差，故还应继续进行迭代当前16页，总共35页。5有理插值法在某些情况下，当目标函数连续可导、存在极值点时，用0.618法迭代计算量大，而用二次、三次多项式去插值也不太合适，这时可采用有理插值法。所谓有理插值法，就是用一个有理函数（有限连分数形式）去拟和原目标函数，从而找出函数的驻点、导数的近似值的一种最优化的计算方法。当前17页，总共35页。5有理插值法有限连分数的基本概念：设a0为实数，a1,a2,…,an均为大于、等于1的实数，把分数：成为有限连分数。由于这种写法很占篇幅，故常用符号：表示。当前18页，总共35页。5有理插值法例如：当前19页，总共35页。5有理插值法（1）计算有理插值函数的公式当前20页，总共35页。5有理插值法则有：由这个迭代形式，要把xi与ai计算出来当前21页，总共35页。5有理插值法（2）计算驻点f’(x)=0的公式公式：当前22页，总共35页。5有理插值法（5）若当前23页，总共35页。6坐标轮换法坐标轮换法是一种最古老的多维搜索转一维搜索的算法。它的迭代过程是沿不同的坐标方向轮流地进行搜索。设初始点为X0,先只改变一个变量，保持其它变量为常数，进行一维寻优，得到第一个最优点X1；再换一个变量，同样进行一维搜索，得到第二个最优点X2。如此继续下去，逐步逼近。像“爬山”一样，一步一步地爬上顶峰。当前24页，总共35页。6坐标轮换法迭代公式：Xk+α*S=Xk+1式中S——搜索方向的单位向量；

α——步长，是个标量一维问题的方法可以拓展到多维问题：多维问题的计算程序：（1）给出初始点及精度ε当前25页，总共35页。6坐标轮换法当前26页，总共35页。7步长加速法坐标轮换法寻优时，当目标函数出现了“脊线”，本来沿脊线方向一步或较少步数可达最优，但因坐标轮换法总是沿平行于坐标轴方向搜索，不能沿脊线前进方向搜索，所以会浪费很多时间。并且，若从X0前进一步，恰好搜索到脊线上的X点，便会无法继续向前搜索，因而不能或很难找到最优点。当前27页，总共35页。7步长加速法可是，脊线方向却是到达最优点的有利方向。因此，遵循脊线方向爬山的方法正是步长加速法的基本思想。下面以二维为例，具体介绍这一方法的计算过程。当前28页，总共35页。计算过程：7步长加速法当前29页，总共35页。7步长加速法当前30页，总共35页。步长加速法编程容易、又可靠，但需要做大量的函数值的计算。主要缺点是：这种方法不能根据实际情况改变搜索方向，因而，收敛速度慢7步长加速法当前31页，总共35页。8单纯形算法单纯形算法作为直接搜索的数值解法之一，是利用单纯形的顶点，计算其函数值，按一定的规则进行探测性搜索。通过对搜索区内单纯形顶点的函数值进行直接比较，可以判断目标函数的变化趋势，确定有利的搜索方向和步长。此方法的核心是在选择新的较好的单纯形顶点的过程中，包含有反射、扩展、压缩三种类型的过程。当前32页，总共35页。单纯形算法的基本过程：（1）构造单纯形、计算函数值首先，以初始点X0为一点，沿某一方向按一定初始步长h取另外两个点，构造一个三角形，即二维单纯形HGL。然后，计算各顶点的函数值。8单纯形算法当前33页，总共35页。（2）反射过程若函数值fH>fG>fL,说明最差点H的反对称方向目标函数会有所改进，可作为下一步的搜索方向