第六章 约束规划.doc

第六章 约束优化方法工程实际优化问题绝大多数属于约束非线性规划问题，其一般数学表达式为：求解方法可分为：直接法和间接法。两类方法的特点见表1分类举例优点缺点应用场合直接法坐标轮换法随机方向搜索法复合形法算法简单、直观计算量大，收敛慢维数低，函数复杂，精度要求低的优化问题间接法简约梯度法惩罚函数法序列二次规划收敛快，整体计算量小公式较复杂大型优化问题6.1 约束随机方向搜索法6.1.1 基本原理在可行域内选一初始点X0，以一初始步长沿一随机方向S1，求得探索点X。S1应保证X在可行域内且使目标函数值下降，即新点应有可行性和下降性。改变步长，继续在S1方向上探索，得到S1方向上的最优点X1。以X1为初始点，在另一随机方向S2上重复上述过程，得到S2方向上的最优点X2。如此重复下去。当某一成功点X*沿着N（N=50500）个随机方向的探索均失败时，以X*为最优解。6.1.2 初始点的选取要求初始点可行点。当约束条件比较简单时，可人为确定；当约束条件复杂时，人为方法比较困难，可随机选取，即利用计算机产生的伪随机数来生成初始点。具体方法为：设设计变量的分量xi在取值范围为区间ai,bi，qi为区间（0，1）内的随机数，则xi的随机数为 由此可得到X所有分量随机数，然后将X代入约束条件中检验，若满足所有约束条件，则X是可行点。否则应重新选取初始点。6.1.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由此得第一个随机方向为：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）作为初始复合形的顶点，然后比较复合形各顶点目标函数值的大小，目标函数值最大的点为坏点，以坏点之外的点的中心为映射点为中心，求出坏点的映射点。一般映射点优于坏点，以映射点代替坏点，构成新的复形。如此循环，使复合形不断向最优点移动和收缩。当收缩到复合形的各个顶点与形心非常接近、满足迭代精度要求时为止。最后输出复合形顶点中目标函数值最小的顶点为近似最优点。如图二维约束优化问题，n=2, 取4个顶点构成初始复合形，设这4个点中目标函数值最大的点为X1 ，记为XH，目标函数值最小的点为X3，记为XL。丢弃XH点，求另外3点的中心XC,连接XC和XH，在连线上确定出映射点XR。式中为映射系数，一般1，通常取=1.3。 若XR在可行域内，且XR的目标函数值优于XH，则以XR替换XH形成新的复合形，重复上述过程。若XR不满足上述两个条件，则将映射系数减半，可以多次减半。若变得很小仍不能使XR满足条件，可以次坏点代替坏点进行映射。在求映射点之前，若XC在可行域之外，则可行域可能是一个非凸集，这时可由XC与XL构成一个超立方体（二维情况下为长方形），在该区域内重新利用伪随机数产生k个顶点，构成新的复合形。6.2.2 初始复合形法的产生对于维数较低的简单优化问题，可以人为给出初始复合形顶点。对于复杂优化问题，多采用随机方法产生初始复合形。过程如下：（1） 利用随机函数，生成第一个顶点，确保该顶点在可行域内。 （2） 产生其他（k-1）个随机点若X2、X3、Xq都在可行域内，则它们可作为初始复合形的顶点。若Xq+1点不在可行域，如图， 先求出已在可行域中的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在可行域内。因F(XR)=5.10922时，H为正定矩阵，故L有最优解。（1） 取r=8, =0,代入增广拉格朗日函数求其极值,令：得：检验是否满足条件,取的初始值为一较大值，如10。则有故不需要增大罚因子，仍保持为r=8。现求，由迭代公式得：(2)将=4，r=8代入L函数中求L的极值得：条件不满足，故增大罚因子，即r=8*10=80（3） 将=4，r=80代入L函数中求L的极值得：条件满足，故不需要增大罚因子现求，由迭代公式得将新的和r代入L函数中求L的极值得：,满足收敛条件，迭代终止。最优解为，f(X)=-0.000986。6.5 二次规划二次规划是指目标函数为二次型，约束条件为线性式的规划问题，即：设式中变量数为n，约束数为m。回顾库恩塔克条件：min f(x), xRns.t. gu(x) 0 (u=1,2,.,m) hv(x) =0 (v=1,2,.,p)如果x*是一个局部极小值点，则该点的目标函数梯度可表示成该点诸约束面梯度的线性组合。即： (2-13)式中q为X*处不等式约束面的数目；j为X*处等式约束面的数目。为非负乘子，也称拉格朗日乘子。若某个约束不起作用（即X*不在约束面上），则对应的为0.对于二次规划，K-T条件为：式中、分别为约束条件、变量的拉格朗日乘子，y为松弛变量。上式中的一、二式构成了一个线性方程组，可由单纯形法求解。但没有目标函数，可以在方程中引入伪变量，并构造一个伪目标函数。使伪目标函数为0，并将伪变量变成非基本变量，即得到方程的解。三、四两式表明，不能同时进入基变量，也不能同时进入基变量。例：用单纯形换基法求二次规划：解：将原问题改写成则C=-8,-10, D=2 0;0 2,A=3 2,b=6由 得：即K-T条件为：前三个方程为线性方程，变量个数为5，可用单纯形法求解。后三式表示相乘的两个变量不能同时进基。引入人工变量和伪目标函数建立单纯形表：将of行中与z1、z2对应的系数1、1变换为0：将of行中与r对应的系数-5变换为0，在该列生成一个基变量，即r列进基，z1列出基：x2列进基，z2列出基读出最优解clc;syms x1 x2 r u1 u2 y z1 z2 fhead=x1 x2 r u1 u2 y z1 z2 f;of=0 0 0 0 0 0 1 1 0;l1=2 0 3 -1 0 0 1 0 8;l2=0 2 2 0 -1 0 0 1 10;l3=3 2 0 0 0 1 0 0 6;head;of;l1;l2;l3 of=of-l1-l2; head;of;l1;l2;l3l1=l1/3;of=of+l1*5;l2=l2-l1*2;head;of;l1;l2;l3of=of+l2;l3=l3-l2;l2=l2/2;head;of;l1;l2;l3l3=l3*3/13;l1=l1-l3*2/3;l2=l2+l3*2/3;head;of;l1;l2;l3用matlab优化工具箱函数检验：H=2 0;0 2;C=-8;-10;A=3 2;-1 0;0 -1;b=6;0;0;x=quadprog(H,C,A,b)序列二次规划：对于目标函数及约束条件均为非线性的规划问题，可将其按泰勒级数在迭代点展开成二次规划问题，解此二次规划，得到下一个迭代点。由于涉及到海塞矩阵，可采用变尺度法逼近海塞矩阵的逆。序列线性规划：同样对于上述非线性的规划问题，可以在迭代点将其展开成线性规划问题，利用单纯性求出新的迭代点。用以上两种方法求解非线性规划，存在两个问题： 1）由于线性化带来的误差，近似最优解可能落在原问题的可行域外，甚至与真正的最优解相距很远。当初始