【教学课件】第十一讲非线性规划(三).ppt
第十一讲 非线性规划（三）,1 不使用导数的无约束寻优方法,1 不使用导数的无约束寻优方法（1）,不用导数的方法又称最优化搜索法，一般情况，利用导数迭代寻优比搜索法速度快。然而利用导数寻优常常面临两个困难：在多变量或复杂函数中，求导困难。执行方法前准备工作太多。因此，对使用者来说，非导数型搜索法还是常用的。,1 不使用导数的无约束寻优方法（2）,1直接搜索法坐标轮换法该法是在寻优过程中，每次先让其它变量不变，轮流的顺次令某一个变量变化并取函数f(X)极小点（或极大点）。起始点为X(0)，先沿第1个坐标方向e1进行搜索，得最佳步长(0)及最优点X(1)，使满足：f(X(0)+e1)=f(X(0)+(0)e1)=f(X(1)即 X(1)=X(0)+(0)e1,1 不使用导数的无约束寻优方法（3）,然后以X(1)为起点，沿e2坐标搜索，得最优解X(2)，即(X(1)+e2)=f(X(2)，X(2)=X(1)+(1)e2 直到en为止，得X(n)：min f(X(n1)+en)=f(X(n1)+(n1)en)=f(X(n)即 X(n)=X(n1)+(n1)en若X(n)X(0)1，则停止，得最优解X(n)=X*，否则，以X(n)为起点（令X(0)=X(n)）重新按上述步骤搜索。,1 不使用导数的无约束寻优方法（4）,这种方法简单、直观，但对于山脊形函数或自变量间有大的交互作用不适用。例如图4-11所示函数就不宜用该法寻优。,1 不使用导数的无约束寻优方法（5）,步长加速法(Hooke and Jeeves method)或模式搜索法（Pattern Search method）。该法为改进坐标轮换法而设计，方法搜索简单（不在某方向上取极值点）。其主要分两步进行：环绕基点的“探测搜索”，称I型搜索。在选择的极小化方向上的“模式搜索”。又称II型搜索。第一步：先给出X的初始值X(0)及每步增量X值，然后按增量变化，求出下一个较好点。其方法为（都以求极小点为例）：,1 不使用导数的无约束寻优方法（6）,先令x1(0)改变x1(0),即x1(1)=x1(0)+x1(0)，若fX，则以x1(0)+x1(0)作为X新元素分量；否则，令x1(1)=x1(0)x1(0)，若fX就令x1(0)x1(0)为新元素分量；若都不能使f fX，就仍令原X(0)为新元素，然后按同样方法把X2(0)试采改变一个X2(0)值，直到变化n次，找到一个新点X(1)，便完成了“探测搜索”。第二步：以新点为基点，连接，按此矢量方向进行模式搜索或加速移步，模式搜索得到X(2)后，再进行II型探测搜索，就得到新点X(3)，,1 不使用导数的无约束寻优方法（7）,若fX(3)fX(1)，说明模式搜索成功，否则失败。第三步：若模式搜索成功，继续向前搜索；否则，返回上一点，缩小步长继续探测搜索。例4-15求解下述无约束极值问题max fX=max,起始点选X(0)=2.00，2.80T，初始X选为0.60，0.84T fX(0)=f2.00，2.80=0.059该例题求解过程如图4-12所示。,1 不使用导数的无约束寻优方法（8）,图4-12 模式搜索法例题,1 不使用导数的无约束寻优方法（9）,2可变多面体法正多面体法例如，已知两维变量函数f(X)的等位线示于图4-13，内圈比外圈函数低。,图4-13 极小化f(X)时得到的正单纯形序列,1 不使用导数的无约束寻优方法（10）,其思路为，首先取3个点（n+1=2+1）X(1)，X(2)，X(3)，并计算函数值f(X(1)，f(X(2)，f(X(3)。然后比较大小（这三个点称为初始正多面体）。发现f(X(3)最大，舍去f(X(3)，找出余下两点X(1)和X(2)的形心点，连结X(3)与形心点并延长找出X(3)关于形心点的对称点X(4)，再用X(1)，X(2)和X(4)构成新的正多面体，继续前述步骤，直到找出极小点为止。图4-13中描绘了寻找f(X)极小点的正多面体序列。,1 不使用导数的无约束寻优方法（11）,可变多面体法该法在迭代过程中，不保持每步都为正多面体，而是根据情况改变形状，故称可变多面体法。其算法步骤如下：设 Xi(k)=x i1(k)，x ij(k)，x in(k)T，i=1，n+1是搜索第k阶段（k=0，1，）上n维欧氏空间的第i个顶点，其目标函数为fXi(k)首先计算n+1个顶点函数值并找出函数最大及最小的点Xh和Xl，即：,1 不使用导数的无约束寻优方法（12）,fXh(k)=max fX1(k)，fXn+1(k)fXl(k)=min fX1(k)，fXn+1(k)找出去掉Xh后的n个项点的形心坐标 j=1，2，n其中，j 各坐标方向。初始多面体通常选为正多面体，然后通过计算进行四步操作：,1 不使用导数的无约束寻优方法（13）,i)反射Xn+3(k)Xn+2(k)(Xn+2(k)Xh(k)0称反射系数，=1时可保持正多面体；1说明反射点可伸缩，通常取=1。ii)扩大若fXn+3(k)fXl(k)，则扩大战果，令Xn+4(k)Xn+2(k)Xn+3(k)Xn+2(k)为扩大系数，通常取=2。,1 不使用导数的无约束寻优方法（14）,若fXn+4(k)fXi(k)说明反射点值仍较大，则应收缩进去，即Xn+5(k)Xn+2(k)+Xh(k)Xn+2(k)01为收缩系数，一般取0.5且用Xn+5(k)取代Xh(k)。,1 不使用导数的无约束寻优方法（15）,iv)缩减 如果fXn+3(k)fXh(k)，需将所有矢量Xi(k)Xl(k)缩减一半（i=1，2，n+1），即都向最小点靠近。Xi(k)=Xl(k)+0.5Xi(k)Xl(k)i=1，2，n+1v)其余情况 令Xn+3(k)取代Xh(k)。这样便又构成新的多面体，重复上述步骤继续下去，直到多面体小到给定精度为止。其结束规则为：,其中，给定精度,1 不使用导数的无约束寻优方法（16）,3Powell法（鲍威尔法）（略）,
