第四章非线性规划4-复合形法

第四节 复合形法复合形法(Complex Method)是 1965 年由博克斯(Box)提出，后经古恩(Gwin)修正的解非线性规划的一种直接搜索法。如同随机方向搜索法一样在确定搜索方向时，它不需要函数的梯度信息，它是求解非线规划中的一种简单适用的方法。一、基本原理对于约束优化问题 (0)min . 1,23,nuiiifXRstgmaxb使用迭代格式 1= ,kkkkXXS所谓复合形是指在 n 维设计空间的可行域内由 k(n+12n)个顶点所构成的多面体。复合形法是一种在可行域内直接的求优方法。利用复合形各顶点处目标函数值的大小关系，判断目标函数值的下降方向，不断丢掉函数值最大的所谓最差点，代之以既使目标函数值有所下降又能满足所有约束条件的一个新点，从而不断地构成新的复合形。如此重复计算，使新的复合形不断地向可行域的最优点移动和收缩，直至得到满足收敛准则的近似解为止。 由于对复合形不必保持规则图形，顶点数较多，因此可以求解非线性的约束问题，面且计算稳定可靠。但不能用于解含有等式约束的问题。二、复合形的迭代步骤一）确定复合形的顶点复合形法是一种在可行域内直接的求优方法，要求第一个复合形的 k 个顶点都是可行的。对复合形的顶点数一般推荐取 k=2n，当 n 计算问题的维数较多 (如 n5)时，可取kn+1。如果复合形顶点数少了，一旦出现丢失顶点现象就可能会出现降维搜索而找不到真正的最优点。初始复合形的确定方法有如下几种：(1)给定 k 个初始顶点。由设计者预先选择 k 个设计方案，即人工构造一个初始复合形。由于 k 个顶点都必须满足所有的约束条件，因此当设计变量数目较多或约束条件比较复杂时，这样做可能是很不方便的或者是很困难的。(2)给定一个初始顶点，随机产生其他顶点。如果用常规设计方法能取得一个设计方案，此方案虽然不是最优的，但却是一个可行的。则其他 k-1 个顶点可用随机法产生 ()(-) 1,2 1,2jjiiixarbinjk 式中 各设计变量的 的上、下界限，一般取边界约束值；,i ix0,1区间内服从均匀分布的伪随机数。jir这样随机产生的 k-1 个顶点，虽然可以满足边界约束条件，但不一定能满足性能约束条件，还必须逐个进行检查，把不满足约束条件的顶点移到可行域内。设已有 q 个顶点满足全部约束条件，先求出 q 个顶点的中心点即()1 ,2qtjiijxn ()()1 ,2tjjXin然后将不满足约束条件的点 向中心点 靠拢，即(1)q()t（复合形的收缩运算）(1)()()()0.5qttX若还不满足约束条件，则可以重复用上式计算。 （即以新的 进行收缩）(1)qX只要中心点 是可行点， 点经逐步向()t (1)qX靠拢，最终总能成为一个可行顶点。对随机产生()tX的各个顶点进行这种处理后，最后可取得 k 个初始可行顶点，从而构成初始复合形。事实上，只要可行域是凸集，其中心点必为可行点，因而用上述方法可以成功地在可行域内构成初始复合形。如果可行域为非凸集那就有失败的可能，当中心点处于可行域之外时，就应该缩小随机选点的边界域，重新产生各顶点。(3)随机产牛全部顶点。二）计算各顶点函数值最差点（函数值最大的点）()HX()()maxHkfXfX最好点（函数值最小的点）()L()()inL复合形的几何中心()C即()()1kcjjX()1 ,2kcjiijxn三）复合形法运算，构造新的复合形复合形不断地向可行域的最优点移动和收缩，是通过反射、收缩、扩展和重构复台形等四种运算来实现的。1.反射运算去掉最坏点后所有点的几何中心点 ()oX()1kojjHX反射就是沿最坏点 和 的连线方向上取映射点 ，即()HX()o()RX()()()()Ro式中 称为反射系数一般 ，例如可取 （Box 建议） 。如果 满足所有约束条件，11.3()RX且 ，即可用 代替 组成新复合形，完成一次迭代。如果 不满足约()()RHfXf()RX()H ()束条件，或不满足 ，则将反射系数 减半重新计算 ，若仍不满足要求，可()()Rf()R继续将 减半，直到 减到很小( 例如小于 10-5)还不满足要求时，那就只能放弃这一方向，改用次坏点的映射方向，重新寻求满足条件的映像点。()G2.扩展运算若初次确定的反射点 ，其目标函数值比最好点 的还小，即 时，说()RX()LX()()RLfXf明沿此方向映射的效果显著，有进一步扩张的必要，以探求更好的点。即按下式计算新点（扩展运算）()()()()EooX式中， 称为扩展系数，一般多 。1如果 ，则说明扩展成功，用 替换 组成新复合形，完成本次迭代。()()ERffX()EX()R如果 ，则扩展失败，仍取原反射点 替换 组成新复合形。()()()()H3. 收缩运算若已找不到好的反射点，还可以从 到中心点 连线以内收缩寻找。()H()o按下式计算收缩点 ()MX()()()()MooHXX式中， 称为收缩系数，一般 。与扩展同样，如果 则收缩成功，01()()MHfXf用 替换 ，否则失败。()M()H4.重构若采取上述措施均元效，还可以采取向最好点 靠拢的措施，即：()LX()()()()0.5GLLGXX()()()()HH各顶点向最好点靠拢后再重新寻求新顶点。四）检查停机准则在迭代计算中，由于复合形不断向最好点移动和缩小，因此当复合形的 k 个顶点 的目标函数值()kX的与中心点 均方差很小时，则停止迭代()CX1()()21kjjff或 ()()1maxjCjkX五）获取最优解满足停机准则后取函数值最小的顶点作为最优解。三、算法框图四、讨论由于复合形法在迭代过程中不必计算目标函数的一、二阶导数，