第6章约束优化方法课件.ppt

第6章约束优化方法第1页，此课件共102页哦 机械优化设计中的问题，大多数属于约束优化设机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为计问题，其数学模型为min(),.()01,2,()01,2,njkf XRst gXjmh Xklx第2页，此课件共102页哦 直接解法：随机方向搜索法、复合形法、可行方向法等直接解法：随机方向搜索法、复合形法、可行方向法等 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法 增广乘子法等增广乘子法等一一.有约束问题解法分类：有约束问题解法分类：二二.直接解法的基本思想：直接解法的基本思想：合理选择初始点，确定搜索方向，合理选择初始点，确定搜索方向，在可行域中在可行域中寻优，经过若干次迭代，收寻优，经过若干次迭代，收敛至最优点。敛至最优点。Xk+1=Xk+kdkdk:可行搜索方向。即设计点沿该方向作微量移动时可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下目标函数值将下 降降,且不会超出可行域且不会超出可行域直接解法通常适用于直接解法通常适用于仅含不等式约束仅含不等式约束的问题的问题第3页，此课件共102页哦特点：特点：由于求解过程在可行域内进行；无论迭代计算何时终止由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点都可以获得一个比初始点好的设计点;若可行域是凸集，目标函数是定义在凸集上的凸函数，若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。则收敛到全局最优点；否则，结果与初始点有关。凸可行域凸可行域x1x20X(0)X(0)X(0)X(0)非凸可行域非凸可行域x1x20X1*X2*第4页，此课件共102页哦12(,)()X r rf x)()(1211xhHrxgGrpvvmuu原理原理：将有约束优化问题转化为无约束优化问题来解决。：将有约束优化问题转化为无约束优化问题来解决。方法方法：以原目标函数和加权的约束函数共同构成一个新的：以原目标函数和加权的约束函数共同构成一个新的 目标函数目标函数 (X,r1,r2)，成为无约束优化问题，成为无约束优化问题。通。通 过不断调整加权因子，产生一系列过不断调整加权因子，产生一系列函数的极小点函数的极小点 序列序列 X(k)*(r1(k),r2(k)k=0,1,2，逐渐收敛到，逐渐收敛到原目原目 标函数的约束最优解标函数的约束最优解。其中：新目标函数：其中：新目标函数：三三.间接解法的基本思想：间接解法的基本思想：惩罚因子：惩罚因子：r1,r2第5页，此课件共102页哦一一.基本思想：基本思想：随机产生随机产生初始点初始点，随机产生随机产生若干个若干个搜索方向搜索方向d d k，并从中选择一，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保：确保：新迭代点在可行域中新迭代点在可行域中 目标函数值的下降性。目标函数值的下降性。X(0)X(L)X(1)X*x1x20第6页，此课件共102页哦二二.初始点的选择初始点的选择 随机方向法的初始点随机方向法的初始点X0必须是必须是一个可行点一个可行点，既满足全部，既满足全部 不等式约束条件。不等式约束条件。初始点可以通过随机选择的方法产生。初始点可以通过随机选择的方法产生。1）输入设计变量的上限值和下限值，即）输入设计变量的上限值和下限值，即aixi bi2）在区间（）在区间（0，1）内产生）内产生n个个伪随机数伪随机数qi3）计算随机点）计算随机点x的各分量的各分量xi=ai+qi(bi-ai)4）判别随机点）判别随机点X是否可行，若随机点可行，用是否可行，若随机点可行，用X0X 为初始点；若非可行点，转到步骤为初始点；若非可行点，转到步骤2）重新产生随）重新产生随 机点，直到可行为止。机点，直到可行为止。第7页，此课件共102页哦三三.可行搜索方向的产生可行搜索方向的产生从从k个随机方向中，个随机方向中，选取一个较好的方向。选取一个较好的方向。121211.jjjnjjinirrerr 1）在）在(-1,1)区间内产生伪随机数区间内产生伪随机数rij，得随机单位向量，得随机单位向量e j 2)取一试验步长取一试验步长a0，按下式计算，按下式计算k个随机点个随机点00jjXXa e第8页，此课件共102页哦3）检验）检验k个随机点是否为可行点，除去非可行点，计算个随机点是否为可行点，除去非可行点，计算 余下的可行点的目标函数值，比较其大小，选出目标余下的可行点的目标函数值，比较其大小，选出目标 函数最小的点函数最小的点XL。4)比较比较XL 和和X0两点的目标函数值两点的目标函数值:若若f(XL)f(X0)，则，则 取取XL 和和X0连线方向为可行搜索方向；连线方向为可行搜索方向；若若f(XL)f(X0)，则缩小步长，则缩小步长0，转步骤，转步骤2）重新计算，）重新计算，直至直至f(XL)f(X0)为止。为止。0 缩小到很小仍然找不到一个缩小到很小仍然找不到一个XL，使，使 f(XL)f(X(2)f(X(3),X(1)为最坏点，称为为最坏点，称为X(H)，通过映射得到新点，通过映射得到新点X(R)，X(R)X(S)a(X(S)-X(H)以以X(R)来代替来代替X(H)，组成新的单，组成新的单纯形纯形X(R)X(2)X(3)。其中。其中f(X(R)1；称为映射因子；称为映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定义定义：在：在n维空间中，由维空间中，由n+1个点组成个点组成的图形称单纯形。的图形称单纯形。X*()()11,1,2,1nSiii HXXinn 除除X(H)外，其它顶点的外，其它顶点的几何中心几何中心第13页，此课件共102页哦二二.复合形法：复合形法：定义定义：在在n维空间中，由维空间中，由 kn+1 个点组成的多面体称为复合形。个点组成的多面体称为复合形。基本思想基本思想：以一个较好的新点，代替原复合形中的最坏点，组成新的复以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：说明：单纯形是无约束优化方法，复合形用于约束优化的方法。单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。因为迭代过程始终在可行域内进行，运行结果可靠。第14页，此课件共102页哦三三.迭代方法迭代方法：1.映射法映射法：例：二维空间中，例：二维空间中，k=4，复合形是，复合形是四面体四面体X(1)X(2)X(3)X(4)，计算得：，计算得：f(X(1)f(X(2)f(X(3)1，建议先取，建议先取1.3。若求得的若求得的X(R)在可行域内，且在可行域内，且f(X(R)f(X(H)，则以，则以X(R)代替代替X(H)组成新复组成新复合形，再进行下轮迭代。合形，再进行下轮迭代。X(S)X(R)X(H)X(1)X(4)X(3)X(2)第15页，此课件共102页哦变形法一变形法一 扩张：扩张：若若f(X(R)f(X(L)，则可沿此方向扩张，则可沿此方向扩张 取取 若若f(X(E)f(X(L)，则扩张失败，以，则扩张失败，以X(R)代替代替X(H)组成新复合形组成新复合形()()()()(),1ESRSXXXX X(S)X(R)X(H)X(E)X(1)X(4)X(3)X(2)第16页，此课件共102页哦变形法二变形法二 收缩：收缩：若在映射法中若在映射法中f(X(R)f(X(H),则以则以a0.5a重复采用映射法重复采用映射法 若直至若直至a10-5仍不成功，考虑采用收缩法仍不成功，考虑采用收缩法 取取 若若f(X(K):检查终止准则检查终止准则 若若f(X(R)f(X(H)，以，以x(R)代替代替x(H)重构复合形后转步骤重构复合形后转步骤8f(X(R)f(X(H)，转步骤，转步骤71是，则是，则a=0.5a，转步骤，转步骤5否，则调用收缩法或压缩法，重构复合形后转步骤否，则调用收缩法或压缩法，重构复合形后转步骤3 2111,.,111,.,，其中：；kkjccjijjinf Xf XXXkkjk 是，则迭代结束，以此复合形的是，则迭代结束，以此复合形的x(L)为为X否，则以重构的复合形转步骤否，则以重构的复合形转步骤2第22页，此课件共102页哦例例 用复合形法求解用复合形法求解解解:1):1)产生初始复合形的顶点。产生初始复合形的顶点。取复合形顶点取复合形顶点的数目为的数目为k=2=2n=4,=4,初始复合形的四个顶点为初始复合形的四个顶点为以上四点均满足约束条件以上四点均满足约束条件2 2）四点的函数值）四点的函数值:由此可知最坏点为由此可知最坏点为X1 10 0,最好点为最好点为X4 40 0.221212121212min10460.11006,08fXxxx xxxs tg Xxxxx 001200341,5.5,1,42,6.4,3,3.5TTTTXXXX 0012003453.57,4746.56,26.75fXfXfXfX24602468x1x2X10X40X20X30第23页，此课件共102页哦3)3)计算除去坏点后，计算除去坏点后，各点的中心点各点的中心点4 4）检查）检查XC0点的可行性，点的可行性，由于由于 所以所以Xc0是可行点。是可行点。000023412321146.43.54.6333CXXXX 0001224.63-114.370,026,04.638Cg XXX 24602468x1x2X10X40X20X30Xc0第24页，此课件共102页哦5)求反射点求反射点Xr0并检查其可行性并检查其可行性取反射系数取反射系数 =1.3，可得反射点可得反射点也是可行的。也是可行的。6）比较反射点与最坏点的目标函数值）比较反射点与最坏点的目标函数值用用Xr0代替代替XH0，与其余，与其余3点构成新的复合形。点构成新的复合形。第二轮迭代，第二轮迭代，k=1新复合形的四个顶点为新复合形的四个顶点为其对应的函数值为其对应的函数值为00002213.31.34.634.635.53.499rCChXXXX00124.5953.57rfXfX 111211343.3,3.499,1,42,6.4,3,3.5TTTTXXXX 1112113424.59,47,46.56,26.75fXfXfXfX24602468x1x2X10X40X20X30Xr0第25页，此课件共102页哦Xr124602468x1x2X41X21X31 由此可见，由此可见，XH1=X21=1,4T，除去坏点后其余各点的中心为除去坏点后其余各点的中心为XC1=2.77,4.46T,满足所有约束条件满足所有约束条件，是可行点。是可行点。进行反射计算，进行反射计算，得得Xr1=5.071,5.058T,经检验经检验Xr1也是可行点，其也是可行点，其f(Xr1)=14.71 5 时，时，k 取值可小些。取值可小些。第27页，此课件共102页哦一一.基本思想基本思想：在可行域内选择一个初始点在可行域内选择一个初始点X(0)，确定了一个可行方向，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：和适当的步长后，按照下式进行迭代计算：X(k+1)=X(k)+ad 通过不断的调整可行方向，使迭代点逐步逼近约束最优通过不断的调整可行方向，使迭代点逐步逼近约束最优点。点。该方法是求解大型约束优化问题的主要方法之一。该方法是求解大型约束优化问题的主要方法之一。第28页，此课件共102页哦二二.搜索策略：搜索策略：根据目标函数和约束函数的不同性态，选择不同的搜索策略。根据目标函数和约束函数的不同性态，选择不同的搜索策略。1)边界反弹法边界反弹法：第一次搜索为负梯度方向，终止于边：第一次搜索为负梯度方向，终止于边 界。以后各次搜索方向均为适用可行方向，以最大界。以后各次搜索方向均为适用可行方向，以最大 步长从一个边界反弹到另一个边界，直至满足收敛步长从一个边界反弹到另一个边界，直至满足收敛 条件。条件。f(X)X(0)X(1)X(2)X*X(3)第29页，此课件共102页哦 2)2)最优步长法：最优步长法：第一次搜索为负梯度方向，终止于边第一次搜索为负梯度方向，终止于边 界。第二次搜索沿适用可行方向作一维搜索以最优界。第二次搜索沿适用可行方向作一维搜索以最优 步长因子求得最优点。反复以上两步，直至得到最步长因子求得最优点。反复以上两步，直至得到最 优点优点X*。X(1)X(0)X(2)X(3)X*f(X)第30页，此课件共102页哦 3)贴边搜索法贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。约束面，经过有限的几步就可以收敛到最优点。X(1)X(0)X(2)X*第31页，此课件共102页哦 若约束面是非线性时，从若约束面是非线性时，从X(k)点沿切线（面）方向点沿切线（面）方向d(k)搜索，搜索，会进入非可行域。会进入非可行域。容差带容差带：建立约束面的容差带建立约束面的容差带+，从从 X(k)出发，沿出发，沿d(k)方向搜索方向搜索到到 d(k)方向与方向与g(X)+=0 的交点的交点X 后，再沿适时约束的负梯后，再沿适时约束的负梯度方向返回约束面的度方向返回约束面的X(k+1)点。点。11kXXgXX(k)g(X)g(X)+X-g(X)d(k)X(k+1)第32页，此课件共102页哦调整步长因子调整步长因子1：X(k+1)=X-a1g(X)将将g(X)在在X 点泰勒展开，取一阶近似式：点泰勒展开，取一阶近似式：g(X)g(X)+g(X)T(X-X )进而得到：进而得到：g(X(k+1)g(X)+g(X)T(X-a1g(X)-X)g(X)+g(X)T-a1g(X)为了让为了让X(k+1)到达约束面，令到达约束面，令g(X(k+1)=0得得:1 Tg Xg Xg X X(k)X(k+1)g(X)g(X)+=0X-g(X)d(k)第33页，此课件共102页哦三三.可行方向的确定可行方向的确定可行方向应该满足可行方向应该满足设计点设计点可行可行及及目标函数值目标函数值下降下降两个条件两个条件 1)可行条件可行条件:gj(Xk)T dk 0 j=1,2,J(起作用约束的个数起作用约束的个数)g(Xk)dkg1(Xk)g2(Xk)dkXkg1(X)=0g2(X)=0第34页，此课件共102页哦三三.可行方向的确定可行方向的确定 2)目标函数值下降条件目标函数值下降条件:f(Xk)T dk 0 f(Xk)dkg1(X)=0g2(X)=0第35页，此课件共102页哦三三.可行方向的确定可行方向的确定gj(Xk)T dk 0 保证在可行域内保证在可行域内f(Xk)T dk 0,g2(Xt)0。应。应将将Xt 点调整到点调整到g1(Xt)=0 的约束面上的约束面上，因为对于，因为对于Xt 点来说，点来说，g1(Xt)的约束的约束违反量比违反量比 g2(Xt)大。若设大。若设gk(Xt)为约为约束违反量最大的约束条件，束违反量最大的约束条件，则应满则应满足足 1,2,max0ktjjJgXgXx1x20XkXk+1Xtg1(X)=0g2(X)=0第43页，此课件共102页哦将试验点将试验点Xt调整到调整到gk(Xt)=0的约束面上的方法的约束面上的方法:试探法：当试验点位于非可行域时，将试验步长试探法：当试验点位于非可行域时，将试验步长 t缩短；当位于可缩短；当位于可行域时，将试验步长行域时，将试验步长 t加倍，直至满足加倍，直至满足 gj(X)0(j=1,2,J)，即认为试验点已经被调整到约束面上了。，即认为试验点已经被调整到约束面上了。at=at+a0Xt=Xk+at dk gk(Xt)0?a0=0.7a0 at=at-a0否否a0=0.7a0 否否 gk(Xt)?是是 结束结束aM=at 是是第44页，此课件共102页哦若考虑约束允差若考虑约束允差，并按允差，并按允差中心中心/2做线性内插，做线性内插，可以得可以得到将到将Xt1调整到约束面上的步调整到约束面上的步长长 s。本次迭代步长取为本次迭代步长取为(b)插值法：利用线性插值将位于非可行域的试验点插值法：利用线性插值将位于非可行域的试验点Xt 调整到调整到 约束面上。设试验步长约束面上。设试验步长 t，求得可行试验点，求得可行试验点:当试验步长为当试验步长为 t+0时，时，求得非可行试验点求得非可行试验点:并设在该两点的约束函数分别为并设在该两点的约束函数分别为 gk(Xt1)0 和和 gk(Xt2)0 1kkttXXd 20kkttXXd 10210 5.ktsktktgXgXgX kMts asagk(X)a0gk(Xt2)atgk(Xt1)第45页，此课件共102页哦收敛条件收敛条件2()kTkf Xd 2）设计点）设计点Xk满足库恩满足库恩-塔克条件塔克条件1()()00(1,2,)Jkkjjjjf XgXjJ 1）设计点）设计点Xk及约束允差及约束允差 满足满足第46页，此课件共102页哦kTkkkTkkkdxfdxf当当5.0可行方向法的计算步骤可行方向法的计算步骤1）在可行域内选一个初始点）在可行域内选一个初始点X0，给出约束允差，给出约束允差 及收敛精度值及收敛精度值。2）令迭代次数）令迭代次数k=0,第一次迭代的搜索方向取第一次迭代的搜索方向取d0=f(X0)估算试验步长估算试验步长 t，计算试验点，计算试验点Xt若试验点若试验点Xt满足满足 gj(Xt)0，Xt点必位于第点必位于第j个约束面上，个约束面上，则则转步骤转步骤6）；）；若试验点若试验点Xt 位于可行域内，位于可行域内，则加大试验步长则加大试验步长 t，重新计算新，重新计算新的试验点，直至的试验点，直至Xt 越出可行域，越出可行域，再转步骤再转步骤5）；）；若试验点位于非可行域，若试验点位于非可行域，则直接转步骤则直接转步骤5）第47页，此课件共102页哦kTkkkTkkkdxfdxf当当5.0 5）确定约束违反量最大的约束函数）确定约束违反量最大的约束函数gk(Xt)。用试探法或插值法计算调整。用试探法或插值法计算调整步长步长 t，使试验点，使试验点xt返回到约束面上，返回到约束面上，则完成一次迭代。再令则完成一次迭代。再令k k+1,Xk=Xt ,转步骤转步骤6）6）在新的设计点在新的设计点Xk处产生新的可行方向处产生新的可行方向dk7)在在Xk点满足收敛条件，点满足收敛条件，停止迭代。约束最优解为停止迭代。约束最优解为X*=Xk,f(X*)=f(Xk)。否则，改变允差。否则，改变允差 的值，令的值，令 0 5.TkkkkTkkkfXdfXd 第48页，此课件共102页哦例例 用可行方向法求约束优化问题的约束最优解。用可行方向法求约束优化问题的约束最优解。Min f(X)=x12+2x22 -10 x1-x1x2-4x2+60 s.t.g1(X)=x1 0 g2(X)=x2 0 g3(X)=x1 6 0 g4(X)=x2 8 0 g5(X)=x1+x2 11 0 解：取初始点解：取初始点X0=0 1T，为约束边界，为约束边界g1(X)=0上的一点。第一次上的一点。第一次迭代用优选方向法确定可行方向。首先计算迭代用优选方向法确定可行方向。首先计算X0点的目标函数点的目标函数f(X0)和和约束函数约束函数g1(X0)的梯度的梯度01202121011242xxxfXxx0110gX第49页，此课件共102页哦为在可行下降扇形区内寻找最优方向，需求解一个以为在可行下降扇形区内寻找最优方向，需求解一个以可行方向可行方向d=d1 d2T为设计变量的优化问题，其数为设计变量的优化问题，其数学模型为：学模型为：0120110122212min()112.()0()11201TTTf Xddds tgXddf Xddddd 第50页，此课件共102页哦最优方向是最优方向是d*=0.984，0.179T，它是目标函数等值线（直线束，它是目标函数等值线（直线束）和约束函数）和约束函数d12+d22=1（半径为（半径为1的圆）的切点。第一次迭代的的圆）的切点。第一次迭代的可行方向为可行方向为d0=d*。d1d*-1101-1d2目标函数减小方向目标函数减小方向0120110122212min()112.()0()11201TTTf Xddds tgXddf Xddddd 第51页，此课件共102页哦 第一次迭代的可行方向为第一次迭代的可行方向为d0=d*。若步长取。若步长取 0=6.098，则，则 可见第一次迭代点可见第一次迭代点X1 在约束边界在约束边界g3(X1)=0上。上。100000.98466.09810.1792.091XXd x1x2g1(X)=0g4(X)=0g2(X)=0g3(X)=0g5(X)=0XkX1X0d00246810264810-f(X1)第52页，此课件共102页哦第二次迭代用梯度投影法来确定可行方向。迭代点第二次迭代用梯度投影法来确定可行方向。迭代点x1的目的目标函数负梯度标函数负梯度-f(X1)=0.092 5.818T，不满足方向的可行条，不满足方向的可行条件。现将件。现将f(X1)投影到约束边界投影到约束边界g3(X)=0上，上，计算投影算计算投影算子子P本次迭代的可行方向为本次迭代的可行方向为 1111133331()()()()1011001 010010001TTPIgXgXgXgX 1110()1()P f XdP f X 第53页，此课件共102页哦显然，显然，d1为沿约束边界为沿约束边界g3(X)=0的方向。若取的方向。若取 1=2.909，则本，则本次迭代点次迭代点即为该问题的约束最优点即为该问题的约束最优点X*则得约束最优解则得约束最优解 21116062.9092.09115XXd 6*,*115XfX x1x2g1(X)=0g4(X)=0g2(X)=0g3(X)=0g5(X)=0-f(X1)XkX1X0d00246810264810第54页，此课件共102页哦121211(,)()()()mlkkkkjkijX rrf XrG g XrH h X 将有约束的优化问题转化为无约束优化问题来求解。将有约束的优化问题转化为无约束优化问题来求解。保证保证：转化后的无约束优化问题与原约束问题具有：转化后的无约束优化问题与原约束问题具有同同 一最优解一最优解。min(),.()01,2,()01,2,njkf XXRs t gXjmhXkl 构成一个新的目标函数：构成一个新的目标函数：惩罚项惩罚项惩罚因子惩罚因子惩罚函数惩罚函数第55页，此课件共102页哦 从而保证从而保证11lim()0mkikirG g X 21lim()0lkjkjrH h X 12lim(,)()0kkkkX rrf X 惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质：根据惩罚项的不同构成形式，惩罚函数法又可分为根据惩罚项的不同构成形式，惩罚函数法又可分为内点惩内点惩罚函数法、外点惩罚函数法和混合惩罚函数法罚函数法、外点惩罚函数法和混合惩罚函数法121211(,)()()()mlkkkkjkijX rrf XrG gXrH h X 第56页，此课件共102页哦一一.内点惩罚函数法内点惩罚函数法 基本思想基本思想内点法将新目标函数内点法将新目标函数(X,r)构构筑在筑在可行域可行域D内内，随着惩罚因，随着惩罚因子子r(k)的不断的不断递减递减，生成一，生成一系列新目标函数系列新目标函数(Xk,r(k)，在可行域在可行域内内逐步迭代，产生的逐步迭代，产生的极值点极值点Xk*(r(k)序列从可行域序列从可行域内内部趋向原目标函数的约束部趋向原目标函数的约束最优点最优点 X*。例例：min.f(X)=x s.t.g(X)=1-x 011()()(,)kkX rxrx 新目标函数新目标函数:(X,r(k)(X*,r(k)=2x*-1r=0.1r=0.01(X,r(k)f(X)=xxf(X)1220g(x)=1-xX1*X2*r=0.001X*第57页，此课件共102页哦2.惩罚函数的形式惩罚函数的形式 ()()11(,)()()mkkuuX rf XrgX ()()1(,)()ln()mkkuuX rf XrgX 其中：惩罚（加权）因子其中：惩罚（加权）因子 降低系数降低系数 c：0 c 1)()1()0(.krrr1()()kkrc r 0lim)(kkr当()(,)(),*kkX rf XXX()0g X 当当x在可行域内在可行域内远离约束边界远离约束边界时：时：当当x由可行城内由可行城内靠近约束边界靠近约束边界时：时：0)(Xg0)(1Xg障碍项障碍项1()g X 第58页，此课件共102页哦 (0)(0)01()1muuf XrgX 3.3.几个参数的选择几个参数的选择惩罚因子初始值惩罚因子初始值 r(0)的选择：的选择：过大、过小均不好，建议考虑选择过大、过小均不好，建议考虑选择r(0)=1或者：或者：2.降低系数降低系数 c 的选择：的选择：c 的典型值为的典型值为0.10.7。3.初始点初始点 X(0)的选择的选择：要求：要求：在可行域内；在可行域内；不要离约束边界太近。不要离约束边界太近。方法：方法：人工估算，需要校核可行性；人工估算，需要校核可行性；计算机随机产生，也需校核可行性。计算机随机产生，也需校核可行性。()()11(,)()()mkkuuX rf XrgXX1*X2*X*xf(X)(X,r(k)(X*,r(k)=2x*-1r=0.1r=0.01r=0.001g(x)=1-x(X,r(k)122f(X)=x0第59页，此课件共102页哦 001 2()max,.,；ug XgXuS 初始点确定方法：初始点确定方法：任意给出一个初始点；任意给出一个初始点；判断其可行性，若违反了判断其可行性，若违反了S个约束，求出不满足约束中的最大值：个约束，求出不满足约束中的最大值：应用优化方法减少违反约束：应用优化方法减少违反约束：001 2101min.,.,.,nuuug XxRs tgXgXuSgXuSm 以求得的设计点作为新初始点，继续其判断可行性，若仍有不以求得的设计点作为新初始点，继续其判断可行性，若仍有不 满足的约束，则重复上述过程，直至初始点可行。满足的约束，则重复上述过程，直至初始点可行。第60页，此课件共102页哦 判断是否收敛：判断是否收敛：(1)*(1)*()1()()kkkkXrXr (1)*(1)*()2*(1)(1)()()()kkkkkkXrXrXr 4.4.内点惩罚函数法步骤内点惩罚函数法步骤：选取合适的初始点选取合适的初始点 X(0)，以及，以及 r(0)、c、计算精度、计算精度 1、2，令，令 k=0；构造惩罚（新目标）函数；构造惩罚（新目标）函数；调用无约束优化方法，求新目标函数的最优解调用无约束优化方法，求新目标函数的最优解 Xk*和和 (Xk,r(k)；若均满足，停止迭代，有约束优化问题的最优点为若均满足，停止迭代，有约束优化问题的最优点为 X*=Xk*；若有一个准则不满足，则令若有一个准则不满足，则令 并转入第并转入第 3 步，继续计算。步，继续计算。(0)()(1)()*(),1kkkkXXrrc rkk第61页，此课件共102页哦例：用内点法求下列问题的最优解：例：用内点法求下列问题的最优解：12211221min().()0()0F Xxxs tgXxxgXx 21(,)()ln()kkjjX rF XrgX 212211(,)ln()ln()kkkX rxxrxxrx 构造惩罚函数构造惩罚函数第62页，此课件共102页哦0)(00:0238.0)(135.0103.0:125.0333kkkXFXrXFXr当当75.1)(25.15.0:1000XFXr当09.1)(782.0309.0:5.0111XFXr当466.0)(283.0183.0:25.0222XFXr当212211(,)ln()ln()kkkX rxxrxxrx 第63页，此课件共102页哦0)(12xXg0)(2211xxXg1x2x21)(xxXF0)(00kkXFX11225.15.0:100Xr当782.0309.0:5.011Xr当283.0183.0:25.022Xr当212211(,)ln()ln()kkkX rxxrxxrx第64页，此课件共102页哦二二.外点惩罚函数法外点惩罚函数法 1.基本原理基本原理外点法将新目标函数外点法将新目标函数(X,r)构筑在构筑在可行域可行域 D 外外，随着惩罚因子，随着惩罚因子r(k)的不断的不断递增递增，生，生成一系列新目标函数成一系列新目标函数(Xk,r(k)，在，在可行域外可行域外逐步迭代，产生的极值点逐步迭代，产生的极值点Xk*(r(k)序序列从可行域列从可行域外外部趋向原目标函数的约束最优点部趋向原目标函数的约束最优点X*。2(11,1)kkX rxxxxxr 新目标函数：新目标函数：例：求下述约束优化问题的最优点。例：求下述约束优化问题的最优点。min.f(X)=x x R1 s.t g(X)=1-x 0(X*,(X*,r)可行域可行域g(X)=1-x=0f(X)=x*()1(,)22kxXr(X,r(k)f(X)12x120(X,r(k)X*(r(0)r(0)=0.25r(1)=0.5r(2)=1r(3)=2第65页，此课件共102页哦惩罚函数可取为惩罚函数可取为()()2211(,)()max(0,()()qmkkuvuvX rf XrgXhX 2)惩罚因子惩罚因子r(k).)()2()1()0(krrrr.,)(krk时当 1)当设计点在可行域内时当设计点在可行域内时,惩罚项为惩罚项为0,不惩罚不惩罚;当设当设 计点在可行域外计点在可行域外 时时,惩罚项大于惩罚项大于0,有惩罚作用。有惩罚作用。外点法可以用来求解含外点法可以用来求解含不等式和等式约束不等式和等式约束的优化问题。的优化问题。衰减项衰减项第66页，此课件共102页哦3.3.几个参数的选择几个参数的选择r(0)的选择的选择:r(0)过大，会使惩罚函数的等值线变形或偏心，求极过大，会使惩罚函数的等值线变形或偏心，求极 值困难。值困难。r(0)过小，迭代次数太多。过小，迭代次数太多。一般取一般取 r(0)1 或者或者 (0)000.021,2,.uurumm gXfX X(0)的选择：的选择：基本上可以在可行域内外，任意选择。基本上可以在可行域内外，任意选择。递增系数递增系数c的选择的选择：r(k)=c r(k-1)通常选择通常选择 5 10，可根据具体题目，进行试算调整。，可根据具体题目，进行试算调整。0(0)maxurr 第67页，此课件共102页哦例：用外点法求解下列有约束优化问题例：用外点法求解下列有约束优化问题3121min()(1)3f Xxx1122s.t.()10()0g XxgXx 解：惩罚函数为：解：惩罚函数为：32212121(,)(1)max(0,1)max(0,)3X rxxrxrx312123221212121(1)()0,()0)31(1)(1)()()0,()0)3xxg XgXxxrxrxg XgX第68页，此课件共102页哦212111(1)(1)2(1)xxxrx2211 2()rxx无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：*1*2()141()0.5x rrrrx rr 求偏导，得求偏导，得 第69页，此课件共102页哦rx1*x2*(r)f*(r)0.01-0.8098-50.0000-24.965-49.99770.1-0.4597-5.0000-2.2344-4.947410.2361-0.5000.96310.1295100.8322-0.05002.30682.000110000.9980-0.00052.66242.6582108/38/3优化过程收敛情况优化过程收敛情况第70页，此课件共102页哦 内、外点法不同内、外点法不同2212min()f Xxx1s.t.()10g Xx g(X)=0f(X)=123x1x20112f(X)=1012231g(X)=0 x1x2012231g(X)=0 x2f(X)=1x10122-11g(X)=0 x1x23-2-3-1-20122-11g(X)=0 x1x23-2-3-1-2330122-11g(X)=0 x1x23-2-3-1-23第71页，此课件共102页哦内点法特点：内点法特点：（1 1）初始点必须为严格的可行点）初始点必须为严格的可行点 （2 2）不适于具有等式约束的数学模型不适于具有等式约束的数学模型 （3 3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案 （4 4）一般收敛较慢）一般收敛较慢 （5 5）初始惩罚因子要选择得当）初始惩罚因子要选择得当 （6 6）惩罚因子为递减，递减率）惩罚因子为递减，递减率c c有有0c10c1 c1 第72页，此课件共102页哦三三.混合惩罚函数法混合惩罚函数法1.1.基本思想基本思想采用内点法和外点法相结合的混合惩罚函数法，发挥内点法和采用内点法和外点法相结合的混合惩罚函数法，发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。计问题。2.2.惩罚函数的形式惩罚函数的形式一般既包括障碍项，也包括衰减项。一般既包括障碍项，也包括衰减项。211010011.(,),lim01,的选择，参考内点法，应为内点。pmkkvuvukkxkX rfXrhXgXrrrrrrX 第73页，此课件共102页哦原理简单，算法易行，适应范围广，可利用无约束最原理简单，算法易行，适应范围广，可利用无约束最 优化方法资源。优化方法资源。（1）初始惩罚因子）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，取值不当可导致惩罚函数变得病态，使无约束优化计算困难。使无约束优化计算困难。（2）理论上讲，只有惩罚因子）理论上讲，只有惩罚因子 r(k)0（内点法）或（内点法）或 r(k)趋于无穷趋于无穷（外点法）时，算法才收敛，因此序（外点法）时，算法才收敛，因此序 列迭代过程收敛速度慢。列迭代过程收敛速度慢。计算过程稳定，计算效率超过惩罚函数法计算过程稳定，计算效率超过惩罚函数法第74页，此课件共102页哦min().()0pf Xs thX 一、一、拉格朗日乘子法（升维法拉格朗日乘子法（升维法）1,lpppF XfXhX 0(1,2,)iFinx 0(1,2,)pFpl l+n个方程个方程l+n个未知变量个未知变量第75页，此课件共102页哦例例:用拉格朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解2212121212min()60104.()80f Xxxxxx xs th Xxx22122121216010(4()8,)LxxxXxxxx x 1121020 xLxx 解解 构造拉格朗日函数构造拉格朗日函数1280 xLx 221420 xxLx 令令L=0,得到得到求解得：求解得：*12533()17xxf X 第76页，此课件共102页哦min().()0pf Xs thX 1(,)()()lpppL Xf XhX 构造拉格朗日函数构造拉格朗日函数构造外点惩罚函数构造外点惩罚函数()2