《第六章 约束规划.doc》由会员分享，可在线阅读，更多相关《第六章 约束规划.doc（22页珍藏版）》请在金锄头文库上搜索。
1、第六章 约束优化方法工程实际优化问题绝大多数属于约束非线性规划问题，其一般数学表达式为：求解方法可分为：直接法和间接法。两类方法的特点见表1分类举例优点缺点应用场合直接法坐标轮换法随机方向搜索法复合形法算法简单、直观计算量大，收敛慢维数低，函数复杂，精度要求低的优化问题间接法简约梯度法惩罚函数法序列二次规划收敛快，整体计算量小公式较复杂大型优化问题6.1 约束随机方向搜索法6.1.1 基本原理在可行域内选一初始点X0，以一初始步长沿一随机方向S1，求得探索点X。S1应保证X在可行域内且使目标函数值下降，即新点应有可行性和下降性。改变步长，继续在S1方向上探索，得到S1方向上的最优点X1。以X1
2、为初始点，在另一随机方向S2上重复上述过程，得到S2方向上的最优点X2。如此重复下去。当某一成功点X*沿着N（N=50500）个随机方向的探索均失败时，以X*为最优解。6.1.2 初始点的选取要求初始点可行点。当约束条件比较简单时，可人为确定；当约束条件复杂时，人为方法比较困难，可随机选取，即利用计算机产生的伪随机数来生成初始点。具体方法为：设设计变量的分量xi在取值范围为区间ai,bi，qi为区间（0，1）内的随机数，则xi的随机数为 由此可得到X所有分量随机数，然后将X代入约束条件中检验，若满足所有约束条件，则X是可行点。否则应重新选取初始点。6.1.3 随机搜索方向的产生以二维问题为例，
3、说明随机搜索方向的产生方法。若y1、y2为区间-1，1上两个随机数，则向量y1,y2可为平面内的任意方向。取向量y1,y2的单位向量e则e的端点位于单位圆的圆周上。对于三维问题，单位向量e的端点位于以单位长度为半径的球面上。上式中要求y1、y2在区间-1，1内随机取值，若计算机只能产生0,1区间内的伪随机数ri，可用下式将其转换为-1,1区间的伪随机数：6.1.4 举例例：用约束随机方向搜索法求解解：人工选取一初始点X0=5，5T，初始点在可行域内。相应的目标函数值为F(X0)=50。第一次迭代1)产生两个伪随机数，求出第一个随机方向。生成两个伪随机数r1=0.9, r2=0.2由此得第一个随
4、机方向为：2)求第一个迭代点第一个迭代点表达式为：式中a为步长。将X1的表达式代入目标函数中，进行一维搜索，令目标函数对步长a的一阶导数为0，即可求出沿e1方向的最优步长。第一个迭代点为：3）检验X（1）点是否满足约束条件g(X(1)=24.2+5.6=1412，X（1）满足约束条件，是可行点。相应的目标函数值为:第二次迭代以X1为初始点，重新生成随机搜索方向e2。（以下过程略）6.2 复合形法6.2.1 复合形法的基本原理在n维空间的可行域中选取k个设计点（通常取n+1k2n）作为初始复合形的顶点，然后比较复合形各顶点目标函数值的大小，目标函数值最大的点为坏点，以坏点之外的点的中心为映射点为
5、中心，求出坏点的映射点。一般映射点优于坏点，以映射点代替坏点，构成新的复形。如此循环，使复合形不断向最优点移动和收缩。当收缩到复合形的各个顶点与形心非常接近、满足迭代精度要求时为止。最后输出复合形顶点中目标函数值最小的顶点为近似最优点。如图二维约束优化问题，n=2, 取4个顶点构成初始复合形，设这4个点中目标函数值最大的点为X1 ，记为XH，目标函数值最小的点为X3，记为XL。丢弃XH点，求另外3点的中心XC,连接XC和XH，在连线上确定出映射点XR。式中为映射系数，一般1，通常取=1.3。 若XR在可行域内，且XR的目标函数值优于XH，则以XR替换XH形成新的复合形，重复上述过程。若XR不满
6、足上述两个条件，则将映射系数减半，可以多次减半。若变得很小仍不能使XR满足条件，可以次坏点代替坏点进行映射。在求映射点之前，若XC在可行域之外，则可行域可能是一个非凸集，这时可由XC与XL构成一个超立方体（二维情况下为长方形），在该区域内重新利用伪随机数产生k个顶点，构成新的复合形。6.2.2 初始复合形法的产生对于维数较低的简单优化问题，可以人为给出初始复合形顶点。对于复杂优化问题，多采用随机方法产生初始复合形。过程如下：（1） 利用随机函数，生成第一个顶点，确保该顶点在可行域内。 （2） 产生其他（k-1）个随机点若X2、X3、Xq都在可行域内，则它们可作为初始复合形的顶点。若Xq+1点不
7、在可行域，如图， 先求出已在可行域中的q个顶点的中心XD，然后在XD 与Xq+1连线上移动Xq+1点，使Xq+1到XD的距离减半，即：若推移后Xq+1点进入了可行域，则将Xq+1点作为初始复合形的第q+1个顶点，否则继续缩短Xq+1到XD的距离。6.2.3复合形法举例例：用复合形法求解约束优化问题，迭代精度为0.01。解：n=2,取复合形顶点数k=2n=4。（1） 人为给出4个复合形顶点。经检验4个顶点均在可行域内。（2） 进行迭代，获得新的复合形。求4个点的目标函数值：知.计算除坏点外所有顶点的中心XC：经检验XC在可行域内。求XH的映射点XR，取映射系数为1.3：经检验，映射点XR在可行域
8、内。因F(XR)=5.1092 F(XH)，故用映射点替换X3，构成新的复合形：4个点的目标函数值为：最坏点为X4，最好点为X3。（3） 检验迭代终止条件常用各顶点与好点的目标函数之差的均方根小于误差作为终止迭代条件，即若满足以上条件，XL为最优解。对于本题，不满足迭代终止条件，需继续迭代。在新的复合形中重复上述过程6.3 惩罚函数法惩罚函数法的基本思想是：根据约束条件构造惩罚函数，并将其加到目标函数中，将约束问题转化为无约束问题。惩罚函数法可分为外罚函数法、内罚函数法和混合函数法。6.3.1 外罚函数法6.3.1.1 外罚函数法基本原理该法的主要特点是惩罚函数定义在可行域外部，求解过程中从可
9、行域的外部逐渐逼近原来有约束优化问题的最优解。它既可用于求解不等式约束优化问题，也可用于求解等式约束问题。先介绍这种方法对不等约束问题的处理。设原约束优化问题为：构造一般形式的外罚函数为式中第二项为惩罚项，其中k是惩罚因子，在迭代过程中k的取值会越来越大取值，即k是一个递增的正数列：由此可知，当X在可行域内和约束边界上时，无论k取何值，惩罚项均为0。当X违反约束条件时，无论k取何值，惩罚项不为0，表明X在可行域外面，且X离约束边界越远，惩罚项的值越大。 当k由小变大时，迭代点必需由边界外向可行域靠拢才能使目标函数有最优解。例：用外罚函数法求解下列约束优化问题解：构造惩罚函数，将原问题转化为无约
10、束优化问题，即：选择一个适当的初始外点X0和一个初始惩罚因子0，用无约束优化问题求解方法（如牛顿法、变尺度法等）解出与之对应的最优值，然后令k不断增大，当k趋于无穷大时所得X即为最优解。但本题比较简单，可用解析法求解,即令得到：当k趋于无穷大时，X=1，P=1.此二值即为最优解和最小值。若优化问题中约束条件为等式约束，也可作类似处理，得到一个罚函数综合不等式约束和等式约束，得到一般约束优化问题的外罚函数表达式：6.3.1.2 约束裕量问题实际计算中惩罚因子k不可能达到无穷大，因此最后所得的最优点也就不可能收敛到原问题的最优点，而是落在可行域的外部，这就不能严格满足约束条件。为克服外罚函数法的这
11、一缺点，引入约束裕量，将可行域边界向内收缩一个微量，即重新定义约束条件：式中即为约束裕量，不能取值过大，以免所得结果与最优点相差太远，一般取。6.3.1.3 外罚函数法的迭代步骤（1） 给定初始条件：初始点，初始惩罚因子，迭代精度，惩罚因子递增系数。（2） 用无约束优化方法求罚函数的极小点（3） 用点距准则或函数值下降准则检验相邻两次迭代中的极小点是否满足迭代终止条件。若不满足，则增加惩罚因子，用当前极值点作为初始点，重新迭代。6.3.1.4 外罚函数法应用中的问题（1） 初始点可以在可行域内，也可以在可行域外，对实际计算很方便。（2） 初始惩罚因子和递增系数的选取对方法的有效性和收敛速度都有
12、影响。取值过小，会增加迭代次数，取值过大，罚函数的性态会变差，导致求解困难。6.3.2 内罚函数法特点为：只适用于不等式约束，惩罚函数定义在可行域的内部，每一迭代点都在可行域内部移动，并逐渐逼近原约束优化问题的最优解。（迭代过程的每个一设计点都对应一个可行方案）内罚函数可构造为：惩罚因子是一个递减的正数数值，即：例：用内罚函数法求解下列约束优化问题 解:构造内罚函数为用解析法求极值6.3.3 混合罚函数法混合罚函数法是内罚函数法和外罚函数法的综合。对于p个等式约束，构造外罚函数，对m个不等式约束，构造内罚函数，得到混合罚函数为式中，使用统一的惩罚因子，它是一个递增数列：例：求下列优化问题的混合
13、罚函数罚函数为式中，惩罚因子是一个递增数列：。罚函数法原理简单，算法易行，适用面广，可以和各种有效的无约束最优化方法结合。但也存在问题：从理论上讲，只有当惩罚因子趋于无穷时或0时，算法才收敛，因此收敛较慢。另外，当惩罚因子的初始值选取不当时，惩罚函数可能变得病态，使计算发生困难。6.4 增广乘子法6.4.1 拉格朗日乘子法拉格朗日乘子法是一种古典的求约束极值的间接法。设有具有等式约束的优化问题：(不等式约束也可以通过引入松弛变量转换为等式约束)得到拉格朗日函数:式中为拉格朗日乘子，为变量，故拉格朗日函数共有（n+p）个变量。为求L(X, )的极值，令L(X, )=0，得到(n+p)个方程：拉格
14、朗日乘子法看似简单，但实际存在许多问题：其一，当L(X, )为非凸函数时，求得的最优点可能是鞍点，因为海塞矩阵H不一定为正定；其二，对于大型非线性优化问题，(n+p)个方程为高次方程组，用数值方法求解(n+p)个方程的难度几乎与求解优化问题本身的难度相当；其三，还必须分离出程组的重根。因此，拉格朗日乘子法不是一种有效的求解约束优化问题的方法。6.4.2 增广乘子法增广乘子法来源于拉格朗日乘子法，是拉氏乘子法与罚函数法的综合。其搜索策略与外罚函数相仿。具体做法是，用外罚函数替代原目标函数，原约束条件不变，得到一个增广极值问题，然后构造该问题拉格朗日函数。原问题为：增广极值问题为：可以证明，增广极值问题不仅与原问题同解，而且与原问题有相同的拉格朗日乘子。增广拉格朗日函数：当r足够大时，L的海塞矩阵为正定，L必有极小值。但确定r的临界值较困难，实际求解时是采取交替修改惩罚因子r和拉格朗日乘子，经反复迭代得到足够大的r和最优的。迭代公式的来历如下：对增广拉格朗日函数求极值：若对原问题采用拉格朗日函数求极值，得：比较以上两式，得到迭代公式：式中，惩罚因子是一个递增数列：,一般取为等比数列，比例系数为c=10。令,Powell等人证明，当r足够大时，必能满足这时r不需要再增大。r一般
