第5章-约束优化方法2(白版)

第五章有约束优化方法§5-1引言§5-2随机方向法§5-3复合形法§5-4可行方向法§5-5惩罚函数法§5-6序列二次规划法§5-1引言机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为min(),..()01,2,,()01,2,,njkfRstgjmhklxxxx上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行域必是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，探索结果经常与初始点的选择有关。为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。（1）直接法直接法包括：网格法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。（2）间接法间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、广义乘子法、广义简约梯度法和约束变尺度法等。根据求解方式的不同，约束优化设计问题可分为:直接解法、间接解法。直接解法通常适用于仅含不等式约束的问题，思路是在m个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向d且以适当的步长，进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。1(0,1,2,)kkkkdkxxkkd步长可行搜索方向可行搜索方向:当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。间接解法的基本思路是按照一定的原则构造一个包含原目标函数和约束条件的新目标函数，即将原约束优化问题转化成为一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解。§5-2随机方向法基本思想：利用计算机产生的随机数所构成的随机方向进行搜索，产生的新点必须在可行域内，即满足直接法的特性。随机方向法，是约束最优化问题的一种常用的直接求解方法。它和随机梯度法、Gauss－Seidel法等都属于约束随机法。其基本原理如图所示，在约束可行域S内选取一个初始点X(0)，在不破坏约束的条件下以合适的步长a。沿X(0)点周围几个不同的方向（以某种形式产生的随机方向）进行若干次探索，并计算各方向上等距离（步长a。）点的函数值，找出其中的最小值f（X(l)）及点X(l)。若f（X(l)）＜f（X(0)），则继续沿方向（X(l)-X(0)）以适当的步长a向前跨步，得到新点X(1)，若f（X(1)）老f（X(l)），则将新的起点移至X(1)，重复前面过程。否则应缩短步长a，直至取得约束好点。如此循环下去。当迭代的步长已经很小时，则表明已经逼近约束最优点。达到计算精度要求时，即可结束迭代计算。图约束随机方向探索法的基本原理随机方向探索法的一般迭代计算公式为：X(k+1)=X(k)+aS(k)(k=0,1,2,…)式中a为步长，S(k)为第k次迭代的随机探索方向。因此，随机方向探索法的计算过程可归结为：复合形法是求解约束非线性最优化问题的一种重要的直接方法。它来源于用于求解无约束非线性最优化问题的单纯形法，实际上是单纯形法在约束问题中的发展。如前所述，在求解无约束问题的单纯形法中，不需计算目标函数的梯度，而是靠选取单纯形的顶点井比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。在用于求解约束问题的复合形法中，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。§5-3复合形法基本思想：在可行域中选取K个设计点（n+1≤K≤2n）作为初始复合形的顶点。比较各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的中心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。反复迭代计算，使复合形不断向最优点移动和收缩，直至收缩到复合形的顶点与形心非常接近，且满足迭代精度要求为止。令：X(4)=X(0)+α(X(0)-X(H))称X(4)为映射点，记为X(R)，α为映射系数，通常取α=1.3，可根据实际情况进行缩减。取次好点和好点连线的中点为X(0)。一般情况下，映射点的函数值比坏点的函数值要小，即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)。在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。在迭代过程中，按映射系数α=1.3得到的映射点，不一定满足适用性和可行性，如出现此情况，将映射系数减半，重新取得X(R)，使它满足适用性和可行性。一、初始复合形的构成复合形的顶点K通常取n+1≤K≤2n个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，先产生K个随机点，然后再把非可行点逐一调入可行域内。1、产生K个随机点xi=ai+ξi(bi-ai)i=1,2,….,nξi为（0，1）区间内产生的均匀分布的随机数，需要n个随机数产生一个点X(1)。同样，产生其它的随机点X(2)、X(3)、……X(K)。2、将非可行点调入可行域将产生的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)。()()()()()():()min{(),1,2,,}:()max{(),1,2,,}LLjHHjXFXFXjKXFXFXjK（3）计算坏点外的其余各顶点的中心点X(0)。()011,1KjjXXjHk（4）计算映射点X(R)检查X(R)是否在可行域内。若X(R)为非可行点，将映射系数减半后再按上式改变映射点，直到X(R)进入可行域内为止。()(0)(0)()()RHXXXX（5）构造新的复合形计算映射点的函数值F(X(R))，并与坏点的函数值F(X(H))比较，可能存在两种情况：1）映射点优于坏点F(X(R))F(X(H))在此情况，用X(R)代替X(H)，构成新的复合形。若经过多次的映射系数减半，仍不能使映射点由于坏点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点()()():()max{(),1,2,,,}SHSHjXFXFXjKjH的映射。()01()(0)(0)()1,1()KjjRSHXXjSHkXXXX再转回本步骤的开始处，直到构成新的复合形。2）映射点次于坏点F(X(R))〉F(X(H))这种情况由于映射点过远引起的，减半映射系数，若有F(X(R))F(X(H))，这又转化为第一种情况。(6)判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即1()()2211{[()()]}KjLjFXFXK2）各顶点与好点的函数值之差的平方和小于误差限，即3）各顶点与好点函数值差的绝对值之和小于误差限，即如果不满足终止迭代条件，则返回步骤2继续进行下一次迭代；否则，可将最后复合形的好点X(L)及其函数值F(X(L))作为最优解输出。()()1()()KjLjFXFX()()21[()()]KjLjFXFX方法特点（1）复合形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。但复合形各顶点的选择和替换，不仅要满足目标函数值下降的要求，还应当满足所有的约束条件。（2）复合形法适用于仅含不等式约束的问题。可行方向是求解大型不等式约束优化问题的主要方法之一。基本思想：这种方法的基本原理是在可行域内选择一个初始点，当确定了一个可行方向d和适当的步长后，按式:0x§5-4可行方向法1(0,1,2,)kkkkkxxd进行迭代计算,迭代点既不超出可行域,又使目标函数的值有所下降。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。可行方向法的搜索策略？即：11()0()()kukkgFFxxxOx1x2Ox1x2a)极值点处于多角形的某一顶点上b)极值点处于等值线的中心c)极值点处于约束曲线与等值线的切点上d)极值点处于两个约束曲线的交点上x﹡g1(x)＝0g2(x)＝0g3(x)＝0x﹡g2(x)＝0g3(x)＝0g4(x)＝0g1(x)＝0g2(x)＝0Ox1x2Ox1x2x﹡g2(x)＝0x﹡g1(x)＝0g1(x)＝0图1-101.可行方向法的搜索策略第一步迭代都是从可行的初始点出发，沿点的负梯度方向，将初始点移动到某一个约束面（只有一个起作用的约束时）上,或约束面的交集（有几个起作用的约束时）上。0x00()fdx根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索。0x1x2x0xkdkxk+1g2(x)=0g1(x)=00()fx1新点在可行域内的情况0x1x2x0xkdkxk+1g2(x)=0g1(x)=0g3(x)=00()fx2新点在可行域外的情况0x1x2x0xkxk+1g2(x)=0g1(x)=0g3(x)=00()fx3沿线性约束面的搜索0x1x2x0xkxk+1g2(x)=0g1(x)=0g3(x)=00()fx1()fxx4沿非线性约束面的搜索2.产生可行方向的条件可行方向是指沿该方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。可行方向应满足两个条件:(1)可行;(2)下降。1）可行条件方向的可行条件是指沿该方向作微小移动后，所得到的新点为可行点。dkxk()kgxdkxk1()kgx122()kgxg1(x)=0g2(x)=0[()]0kTkgxd[()]0(1,2,,)kTkjjJgxd2）下降条件方向的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。[()]0kTkfxddkxkg1(x)=0g2(x)=00()fx满足可行和下降条件，即式:[()]0(1,2,,)kTkjjJgxd[()]0kTkfxddkxk1()kgx122()kgxg1(x)=0g2(x)=0可行下降方向区0()fx位于约束曲面在点xk的切线和目标函数等值线在点xk的切线所围成的扇形区内，该扇形区称为可行下降方向区。同时成立的方向称可行方向。3.可行方向的产生方法满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向。（1）优选方向法[()]0(1,2,,)kTkjjJgxd[()]0kTkfxd由条件：求一个以搜索方向d为设计变量的约束优化问题min[()]kTkfxd[()]0(1,2,,)kTkjjJgxd[()]0kTkfxds.t.1kd各函数均为设计变量dk的线性