优化设计3惩罚函数法

2020/1/713.5多维约束优化方法3.5.1复合形法可行方向法3.5.2拉格朗日乘子法3.5.3罚函数法2020/1/722020/1/733.5.1复合形法2020/1/74复合形法的优化过程：1）在可行域内选定K个点，构成以这K个点为顶点的不规则多面体作为初始复合形。一般n+1≤K≤2n，当维数n较小时取较大的K（如K=2n）；当n较大时，取较小的K。2）然后比较复合形各顶点的函数值，找出最坏点X(b)，和除X(b)之外的其它各点的点集中心X(c)。3）从X(b)出发通过X(c)作一射线，在此射线上找到一个既满足约束条件，函数值又有改善的新顶点——反射点X(r)。再舍弃最坏点X(b)，代之以反射点X(r)，构成新复合形。如此反复进行，直至得到最优点为止。2020/1/75复合形法的特点：原理简单、方法直观、不需要计算导数。也不需要一维搜索，复合形不要求为规则图形，灵活可变。适宜处理不等式约束问题且能防止顶点退化。在求解过程中涉及的可行域较广，故结果可靠。但复合形法不适宜应用于中、高维问题，原因是维数若太高，计算量急增，收敛很慢。2020/1/762、复合形法计算步骤（1）输入各常量，如设计变量个数n，收敛精度ε1、ε2，初始反射系数α，设计变量的上下界值bj和aj,j=1,2,…,n。（2）产生初始复合形，其各顶点要在可行域内，且满足约束条件。即第一个顶点产生方法不限，其余k-1个顶点可按随机法产生（设复合形有k个顶点）。xi(0)=a+qi(b-a)i=1,2,…,k。k为顶点号；qk为(0,1)区间内的伪随机数，一般可查表或由电子计算机提供，亦可自编程产生。2020/1/77（3）计算各顶点的目标函数值，找出最坏点X(H)、次坏点X(G)、最好点X(L)，即X(H):f(X(H))=max{f(X(i)),i=1,2,…,k}X(G):f(X(G))=max{f(X(i)),i=1,2,…,k,k≠H}X(L):f(X(L))=min{f(X(i)),i=1,2,…,k}（4）计算除最坏点X(H)之外的k-1个顶点的中心点X(C)，即X(C)=[1/(k-1)]∑X(i)(i=1,2,…,k,k≠H)2020/1/78检验中心X(c)，若X(c)在可行域内，则继续执行步骤(5)；若X(c)不在可行域内，此时可行域为非凸集，如图所示，此时转步骤(2),直至X(c)成为可行点为止。2020/1/79（5）在最坏点X(H)和中心点X(c)的连线方向上取反射点X(R)，即X(R)=X(c)+α(X(c)–X(H))式中反射系数α的初值一般取为α=1.3。求出反射点X(R)后，对该点进行可行性检查，若X(R)越出了可行域，如图所示，则将反射系数α减半，使X(R)点退回可行域，得到新的X(R)点。若新反射点X(r)仍未退回可行域，继续将α减半，如此反复，直至X(R)为可行点为止。2020/1/710（6）计算反射点的函数值f(X(R))，并与最坏点X(H)比较。若f(X(R))f(X(H))，则用反射点X(R)代替最坏点X(H)，构成新的复合形，转步骤（7）。若f(X(R))≥f(X(H))，则将反射系数α减半，转（5），重新计算反射点。若直到反射系数α小于一个预先给定的很小正数时，反射点的函数值仍大于最坏点函数值，则说明该反射方向不好，此时改用次坏点X(G)代替最坏点X(H)，即X(H)=X(G),换一个反射方向，转（4）。2020/1/711（7）终止判别：反复执行上述过程中，随着反射系数α的不断减半，复合形逐渐向最优点收缩，复合形越来越小，直到满足时，迭代结束。此时复合形中目标函数值最小的顶点（或用X(C0)点）即为最优解。式中XC为复合形所有顶点的点集中心，即若复合形不满足(a)式，则应转向（3），开始下一次迭代。)(}]()([1{11221aXfXfkkicikiiCXkX112020/1/7122020/1/7132020/1/7142020/1/7152020/1/7162020/1/717原理：从可行域内的一个可行点出发，选择一个可行的搜索方向和步长，使产生的下一个相对较优的迭代点，既不超出可行域又使目标函数值有所下降。最佳可行下降方向：最优搜索步长：可行方向法:2020/1/7183.5.2拉格朗日乘子法对于等式约束问题minf(X)=f(x1,x2,…,xn)s.t.hj(X)=0,j=1,2,…,p由数学基础知识可知，可以将其转化为求拉格朗日函数无约束的极值问题。引入拉格朗日函数L(X,λ)=f(X)+∑λjhj(X)(j=1,2,…,p)式中λj为拉格朗日乘子，则问题的极值条件为pjhLnixhxfxLjjpjijii,,2,1,0,,2,1,012020/1/719共有n+p个方程，可解出x1*,x2*,…,xn*和λ1*，λ2*,…,λn*共n+p个未知量，则有若X*及λ*是L(X*,λ*)的极小点，则X*必为f(X)的极小点。为了便于在计算机上利用直接寻优方法进行迭代计算，一般引入函数然后对Z函数求极小值，即可求得原问题的最优解。*)(*)*,(,,2,1,0*)(XfXLpjXhjjpjjniiXhxLZ1212)]([)(2020/1/720对于不等式约束优化问题，可设法引入松弛变量，使不等式变成等式，即可按等式约束优化问题求解。例如：对于下面不等式约束条件g(X)=ax1+bx2+c≥0引入松弛变量x3，并为保证引入项为正值，均用松弛变量的平方，即有g/(X)=ax1+bx2+c-x32=02020/1/7212020/1/72232020/1/7233.5.3惩罚函数法不等式约束的优化问题也转化为无约束优化问题,这种转化必须满足一定的条件：1、不能破坏约束问题的约束条件；2、使它归结到原约束问题的同一最优解上。惩罚函数法将有约束优化问题中的各约束函数gi(X)和hj(X)，以一定的形式附加到原目标函数f(X)上去，构造一个新的目标函数，称为惩罚函数，其一般形式为pjjkmiikkkXhHrXgGrXfrrXP1)(21)(1)(2)(1)]([])([)(),,(2020/1/724于是，问题归结为在设计空间Rn中（而不是在可行域D内）求函数P的无约束极小,即minP(X,r1(k),r2(k)),X∈RnG[gi(X)]和H[hj(X)]分别是人为构造的gi(X)和hj(X)的泛函；r1(k)和r2(k)是人为构造的罚参数或罚因子，定义为正实数。它们随迭代次数k的增加，不断进行调整，每一次调整，对惩罚函数P做一次无约束优化，得到一个无约束最优解。随着罚因子的不断调整，无约束最优解不断逼近有约束最优解。pjjkmiikkkXhHrXgGrXfrrXP1)(21)(1)(2)(1)]([])([)(),,(2020/1/725罚函数的求解过程是：定义G[gi(X)]和H[hj(X)]的形式，选择罚因子的序列r1(k)和r2(k)，每调整一次罚因子的值，即对罚函数P作一次无约束优化，可得一个无约束最优解；随着罚因子的不断调整，无约束最优解不断逼近有约束最优解。这是一种序列求优过程，故罚函数又称为“序列无约束极小化方法”（SequentialUnconstrainedMinizationTechnique），简称为SUMT法。2020/1/726为使罚函数P(X,r1(k),r2(k))的极小点序列X*(r1(k),r2(k))(k=1,2,…，)收敛到目标函数f(X)的约束最优解，上式中的惩罚项必须具有以下极限性质：从而有根据约束形式，定义的泛函及罚因子调整方法的不同，罚函数又分为外点法、内点法和混合函数法三种。pjjkkmiikkXhHrXgGr1)(21)(10)]([lim0)]([lim0|)(),,(|lim)(2)(1kXfrrXPkk2020/1/7271、内点法内点法是求解不等式约束优化的有效方法。内点法要求迭代过程总是在可行域内进行，即所有迭代点都是可行的。特别地，初始点必须是可行点。为了在可行域内求f(X)的极小值，内点法在可行域的边界上设置了一道无法逾越的“高墙”，不让迭代点X跑出可行域。当迭代点X接近边界时，函数值陡然增大起来，对边界上的点干脆施加无穷大的惩罚，把迭代点封闭在可行域内。因此，内点法也称为“围墙”函数或“障碍”函数法。2020/1/728内点法是改造原目标函数f(X)，使其在边界附近尽量抬高，离边界越近，抬得越高。不难想到，构造如下的罚函数可以实现上述想法：式中右端第二项为内点法惩罚项，当迭代点X从可行域内部接近某个约束gi(X)≤0的界面gi(X)=0时，-1/gi(X)就趋于无穷大，它像绝壁一样阻止迭代点越出边界。miikkXgrXfrXP1)()()(1)(),(2020/1/729除上式外，常用的内点罚函数形式还有：等等，只要它具有在可行域内离边界稍远处其惩罚项函数极小，而一旦迭代点趋近边界时，函数值陡然增大这一特点即可。miikkmiikkXgrXfrXPXgrXfrXP12)()(1)()()]([1)(),()](ln[)(),(2020/1/730上式中，r(k)是一个递减的正数序列，开始较大，逐渐减小，即r(1)r(2)…r(k)r(k+1)…→0相应于罚因子r(1)、r(2)、…所得到的一系列无约束极值问题的极小点序列{X(r(k))}的极限点(k趋于无穷大)，就是原约束问题的最优点X*。为什么内点法要使罚因子逐渐减小呢？因为随着r(k)的逐渐减小，相当于罚函数P(X,r(k))中的惩罚项的作用越来越小，那么函数P(X,r(k))的最优点X*(r(k))也就是可能从可行域内部越来越靠近其边界（因通常最优点X*总是在可行域的边界上）。因此，内点法中，随着r(k)的减小逐渐把最优点序列{X*(r(k))}引向原问题的最优点X*，这样就将原约束优化问题转化为序列无约束优化问题。2020/1/731内点法算法步骤：(1)在可行域内找到一个初始内点X(0)，要求该点满足各约束条件。（给定初始罚因子r(0)0，罚因子递减系数C(0C1)，通常取C=0.1～0.02），判别收敛的正数ε，置K=0。(2)构造内点罚函数P(X*,r(k))，用任一种无约束极小化方法极小化P(X,r(k))，求出X*(r(k))。(3)判别收敛与否，即判别X*(r(k))是否为原问题的最优解，若是则迭代结束；否则转下一步。(4)求下一个罚因子r(k+1)的值：r(k+1)=C·r(k),以X(0)=X*(r(k))作为新的初始点，置K=K+1，转（2）。2020/1/732内点法罚函数常用的收敛判别准则：(1)点收敛准则：‖X(k+1)-X(k)‖≤ε(2)目标函数准则（绝对差）：∣f(X(k+1))-f(X(k))∣≤ε(3)目标函数准则（相对差）：|[f(X(k+1))–f(X(k))]/f(X(k))|≤ε(4)惩罚项准则：r(k)G[gi(X)]≤ε2020/1/7332020/1/734例3-7约束优化问题01)(:2)(min1xxgxxxfDRDxxgxgG11)(1)]([xrxxgGrxfrxPkkk12)]([)(),()()()(采用内点法求解如下。构造泛函及罚函数2020/1/735为了便于说明迭代过程，下面用解析法来求极值。)()()*()()*()()*(2)(221),(22121)(210)1(121kkkkkkkkrrxPrxfrxxrdxdP取初始罚因子25.0)0(r，罚因子的递减率c＝0.12020/1/7362．计算步骤（1）在可行域内任选一严格初始内点X(0)，最好不要靠近约束边界；选一适当大的初始罚因子r(0)和罚因子递减率0c1，