机械优化设计第6章约束优化方法课件.ppt

1、机械优化设计第六章第六章 约束优化方法约束优化方法 6.1 概概 述述 6.2 随机方向法随机方向法 6.3 复合形方法复合形方法 6.4 可行方向法可行方向法 6.5 惩罚函数法惩罚函数法 6.6 增广乘子法增广乘子法 6.11遗传算遗传算 法简述法简述6.10结构优化法简述结构优化法简述 6.9 二次规划法二次规划法 6.8广义简约梯度法广义简约梯度法 6.7 非线性规划问题非线性规划问题的线性化解法的线性化解法线线性逼近法性逼近法 机械优化设计中的问题，大多数属于约束优化设机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为计问题，其数学模型为min( ),. .( )01,2

2、,( )01,2,njkfRst gjmhklxxxx第一节第一节 概述概述第一节第一节 概述概述l 直接解法：随机方向搜索法、复合形法、可行方向法直接解法：随机方向搜索法、复合形法、可行方向法l 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法法一一. . 有约束问题解法分类：有约束问题解法分类：二二. . 直接解法的基本思想：直接解法的基本思想： 合理选择初始点，确定搜索方向，合理选择初始点，确定搜索方向，在可行域中在可行域中寻优，经过若干次迭寻优，经过若干次迭代，收敛至最优点。代，收敛至最优点。 xk+1= xk+kdkdk:

3、 可行搜索方向。即设计点沿该方向作微量移动时可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下目标函数值将下 降降,且不会超出可行域且不会超出可行域直接解法通常适用于直接解法通常适用于仅含不等式约束仅含不等式约束的问题的问题第一节第一节 概述概述特点：特点：由于求解过程在可行域内进行；无论迭代计算何时终止由于求解过程在可行域内进行；无论迭代计算何时终止, , 都可以获得一个比初始点好的设计点都可以获得一个比初始点好的设计点; ; 若可行域是凸集，目标函数是定义在凸集上的凸函数，若可行域是凸集，目标函数是定义在凸集上的凸函数， 则收敛到全局最优点；否则，结果与初始点有关。则收敛到全局最优

4、点；否则，结果与初始点有关。凸可行域凸可行域非凸可行域非凸可行域第一节第一节 概述概述)(),(21xfrrx)()(1211xhHrxgGrpvvmuu原理原理：将有约束优化问题转化为无约束优化问题来解决。：将有约束优化问题转化为无约束优化问题来解决。方法方法：以原目标函数和加权的约束函数共同构成一个新的：以原目标函数和加权的约束函数共同构成一个新的 目标函数目标函数 ( x, r1 ,r2 )，成为无约束优化问题，成为无约束优化问题 。通。通 过不断调整加权因子，产生一系列过不断调整加权因子，产生一系列函数的极小点函数的极小点 序列序列 x(k)* (r1(k),r2(k) k= 0,1,

5、2 ，逐渐收敛到，逐渐收敛到原目标原目标 函数的约束最优解函数的约束最优解。 其中：新目标函数：其中：新目标函数：三三. . 间接解法的基本思想：间接解法的基本思想： 惩罚因子：惩罚因子： r1 , r2第二节第二节 随机方向法随机方向法一一. . 基本思想：基本思想：随机产生随机产生初始点初始点，随机产生随机产生若干个若干个搜索方向搜索方向d dk k，并从中，并从中选择一个能使目标函数值下降最快的方向作为可行搜索选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。方向进行搜索。确保：确保： 新迭代点在可行域中新迭代点在可行域中 目标函数值的下降性。目标函数值的下降性。x(0)x(

6、L)x(1)x*二二. .初始点的选择初始点的选择 随机方向法的初始点随机方向法的初始点x0必须是必须是一个可行点一个可行点，既满足全部，既满足全部 不等式约束条件。不等式约束条件。初始点可以通过随机选择的方法产生。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即）输入设计变量的下限值和上限值，即iiiaxb2）在区间（）在区间（0，1）内产生）内产生n个个伪随机数伪随机数iq3）计算随机点）计算随机点x的各分量的各分量()iiiiixabaq4）判别随机点）判别随机点x是否可行，若随机点可行，用是否可行，若随机点可行，用x0 x 为初始点；若非可行点，转到步骤为初始点；

7、若非可行点，转到步骤2）重新产生随）重新产生随 机点，直到可行为止。机点，直到可行为止。第二节第二节 随机方向法随机方向法三三. .可行搜索方向的产生可行搜索方向的产生从从k个随机方向中，个随机方向中， 选取一个较好的方向。选取一个较好的方向。 121211.jjjnjjinirrerr jir1）在）在(-1,1)区间内产生伪随机数区间内产生伪随机数 ，得随机单位向量，得随机单位向量je2) 取一试验步长取一试验步长a0，按下式计算，按下式计算k个随机点个随机点00jjxxa e第二节第二节 随机方向法随机方向法3）检验）检验k个随机点是否为可行点，除去非可行点，计算个随机点是否为可行点，除

8、去非可行点，计算 余下的可行点的目标函数值，比较其大小，选出目标余下的可行点的目标函数值，比较其大小，选出目标 函数最小的点函数最小的点xL 。4) 比较比较xL 和和x0两点的目标函数值两点的目标函数值: 若若f(xL) f(x0)，则，则 取取xL 和和x0连线方向为可行搜索方向；连线方向为可行搜索方向； 若若f(xL) f(x0)，则缩小步长，则缩小步长0 ，转步骤，转步骤1）重新计算，）重新计算， 直至直至f(xL) f(x0)为止。为止。 0 缩小到很小仍然找不到一个缩小到很小仍然找不到一个xL，使，使 f(xL) f(x(2)f(x(3), x(1)为最坏点，为最坏点，称为称为x(

9、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 X(1)(1)=X=X(H)(H)X X(2)(2)X X(3)(3)X X(S)(S)X X(R)(R)=X=X(4)(4)X X(5)(5)X X(6)(6)定义定义：在：在n n维空间中，由维空间中，由n n+1+1个点组个点组成的图形称单纯形。成的图形称单纯形。X X* *()( )11,1,2,1nSiii Hxxinn 除除x(H)外，其它顶外

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

11、比单纯形更灵活易变。l 复合形只能解决不等式约束问题。复合形只能解决不等式约束问题。l 因为迭代过程始终在可行域内进行，运行结果可靠。因为迭代过程始终在可行域内进行，运行结果可靠。三三. . 迭代方法：迭代方法：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)组组成新复合形，再进行下轮迭代。成新复合形，再进行下轮迭代。

12、X(S)X(R) X(H)2. 变形法一变形法一 扩张：扩张： 若若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)3. 变形法二变形法二 收缩：收缩： 若在映射法中若在映射法中f(x(R) f (x(H),则以则以a0.5a重复采用映射法重复采用映射法 若直至若直至a10-5仍不成功，考虑采用收缩法仍不成功，考虑采用收缩法 取取 若若f(x(K) : 8.检查终止准则检查终止准则 若若f(

13、x(R) 5 时，时，k 取值可小些。取值可小些。 一一. . 基本思想基本思想：在可行域内选择一个初始点在可行域内选择一个初始点x(0)，确定了一个可行，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：方向和适当的步长后，按照下式进行迭代计算： x(k+1) =x(k)+ad 通过不断的调整可行方向，使迭代点逐步逼近约通过不断的调整可行方向，使迭代点逐步逼近约束最优点。束最优点。第四节第四节 可行方向法可行方向法二二. . 搜索策略：搜索策略： 根据目标函数和约束函数的不同性态，选择不同的搜索策略。根据目标函数和约束函数的不同性态，选择不同的搜索策略。 边界反弹法边界反弹法：第一次搜

14、索为负梯度方向，终止于边：第一次搜索为负梯度方向，终止于边 界。以后各次搜索方向均为适用可行方向，以最大界。以后各次搜索方向均为适用可行方向，以最大 步长从一个边界反弹到另一个边界，直至满足收敛步长从一个边界反弹到另一个边界，直至满足收敛 条件。条件。x(1)x(2)x(3)x*x(0)第四节第四节 可行方向法可行方向法 最优步长法：最优步长法：第一次搜索为负梯度方向，终止于边第一次搜索为负梯度方向，终止于边 界。第二次搜索沿适用可行方向作一维搜索以最优界。第二次搜索沿适用可行方向作一维搜索以最优 步长因子求得最优点。反复以上两步，直至得到最步长因子求得最优点。反复以上两步，直至得到最 优点优

15、点x x* *。x(1)x(2)x(3)x*x(0)第四节第四节 可行方向法可行方向法 贴边搜索法贴边搜索法： 第一次搜索为负梯度方向，终止于边界。以后各次搜索第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。贴边（约束面）进行。 若适时约束面是线性约束，每次搜索到约束面的交集时，若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。移至另一个约束面，经过有限的几步就可以收敛到最优点。x(1)x(2)x*x(0)第四节第四节 可行方向法可行方向法 若约束面是非线性时，从若约束面是非线性时，从x(k)点沿切线（面）方向点沿切线（面

16、）方向d(k) 搜索，会进入非可行域。搜索，会进入非可行域。容差带容差带： 建立约束面的容差带建立约束面的容差带 +， 从从 x(k) 出发，沿出发，沿d(k)方向搜索方向搜索到到 d(k) 方向与方向与g(x) +=0 的交点的交点x后，再沿适时约束的负梯后，再沿适时约束的负梯度方向返回约束面的度方向返回约束面的x(k+1)点。点。 11xgxxkx(k)x(k+1)g(x)g(x)+ x-g(x)d(k)第四节第四节 可行方向法可行方向法调整步长因子调整步长因子1 ： x (k+1) =x-a1g(x)将将g(x)在在x点泰勒展开，取一阶近似式：点泰勒展开，取一阶近似式： g(x) g(x

17、)+g(x) T(x-x )进而得到：进而得到： g(x (k+1) ) g(x)+g(x) T-a1g(x)为了让为了让x (k+1)到达约束面，令到达约束面，令g(x (k+1) ) =0得得: 1 Tg xg xg x 第四节第四节 可行方向法可行方向法三三. .可行方向的确定可行方向的确定可行方向应该满足可行方向应该满足设计点设计点可行可行及及目标函数值目标函数值下降下降两个条件两个条件 可行条件可行条件: gj(xk)T dk 0 j=1,2, J(起作用约束的个数起作用约束的个数) g(xk)dkg1(xk)g2(xk)dk第四节第四节 可行方向法可行方向法三三. .可行方向的确定

18、可行方向的确定 目标函数值下降条件目标函数值下降条件: f(xk)T dk 0 f(xk)dk第四节第四节 可行方向法可行方向法三三. .可行方向的确定可行方向的确定gj(xk)T dk 0 保证在可行域内保证在可行域内f(xk)T dk 0 保证目标函数值下降保证目标函数值下降 可可行行方方向向第四节第四节 可行方向法可行方向法 优选方向法优选方向法四四. . 可行方向产生方法可行方向产生方法min ()s.t()0(1,2, )()0kTkTjkTf xdgxdjJf xdd 式中：式中：d为求解变量，为求解变量，gj(xk)T 、f(xk)T为定值，为定值， 可用线性规划方法求解可用线性

19、规划方法求解第四节第四节 可行方向法可行方向法 梯度投影法：梯度投影法： 可行方向可行方向: : 其中其中: :p为投影算子为投影算子()/()kkkdp f xp f x 12(),(),()kkkJGgxgxgx 1TTpIG G GG J-起作用的约束个数起作用的约束个数第四节第四节 可行方向法可行方向法 取最优步长取最优步长五五. . 步长的确定步长的确定若若x(k+1)为可行点，为可行点， a作为本次迭代步长作为本次迭代步长 x(k+1) =x(k)+ad ad x(k+1) 第四节第四节 可行方向法可行方向法 取最大步长取最大步长aM五五. . 步长的确定步长的确定ad aMd x

20、(k+1) x(k+1) =x(k)+ad 第四节第四节 可行方向法可行方向法收敛条件收敛条件2()kTkf xd 2）设计点）设计点xk满足库恩满足库恩-塔克条件塔克条件1()()00(1,2, )Jkkjjjjf xg xjJ 1）设计点）设计点xk及约束允差及约束允差 满足满足例例 用可行方向法求约束优化问题的约束最优解。用可行方向法求约束优化问题的约束最优解。 Min f(x1, x2) = 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 g

21、5(x) = x1 + x2 11 0 解：取初始点解：取初始点x0 = 0 1T，为约束，为约束 边界边界g1(x) = 0上的一点。上的一点。第一次迭代用优选方向法确定可行方向。首先计算第一次迭代用优选方向法确定可行方向。首先计算x0点的目标点的目标函数函数f(x0)和约束函数和约束函数g1(x0)的梯度的梯度21142102012210 xxxxxxf 0101xg为在可行下降扇形区内寻找最优方向，需求解为在可行下降扇形区内寻找最优方向，需求解一个以可行方向一个以可行方向d=d1 d2T为设计变量的线性为设计变量的线性规划问题，其数学模型为：规划问题，其数学模型为：01201101222

22、12min()112. .()0()11201TTTf xddds tgxddf xddddd 最优方向是最优方向是d*=0.984 0.179T，它是目标函数等值线（直，它是目标函数等值线（直线束）和约束函数线束）和约束函数d12+d22=1（半径为（半径为1的圆）的切点。第一的圆）的切点。第一次迭代的可行方向为次迭代的可行方向为d0=d*。 第一次迭代的可行方向为第一次迭代的可行方向为d0=d*。若步长取。若步长取 0=6.098，则，则 可见第一次迭代点可见第一次迭代点x1 在约束边界在约束边界g3(x1)=0上。上。 091. 26179. 0984. 0098. 6100001dxx

23、第二次迭代用梯度投影法来确定可行方向。迭代点第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度的目标函数负梯度- f(x1)=0.092 5.818T，不满足方，不满足方向的可行条件。现将向的可行条件。现将f(x1)投影到约束边界投影到约束边界g3(x)=0上，上， 计算投影算子计算投影算子P本次迭代的可行方向为本次迭代的可行方向为 1111133331()()()1011001 010010001TTPIgxgxgxgx 10)()(111xfPxfPd显然，显然，d1为沿约束边界为沿约束边界g3(x)=0的方向。若取的方向。若取 1=2.909，则本次迭代点则本次迭代点即为该

24、问题的约束最优点即为该问题的约束最优点x*则得约束最优解则得约束最优解 5610909. 2091. 261112dxx11*,56*xfx121211( ,)( )( )( )mlkkkkjkijx rrf xrG gxrH h x 将有约束的优化问题转化为无约束优化问题来求解。将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。归结到原约束问题的同一最优解上去。 min( ),. .( )01,2,( )01,2,njkf xxRs t gxjmh xkl 构成一个新的目

25、标函数：构成一个新的目标函数：第五节第五节 惩罚函数法惩罚函数法惩罚项惩罚项惩罚因子惩罚因子惩罚函数惩罚函数 从而保证从而保证11lim( )0mkikirG g x 21lim( )0lkjkjrH h x 12lim( ,)()0kkkkx rrf x 惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质： 根据惩罚项的不同构成形式，惩罚函数法又可分为根据惩罚项的不同构成形式，惩罚函数法又可分为内内点惩罚函数法、外点惩罚函数法和混合惩罚函数法点惩罚函数法、外点惩罚函数法和混合惩罚函数法第五节第五节 惩罚函数法惩罚函数法121211( ,)( )( )( )mlkkkkjkijx rrf

26、xrG gxrH h x xrxrxkk11),()()(新目标函数：一一. . 内点惩罚函数法内点惩罚函数法 1. 基本思想基本思想内点法将新目标函数内点法将新目标函数( x , r ) 构筑在可行域构筑在可行域D内内，随着惩罚，随着惩罚因子因子r(k)的不断的不断递减递减，生成一，生成一系列新目标函数系列新目标函数(xk, r(k)，在可行域在可行域内内逐步迭代，产生逐步迭代，产生的极值点的极值点xk*(r(k)序列从可行序列从可行域域内内部趋向原目标函数的约部趋向原目标函数的约束最优点束最优点 x* 。例例：min. f(x)=x s.t. g (x) =1-x 0X X1 1* *X

27、X2 2* *X X* *2. 惩罚函数的形式惩罚函数的形式 ( )( )11( ,)( )( )mkkuux rf xrgx ( )( )1( ,)( )ln( )mkkuux rf xrgx 其中：惩罚（加权）因子其中：惩罚（加权）因子 降低系数降低系数 c： 0 c 1)()1()0(.krrr)()1(kkrcr0lim)(kkr当( )( ,)( ),*kkx rf xxx则则)(10)(XgXg当当x在可在可行 域 内行 域 内远 离 约远 离 约束 边 界束 边 界时：时：当当x由可由可行 城 内行 城 内靠 近 约靠 近 约束 边 界束 边 界时：时：0)(Xg0)(1Xg障碍

28、项障碍项 (0)(0)01()1muuf xrgx 3. 3. 几个参数的选择几个参数的选择1.惩罚因子初始值惩罚因子初始值 r(0) 的选择：的选择： 过大、过小均不好，建议考虑选择过大、过小均不好，建议考虑选择r(0) =1或者：或者：2. 降低系数降低系数 c 的选择：的选择：c 的典型值为的典型值为0.10.7。 3. 初始点初始点 x (0) 的选择：的选择：要求：要求： 在可行域内；在可行域内； 不要离约束边界太近。不要离约束边界太近。方法：方法： 人工估算，需要校核可行性；人工估算，需要校核可行性； 计算机随机产生，也需校核可行性。计算机随机产生，也需校核可行性。muukkxgr

29、xfrx11)()(),()()( ；Suxgxguk,.,2 , 1max)(00 搜索方法：搜索方法：l 任意给出一个初始点；任意给出一个初始点；l 判断其可行性，若违反了判断其可行性，若违反了S个约束，求出不满足约束中的最大值：个约束，求出不满足约束中的最大值：l 应用优化方法减少违反约束：应用优化方法减少违反约束： mSuxgSuxgxgtsRxxguuunk,.,101,.,2 , 10. .min0l 以求得的设计点作为新初始点，继续其判断可行性，若仍有不以求得的设计点作为新初始点，继续其判断可行性，若仍有不 满足的约束，则重复上述过程，直至初始点可行。满足的约束，则重复上述过程，

30、直至初始点可行。 判断是否收敛：判断是否收敛：1)()1()1()(*)(*kkkkrxrx2)1()1()()1()1()(*()(*()(*(kkkkkkrxrxrx4. 4. 步骤步骤： 选取合适的初始点选取合适的初始点 x(0) ，以及，以及 r(0)、c、计算精度、计算精度 1、2 ，令，令 k=0； 构造惩罚（新目标）函数；构造惩罚（新目标）函数； 调用无约束优化方法，求新目标函数的最优解调用无约束优化方法，求新目标函数的最优解 xk* 和和 (xk , r(k) ) ；若均满足，停止迭代，有约束优化问题的最优点为若均满足，停止迭代，有约束优化问题的最优点为 x*=xk*；若有一个

31、准则不满足，则令若有一个准则不满足，则令 并转入第并转入第 3 步，继续计算。步，继续计算。1,),(*)()1()()0(kkrcrrxxkkkk例：用内点法求下列问题的最优解：例：用内点法求下列问题的最优解：12211221min(). .()0()0F Xxxs tgXxxgXx 21(,)()ln()kkjjX rF XrgX 212211(,)ln()ln()kkkX rxxrxxrx 构造惩罚函数构造惩罚函数0)(00:0238. 0)(135. 0103. 0:125. 0333kkkXFXrXFXr当当75. 1)(25. 15 . 0:1000XFXr当09. 1)(782.

32、 0309. 0:5 . 0111XFXr当466. 0)(283. 0183. 0:25. 0222XFXr当212211(,)ln()ln()kkkX rxxrxxrx 0)(12xXg0)(2211xxXg1x2x21)(xxXF0)(00kkXFX1 11 12 225. 15 . 0:100Xr当782. 0309. 0:5 . 011Xr当283. 0183. 0:25. 022Xr当212211(,)ln()ln()kkkX rxxrxxrx二二. .外点惩罚函数法外点惩罚函数法 1. 基本原理基本原理外点法将新目标函数外点法将新目标函数( x , r ) 构筑在可行域构筑在可行

33、域 D 外外，随着惩罚因子，随着惩罚因子 r(k) 的的不断不断递增递增，生成一系列新目标函数，生成一系列新目标函数 (xk ,r(k)，在可行域，在可行域外外逐步迭代，产逐步迭代，产生的极值点生的极值点 xk*(r(k) 序列从可行域序列从可行域外外部趋向原目标函数的约束最优点部趋向原目标函数的约束最优点 x* 。 2(1)1,1kkxrxxx rxx ；。新目标函数：新目标函数：例：求下述约束优化问题的最优点。例：求下述约束优化问题的最优点。 min. f (X) = x x R1 s.t g (X) = 1-x 0惩罚函数可取为惩罚函数可取为( )( )2211( ,)( )max(0,

34、( )( )pqkkuvuvx rf xrgxhx 2) 惩罚因子惩罚因子)(kr.)()2() 1 ()0(krrrr.,)(krk时当 1) 当设计点在可行域内时当设计点在可行域内时,惩罚项为惩罚项为0, 不惩罚不惩罚; 当设当设 计点在可行域外计点在可行域外 时时, 惩罚项大于惩罚项大于0, 有惩罚作用有惩罚作用.外点法可以用来求解含外点法可以用来求解含不等式和等式约束不等式和等式约束的优化问题。的优化问题。衰减项衰减项3. 3. 几个参数的选择几个参数的选择r (0) 的选择的选择: r (0) 过大，会使惩罚函数的等值线变形或偏心，求极过大，会使惩罚函数的等值线变形或偏心，求极 值困

35、难。值困难。r (0) 过小，迭代次数太多。过小，迭代次数太多。 r (0) 1或者或者 (0)000.021,2,.uurumm gxfx x(0) 的选择：的选择： 基本上可以在可行域内外，任意选择。基本上可以在可行域内外，任意选择。递增系数递增系数c的选择：的选择： 通常选择通常选择 5 10，可根据具体题目，进行试算调整。，可根据具体题目，进行试算调整。 0(0)maxurr ( )(1)kkrcr内点法特点：内点法特点： （1 1）初始点必须为严格的可行点）初始点必须为严格的可行点 （2 2）不适于具有等式约束的数学模型不适于具有等式约束的数学模型 （3 3）迭代过程中各个点均为可行

36、设计方案）迭代过程中各个点均为可行设计方案 （4 4）一般收敛较慢）一般收敛较慢 （5 5）初始惩罚因子要选择得当）初始惩罚因子要选择得当 （6 6）惩罚因子为递减，递减率）惩罚因子为递减，递减率c c有有0c10c1 c1 三三. . 混合惩罚函数法混合惩罚函数法1.1. 基本思想基本思想采用内点法和外点法相结合的混合惩罚函数法，以发挥内采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。束的优化设计问题。2. 2. 惩罚函数的形式惩罚函数的形式一般既包括障碍项，也包括衰减项。

37、一般既包括障碍项，也包括衰减项。 211010011.( ,),lim01,pmkkvuvkukkxx rfxrhxgxrrrrrrx 的的选选择择，参参考考内内点点法法，应应为为内内点点。 原理简单，算法易行，适应范围广，可利用无约束原理简单，算法易行，适应范围广，可利用无约束最最 优化方法资源。优化方法资源。（1）初始惩罚因子）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，取值不当可导致惩罚函数变得病态， 使无约束优化计算困难。使无约束优化计算困难。（2）理论上讲，只有惩罚因子）理论上讲，只有惩罚因子 r (k) 0 （内点法）或（内点法）或 r (k) 趋于无穷趋于无穷 （外点法）

38、时，算法才收敛，因此序（外点法）时，算法才收敛，因此序 列迭代过程收敛速度慢。列迭代过程收敛速度慢。 计算过程稳定，计算效率超过惩罚函数法计算过程稳定，计算效率超过惩罚函数法min(). .()0pf Xs thX 一、一、 拉格朗日乘子法（升维法）拉格朗日乘子法（升维法）第六节第六节 增广乘子法增广乘子法 1,lpppF xfxhx 0 (1,2,)iFinx 0 (1,2,)pFpl l+n个方程个方程l+n个未知变量个未知变量例例: :用拉格朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解2212121212min()60104. .()80f Xxxxxx xs th X

39、xx2212121212(, )60104(8)L Xxxxxx xxx1211020Lxxx 解解 构造拉格朗日函数构造拉格朗日函数1280Lxx 212420Lxxx 令令L=0,得到得到求解得：求解得：*12533()17xxf X min(). .()0pf Xs thX 1(, )()()lpppL Xf XhX 构造拉格朗日函数构造拉格朗日函数构造外点惩罚函数构造外点惩罚函数( )2( )1(,)()()2klkpprX rf XhX (, )0L X *,X ( )kr *X*X二二.等式约束的增广乘子法等式约束的增广乘子法 采用拉格朗日乘子法时求解有难度采用拉格朗日乘子法时求解

40、有难度,而罚函数法当迭而罚函数法当迭代点接近边界时函数常有病态代点接近边界时函数常有病态, 此法的思路是把两者结此法的思路是把两者结合起来。其增广拉格朗日函数为合起来。其增广拉格朗日函数为:( )211(, )()()()2kllppppprM Xrf XhXhX ( )21(,()2)klpprhXL X min(). .()0pf Xs thX 等式约束增广乘子法等式约束增广乘子法( )2( )11(, ,)()()()2kllkppppprM Xrf XhXhX( )112( )1()0()01()02llppkppppiiiipplpkphhMfrhXxxxxMhXMhXr *,X 不

41、论不论r(k)取何值取何值，增广乘子函数增广乘子函数与与原函数原函数具有具有相同相同的约束极的约束极值点值点X*，与，与拉格朗日函数拉格朗日函数有有相同相同的拉格朗日乘子向量。的拉格朗日乘子向量。等式约束增广乘子法等式约束增广乘子法( )2( )11(, ,)()()()2kplkppppprM Xrf XhXhX( )211(, )()()()2kllppppprM Xf XhXhX( )2( )( )11(,)()()()2kllkkppppprM Xf XhXhX( )( )( )( )12.kkkkp *( )()(1,2,.)kXk *()X 等式约束增广乘子法等式约束增广乘子法(1

42、)( )( )kkk 增广乘子法中的乘子迭代增广乘子法中的乘子迭代(1)( )( )( )()kkkkppprhX 等式约束增广乘子法等式约束增广乘子法参数选取参数选取没有其它信息情况下，初始乘子向量没有其它信息情况下，初始乘子向量 (0)0增广乘子函数和外点惩罚函数形式相同；从增广乘子函数和外点惩罚函数形式相同；从第二次迭代开始，乘子向量按式子进行校正。第二次迭代开始，乘子向量按式子进行校正。惩罚因子初始值惩罚因子初始值r r(0)(0)按照外点法取。按照外点法取。( )( )(1)(1)( )( )(1),()(),()()kkkkkkkCrwhen h Xh Xrrwhen h Xh X

43、 从第二次迭代开始，惩罚因子按下式递增：从第二次迭代开始，惩罚因子按下式递增：惩罚因子递增系数，惩罚因子递增系数，C=10C=10判别数，通常取判别数，通常取0.250.25(0)(0)(0), , ,0,0XrCk ( )2( )11min(, ,)()()()2kllkppppprM Xrf XhXhX( )*( )( )(,)kkkXXr 2( )( )1()()lkkpph XhX (1)( )( )( )()kkkkppprhX ( )()kh X (1)( ),1kkrrkk ( )*kXX等式约束增广乘子法等式约束增广乘子法计算步骤计算步骤： 1. 选取设计变量的初始点选取设计变

44、量的初始点x0，惩罚因子初值，惩罚因子初值r0，增长，增长系数系数，判别数，判别数，收敛精度，收敛精度，乘子向量，乘子向量p0=0 (p=1,2, l), 迭代次数迭代次数k=0；2. 构造增广乘子函数构造增广乘子函数M(x,r)，并用无约束方法求，并用无约束方法求 min M(x,r) ，得无约束最优解，得无约束最优解xk=x*(k,rk)3. 计算计算4. 校正乘子向量校正乘子向量5. 如果如果 ，迭代终止，约束最优解为，迭代终止，约束最优解为x*=xk， *= k+1; 否则转步骤否则转步骤66. 计算惩罚因子计算惩罚因子 再令再令k=k+1，转步骤，转步骤212kk1()()lpph

45、xh x 1()kkkkpppr hx k()h x kk-11kk-1,() /() ,() /()kkkrh xh xrrh xh x 例例: :用拉格朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解22121211min()26. .()10f Xxxs th Xxx22212121211(, , )(1)(1)262kkrM Xrxxxxxx解解 构造增广乘子函数构造增广乘子函数确定初始参数：确定初始参数： C2, 0=0, r0=0.1 ，利用解析法求利用解析法求min M(X,r) ，令，令 M(X,r)0 ，可得最优解：可得最优解： 12143()14kkkkkkk

46、krxrrxr 112(1)kkkkkrxx 12kkkrCrr 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.1251( )21()(,)()2,()lkpplpkppr

47、f XrXXXhMh min(). .()0pf Xs thX 不等式约束增广乘子法不等式约束增广乘子法用于求解不等式约束优化问题。用于求解不等式约束优化问题。min(). .()0mjf Xs tgXj 2 ()()0jjjgXgXz引入松弛变量引入松弛变量Zz1, z2 , , zmT,并且令并且令2min(). . ()()0jjjf Xs tgXgXz则不等式约束优化问题转化为等式优化问题则不等式约束优化问题转化为等式优化问题不等式约束增广乘子法不等式约束增广乘子法( )2( )11(, ,)() (,) (,)2kmmkjjjjjrM XrZf XgX ZgX Z构造增广乘子函数构造

48、增广乘子函数(1)( )( )( ) (,)kkkkjjjrgXZ 由于引入松弛变量由于引入松弛变量Z，使原有的，使原有的n维极值问题扩充为维极值问题扩充为n+m维问维问题，计算工作量和求解难度增大，可简化。题，计算工作量和求解难度增大，可简化。( )(, ,)0kZM XrZ ( )2()0kjjjjzrgXz 2 ()()0jjjgXgXz不等式约束增广乘子法不等式约束增广乘子法( )2()0kjjjjzrgXz ( )22( )22( )()0,0()0,()kjjjjjkjjjjjkrgXzzrgXzzgXr 如如果果如如果果2( )( )1max 0,()jjjkkzgXrr 2(

49、)( )( )2( )11(, ,)()max 0,()2mkkkjjjkjM Xrf XrgXr (1)( )( )max 0,()kkkjjjrgX 同时具有等式和不等式约束的增广乘子法同时具有等式和不等式约束的增广乘子法 2( )( )( )211( )1( )2( )2111(, ,)()max 0,()2()()2jjvmkkkjkjkqqkvvvvM Xrf XrgXrrh Xh X min(). .()0uf Xs tgX ()0vh X (1)( )( )11(1)( )( )( )22max 0,()(1,2,.,)()(1,2,., ;)jjvvkkkjkkkkvrgXjm

50、rh Xvq qn 这个方法的基本思想：在某个近似解处将约束函数和目这个方法的基本思想：在某个近似解处将约束函数和目标函数进行泰勒展开，只保留一次项，从而将非线性规划问标函数进行泰勒展开，只保留一次项，从而将非线性规划问题变成线性规划问题。求解此线性规划，并将其最优解作为题变成线性规划问题。求解此线性规划，并将其最优解作为原来问题新的近似解，再展开成新的线性规划问题，再求解。原来问题新的近似解，再展开成新的线性规划问题，再求解。如此重复下去，一直到相邻两次最优解足够接近时为止。如此重复下去，一直到相邻两次最优解足够接近时为止。 序列线性规划法收敛较慢，且最后的近似解不满足非线序列线性规划法收敛