约束优化方法 (2)课件.ppt

《约束优化方法 (2)课件.ppt》由会员分享，可在线阅读，更多相关《约束优化方法 (2)课件.ppt（105页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于约束优化方法(2)现在学习的是第1页，共105页 机械优化设计中的问题，大多数属于约束优化设计机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为问题，其数学模型为6.1 6.1 概概 述述现在学习的是第2页，共105页6.1 6.1 概概 述述 直接解法：随机方向搜索法、复合形法、可行方向法等直接解法：随机方向搜索法、复合形法、可行方向法等 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法 增广乘子法等增广乘子法等一一.有约束问题解法分类：有约束问题解法分类：二二.直接解法的基本思想：直接解法的基本思想：合理选择初

2、始点，确定搜索方向，合理选择初始点，确定搜索方向，在可行域中在可行域中寻优，经过若干次迭代，收敛寻优，经过若干次迭代，收敛至最优点。至最优点。Xk+1=Xk+kdkdk:可行搜索方向。即设计点沿该方向作微量移动时可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下目标函数值将下 降降,且不会超出可行域且不会超出可行域直接解法通常适用于直接解法通常适用于仅含不等式约束仅含不等式约束的问题的问题现在学习的是第3页，共105页6.1 6.1 概概 述述特点：特点：由于求解过程在可行域内进行；无论迭代计算何时终止由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点都

3、可以获得一个比初始点好的设计点;若可行域是凸集，目标函数是定义在凸集上的凸函数，若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。则收敛到全局最优点；否则，结果与初始点有关。凸可行域凸可行域x1x20X(0)X(0)X(0)X(0)非凸可行域非凸可行域x1x20X1*X2*现在学习的是第4页，共105页6.1 6.1 概概 述述原理原理：将有约束优化问题转化为无约束优化问题来解决。：将有约束优化问题转化为无约束优化问题来解决。方法方法：以原目标函数和加权的约束函数共同构成一个新的：以原目标函数和加权的约束函数共同构成一个新的 目标函数目标函数 (X,r

4、1,r2)，成为无约束优化问题，成为无约束优化问题。通。通 过不断调整加权因子，产生一系列过不断调整加权因子，产生一系列函数的极小点函数的极小点 序列序列 X(k)*(r1(k),r2(k)k=0,1,2，逐渐收敛到，逐渐收敛到原目原目 标函数的约束最优解标函数的约束最优解。其中：新目标函数：其中：新目标函数：三三.间接解法的基本思想：间接解法的基本思想：惩罚因子：惩罚因子：r1,r2现在学习的是第5页，共105页6.2 6.2 随机方向法随机方向法一一.基本思想：基本思想：随机产生随机产生初始点初始点，随机产生随机产生若干个若干个搜索方向搜索方向d d k，并从中选择一，并从中选择一个能使目

5、标函数值下降最快的方向作为可行搜索方向进行个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。搜索。确保：确保：新迭代点在可行域中新迭代点在可行域中 目标函数值的下降性。目标函数值的下降性。X(0)X(L)X(1)X*x1x20现在学习的是第6页，共105页二二.初始点的选择初始点的选择 随机方向法的初始点随机方向法的初始点X0必须是必须是一个可行点一个可行点，既满足全部，既满足全部 不等式约束条件。不等式约束条件。初始点可以通过随机选择的方法产生。初始点可以通过随机选择的方法产生。1）输入设计变量的上限值和下限值，即）输入设计变量的上限值和下限值，即aixi bi2）在区间（）在区间（0

6、，1）内产生）内产生n个个伪随机数伪随机数qi3）计算随机点）计算随机点x的各分量的各分量xi=ai+qi(bi-ai)4）判别随机点）判别随机点X是否可行，若随机点可行，用是否可行，若随机点可行，用X0X 为初始点；若非可行点，转到步骤为初始点；若非可行点，转到步骤2）重新产生随）重新产生随 机点，直到可行为止。机点，直到可行为止。6.2 6.2 随机方向法随机方向法现在学习的是第7页，共105页三三.可行搜索方向的产生可行搜索方向的产生从从k个随机方向中，个随机方向中，选取一个较好的方向。选取一个较好的方向。1）在）在(-1,1)区间内产生伪随机数区间内产生伪随机数rij，得随机单位向量，

7、得随机单位向量e j 2)取一试验步长取一试验步长a0，按下式计算，按下式计算k个随机点个随机点6.2 6.2 随机方向法随机方向法现在学习的是第8页，共105页3）检验）检验k个随机点是否为可行点，除去非可行点，计算个随机点是否为可行点，除去非可行点，计算 余下的可行点的目标函数值，比较其大小，选出目标余下的可行点的目标函数值，比较其大小，选出目标 函数最小的点函数最小的点XL。4)比较比较XL 和和X0两点的目标函数值两点的目标函数值:若若f(XL)f(X0)，则，则 取取XL 和和X0连线方向为可行搜索方向；连线方向为可行搜索方向；若若f(XL)f(X0)，则缩小步长，则缩小步长0，转步

8、骤，转步骤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个个点点组组成成的的图图形称单纯形。形

9、称单纯形。X*除除X(H)外，其它顶点外，其它顶点的几何中心的几何中心现在学习的是第13页，共105页二二.复合形法：复合形法：定义定义：在在n维空间中，由维空间中，由 kn+1 个点组成的多面体称为复合形。个点组成的多面体称为复合形。基本思想基本思想：以以一一个个较较好好的的新新点点，代代替替原原复复合合形形中中的的最最坏坏点点，组组成成新新的的复复合形，以不断的迭代，使新复合形逐渐逼近最优点。合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：说明：单纯形是无约束优化方法，复合形用于约束优化的方法。单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。因

10、为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。因为迭代过程始终在可行域内进行，运行结果可靠。现在学习的是第14页，共105页三三.迭代方法迭代方法：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)组成新复合组成新复合形，再进行下轮迭代

11、。形，再进行下轮迭代。X(S)X(R)X(H)X(1)X(4)X(3)X(2)现在学习的是第15页，共105页2.变形法一变形法一 扩张：扩张：若若f(X(R)f(X(L)，则可沿此方向扩张，则可沿此方向扩张 取取 若若f(X(E)f(X(L)，则扩张失败，以，则扩张失败，以X(R)代替代替X(H)组成新复合形组成新复合形 X(S)X(R)X(H)X(E)X(1)X(4)X(3)X(2)现在学习的是第16页，共105页3.变形法二变形法二 收缩：收缩：若在映射法中若在映射法中f(X(R)f(X(H),则以则以a0.5a重复采用映射法重复采用映射法 若直至若直至a10-5仍不成功，考虑采用收缩法

12、仍不成功，考虑采用收缩法 取取 若若f(X(K):8.检查终止准则检查终止准则 若若f(X(R)f(X(H)，以，以x(R)代替代替x(H)重构复合形后转步骤重构复合形后转步骤8f(X(R)f(X(H)，转步骤，转步骤7是，则是，则a=0.5a，转步骤转步骤5否，则调用收缩法或压缩法，重构复合形后转步骤否，则调用收缩法或压缩法，重构复合形后转步骤3是，则迭代结束，以此复合形的是，则迭代结束，以此复合形的x(L)为为X否，则以重构的复合形转步骤否，则以重构的复合形转步骤2现在学习的是第22页，共105页例例 用复合形法求解用复合形法求解解解:1):1)产生初始复合形的顶点。产生初始复合形的顶点。

13、取复合取复合形顶点的数目为形顶点的数目为k=2=2n=4,=4,初始复合形的四初始复合形的四个顶点为个顶点为以上四点均满足约束条件以上四点均满足约束条件2 2）四点的函数值）四点的函数值:由此可知最坏点为由此可知最坏点为X1 10 0,最好点为最好点为X4 40 0.24602468x1x2X10X40X20X30现在学习的是第23页，共105页3)3)计算除去坏点后，计算除去坏点后，各点的中心点各点的中心点4 4）检查）检查XC0点的可行性，点的可行性，由于由于 所以所以Xc0是可行点。是可行点。24602468x1x2X10X40X20X30Xc0现在学习的是第24页，共105页5)求反射

14、点求反射点Xr0并检查其可行性并检查其可行性取反射系数取反射系数 =1.3，可得反射点可得反射点也是可行的。也是可行的。6）比较反射点与最坏点的目标函数值）比较反射点与最坏点的目标函数值用用Xr0代替代替XH0，与其余，与其余3点构成新的复合形。点构成新的复合形。第二轮迭代，第二轮迭代，k=1新复合形的四个顶点为新复合形的四个顶点为其对应的函数值为其对应的函数值为24602468x1x2X10X40X20X30Xr0现在学习的是第25页，共105页Xr124602468x1x2X41X21X31 由此可见，由此可见，XH1=X21=1,4T，除去坏点后其余各点的中心为除去坏点后其余各点的中心为

15、XC1=2.77,4.46T,满足所有约束满足所有约束条件，条件，是可行点。是可行点。进行反射计算，进行反射计算，得得Xr1=5.071,5.058T,经检验经检验Xr1也是可行点，其也是可行点，其f(Xr1)=14.71 5 时，时，k 取值可小些。取值可小些。现在学习的是第27页，共105页6.4 6.4 可行方向法可行方向法一一.基本思想基本思想：在可行域内选择一个初始点在可行域内选择一个初始点X(0)，确定了一个可行方，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：向和适当的步长后，按照下式进行迭代计算：X(k+1)=X(k)+ad 通过不断的调整可行方向，使迭代点逐步逼近约

16、束最优通过不断的调整可行方向，使迭代点逐步逼近约束最优点。点。该方法是求解大型约束优化问题的主要方法之一。该方法是求解大型约束优化问题的主要方法之一。现在学习的是第28页，共105页6.4 6.4 可行方向法可行方向法二二.搜索策略：搜索策略：根据目标函数和约束函数的不同性态，选择不同的搜索策略。根据目标函数和约束函数的不同性态，选择不同的搜索策略。1)边界反弹法边界反弹法：第一次搜索为负梯度方向，终止于边：第一次搜索为负梯度方向，终止于边 界。以后各次搜索方向均为适用可行方向，以最大界。以后各次搜索方向均为适用可行方向，以最大 步长从一个边界反弹到另一个边界，直至满足收敛步长从一个边界反弹到

17、另一个边界，直至满足收敛 条件。条件。f(X)X(0)X(1)X(2)X*X(3)现在学习的是第29页，共105页6.4 6.4 可行方向法可行方向法 2)2)最优步长法：最优步长法：第一次搜索为负梯度方向，终止于边第一次搜索为负梯度方向，终止于边 界。第二次搜索沿适用可行方向作一维搜索以最优界。第二次搜索沿适用可行方向作一维搜索以最优 步长因子求得最优点。反复以上两步，直至得到最步长因子求得最优点。反复以上两步，直至得到最 优点优点X*。X(1)X(0)X(2)X(3)X*f(X)现在学习的是第30页，共105页6.4 6.4 可行方向法可行方向法 3)贴边搜索法贴边搜索法：第一次搜索为负梯

18、度方向，终止于边界。以后各次搜索贴边第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。约束面，经过有限的几步就可以收敛到最优点。X(1)X(0)X(2)X*现在学习的是第31页，共105页6.4 6.4 可行方向法可行方向法 若约束面是非线性时，从若约束面是非线性时，从X(k)点沿切线（面）方向点沿切线（面）方向d(k)搜搜索，会进入非可行域。索，会进入非可行域。容差带容差带：建立约束面的容差带建立约

19、束面的容差带+，从从 X(k)出发，沿出发，沿d(k)方向搜索方向搜索到到 d(k)方向与方向与g(X)+=0 的交点的交点X 后，再沿适时约束的负后，再沿适时约束的负梯度方向返回约束面的梯度方向返回约束面的X(k+1)点。点。X(k)g(X)g(X)+X-g(X)d(k)X(k+1)现在学习的是第32页，共105页6.4 6.4 可行方向法可行方向法调整步长因子调整步长因子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)-

20、X)g(X)+g(X)T-a1g(X)为了让为了让X(k+1)到达约束面，令到达约束面，令g(X(k+1)=0得得:X(k)X(k+1)g(X)g(X)+=0X-g(X)d(k)现在学习的是第33页，共105页6.4 6.4 可行方向法可行方向法三三.可行方向的确定可行方向的确定可行方向应该满足可行方向应该满足设计点设计点可行可行及及目标函数值目标函数值下降下降两个条件两个条件 1)可行条件可行条件:gj(Xk)T dk 0 j=1,2,J(起作用约束的个数起作用约束的个数)g(Xk)dkg1(Xk)g2(Xk)dkXkg1(X)=0g2(X)=0现在学习的是第34页，共105页6.4 6.4

21、 可行方向法可行方向法三三.可行方向的确定可行方向的确定 2)目标函数值下降条件目标函数值下降条件:f(Xk)T dk 0 f(Xk)dkg1(X)=0g2(X)=0现在学习的是第35页，共105页6.4 6.4 可行方向法可行方向法三三.可行方向的确定可行方向的确定gj(Xk)T dk 0 保证在可行域内保证在可行域内f(Xk)T dk 0,g2(Xt)0。应应将将Xt 点点调调整整到到g1(Xt)=0 的的约约束束面面上上，因因为为对对于于Xt 点点来来说说，g1(Xt)的的约约束束违违反反量量比比 g2(Xt)大大。若若设设gk(Xt)为为约约束束违违反反量量最最大大的的约约束束条条件件

22、，则则应满足应满足 x1x20XkXk+1Xtg1(X)=0g2(X)=0现在学习的是第43页，共105页将试验点将试验点Xt调整到调整到gk(Xt)=0的约束面上的方法的约束面上的方法:(a)试探法：当试验点位于非可行域时，将试验步长试探法：当试验点位于非可行域时，将试验步长 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 否

23、否 gk(Xt)?是是 结束结束aM=at 是是现在学习的是第44页，共105页若若考考虑虑约约束束允允差差，并并按按允允差差中中心心/2做做线线性性内内插插，可可以以得得到到将将Xt1调整到约束面上的步长调整到约束面上的步长 s。本次迭代步长取为本次迭代步长取为(b)插值法：利用线性插值将位于非可行域的试验点插值法：利用线性插值将位于非可行域的试验点Xt 调整到调整到 约束面上。设试验步长约束面上。设试验步长 t，求得可行试验点，求得可行试验点:当试验步长为当试验步长为 t+0时，时，求得非可行试验点求得非可行试验点:并设在该两点的约束函数分别为并设在该两点的约束函数分别为 gk(Xt1)0

24、 和和 gk(Xt2)0 asagk(X)a0gk(Xt2)atgk(Xt1)现在学习的是第45页，共105页收敛条件收敛条件2）设计点）设计点Xk满足库恩满足库恩-塔克条件塔克条件 1）设计点）设计点Xk及约束允差及约束允差 满足满足现在学习的是第46页，共105页可行方向法的计算步骤可行方向法的计算步骤1）在可行域内选一个初始点）在可行域内选一个初始点X0，给出约束允差，给出约束允差 及收敛精度值及收敛精度值。2）令迭代次数）令迭代次数k=0,第一次迭代的搜索方向取第一次迭代的搜索方向取d0=f(X0)3)估算试验步长估算试验步长 t，计算试验点，计算试验点Xt4)若试验点若试验点Xt满足

25、满足 gj(Xt)0，Xt点必位于第点必位于第j个约束面上，个约束面上，则则转步骤转步骤6）；）；若试验点若试验点Xt 位于可行域内，位于可行域内，则加大试验步长则加大试验步长 t，重新计算新，重新计算新的试验点，直至的试验点，直至Xt 越出可行域，越出可行域，再转步骤再转步骤5）；）；若试验点位于非可行域，若试验点位于非可行域，则直接转步骤则直接转步骤5）现在学习的是第47页，共105页 5）确定约束违反量最大的约束函数）确定约束违反量最大的约束函数gk(Xt)。用试探法或插值法计算。用试探法或插值法计算调整步长调整步长 t，使试验点，使试验点xt返回到约束面上，返回到约束面上，则完成一次迭

26、代。再令则完成一次迭代。再令k k+1,Xk=Xt ,转步骤转步骤6）6）在新的设计点在新的设计点Xk处产生新的可行方向处产生新的可行方向dk7)在在Xk点满足收敛条件，点满足收敛条件，停止迭代。约束最优解为停止迭代。约束最优解为X*=Xk,f(X*)=f(Xk)。否则，改变允差。否则，改变允差 的值，令的值，令现在学习的是第48页，共105页例例 用可行方向法求约束优化问题的约束最优解。用可行方向法求约束优化问题的约束最优解。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

27、 8 0 g5(X)=x1+x2 11 0 解解：取取初初始始点点X0=0 1T，为为约约束束边边界界g1(X)=0上上的的一一点点。第第一一次次迭迭代代用用优优选选方方向向法法确确定定可可行行方方向向。首首先先计计算算X0点点的的目目标标函函数数f(X0)和约束函数和约束函数g1(X0)的梯度的梯度现在学习的是第49页，共105页为为在在可可行行下下降降扇扇形形区区内内寻寻找找最最优优方方向向，需需求求解解一一个个以以可可行行方方向向d=d1 d2T为为设设计计变变量量的的优优化化问问题题，其其数数学学模型为：模型为：现在学习的是第50页，共105页最优方向是最优方向是d*=0.984，0.

28、179T，它是目标函数等值线（直线束）和，它是目标函数等值线（直线束）和约束函数约束函数d12+d22=1（半径为（半径为1的圆）的切点。第一次迭代的可行方向的圆）的切点。第一次迭代的可行方向为为d0=d*。d1d*-1101-1d2目标函数减小方向目标函数减小方向现在学习的是第51页，共105页 第一次迭代的可行方向为第一次迭代的可行方向为d0=d*。若步长取。若步长取 0=6.098，则，则 可见第一次迭代点可见第一次迭代点X1 在约束边界在约束边界g3(X1)=0上。上。x1x2g1(X)=0g4(X)=0g2(X)=0g3(X)=0g5(X)=0XkX1X0d0024681026481

29、0-f(X1)现在学习的是第52页，共105页第二次迭代用梯度投影法来确定可行方向。迭代点第二次迭代用梯度投影法来确定可行方向。迭代点x1的的目标函数负梯度目标函数负梯度-f(X1)=0.092 5.818T，不满足方向的可行，不满足方向的可行条件。现将条件。现将f(X1)投影到约束边界投影到约束边界g3(X)=0上，上，计算投影算计算投影算子子P本次迭代的可行方向为本次迭代的可行方向为现在学习的是第53页，共105页显然，显然，d1为沿约束边界为沿约束边界g3(X)=0的方向。若取的方向。若取 1=2.909，则本，则本次迭代点次迭代点即为该问题的约束最优点即为该问题的约束最优点X*则得约束

30、最优解则得约束最优解 x1x2g1(X)=0g4(X)=0g2(X)=0g3(X)=0g5(X)=0-f(X1)XkX1X0d00246810264810现在学习的是第54页，共105页将有约束的优化问题转化为无约束优化问题来求解。将有约束的优化问题转化为无约束优化问题来求解。保证保证：转化后的无约束优化问题与原约束问题具有：转化后的无约束优化问题与原约束问题具有同同 一最优解一最优解。构成一个新的目标函数：构成一个新的目标函数：6.5 6.5 惩罚函数法惩罚函数法惩罚项惩罚项惩罚因子惩罚因子惩罚函数惩罚函数现在学习的是第55页，共105页 从而保证从而保证惩罚项必须具有以下极限性质：惩罚项必

31、须具有以下极限性质：根根据据惩惩罚罚项项的的不不同同构构成成形形式式，惩惩罚罚函函数数法法又又可可分分为为内内点点惩惩罚罚函函数法、外点惩罚函数法和混合惩罚函数法数法、外点惩罚函数法和混合惩罚函数法6.5 6.5 惩罚函数法惩罚函数法现在学习的是第56页，共105页一一.内点惩罚函数法内点惩罚函数法 1.基本思想基本思想内内点点法法将将新新目目标标函函数数(X,r)构构筑筑在在可可行行域域D内内，随随着着惩惩罚罚因因子子r(k)的的不不断断递递减减，生生成成一一系系列列新新目目标标函函数数(Xk,r(k)，在在可可行行域域内内逐逐步步迭迭代代，产产生生的的极极值值点点Xk*(r(k)序序列列从

32、从可可行行域域内内部部趋趋向向原原目目标标函函数数的的约约束束最优点最优点 X*。例例：min.f(X)=x s.t.g(X)=1-x 0新目标函数新目标函数:(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页，共105页2.惩罚函数的形式惩罚函数的形式 其中：惩罚（加权）因子其中：惩罚（加权）因子 降低系数降低系数 c：0 c 1当当x在在可可行行域域内内远远离离约约束束边界时：边界时：当当x由由可可行行城城内内靠靠近近约约束束边界时：边界时：障碍项障碍项现在学习的是第

33、58页，共105页3.3.几个参数的选择几个参数的选择1.惩罚因子初始值惩罚因子初始值 r(0)的选择：的选择：过大、过小均不好，建议考虑选择过大、过小均不好，建议考虑选择r(0)=1或或者：者：2.降低系数降低系数 c 的选择：的选择：c 的典型值为的典型值为0.10.7。3.初始点初始点 X(0)的选择的选择：要求：要求：在可行域内；在可行域内；不要离约束边界太近。不要离约束边界太近。方法：方法：人工估算，需要校核可行性；人工估算，需要校核可行性；计算机随机产生，也需校核可行性。计算机随机产生，也需校核可行性。X1*X2*X*xf(X)(X,r(k)(X*,r(k)=2x*-1r=0.1r

34、=0.01r=0.001g(x)=1-x(X,r(k)122f(X)=x0现在学习的是第59页，共105页 初始点确定方法：初始点确定方法：任意给出一个初始点；任意给出一个初始点；判断其可行性，若违反了判断其可行性，若违反了S个约束，求出不满足约束中的最大值：个约束，求出不满足约束中的最大值：应用优化方法减少违反约束：应用优化方法减少违反约束：以求得的设计点作为新初始点，继续其判断可行性，若仍有不以求得的设计点作为新初始点，继续其判断可行性，若仍有不 满足的约束，则重复上述过程，直至初始点可行。满足的约束，则重复上述过程，直至初始点可行。现在学习的是第60页，共105页 判断是否收敛：判断是否

35、收敛：4.4.内点惩罚函数法步骤内点惩罚函数法步骤：选取合适的初始点选取合适的初始点 X(0)，以及，以及 r(0)、c、计算精度、计算精度 1、2，令，令 k=0；构造惩罚（新目标）函数；构造惩罚（新目标）函数；调用无约束优化方法，求新目标函数的最优解调用无约束优化方法，求新目标函数的最优解 Xk*和和 (Xk,r(k)；若均满足，停止迭代，有约束优化问题的最优点为若均满足，停止迭代，有约束优化问题的最优点为 X*=Xk*；若有一个准则不满足，则令若有一个准则不满足，则令 并转入第并转入第 3 步，继续计算。步，继续计算。现在学习的是第61页，共105页例：用内点法求下列问题的最优解：例：用

36、内点法求下列问题的最优解：构造惩罚函数构造惩罚函数现在学习的是第62页，共105页现在学习的是第63页，共105页112现在学习的是第64页，共105页二二.外点惩罚函数法外点惩罚函数法 1.基本原理基本原理外外点点法法将将新新目目标标函函数数(X,r)构构筑筑在在可可行行域域 D 外外，随随着着惩惩罚罚因因子子r(k)的的不不断断递递增增，生生成成一一系系列列新新目目标标函函数数(Xk,r(k)，在在可可行行域域外外逐逐步步迭迭代代，产产生生的的极极值值点点Xk*(r(k)序序列从可行域列从可行域外外部趋向原目标函数的约束最优点部趋向原目标函数的约束最优点X*。新目标函数：新目标函数：例：求

37、下述约束优化问题的最优点。例：求下述约束优化问题的最优点。min.f(X)=x x R1 s.t g(X)=1-x 0(X*,(X*,r)可行域可行域g(X)=1-x=0f(X)=x(X,r(k)f(X)12x120(X,r(k)X*(r(0)r(0)=0.25r(1)=0.5r(2)=1r(3)=2现在学习的是第65页，共105页惩罚函数可取为惩罚函数可取为2)惩罚因子惩罚因子r(k)1)当设计点在可行域内时当设计点在可行域内时,惩罚项为惩罚项为0,不惩罚不惩罚;当设当设 计点在可行域外计点在可行域外 时时,惩罚项大于惩罚项大于0,有惩罚作用。有惩罚作用。外点法可以用来求解含外点法可以用来求

38、解含不等式和等式约束不等式和等式约束的优化问题。的优化问题。衰减项衰减项现在学习的是第66页，共105页3.3.几个参数的选择几个参数的选择r(0)的选择的选择:r(0)过大，会使惩罚函数的等值线变形或偏心，求极过大，会使惩罚函数的等值线变形或偏心，求极 值困难。值困难。r(0)过小，迭代次数太多。过小，迭代次数太多。一般取一般取 r(0)1 或者或者X(0)的选择：的选择：基本上可以在可行域内外，任意选择。基本上可以在可行域内外，任意选择。递增系数递增系数c的选择的选择：r(k)=c r(k-1)通常选择通常选择 5 10，可根据具体题目，进行试算调整。，可根据具体题目，进行试算调整。现在学

39、习的是第67页，共105页例：用外点法求解下列有约束优化问题例：用外点法求解下列有约束优化问题解：惩罚函数为：解：惩罚函数为：现在学习的是第68页，共105页无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：求偏导，得求偏导，得 现在学习的是第69页，共105页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.662

40、42.6582108/38/3优化过程收敛情况优化过程收敛情况现在学习的是第70页，共105页 内、外点法不同内、外点法不同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页，共105页内点法特点：内点法特点：（1 1）初始点必须为严格的可行点）初始点必须为严格的可行点 （2 2）不适于具有等式约束的数学模型不适于具有等式约

41、束的数学模型 （3 3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案 （4 4）一般收敛较慢）一般收敛较慢 （5 5）初始惩罚因子要选择得当）初始惩罚因子要选择得当 （6 6）惩罚因子为递减，递减率）惩罚因子为递减，递减率c c有有0c10c1 c1 现在学习的是第72页，共105页三三.混合惩罚函数法混合惩罚函数法1.1.基本思想基本思想采用内点法和外点法相结合的混合惩罚函数法，发挥内点法和采用内点法和外点法相结合的混合惩罚函数法，发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。计问题。2.

42、2.惩罚函数的形式惩罚函数的形式一般既包括障碍项，也包括衰减项。一般既包括障碍项，也包括衰减项。现在学习的是第73页，共105页惩罚函数法惩罚函数法优点优点优点优点：原理简单，算法易行，适应范围广，可利用无约束最原理简单，算法易行，适应范围广，可利用无约束最 优化方法资源。优化方法资源。缺点缺点缺点缺点：（1）初始惩罚因子）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，取值不当可导致惩罚函数变得病态，使无约束优化计算困难。使无约束优化计算困难。（2）理论上讲，只有惩罚因子）理论上讲，只有惩罚因子 r(k)0（内点法）或（内点法）或 r(k)趋于无穷趋于无穷（外点法）时，算法才收敛，因此序

43、（外点法）时，算法才收敛，因此序 列迭代过程收敛速度慢。列迭代过程收敛速度慢。增广乘子法增广乘子法 外点惩罚函数拉格朗日函数外点惩罚函数拉格朗日函数外点惩罚函数拉格朗日函数外点惩罚函数拉格朗日函数 计算过程稳定，计算效率超过惩罚函数法计算过程稳定，计算效率超过惩罚函数法现在学习的是第74页，共105页拉格朗日函数拉格朗日函数拉格朗日函数拉格朗日函数一、一、拉格朗日乘子法（升维法拉格朗日乘子法（升维法）6.6 6.6 增广乘子法增广乘子法l+n个方程个方程l+n个未知变量个未知变量具有相具有相具有相具有相同的最同的最同的最同的最优解优解优解优解X X*现在学习的是第75页，共105页例例:用拉格

44、朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解解解 构造拉格朗日函数构造拉格朗日函数令令L=0,得到得到求解得：求解得：现在学习的是第76页，共105页构造拉格朗日函数构造拉格朗日函数构造外点惩罚函数构造外点惩罚函数现在学习的是第77页，共105页二、等式约束的增广乘子法二、等式约束的增广乘子法 采采用用拉拉格格朗朗日日乘乘子子法法时时求求解解有有难难度度,而而罚罚函函数数法法当当迭迭代代点点接接近近边边界界时时函函数数常常有有病病态态,此此法法的的思思路路是是把把两两者者结结合合起起来来。其其增增广拉格朗日函数为广拉格朗日函数为:现在学习的是第78页，共105页不论不论r(k

45、)取何值取何值，增广乘子函数增广乘子函数与与原函数原函数具有具有相同相同的约束极值点的约束极值点X*，与，与拉格朗日函数拉格朗日函数有有相同相同的拉格朗日乘子向量。的拉格朗日乘子向量。二、等式约束的增广乘子法二、等式约束的增广乘子法现在学习的是第79页，共105页例例:求下列优化问题的最优解求下列优化问题的最优解构造拉格朗日函数构造拉格朗日函数:求解可得求解可得:对应海赛矩阵对应海赛矩阵:非正定非正定现在学习的是第80页，共105页构造增广乘子函数构造增广乘子函数:对应海赛矩阵对应海赛矩阵:r不需要趋于无穷大，只要取一个不需要趋于无穷大，只要取一个足够大的定值足够大的定值，且恰好选，且恰好选取

46、了一个取了一个=*,X*就是函数就是函数M(X，r)的极小点的极小点现在学习的是第81页，共105页二、等式约束的增广乘子法二、等式约束的增广乘子法现在学习的是第82页，共105页增广乘子法中的乘子迭代增广乘子法中的乘子迭代二、等式约束的增广乘子法二、等式约束的增广乘子法校正量校正量近似牛顿法近似牛顿法得到的校正量得到的校正量现在学习的是第83页，共105页参数选取参数选取没有其它信息情况下，初始乘子向量没有其它信息情况下，初始乘子向量 增广乘子函数和外点惩罚函数形式相同；从增广乘子函数和外点惩罚函数形式相同；从第二次迭代开始，乘子向量按公式进行校正。第二次迭代开始，乘子向量按公式进行校正。惩

47、罚因子初始值惩罚因子初始值r r(0)(0)按照外点法取。按照外点法取。从第二次迭代开始，惩罚因子按下式递增：从第二次迭代开始，惩罚因子按下式递增：惩罚因子递增系数，惩罚因子递增系数，=10=10判别数，通常取判别数，通常取0.250.25二、等式约束的增广乘子法二、等式约束的增广乘子法现在学习的是第84页，共105页等式约束增广乘子法等式约束增广乘子法计算步骤计算步骤：1.选选取取设设计计变变量量的的初初始始点点X0，惩惩罚罚因因子子初初值值r0，增增长长系系数数，判判别别数数，收收敛敛精精度度，乘乘子子向向量量p0=0 (p=1,2,l),迭代次数迭代次数k=0；2.构造增广乘子函数构造增

48、广乘子函数M(X,r)，并用无约束方法求，并用无约束方法求 min M(X,r)，得无约束最优解，得无约束最优解Xk=X*(k,rk)3.计算计算4.校正乘子向量校正乘子向量5.如如果果 ，迭迭代代终终止止，约约束束最最优优解解为为X*=Xk，*=k+1;否则转步骤否则转步骤66.计算惩罚因子计算惩罚因子 再令再令k=k+1，转步骤，转步骤2现在学习的是第85页，共105页例例:用用增广增广乘子法求下列问题的最优解乘子法求下列问题的最优解解解 构造增广乘子函数构造增广乘子函数确定初始参数：确定初始参数：2,0=0,r0=0.1，现在学习的是第86页，共105页利用解析法求利用解析法求min M

49、(X,r)，令，令 M(X,r)0，可得最优解：可得最优解：现在学习的是第87页，共105页krkkxk10.10(0.0714,0,2142)20.20.0714(0.1507,0.4523)30.40.1507(0.2118,0.6355)40.80.2118(0.3409,0.7227)51.60.2409(0.2487,0.7463)63.20.2487(0.2499,0.7497)76.40.2499(0.2499,0.7499)迭代迭代6次得到最优解次得到最优解,迭代结果如下迭代结果如下:精确解精确解:X*=0.25,0.75,f(X*)=0.125现在学习的是第88页，共105页

50、三、三、不等式约束增广乘子法不等式约束增广乘子法用于求解不等式约束优化问题。用于求解不等式约束优化问题。引入松弛变量引入松弛变量Zz1,z2,zmT,并且令并且令则不等式约束优化问题转化为等式优化问题则不等式约束优化问题转化为等式优化问题现在学习的是第89页，共105页构造增广乘子函数构造增广乘子函数由于引入松弛变量由于引入松弛变量Z，使原有的，使原有的n维极值问题扩充为维极值问题扩充为n+m维问题，计维问题，计算工作量和求解难度增大，可简化算工作量和求解难度增大，可简化:三、三、不等式约束增广乘子法不等式约束增广乘子法现在学习的是第90页，共105页带入到带入到得到：得到：现在学习的是第91