第2章优化设计.

15.约束优化方法工程中的大量优化设计问题，都是约束优化问题，它的一般数学模型为：min(),..()01,2,...,()01,2,...,nuvfXXRstgXumhXvp求解这类问题的方法称约束优化方法，最优点X*称为约束最优点。约束优化算法大致可归纳为两大类：●直接解法●间接解法（2-59）思考如何求解2直接解法这类方法对于只有不等式约束的优化问题是有效的。这类方法的基本思想是：在约束的可行域内直接搜索出它的约束最优解。属于这类方法的主要有：网格法，可行方向法，复合形法等。间接解法这类方法对于解决具有不等式约束和等式约束条件的优化问题都有效。它的基本思想是：将复杂的约束问题转化为一系列无约束优化问题，即按一定原则构造一个新的目标函数，并以它的最优化解去逐步逼近原约束问题的最优解。约束问题通过这种方法的处理，就可以采用无约束优化方法求解。属于这类方法的主要有：消元法、简约梯度法、惩罚函数法等。()X本节主要介绍复合形法和惩罚函数法。3复合形法是适用于具有不等式约束优化问题的一种直接算法。该法的基本思路是：在n维优化设计空间的可行域D内，构造具有k个顶点的多边形（或多面体），称作复合形。复合形的每个顶点都代表一个设计方案。然后，计算复合形各顶点的目标函数值并逐一进行比较，取函数值最大者为最坏点，最小者为最好点。再以去掉最坏点的其余各点的中心点为映射轴心，在最坏点和其余各点的中心点的连线上，寻找一个既满足约束条件，又使目标函数值有所改善的坏点映射点，并以该映射点替换坏点而构成新的复合形。按照上述步骤重复多次，不断地去掉最坏点，这样不断调整复合形的顶点，使复合形不断向最优点靠拢，最后搜索到约束优化问题的最优解。(12)nkn5.1复合形法4对于二维问题，复合形法的搜索原理，如图2-33所示。图2-33复合形法原理5所以，复合形法的迭代过程实际就是通过对复合形各顶点的函数值计算与比较，反复进行点的映射与复合形的收缩，使之逐步逼近约束问题最优解的。min(),..()0,(12,)nufXXRstgXum，，（2-60）根据上述复合形法的基本思想，对于求解的优化问题时，采用复合形法来求解，需分两步进行：第一步是在设计空间的可行域内产生k个初始顶点构成一个不规则的多面体，即生成初始复合形。一般取复合形顶点数为：。第二步进行该复合形的调优迭代计算。通过对各顶点函数值大小的比较，判断下降方向，不断用新的可行好点取代坏点，构成新的复合形，使它逐步向约束最优点移动、收缩和逼近，直到满足一定的收敛精度为止。{()0,1,2,,}uDXgXum12nkn6初始复合形的生成通常，初始复合形的生成方法主要采用如下两种方法：生成初始复合形，实际就是要确定k个可行点作为初始复合形的顶点。（1）人为给定k个初始顶点。可由设计者预先选择k个设计方案，即人工构造一个初始复合形。k个顶点都必须满足所有的约束条件。()()()jjiiiiiXarba)(jir,iiab（2）给定一个初始顶点，随机产生其它顶点。在高维且多约束情况下，一般是人为地确定一个初始可形点，其余个顶点可用随机法产生，即（2-61）式中，——复合形顶点的标号；——设计变量的标号，表示点的坐标分量；——设计变量的解域或上下界；——[0，1]区间内服从均匀分布伪随机数。()(2,3,,)jXjk(1,2,,)in(2,3,,)jkij(1)X1k(1,2,,)iXin7()()11qcjjXXq)1(qX)(cX(1)'()(1)()0.5()qcqcXXXX(1)'qX(1)'qX(2)(3)(),,,qqpXXX用上述方法随机产生的k-1个顶点，虽然可以满足设计变量的边界约束条件，但不一定是可行点，所以还必须逐个检查其可行性，并使其成为可行点。设已有q（1≤q≤k）个顶点满足全部约束条件，第q+1点X（q+1）不是可行点，则先求出q个顶点的中心点（2-62）然后将不满足约束条件的点向中心点靠拢，即（2-63）若新得到的仍在可行域外，则重复上式（2-63）进行调整，直到点成为可行点为止。然后，同样处理其余诸点，使其全部进入可行域内，从而构成一个所有顶点均在可行域内的初始复合形。满足某i变量边界的顶点不一定满足非i变量的约束8复合形法的调优迭代初始复合形生成后，其调优迭代计算按下述步骤进行：（1）计算初始复合形各顶点的函数值，选出好点、坏点、次坏点：()()()()()()()()():()min{(),1,2,,}:()max{(),1,2,,}:()max{(),1,2,,;}LLjHHjGGjXfXfXjkXfXfXjkXfXfXjkjH（2）计算除坏点X（H）外其余k-1个顶点的几何中心点：1()()11,1kSjjXXjHk并检验X（S）点是否在可行域内。如果X（S）是可行点，则执行下步（3）；否则转第（4）步。（3）沿X（H）和X（S）连线方向求映射点X（R）：()()()()()RSSHXXXX（2-64）式中，称映射系数，通常取。然后，检验X（R）可行性。1.39（4）若X（S）在可行域外，此时D可能是非凸集，如图2-34所示。此时利用X（S）和X（L）重复确定一个区间，在此区间内重新随机产生k个顶点构成复合形。图2-34可行域为非凸集10重新构成复合形后，重复第（1）、（2）步，直到成为可行点为止。)()(LiiSiiXbXa(1,2,,)in（2-66）()()()()(),LSLSiiXXXX即点在的右边若则取)()(SiiLiiXbXa(1,2,,)in（2-65）)(SX新的区间如图中虚线所示：()()()()(),1,2,,,LSLSiiXXXXin即点在的左边其边界值若则取11（5）计算映射点的目标函数值f（X（R）），若f（X（R））f（X（H）），则用映射点替换坏点，构成新的复合形，完成一次调优迭代计算，并转向第（1）步；否则继续下一步。（6）若f（X（R））f（X（H）），则将映射系数α减半，重新计算映射点。如果新的映射点X（R）既为可行点，又满足f（X（R））f（X（H）），即代替X（H），完成本次迭代；否则继续将α减半，直到当α值减到小于预先给定的一个很小正数（例如）时，仍不能使映射点优于坏点，则说明该映射方向不对，应改用次坏点X（G）替换坏点再行映射。510（7）进行收敛判断。若满足1/22()()11()()kjcjfXfXk)(cX()()11(1,2,,)1kcjiijXXink时可结束迭代计算。此时复合形中目标函数值最小的顶点即为该约束优化问题的最优点。上式（2-67）中的为复合形所有顶点的点集中心，即（2-67）（2-68）12复合形法的迭代计算框图，如图2-35所示。图2-35复合形法的计算框图13惩罚函数法是一种用来求解约束优化问题的间接解法。该算法的基本思想是：将约束优化问题的数学模型改造成为无约束的数学模型，然后按无约束问题进行一系列的无约束最优化求解，直到求得原问题的最优解。根据所构造的目标函数的形式不同，决定了搜索点是在可行域内、或在可行域外，因而该算法又分为如下三种：内点罚函数法内点罚函数法适合于求解不等式约束优化问题，即min(),..()0,1,2,,nufXXDRstgXum●内点罚函数法●外点罚函数法●混合罚函数法5.2惩罚函数法14则构造的新目标函数为：(k)()1(,r)()[()]mkuuXfXrGgX式中：为惩罚因子，它是一递减正数序列，即)(kr(0)(1)(2)()(1)(k),r0;limkkkrrrrr且为此，取，这里c为递减系数，1c0；)()1(kkcrr)]([1XgGumu为以gu（X）为函数的复合函数，或称与不等式约束有关的惩罚项。然后对新目标函数按无约束问题求解，即(k)*(k)min(,)XrX在求解过程中，针对不同的，就有一个与之对应的极小值点，随着的减小，使求得的也逐步向原问题的最优点逼近。所以该方法也称为“序列无约束极小化”方法。()kr*()*()()kkXXr()kr*()kX15对于内点罚函数法，求解过程要求保证：（1）初始点和所求得的序列最优点，都应是可行点；（2）求解到最后，序列最优点应逼近最优点X*。)0(X*()kX*()kX对于不等式约束优化问题，根据罚函数法的基本思想，将罚函数定义在可行域内部，可以构造其内点罚函数的一般形式为()()11(,)()()mkkuuXrfXrgX或（2-72）（2-71）()()1(,)()ln[()]mkkuuXrfXrgX式中，惩罚因子，是一递减的正数序列，即，且。(0)(1)(2)rrr()0krlim0k()kr16)0(X)0(r()()11(,)()()mkkuuXrfXrgX（3）构造惩罚函数()min(,)kXr*()()kXr(1)()kkXX(1)()()()()()kkkfXfXfX**()**()(),(())kkXXrffXr**,Xf（4）求解无约束优化问题，得；（5）进行收敛判断，若满足或则令，停止迭代计算，输出最优解；否则转下步；（6）取，以作为新的初始点，置转步骤（3）继续迭代。(1)()kkrCr(0)*()()kXXr1kk内点罚函数法的迭代步骤如下：（1）在可行域内确定一个初始点；（2）给定初始罚因子、惩罚因子递减系数C和收敛精度ε；置k=0；17内点法的程序框图，见图2-36。图2-36内点法程序框图)0(r)0(r)0(r)0(r(0)(0)1()1()muufXrgX在内点法中，初始罚因子的选择很重要。根据经验，一般可取=1~50，但多数情况是取=1。也有建议按初始惩罚项作用与初始目标函数作用相近原则来确定值，即递减系数C一般取为：C=0.1～0.5，常取0.1。18内点法例题例2-1试用内点罚函数法求解如下优化问题：1min(),..()10fxxxRstgxx解：此题的标准解为：。根据内点法的基本思想，首先构造罚函数，按式（2-71）可写出：**1,()1xfx()()()11(,)()()1kkkxrfxrxrgxx可以看出由两部分组成，即，其中：()(,)kxr()()21111kkrrxx1()fxx1219即：是原目标函数，为一直线；是一族倒数曲线，当。则两曲线的组合则构成曲线，如下图所示。12()(,)kxr21,x时20对求导并令其一阶导数为零，即()(,)kxr()()()2(,)11101(1)kkkdxrdxrrdxdxxx可求得其无约束极值点：惩罚函数值为：*()()()1kkxrr*()()()((),)12kkkxrrr当选用不同的惩罚因子时，可得到不同的极值点及Φ曲线。取递减数列，由上式可得序列如下：()kr*()*()()(,)kkxrxr和()*()*()1,0.1,0.01,0.001,0()2,1.316,1.10,1.0316,1(,)3,1.632,1.20,1.0630,1kkkrxrxr上图表示出取值不同时所得到的约束最优点逐步逼近原问题最优点的情形。()kr*x()kr*()()kxr21由上图可以看出，当惩罚因子为一个递减数列时，无约束极值点离约束最优解愈来愈近，当即得到真正的约束最优解。此时，罚函数也收敛于原目标函数的最优值，即*x()*()*0()1,kkrxrx时,*()()*((),)()1kkxrrfx*()()kxr22外点罚函数法外点罚函数法适用于具有等式和不等式约束优化问题。将罚函数定