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

机械优化设计第六章第六章 约束优化方法约束优化方法 6.1 概概 述述 6.2 随机方向法随机方向法 6.3 复合形方法复合形方法 6.4 可行方向法可行方向法 6.5 惩罚函数法惩罚函数法 6.6 增广乘子法增广乘子法 6.11遗传算遗传算 法简述法简述6.10结构优化法简述结构优化法简述 6.9 二次规划法二次规划法 6.8广义简约梯度法广义简约梯度法 6.7 非线性规划问题非线性规划问题的线性化解法的线性化解法线性线性逼近法逼近法 机械优化设计中的问题，大多数属于约束优化设机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为计问题，其数学模型为第一节第一节 概述概述第一节第一节 概述概述l 直接解法：随机方向搜索法、复合形法、可行方向法直接解法：随机方向搜索法、复合形法、可行方向法l 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一一.有约束问题解法分类：有约束问题解法分类：二二.直接解法的基本思想：直接解法的基本思想：合理选择初始点，确定搜索方向，合理选择初始点，确定搜索方向，在可行域中在可行域中寻优，经过若干次迭寻优，经过若干次迭代，收敛至最优点。代，收敛至最优点。xk+1=xk+kdkdk:可行搜索方向。即设计点沿该方向作微量移动时可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下目标函数值将下 降降,且不会超出可行域且不会超出可行域直接解法通常适用于直接解法通常适用于仅含不等式约束仅含不等式约束的问题的问题第一节第一节 概述概述特点：特点：由于求解过程在可行域内进行；无论迭代计算何时终止由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点都可以获得一个比初始点好的设计点;若可行域是凸集，目标函数是定义在凸集上的凸函数，若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。则收敛到全局最优点；否则，结果与初始点有关。凸可行域凸可行域非凸可行域非凸可行域第一节第一节 概述概述原理原理：将有约束优化问题转化为无约束优化问题来解决。：将有约束优化问题转化为无约束优化问题来解决。方法方法：以原目标函数和加权的约束函数共同构成一个新的：以原目标函数和加权的约束函数共同构成一个新的 目标函数目标函数 (x,r1,r2)，成为无约束优化问题，成为无约束优化问题。通。通 过不断调整加权因子，产生一系列过不断调整加权因子，产生一系列函数的极小点函数的极小点 序列序列 x(k)*(r1(k),r2(k)k=0,1,2，逐渐收敛到，逐渐收敛到原目标原目标 函数的约束最优解函数的约束最优解。其中：新目标函数：其中：新目标函数：三三.间接解法的基本思想：间接解法的基本思想：惩罚因子：惩罚因子：r1,r2第二节第二节 随机方向法随机方向法一一.基本思想：基本思想：随机产生随机产生初始点初始点，随机产生随机产生若干个若干个搜索方向搜索方向d dk k，并从中，并从中选择一个能使目标函数值下降最快的方向作为可行搜索选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。方向进行搜索。确保：确保：新迭代点在可行域中新迭代点在可行域中 目标函数值的下降性。目标函数值的下降性。x(0)x(L)x(1)x*二二.初始点的选择初始点的选择 随机方向法的初始点随机方向法的初始点x0必须是必须是一个可行点一个可行点，既满足全部，既满足全部 不等式约束条件。不等式约束条件。初始点可以通过随机选择的方法产生。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即）输入设计变量的下限值和上限值，即2）在区间（）在区间（0，1）内产生）内产生n个个伪随机数伪随机数3）计算随机点）计算随机点x的各分量的各分量4）判别随机点）判别随机点x是否可行，若随机点可行，用是否可行，若随机点可行，用x0 x 为初始点；若非可行点，转到步骤为初始点；若非可行点，转到步骤2）重新产生随）重新产生随 机点，直到可行为止。机点，直到可行为止。第二节第二节 随机方向法随机方向法三三.可行搜索方向的产生可行搜索方向的产生从从k个随机方向中，个随机方向中，选取一个较好的方向。选取一个较好的方向。1）在）在(-1,1)区间内产生伪随机数区间内产生伪随机数 ，得随机单位向量，得随机单位向量2)取一试验步长取一试验步长a0，按下式计算，按下式计算k个随机点个随机点第二节第二节 随机方向法随机方向法3）检验）检验k个随机点是否为可行点，除去非可行点，计算个随机点是否为可行点，除去非可行点，计算 余下的可行点的目标函数值，比较其大小，选出目标余下的可行点的目标函数值，比较其大小，选出目标 函数最小的点函数最小的点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(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*除除x(H)外，其它顶外，其它顶点的几何中心点的几何中心第三节第三节 复合形法复合形法二二.复合形法：复合形法：定义定义：在在n维空间中，由维空间中，由 kn+1 个点组成的多面体称为复合形。个点组成的多面体称为复合形。基本思想基本思想：以以一一个个较较好好的的新新点点，代代替替原原复复合合形形中中的的最最坏坏点点，组组成成新新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。的复合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：说明：l 单纯形是无约束优化方法，复合形用于约束优化的方法。单纯形是无约束优化方法，复合形用于约束优化的方法。l 因为顶点数较多，所以比单纯形更灵活易变。因为顶点数较多，所以比单纯形更灵活易变。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)组组成新复合形，再进行下轮迭代。成新复合形，再进行下轮迭代。X(S)X(R)X(H)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)3.变形法二变形法二 收缩：收缩：若在映射法中若在映射法中f(x(R)f(x(H),则以则以a0.5a重复采用映射法重复采用映射法 若直至若直至a10-5仍不成功，考虑采用收缩法仍不成功，考虑采用收缩法 取取 若若f(x(K):检查终止准则检查终止准则 若若f(x(R)5 时，时，k 取值可小些。取值可小些。一一.基本思想基本思想：在可行域内选择一个初始点在可行域内选择一个初始点x(0)，确定了一个可行，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：方向和适当的步长后，按照下式进行迭代计算：x(k+1)=x(k)+ad 通过不断的调整可行方向，使迭代点逐步逼近约通过不断的调整可行方向，使迭代点逐步逼近约束最优点。束最优点。第四节第四节 可行方向法可行方向法二二.搜索策略：搜索策略：根据目标函数和约束函数的不同性态，选择不同的搜索策略。根据目标函数和约束函数的不同性态，选择不同的搜索策略。边界反弹法边界反弹法：第一次搜索为负梯度方向，终止于边：第一次搜索为负梯度方向，终止于边 界。以后各次搜索方向均为适用可行方向，以最大界。以后各次搜索方向均为适用可行方向，以最大 步长从一个边界反弹到另一个边界，直至满足收敛步长从一个边界反弹到另一个边界，直至满足收敛 条件。条件。x(1)x(2)x(3)x*x(0)第四节第四节 可行方向法可行方向法 最优步长法：最优步长法：第一次搜索为负梯度方向，终止于边第一次搜索为负梯度方向，终止于边 界。第二次搜索沿适用可行方向作一维搜索以最优界。第二次搜索沿适用可行方向作一维搜索以最优 步长因子求得最优点。反复以上两步，直至得到最步长因子求得最优点。反复以上两步，直至得到最 优点优点x x*。x(1)x(2)x(3)x*x(0)第四节第四节 可行方向法可行方向法 贴边搜索法贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。边（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。移至另一个约束面，经过有限的几步就可以收敛到最优点。x(1)x(2)x*x(0)第四节第四节 可行方向法可行方向法 若约束面是非线性时，从若约束面是非线性时，从x(k)点沿切线（面）方向点沿切线（面）方向d(k)搜索，会进入非可行域。搜索，会进入非可行域。容差带容差带：建立约束面的容差带建立约束面的容差带+，从从 x(k)出发，沿出发，沿d(k)方向搜索方向搜索到到 d(k)方向与方向与g(x)+=0 的交点的交点x后，再沿适时约束的负梯后，再沿适时约束的负梯度方向返回约束面的度方向返回约束面的x(k+1)点。点。x(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)+g(x)T(x-x)进而得到：进而得到：g(x(k+1)g(x)+g(x)T-a1g(x)为了让为了让x(k+1)到达约束面，令到达约束面，令g(x(k+1)=0得得:第四节第四节 可行方向法可行方向法三三.可行方向的确定可行方向的确定可行方向应该满足可行方向应该满足设计点设计点可行可行及及目标函数值目标函数值下降下降两个条件两个条件 可行条件可行条件:gj(xk)T dk 0 j=1,2,J(起作用约束的个数起作用约束的个数)g(xk)dkg1(xk)g2(xk)dk第四节第四节 可行方向法可行方向法三三.可行方向的确定可行方向的确定 目标函数值下降条件目标函数值下降条件:f(xk)T dk 0 f(xk)dk第四节第四节 可行方向法可行方向法三三.可行方向的确定可行方向的确定gj(xk)T dk 0 保证在可行域内保证在可行域内f(xk)T dk 0 保证目标函数值下降保证目标函数值下降 可可行行方方向向第四节第四节 可行方向法可行方向法 优选方向法优选方向法四四.可行方向产生方法可行方向产生方法式中：式中：d为求解变量，为求解变量，gj(xk)T、f(xk)T为定值，为定值，可用线性规划方法求解可用线性规划方法求解第四节第四节 可行方向法可行方向法 梯度投影法：梯度投影法：可行方向可行方向:其中其中:p为投影算子为投影算子J-起作用的约束个数起作用的约束个数第四节第四节 可行方向法可行方向法 取最优步长取最优步长五五.步长的确定步长的确定若若x(k+1)为可行点，为可行点，a作为本次迭代步长作为本次迭代步长 x(k+1)=x(k)+ad ad x(k+1)第四节第四节 可行方向法可行方向法 取最大步长取最大步长aM五五.步长的确定步长的确定ad aMd x(k+1)x(k+1)=x(k)+ad 第四节第四节 可行方向法可行方向法收敛条件收敛条件2）设计点）设计点xk满足库恩满足库恩-塔克条件塔克条件 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 g5(x)=x1+x2 11 0 解解：取取初初始始点点x0=0 1T，为为约约束束 边边界界g1(x)=0上上的的一一点点。第第一一次次迭迭代代用用优优选选方方向向法法确确定定可可行行方方向向。首首先先计计算算x0点点的的目目标标函数函数f(x0)和约束函数和约束函数g1(x0)的梯度的梯度为为在在可可行行下下降降扇扇形形区区内内寻寻找找最最优优方方向向，需需求求解解一一个个以以可可行行方方向向d=d1 d2T为为设设计计变变量量的的线线性性规划问题，其数学模型为：规划问题，其数学模型为：最优方向是最优方向是d*=0.984 0.179T，它是目标函数等值线（直，它是目标函数等值线（直线束）和约束函数线束）和约束函数d12+d22=1（半径为（半径为1的圆）的切点。第一的圆）的切点。第一次迭代的可行方向为次迭代的可行方向为d0=d*。第一次迭代的可行方向为第一次迭代的可行方向为d0=d*。若步长取。若步长取 0=6.098，则，则 可见第一次迭代点可见第一次迭代点x1 在约束边界在约束边界g3(x1)=0上。上。第二次迭代用梯度投影法来确定可行方向。迭代点第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度的目标函数负梯度-f(x1)=0.092 5.818T，不满足方，不满足方向的可行条件。现将向的可行条件。现将f(x1)投影到约束边界投影到约束边界g3(x)=0上，上，计算投影算子计算投影算子P本次迭代的可行方向为本次迭代的可行方向为显然，显然，d1为沿约束边界为沿约束边界g3(x)=0的方向。若取的方向。若取 1=2.909，则本次迭代点则本次迭代点即为该问题的约束最优点即为该问题的约束最优点x*则得约束最优解则得约束最优解 将将有有约约束束的的优优化化问问题题转转化化为为无无约约束束优优化化问问题题来来求求解解。前前提提：一一是是不不能能破破坏坏约约束束问问题题的的约约束束条条件件，二二是是使使它它归归结结到原约束问题的同一最优解上去。到原约束问题的同一最优解上去。构成一个新的目标函数：构成一个新的目标函数：第五节第五节 惩罚函数法惩罚函数法惩罚项惩罚项惩罚因子惩罚因子惩罚函数惩罚函数 从而保证从而保证惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质：根根据据惩惩罚罚项项的的不不同同构构成成形形式式，惩惩罚罚函函数数法法又又可可分分为为内内点点惩罚函数法、外点惩罚函数法和混合惩罚函数法惩罚函数法、外点惩罚函数法和混合惩罚函数法第五节第五节 惩罚函数法惩罚函数法一一.内点惩罚函数法内点惩罚函数法 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 X2 2*X X*2.惩罚函数的形式惩罚函数的形式 其中：惩罚（加权）因子其中：惩罚（加权）因子 降低系数降低系数 c：0 c 1当当x在在可可行行域域内内远远离离约约束束边边界界时：时：当当x由由可可行行 城城 内内靠靠 近近 约约束束 边边 界界时：时：障碍项障碍项3.3.几个参数的选择几个参数的选择1.惩罚因子初始值惩罚因子初始值 r(0)的选择：的选择：过大、过小均不好，建议考虑选择过大、过小均不好，建议考虑选择r(0)=1或者：或者：2.降低系数降低系数 c 的选择：的选择：c 的典型值为的典型值为0.10.7。3.初始点初始点 x(0)的选择：的选择：要求：要求：在可行域内；在可行域内；不要离约束边界太近。不要离约束边界太近。方法：方法：人工估算，需要校核可行性；人工估算，需要校核可行性；计算机随机产生，也需校核可行性。计算机随机产生，也需校核可行性。搜索方法：搜索方法：l 任意给出一个初始点；任意给出一个初始点；l 判断其可行性，若违反了判断其可行性，若违反了S个约束，求出不满足约束中的最大值：个约束，求出不满足约束中的最大值：l 应用优化方法减少违反约束：应用优化方法减少违反约束：l 以求得的设计点作为新初始点，继续其判断可行性，若仍有不以求得的设计点作为新初始点，继续其判断可行性，若仍有不 满足的约束，则重复上述过程，直至初始点可行。满足的约束，则重复上述过程，直至初始点可行。判断是否收敛：判断是否收敛：4.4.步骤步骤：选取合适的初始点选取合适的初始点 x(0)，以及，以及 r(0)、c、计算精度、计算精度 1、2，令，令 k=0；构造惩罚（新目标）函数；构造惩罚（新目标）函数；调用无约束优化方法，求新目标函数的最优解调用无约束优化方法，求新目标函数的最优解 xk*和和 (xk,r(k)；若均满足，停止迭代，有约束优化问题的最优点为若均满足，停止迭代，有约束优化问题的最优点为 x*=xk*；若有一个准则不满足，则令若有一个准则不满足，则令 并转入第并转入第 3 步，继续计算。步，继续计算。例：用内点法求下列问题的最优解：例：用内点法求下列问题的最优解：构造惩罚函数构造惩罚函数1 11 12 2二二.外点惩罚函数法外点惩罚函数法 1.基本原理基本原理外外点点法法将将新新目目标标函函数数(x,r)构构筑筑在在可可行行域域 D 外外，随随着着惩惩罚罚因因子子 r(k)的的不不断断递递增增，生生成成一一系系列列新新目目标标函函数数(xk,r(k)，在在可可行行域域外外逐逐步步迭迭代代，产产生生的的极极值值点点 xk*(r(k)序序列列从从可可行行域域外外部部趋趋向向原原目目标标函函数数的的约约束束最最优优点点 x*。新目标函数：新目标函数：例：求下述约束优化问题的最优点。例：求下述约束优化问题的最优点。min.f(X)=x x R1 s.t g(X)=1-x 0惩罚函数可取为惩罚函数可取为2)惩罚因子惩罚因子 1)当设计点在可行域内时当设计点在可行域内时,惩罚项为惩罚项为0,不惩罚不惩罚;当设当设 计点在可行域外计点在可行域外 时时,惩罚项大于惩罚项大于0,有惩罚作用有惩罚作用.外点法可以用来求解含外点法可以用来求解含不等式和等式约束不等式和等式约束的优化问题。的优化问题。衰减项衰减项3.3.几个参数的选择几个参数的选择r(0)的选择的选择:r(0)过大，会使惩罚函数的等值线变形或偏心，求极过大，会使惩罚函数的等值线变形或偏心，求极 值困难。值困难。r(0)过小，迭代次数太多。过小，迭代次数太多。r(0)1或者或者x(0)的选择：的选择：基本上可以在可行域内外，任意选择。基本上可以在可行域内外，任意选择。递增系数递增系数c的选择：的选择：通常选择通常选择 5 10，可根据具体题目，进行试算调整。，可根据具体题目，进行试算调整。内点法特点：内点法特点：（1 1）初始点必须为严格的可行点）初始点必须为严格的可行点 （2 2）不适于具有等式约束的数学模型不适于具有等式约束的数学模型 （3 3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案 （4 4）一般收敛较慢）一般收敛较慢 （5 5）初始惩罚因子要选择得当）初始惩罚因子要选择得当 （6 6）惩罚因子为递减，递减率）惩罚因子为递减，递减率c c有有0c10c1 c1 三三.混合惩罚函数法混合惩罚函数法1.1.基本思想基本思想采用内点法和外点法相结合的混合惩罚函数法，以发挥内采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。束的优化设计问题。2.2.惩罚函数的形式惩罚函数的形式一般既包括障碍项，也包括衰减项。一般既包括障碍项，也包括衰减项。惩罚函数法惩罚函数法优优优优点点点点：原原理理简简单单，算算法法易易行行，适适应应范范围围广广，可可利利用用无无约约束束最最 优化方法资源。优化方法资源。缺点：缺点：缺点：缺点：（1）初始惩罚因子）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，取值不当可导致惩罚函数变得病态，使无约束优化计算困难。使无约束优化计算困难。（2）理论上讲，只有惩罚因子）理论上讲，只有惩罚因子 r(k)0（内点法）或（内点法）或 r(k)趋于无穷趋于无穷（外点法）时，算法才收敛，因此序（外点法）时，算法才收敛，因此序 列迭代过程收敛速度慢。列迭代过程收敛速度慢。增广乘子法增广乘子法 外点惩罚函数拉格朗日函数外点惩罚函数拉格朗日函数外点惩罚函数拉格朗日函数外点惩罚函数拉格朗日函数 计算过程稳定，计算效率超过惩罚函数法计算过程稳定，计算效率超过惩罚函数法拉格朗日函数拉格朗日函数拉格朗日函数拉格朗日函数一、一、拉格朗日乘子法（升维法）拉格朗日乘子法（升维法）第六节第六节 增广乘子法增广乘子法l+n个方程个方程l+n个未知变量个未知变量具有相具有相具有相具有相同的最同的最同的最同的最优解优解优解优解X X*例例:用拉格朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解解解 构造拉格朗日函数构造拉格朗日函数令令L=0,得到得到求解得：求解得：构造拉格朗日函数构造拉格朗日函数构造外点惩罚函数构造外点惩罚函数二二.等式约束的增广乘子法等式约束的增广乘子法 采采用用拉拉格格朗朗日日乘乘子子法法时时求求解解有有难难度度,而而罚罚函函数数法法当当迭迭代代点点接接近近边边界界时时函函数数常常有有病病态态,此此法法的的思思路路是是把把两两者者结结合起来。其增广拉格朗日函数为合起来。其增广拉格朗日函数为:等式约束增广乘子法等式约束增广乘子法不论不论r(k)取何值取何值，增广乘子函数增广乘子函数与与原函数原函数具有具有相同相同的约束极的约束极值点值点X*，与，与拉格朗日函数拉格朗日函数有有相同相同的拉格朗日乘子向量。的拉格朗日乘子向量。等式约束增广乘子法等式约束增广乘子法等式约束增广乘子法等式约束增广乘子法增广乘子法中的乘子迭代增广乘子法中的乘子迭代等式约束增广乘子法等式约束增广乘子法参数选取参数选取没有其它信息情况下，初始乘子向量没有其它信息情况下，初始乘子向量 增广乘子函数和外点惩罚函数形式相同；从增广乘子函数和外点惩罚函数形式相同；从第二次迭代开始，乘子向量按式子进行校正。第二次迭代开始，乘子向量按式子进行校正。惩罚因子初始值惩罚因子初始值r r(0)(0)按照外点法取。按照外点法取。从第二次迭代开始，惩罚因子按下式递增：从第二次迭代开始，惩罚因子按下式递增：惩罚因子递增系数，惩罚因子递增系数，C=10C=10判别数，通常取判别数，通常取0.250.25等式约束增广乘子法等式约束增广乘子法计算步骤计算步骤：1.选选取取设设计计变变量量的的初初始始点点x0，惩惩罚罚因因子子初初值值r0，增增长长系系数数，判判别别数数，收收敛敛精精度度，乘乘子子向向量量p0=0 (p=1,2,l),迭代次数迭代次数k=0；构造增广乘子函数构造增广乘子函数M(x,r)，并用无约束方法求，并用无约束方法求1.min M(x,r)，得无约束最优解，得无约束最优解xk=x*(k,rk)计算计算1.校正乘子向量校正乘子向量2.如如果果 ，迭迭代代终终止止，约约束束最最优优解解为为x*=xk，*=k+1;否则转步骤否则转步骤63.计算惩罚因子计算惩罚因子 4.再令再令k=k+1，转步骤，转步骤2例例:用拉格朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解解解 构造增广乘子函数构造增广乘子函数确定初始参数：确定初始参数：C2,0=0,r0=0.1，利用解析法求利用解析法求min M(X,r)，令，令 M(X,r)0，可得最优解：，可得最优解：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不等式约束增广乘子法不等式约束增广乘子法用于求解不等式约束优化问题。用于求解不等式约束优化问题。引入松弛变量引入松弛变量Zz1,z2,zmT,并且令并且令则不等式约束优化问题转化为等式优化问题则不等式约束优化问题转化为等式优化问题不等式约束增广乘子法不等式约束增广乘子法构造增广乘子函数构造增广乘子函数由于引入松弛变量由于引入松弛变量Z，使原有的，使原有的n维极值问题扩充为维极值问题扩充为n+m维问维问题，计算工作量和求解难度增大，可简化。题，计算工作量和求解难度增大，可简化。不等式约束增广乘子法不等式约束增广乘子法同时具有等式和不等式约束的增广乘子法同时具有等式和不等式约束的增广乘子法第七节第七节 非线性规划问题的线性化解法非线性规划问题的线性化解法线线性逼近法性逼近法一、序列线性规划法一、序列线性规划法一、序列线性规划法一、序列线性规划法 这这个个方方法法的的基基本本思思想想：在在某某个个近近似似解解处处将将约约束束函函数数和和目目标标函函数数进进行行泰泰勒勒展展开开，只只保保留留一一次次项项，从从而而将将非非线线性性规规划划问问题题变变成成线线性性规规划划问问题题。求求解解此此线线性性规规划划，并并将将其其最最优优解解作作为为原原来来问问题题新新的的近近似似解解，再再展展开开成成新新的的线线性性规规划划问问题题，再再求求解解。如此重复下去，一直到相邻两次最优解足够接近时为止。如此重复下去，一直到相邻两次最优解足够接近时为止。缺点：缺点：缺点：缺点：序序列列线线性性规规划划法法收收敛敛较较慢慢，且且最最后后的的近近似似解解不不满满足足非非线线性性约约束束，有有时时还还会会出出现现不不收收敛敛的的情情况况。为为了了获获得得较较好好的的收收敛敛性而采用一些改进的方法，如割平面法、小步梯度法等。性而采用一些改进的方法，如割平面法、小步梯度法等。第七节第七节 非线性规划问题的线性化解法非线性规划问题的线性化解法线线性逼近法性逼近法二、割平面法二、割平面法二、割平面法二、割平面法 割割平平面面法法主主要要用用于于不不等等式式约约束束的的非非线线性性规规划划问问题题。若若问问题题是是凸凸规规划划问问题题，则则这这种种方方法法将将收收敛敛于于问问题题的的最最优优解解。对对于于非非凸凸规规划划问问题题，某某些些约约束束的的线线性性近近似似可可能能把把原原问问题题可可行行域域切切掉掉一一些些，可可能能最最优优点点恰恰好好就就在在这这些些被被切切去去的的区区域域里里。因因为为这这种种方方法法实实际际上上是是用用线线性性近近似似约约束束把把原原问问题题可可行行域域切切掉掉一一部部分分，所以称为所以称为“割平面法割平面法”。第七节第七节 非线性规划问题的线性化解法非线性规划问题的线性化解法线线性逼近法性逼近法三、小步梯度法三、小步梯度法三、小步梯度法三、小步梯度法 线线性性逼逼近近法法求求解解是是指指按按下下面面的的迭迭代代公公式式对对设设计计点点 进进行行修改，从而获得新的设计点修改，从而获得新的设计点 的方法。的方法。当把上式写成当把上式写成而而 是是一一个个小小数数值值时时，可可把把此此式式作作为为一一个个约约束束列列入入原原问问题题中中去去求求解解。当当用用梯梯度度法法求求解解时时，这这种种方方法法就就是是用用一一个个小小数数值值 限制各寻优方向步长的方法，可称为小步梯度法。限制各寻优方向步长的方法，可称为小步梯度法。只有当只有当 是可行解时，此法收敛较快，否则过程收敛较慢。是可行解时，此法收敛较快，否则过程收敛较慢。第七节第七节 非线性规划问题的线性化解法非线性规划问题的线性化解法线线性逼近法性逼近法四、非线性规划法四、非线性规划法四、非线性规划法四、非线性规划法对对于于灯灯饰饰和和不不等等式式约约束束的的给给线线性性规规划划问问题题，有有一一种种解解法法是是把把最最速速下下降降法法（梯梯度度法法）和和线线性性规规划划法法结结合合起起来来求求解解。它它的的解解法步骤如下：法步骤如下：第第一一步步，当当是是 不不可可行行点点时时，用用最最速速下下降降法法把把它它拉拉到到满满足足约约束集内。此时的函数形式取为：束集内。此时的函数形式取为：第第二二步步，再再用用线线性性规规划划法法。每每次次线线性性规规划划阶阶段段移移步步后后，要要进进行一次判别，看是否满足行一次判别，看是否满足此法的使用效果好于前两种方法。此法的使用效果好于前两种方法。第七节第七节 非线性规划问题的线性化解法非线性规划问题的线性化解法线线性逼近法性逼近法四、非线性规划法四、非线性规划法四、非线性规划法四、非线性规划法对对于于线线性性规规划划问问题题，也也可可以以通通过过泰泰勒勒级级数数展展开开的的方方法法把把约约束束取取成成线线性性的的，目目标标函函数数取取成成二二次次函函数数。这这种种约约束束为为线线性性而而目目标标函函数数是是二二次次函函数数的的最最优优问问题题。有有多多种种求求解解二二次次规规划划问问题题的的方方法法，其其中中一一种种实实际际上上可可以以看看成成是是线线性性规规划划问问题题中中单单纯纯形形法法的的推推广广。因因此此，用用这这样样的的处处理理办办法法来来解解决决非非线线性性规规划划问问题题可可以称为二次规划问题的线性规划解法。以称为二次规划问题的线性规划解法。第八节第八节 广义简约梯度法广义简约梯度法广广广广义义义义简简简简约约约约梯梯梯梯度度度度法法法法也也也也称称称称GRGGRG法法法法。它它它它是是是是简简简简约约约约梯梯梯梯度度度度法法法法推推推推广广广广到到到到求求求求解解解解具具具具有有有有非非非非线线线线性性性性约约约约束束束束的的的的优优优优化化化化问问问问题题题题的的的的一一一一种种种种方方方方法法法法。这这这这种种种种方方方方法法法法是是是是目目目目前前前前求求求求解解解解一一一一般般般般非非非非线线线线性性性性优优优优化化化化问问问问题题题题的的的的最最最最有有有有效效效效的的的的算法之一。算法之一。算法之一。算法之一。一、简约梯度法一、简约梯度法一、简约梯度法一、简约梯度法简简约约梯梯度度法法仅仅用用来来求求解解具具有有线线性性等等式式约约束束的的优优化化问问题题。算算法法的的基基本本思思想想是是设设法法处处理理约约束束函函数数，将将原原问问题题转转化化成成仅仅具具有有变变量边界约束的优化问题，然后求解。量边界约束的优化问题，然后求解。第八节第八节 广义简约梯度法广义简约梯度法二、广义简约梯度法二、广义简约梯度法二、广义简约梯度法二、广义简约梯度法广广义义简简约约梯梯度度法法可可以以用用来来求求解解具具有有非非线线性性等等式式约约束束和和变变量量界界限约束的优化问题，其数学模型为限约束的优化问题，其数学模型为式中的式中的 为变量的下界和上界值。为变量的下界和上界值。第八节第八节 广义简约梯度法广义简约梯度法三、不等式约束函数的处理和换基问题三、不等式约束函数的处理和换基问题三、不等式约束函数的处理和换基问题三、不等式约束函数的处理和换基问题1.1.不等式简约梯度法求解的处理方法不等式简约梯度法求解的处理方法不等式简约梯度法求解的处理方法不等式简约梯度法求解的处理方法 用用广广义义简简约约梯梯度度法法求求解解具具有有不不等等式式约约束束函函数数的的优优化化问问题题时时，需需引引进进新新变变量量，将将不不等等式式约约束束函函数数转转化化成成等等式式约约束束函函数数，即即将将该该问问题题转转化化成成与与式式（6-107）相相同同的的形形式式，然然后后按按前前述述方方法求解。法求解。第八节第八节 广义简约梯度法广义简约梯度法三、不等式约束函数的处理和换基问题三、不等式约束函数的处理和换基问题三、不等式约束函数的处理和换基问题三、不等式约束函数的处理和换基问题2.2.基变量的选择和换基问题基变量的选择和换基问题基变量的选择和换基问题基变量的选择和换基问题按按广广义义简简约约梯梯度度法法原原理理，首首先先应应将将涉涉及及变变量量分分成成基基变变量量和和非非基基变变量量，对对于于只只具具有有等等式式函函数数的的问问题题，应应在在n设设计计变变量量中中选选择择m个个变变量量作作为为基基变变量量，对对于于具具有有不不等等式式约约束束函函数数的的问问题题，应应在在n+l个个变变量量中中选选择择m+l个个变变量量作作为为基基变变量量（l为为松松弛弛变变量量数数），其余的变量为非基变量。，其余的变量为非基变量。为为了了使使基基变变量量的的变变化化尽尽量量少少，应应选选择择远远离离其其边边界界的的变变量量为为基基变变量量。同同时时，为为了了保保证证基基矩矩阵阵非非奇奇异异及及求求逆逆计计算算的的稳稳定定，要要求求基基矩矩阵阵的的主主元元不不能能太太小小以以及及同同列列中中的的其其他他元元素素与与主主元元之之比比不能太大。不能太大。在在迭迭代代过过程程中中，若若某某一一基基变变量量等等于于0，或或等等于于边边界界值值时时，应应换基变量，即选择一非基变量来代替该基变量。换基变量，即选择一非基变量来代替该基变量。第九节第九节 二次规划法二次规划法二二二二次次次次规规规规划划划划法法法法的的的的基基基基本本本本原原原原理理理理是是是是将将将将元元元元问问问问题题题题转转转转化化化化为为为为一一一一系系系系列列列列二二二二次次次次规规规规划划划划的的的的子子子子问问问问题题题题。求求求求解解解解子子子子问问问问题题题题，得得得得到到到到本本本本次次次次迭迭迭迭代代代代的的的的搜搜搜搜索索索索方方方方向向向向，沿沿沿沿搜搜搜搜索索索索方方方方向向向向寻寻寻寻优优优优，最最最最终终终终逼逼逼逼近近近近问问问问题题题题的的的的最最最最优优优优点点点点，因因因因此此此此，这这这这种种种种方方方方法法法法又又又又称称称称为为为为序序序序列列列列二二二二次次次次规规规规划划划划法法法法。另另另另外外外外，算算算算法法法法是是是是利利利利用用用用拟拟拟拟牛牛牛牛顿顿顿顿法法法法（变变变变尺尺尺尺度度度度法法法法）来来来来近近近近似似似似构构构构造造造造海海海海塞塞塞塞矩矩矩矩阵阵阵阵，以以以以建建建建立立立立二二二二次次次次规规规规划划划划子子子子问问问问题题题题，故故故故又又又又可可可可称称称称为为为为约约约约束束束束变变变变尺尺尺尺度度度度法法法法，这这这这种种种种方方方方法法法法被被被被认认认认为为为为是是是是目目目目前前前前最最最最先先先先进进进进的的的的非非非非线线线线性性性性规规规规划划划划计算方法。计