[所有分类]第五章-约束优化方法

第五章约束优化方法§5-1约束最优解及其一阶必要条件§5-2随机方向法§5-3复合形法§5-4可行方向法§5-5内惩罚函数法§5-6外惩罚函数法§5-7混合惩罚函数法§5-8扩展内惩罚函数法§5-1约束最优解及其一阶必要条件机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值必须是满足约束条件，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行域是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，探索结果经常与初始点的选择有关。(为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。)（1）直接法直接解法通常适用于仅含不等式约束的问题。思路:是在m个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向sk且以适当的步长αk，进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。根据求解方式的不同，约束优化设计问题可分为:直接解法、间接解法。直接法主要包括：随机方向法、复合形法和可行方向法。其迭代过程中，每一次的新迭代点X(K+1)都要经过可行性和适用性条件的检验。可行性条件是指新迭代点X(K+1)必须在可行域内，即满足适用性条件是指新迭代点X(K+1)的目标函数值较前一点是下降的，即满足特点：①在可行域内进行；②若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。凸集非凸集(2）间接法目的：将有约束优化问题转化为无约束优化问题方法：以原目标函数和加权的约束函数共同构成一个新的目标函数Φ(x,r1,r2)，成为无约束优化问题。通过不断调整加权因子，产生一系列Φ函数的极小点序列xk*(r1k,r2k)k=0,1,2…，逐渐收敛到原目标函数的约束最优解。间接法主要包括：内点罚函数法、外点罚函数法和混合罚函数法、扩展内惩罚函数法。新目标函数：其中：惩罚项：)(),,()(2)(1xfrrxkk)]([)]([1)(21)(1xhHrxgGrpvvkmuuk加权因子(惩罚因子)：r1(k),r2(k)无约束优化问题：Φ函数的极小点序列x(k)*(r1(k),r2(k))k=0,1,2…其收敛必须满足：§5-2随机方向法基本思想：随机产生初始点X(0)，随机产生搜索方向S(k)，进行搜索。但要确保：①新迭代点在可行域中；②目标函数值的下降性。随机方向法，是约束最优化问题的一种常用的直接求解方法。一、随机方向的构成在计算机语言所适用的函数库中，都有一种随机函数，可以产生0~1之间的均匀分布的随机数，利用产生的随机数构成随机方向。若利用在（0，1）之间产生的随机数，i=1，2，……，n，构成单位矢量S，方法如下。把随机数，转化为另一区间（-1，1）之间的随机数然后由随机数yi构成以下随机方向由于随机数yi在区间（-1，1）内产生，所构成的随机方向矢量S一定是在超球面空间里均匀分布且模等于1的单位矢量。如图5-1所示的二维问题。首先选定可行初始点X(0)，利用随机函数构成随机方向S（1），按给定的初始步长h=h0沿S（1）方向取得试探点检查点X(1)的适用性和可行性，即检查二、随机方向法)3(X)3(x)2(X)0(X)1(S)1(X)2(S*X)3(x图5-1随机方向法直至达到某迭代点不能同时满足适用性和可行性条件时停止，退回到前一点作为该方向搜索中的最终成功点，记作X(1)。进而，将X(1)作为新的始点X(0)←X(1)，再产生另一随机方向S(2)，重复以上过程，得到沿S(2)方向的最终成功点X(2)。如此循环，点列X(1)、X(2)、……必将逼近于约束最优点X*。若两者均满足，X作为新的起点，继续按上述迭代式在S(1)方向上取得新点。重复上述步骤，迭代点可沿S(1)方向前进。(1)若在某个换向转折点处（如图中的X(1)点），沿某搜索方向的试探点目标函数值增大或越出可行域，则弃去该方向，再产生另一随机方向作试探。试探成功就前进，试探失败再重新产生新的随机方向。(2)当在某个转折点处沿m个（预先限定的次数）随机方向试探均失败，如图中点X(2)，则说明以此点为中心，h0为半径的圆周上各点都不是适用、可行的。此时可将初始步长h0缩半后继续试探,直到f(k+1)≤f(k)，且沿m个随机方向都试探失败时，则最后一个成功点（如图中的X(3)点）就是到达预定精度要求的约束最优点，迭代即可结束。(3)m是预先规定在某转折点处产生随机方向所允许的最大数目。对于性态不好的目标函数或可行域有狭长弯道的问题，m应取较大的值，以提高解题的成功率。约束随机方向法的搜索方向比较灵活，当预定的随机方向限定数m足够大时，无“病态”问题出现，一般都能求出最优点。入口X←X(0)，a←a0F0←F(X)K1j←0在（-1，1）区间产生随机数yiX←X(0)+aSYgu(X)≤0F←F(X)FF0?更换初始点X(0)←X，F0←Fj←1(x)X←X(0)+aS给定：X(0)，a0，m，ej=0?Km?a≤e?K←K+1X*←XF*←F出口a←0.5aYYYYNNNNNT21121nniiyyyyS图5-2随机方向法程序框图三举例例：用约束随机方向法求解解：人工选取一初始点X0=[5，5]T，初始点在可行域内。相应的目标函数值为F(X0)=50。第一次迭代1)产生两个伪随机数，求出第一个随机方向。生成两个伪随机数由此得第一个随机方向为：2)求第一个迭代点第一个迭代点表达式为：式中a为步长。将X1的表达式代入目标函数中，进行一维搜索，令目标函数对步长a的一阶导数为0，即可求出沿e1方向的最优步长。第一个迭代点为：3）检验X1点是否满足约束条件g(X1)=2*4.2+5.6=1412，X1满足约束条件，是可行点。相应的目标函数值为:第二次迭代以X1为初始点，继续使用e1方向直到不满足可行性和适用性条件，再重新生成随机搜索方向e2。（以下过程略）目标函数值下降随机方向法方法评价：优点：1对目标函数无性态要求；2收敛快（当随机方向限定数m足够大时）；3不受维数影响，维数愈高，愈体现优点。缺点：1对于严重非线性函数，只能得近似解；2当m不够大时，解的近似程度大；3对于非凸函数，有可能收敛于局部解。复合形法是求解约束非线性最优化问题的一种重要的直接方法。不需计算目标函数的梯度，而是靠选取复合形的顶点井比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。在用于求解约束问题的复合形法中，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。§5-3复合形法比较复合形各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的形心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。一、复合形法基本思想:在n维空间中，由n+1≤k≤2n个点组成的多（边）面体称为复合形。以新的复合形顶点,代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。例如：设有一约束优化问题的数学模型是该目标函数的等值线和可行域的几何图形如图5-3所示。用复合形法求该问题的约束最优解的过程如下:11022334455667788912345678910x*x1x2图5-3复合形法引例令：X(R)=X(S)+α(X(S)-X(H))称X(R)为映射点，α为映射系数，通常取α=1.3，可根据实际情况进行缩减。取次好点和好点连线的中点为X(S)。一般情况下，映射点的函数值比坏点的函数值要小，即F(X(R))F(X(H))。若满足可行域，则用X(R)代替X(H)构成新的复合形。如此反复迭代直到找到最优解。在可行域内任选三个初始点X(1)、X(2)、X(3)，连接这三点形成一个三角形，此三角形称为初始复合形。计算各个顶点函数值F(X(1))、F(X(2))、F(X(3))，找出最大值，记为坏点X(H)。最小值，记为最好点X(L)。在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。二、初始复合形的构成复合形的顶点K≥n+1个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，先产生K个随机点，然后再把非可行点逐一调入可行域内。最终使K个随机点都成为可行点而构成初始复合形。复合形的产生可以：（1）人工选择初始复合形（2）随机产生初始复合形xi=ai+ξi(bi-ai)i=1,2,….,n用这n个随机数xi作为坐标的点X就是一个随机点。这第一个点记作X(1)。同样，产生其它的随机点X(2)、X(3)、……X(K)。1.产生K个随机点根据随机数产生的标准函数，可以在（0，1）开区间内产生均匀分布的随机数ξi。利用该随机数可产生变量xi在给定界限aixibi内的随机数因每产生一个随机点，需要n个随机数，因此，产生k个随机点总共需要连续发生K×n个随机数。2、将非可行点调入可行域用上述方法产生的K个随机点，并不一定都是可行的。但是，只要它们中间有一个点在可行域内，就可以用一定的方法将非可行点逐一调入可行域。将产生的K个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有q个顶点X(1)、X(2)、……X(q)是可行点,其它K-q个为非可行点。对X(q+1)，将其调入可行域的步骤是：（1）计算q个点集的中心X(s)；（2）将第q+1点朝着点X(s)的方向移动，按下式产生新的X(q+1)即X(q+1)=X(s)+0.5(X(q+1)-X(s))这个新点X(q+1)实际就是X(s)与原X(q+1)两点连线的中点，如图。若新的X(q+1)点仍为非可行点，按上式再产生X(q+1)，使它更向X(s)靠拢，最终使其成为可行点。按照这个方法，同样使X(q+2)、X(q+3)、……X(K)都变为可行点，这K个点就构成了初始复合形。三、复合形法的迭代步骤（1）构造初始复合形；（2）计算各顶点的函数值F(X(j))，j=1,2,….,K。选出好点X(L)和坏点X(H)。（3）计算坏点外的其余各顶点的中心点X(s)。（4）计算映射点X(R):检查X(R)是否在可行域内。若X(R)为非可行点，将映射系数减半后再按上式改变映射点，直到X(R)进入可行域内为止。（5）构造新的复合形计算映射点的函数值F(X(R))，并与坏点的函数值F(X(H))比较，可能存在两种情况：1）映射点优于坏点:F(X(R))F(X(H))在此情况，用X(R)代替X(H)，构成新的复合形。2）映射点次于坏点:F(X(R))＞F(X(H))这种情况由于映射点过远引起的，减半映射系数，若有F(X(R))F(X(H))，这又转化为第一种情况。若经过多次的映射系数减半，仍不能使映射点优于坏点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点的映射。()()():()max{(),1,2,,,}SHSHjXFXFXjKjH再转回本步骤的开始处，直到构成新的复合形。(6)判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即1()()2211{[()()]}KjLjFXFXKe-2）各顶点与好点的函数值之差的平方和小于误差限，即3）各顶点与好点函数值差的绝对值之和小于误差限，即如果不满足终止迭代条件，则返回步骤2继续进行下一次迭代；否则，可将最后复合形的好点X(L)及其函数值F(X(L))作为最优解输出()()1()()KjLjFXFXe-()()21[()()]KjLjFXFXe-例：用复合形法求解约束优化问题，迭代精度为0.01。(课堂练习)解：n=2,取复合形顶点数k=2n=4。1.人为给出4个复合形顶点。经检验4个顶点均在可行域内。0.1e1234()10.25,()8,()14.76,(