有约束优化方法课件

第五章 有约束优化方法 5-1 5-1 引言引言5-25-2 随机方向法随机方向法5-35-3 复合形法复合形法5-45-4 可行方向法可行方向法 5-5 5-5 惩罚函数法惩罚函数法5-65-6 序列二次规划法序列二次规划法5-1 5-1 引言引言机械优化设计中的问题，大多数属于约束优化设机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为计问题，其数学模型为上一章讨论的都是无约束条件下非线性函数的寻上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取值都有优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。一定的限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行的可行域内的最小值。只要由约束条件所决定的可行域必是一个凸集，目标函数是凸函数，其约束最优解域必是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，同，而探索到不同的局部最优解上。在这种情况下，探索结果经常与初始点的选择有关。为了能得到全局探索结果经常与初始点的选择有关。为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。要改换几次。（1）直接法）直接法直接法包括：网格法、复合形法、随机试验法、直接法包括：网格法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。随机方向法、可变容差法和可行方向法。（2）间接法）间接法间接法包括：罚函数法、内点罚函数法、外点罚间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、广义乘子法、广义简约梯度函数法、混合罚函数法、广义乘子法、广义简约梯度法和约束变尺度法等。法和约束变尺度法等。根据求解方式的不同，约束优化设计问题可分为根据求解方式的不同，约束优化设计问题可分为:直直接解法、间接解法。接解法、间接解法。间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。间接解法中具有代表性的是惩罚函数法。直接解法的基本思想：在由m个不等式约束条件gu(x)0所确定的可行域内，选择一个初始点x(0)，然后确定一个可行搜索方向S，且以适当的步长沿S方向进行搜索，取得一个目标函数有所改善的可行的新点x(1)，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：x(k+1)x(k)+(k)S(k)(k=0,1,2,)逐步趋向最优解，直到满足终止准则才停止迭代。直接解法通常适用于仅含不等式约束的问题，思路是直接解法通常适用于仅含不等式约束的问题，思路是在在m个不等式约束条件所确定的可行域内，选择一个初始个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向点，然后决定可行搜索方向d 且以适当的步长且以适当的步长，进行，进行搜索，得到一个使目标函数值下降的可行的新点，即完成搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。足收敛条件。步长步长可行搜索方向可行搜索方向可行搜索方向可行搜索方向:当设计点沿该方向作微量移动时，当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域目标函数值将下降，且不会越出可行域。直接解法的原理简单，方法实用，其特点是：1）由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的设计点。2）若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。3）要求可行域有界的非空集。a)可行域是凸集；b)可行域是非凸集间接解法的求解思路：将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。新目标函数加权因子然后对新目标函数进行无约束极小化计算。5-25-2 随机方向法随机方向法基基基基本本本本思思思思想想想想：利利利利用用用用计计计计算算算算机机机机产产产产生生生生的的的的随随随随机机机机数数数数所所所所构构构构成成成成的的的的随随随随机机机机方方方方向向向向进进进进行行行行搜搜搜搜索索索索，产产产产生生生生的的的的新新新新点点点点必必必必须须须须在在在在可可可可行行行行域域域域内内内内，即即即即满满满满足直接法的特性。足直接法的特性。足直接法的特性。足直接法的特性。随随随随机机机机方方方方向向向向法法法法，是是是是约约约约束束束束最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种常常常常用用用用的的的的直直直直接接接接求求求求解解解解方方方方法法法法。它它它它和和和和随随随随机机机机梯梯梯梯度度度度法法法法、GaussGaussSeidelSeidel法法法法等等等等都都都都属于约束随机法。属于约束随机法。属于约束随机法。属于约束随机法。第二节随机方向法随机方向法的基本思路：在可行域内选择一个初始点，利用随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为搜索方向d。从初始点x0出发，沿d 方向以一定步长进行搜索，得到新点X，新点x应满足约束条件且f(x)f(x0)，至此完成一次迭代。基本思路如图所示。随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。一、随机数的产生下面介绍一种常用的产生随机数的数学模型首先令取r=2657863，按一下步骤计算：令若则若则若则则（0，1）之间的随机数在任意(a,b)区间内的随机数二、初始点的选择 随机方向法的初始点x0必须是一个可行点，既满足全部不等式约束条件。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即2）在区间（0，1）内产生n个伪随机数3）计算随机点x的各分量4）判别随机点x是否可行，若随机点可行，用x代替x0为初始点；若非可行点，转到步骤2）重新产生随机点，只到可行为止。三、可行搜索方向的产生产生可行随机方向的方法：从k个随机方向中，选取一个较好的方向。其计算步骤为：1）在(-1,1)区间内产生伪随机数，得随机单位向量2)取一试验步长a0，按下式计算k个随机点3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点XL。4)比较XL 和X0两点的目标函数值，若f(XL)f(X0)，则步长0 缩小，专步骤1）重新计算，直至f(XL)f(X0)为止。如果0 缩小到很小，仍然找不到一个XL，使f(XL)f(X0)则说明X0是一个局部极小点，此时可更换初始点，转步骤1）。产生可行搜索方向的条件为：则可行搜索方向为：四、搜索步长的确定步长由加速步长法确定。随机方向探索法的一般迭代随机方向探索法的一般迭代随机方向探索法的一般迭代随机方向探索法的一般迭代计计算公式算公式算公式算公式为为：X X(k+1)(k+1)=X X(k)(k)+aS+aS(k(k)(k=0,1,2,)(k=0,1,2,)式中式中式中式中a a为为步步步步长长，S S(k(k)为为第第第第k k次迭代的随机探索方向。次迭代的随机探索方向。次迭代的随机探索方向。次迭代的随机探索方向。因此，随机方向探索法的因此，随机方向探索法的因此，随机方向探索法的因此，随机方向探索法的计计算算算算过过程可程可程可程可归结为归结为：X0=X,F0=F=0,F0=F(X0)F=F（X）j=1K=K+1三三.随机方向法随机方向法 的迭代步骤的迭代步骤是是K=0,j=0产生随机方向产生随机方向=0.5否否FF0j=0Km结结束束X*=X0,F*=F0是是否否是是否否是是否否XDD是是否否 复复复复合合合合形形形形法法法法是是是是求求求求解解解解约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种重重重重要要要要的的的的直直直直接接接接方方方方法法法法。它它它它来来来来源源源源于于于于用用用用于于于于求求求求解解解解无无无无约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的单单单单纯纯纯纯形形形形法法法法，实实实实际际际际上上上上是是是是单单单单纯纯纯纯形形形形法法法法在在在在约约约约束束束束问问问问题题题题中中中中的发展。的发展。的发展。的发展。如如如如前前前前所所所所述述述述，在在在在求求求求解解解解无无无无约约约约束束束束问问问问题题题题的的的的单单单单纯纯纯纯形形形形法法法法中中中中，不不不不需需需需计计计计算算算算目目目目标标标标函函函函数数数数的的的的梯梯梯梯度度度度，而而而而是是是是靠靠靠靠选选选选取取取取单单单单纯纯纯纯形形形形的的的的顶顶顶顶点点点点井井井井比比比比较较较较各各各各顶顶顶顶点点点点处处处处目目目目标标标标函函函函数数数数值值值值的的的的大大大大小小小小，来来来来寻寻寻寻找找找找下下下下一一一一步步步步的的的的探探探探索索索索方方方方向向向向的的的的。在在在在用用用用于于于于求求求求解解解解约约约约束束束束问问问问题题题题的的的的复复复复合合合合形形形形法法法法中中中中，复复复复合合合合形形形形各各各各顶顶顶顶点点点点的的的的选选选选择择择择和和和和替替替替换换换换，不不不不仅仅仅仅要要要要满满满满足足足足目目目目标标标标函函函函数数数数值值值值的的的的下下下下降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。5-35-3 复合形法复合形法 它的基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状没改变一次，就向最优点移动一步，直至逼近最优点。由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。二二.初始复合形的构成初始复合形的构成1.复合形顶点数复合形顶点数K K的选择的选择建议建议:小取大值小取大值,大取小值大取小值2)为避免降维为避免降维,K K应取大些应取大些;但过大但过大,计算量也计算量也大大.*1)为保证迭代点能逼近极小点为保证迭代点能逼近极小点,应使应使2.初始复合形顶点的确定初始复合形顶点的确定1)用试凑方法产生用试凑方法产生-适于低维情况适于低维情况;2)用随机方法产生用随机方法产生用随机方法产生用随机方法产生K K个顶点个顶点 先用随机函数产生先用随机函数产生 个随机数个随机数 ,然后变换到预定的区间然后变换到预定的区间 中去中去.这便得到了一个顶点这便得到了一个顶点,要连续产生要连续产生K K个顶点个顶点.初始复合形生成的方法：1）由设计者决定k个可形点，构成初始复合形。设计变量少时适用。2）由设计者选定一个可形点，其余的k-1个可形点用随机法产生。将非可行点调入可行域内将非可行点调入可行域内)检查已获得的各顶点的可行性检查已获得的各顶点的可行性,若无一可行若无一可行,则重新产生随机点则重新产生随机点;若有若有q q个可行个可行,则转下步则转下步.)计算计算q q个可行点点集的几何中心个可行点点集的几何中心)将非可行点逐一调入可行域内将非可行点逐一调入可行域内.若若仍不仍不可行可行,则重则重复此步骤复此步骤,直至进入直至进入可行域为止可行域为止.3）由计算机自动生成初始复合形的所有顶点。二、复合形法的搜索方法1.反射1）计算复合形各顶点的目标函数值，并比较其大小，求出最好点XL、最坏点XH 及 次坏点XG，即2）计算除去最坏点XH 外的（k-1）个顶点的中心XC 3）从统计的观点来看，一般情况下，最坏点XH和中心点XC的连线方向为目标函数的下降方向。4）判别反射点XR的位置 若XR 为可行点，则比较XR 和XH 两点的目标函数值，如果f(XR)=f(XH),则将缩小0.7倍，重新计算新的反射点，若仍不行，继续缩小，直至f(XR)f(XH)为止。若为非可行点，则将缩小0.7倍，直至可行为止。然后再重复可行点的步骤。2.扩张3.收缩三三.终止判别条件终止判别条件各顶点与好点函数值之差的均方根应不大于误差限各顶点与好点函数值之差的均方根应不大于误差限不是十分可靠不是十分可靠,可改变可改变 重作重作,看结果是否相同看结果是否相同.比比较较复复合合形形各各顶顶点点的的函函数数值值，找出好点找出好点XL，坏点坏点XHXH=XR=0.5找出次坏点找出次坏点XSH，XH=XSH满足终止条件满足终止条件？X*=XL,F*=F(XL)结结 束束四四.复合形法的复合形法的迭代步骤迭代步骤是是否否给定给定K，ai,bii=1,2,n产生初始复合形顶点产生初始复合形顶点Xj,j=1,2,K计算复合形各顶点的函数值计算复合形各顶点的函数值F(Xj),j=1,2,K是是是是是是否否否否否否XRDDFRF(XH)仅具有反射策略的复合形法基基基基 本本本本 思思思思 想想想想：在在在在 可可可可 行行行行 域域域域 中中中中 选选选选 取取取取 KK个个个个 设设设设 计计计计 点点点点 （n+1K2nn+1K2n）作作作作为为为为初初初初始始始始复复复复合合合合形形形形的的的的顶顶顶顶点点点点。比比比比较较较较各各各各顶顶顶顶点点点点目目目目标标标标函函函函数数数数值值值值的的的的大大大大小小小小，去去去去掉掉掉掉目目目目标标标标函函函函数数数数值值值值最最最最大大大大的的的的顶顶顶顶点点点点(称称称称最最最最坏坏坏坏点点点点)，以以以以坏坏坏坏点点点点以以以以外外外外其其其其余余余余各各各各点点点点的的的的中中中中心心心心为为为为映映映映射射射射中中中中心心心心，用用用用坏坏坏坏点点点点的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。反反反反复复复复迭迭迭迭代代代代计计计计算算算算，使使使使复复复复合合合合形形形形不不不不断断断断向向向向最最最最优优优优点点点点移移移移动动动动和和和和收收收收缩缩缩缩，直直直直至至至至收收收收缩缩缩缩到到到到复复复复合合合合形形形形的的的的顶顶顶顶点点点点与与与与形形形形心心心心非非非非常常常常接接接接近近近近，且且且且满满满满足迭代精度要求为止。足迭代精度要求为止。足迭代精度要求为止。足迭代精度要求为止。令：令：X(4)=X(0)+(X(0)-X(H)称称X(4)为映射点，记为为映射点，记为X(R)，为映射系数，通常取为映射系数，通常取=1.3，可根据实际情况进行缩减。，可根据实际情况进行缩减。取次好点和好点连线的中点为取次好点和好点连线的中点为X(0)。一般情况下，映射点的函数值比坏点的函数值要一般情况下，映射点的函数值比坏点的函数值要小，即小，即F(X(R)F(X(H)。若满足可行域，则用。若满足可行域，则用X(R)代替代替X(H)构成新的复合形。如此反复迭代直到找到最优解。构成新的复合形。如此反复迭代直到找到最优解。在在可可行行域域内内任任选选三三个个初初始始点点X(1)、X(2)、X(3)，连连接接这这三三点点形形成成一一个个三三角角形形，此此三三角角形形称称为为初初始始复复合合形形。计计算算各各个个顶顶点点函函数数值值F(X(1)、F(X(2)、F(X(3)，找找出出最最大大值值，记记为为坏坏点点X(H)。最最小小值值，记记为为最最好好点点X(L)。在在次次好好点点和和好好点连线与坏点反向一侧的各点应具有较小的目标值。点连线与坏点反向一侧的各点应具有较小的目标值。在在迭迭代代过过程程中中，按按映映射射系系数数=1.3得得到到的的映映射射点点，不不一一定定满满足足适适用用性性和和可可行行性性，如如出出现现此此情情况况，将将映映射射系系数数减减半半，重重新新取取得得X(R)，使使它它满满足足适适用用性性和和可可行性。行性。一、初始复合形的构成一、初始复合形的构成复合形的顶点复合形的顶点K通常取通常取n+1K2n个。对于维数较低个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，为复合形的顶点。对于维数较高的问题，采用随机方法，先产生先产生K个随机点，然后再把非可行点逐一调入可行域内。个随机点，然后再把非可行点逐一调入可行域内。1、产生、产生K个随机点个随机点xi=ai+i(bi-ai)i=1,2,.,ni为（为（0，1）区间内产生的均匀分布的随机数，需要）区间内产生的均匀分布的随机数，需要n个个随机数产生一个点随机数产生一个点X(1)。同样，产生其它的随机点。同样，产生其它的随机点X(2)、X(3)、X(K)。2、将非可行点调入可行域、将非可行点调入可行域将产生的将产生的K个随机点进行判断是否在可行域内，个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有重新排列，将可行点依次排在前面，如有q个顶点个顶点X(1)、X(2)、X(q)是可行点，其它是可行点，其它K-q个为非可行点。个为非可行点。对对X(q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是：（1）计算）计算q个点集的中心个点集的中心X(s)；（2）将第）将第q+1点朝着点点朝着点X(s)的方向移动，按下式产的方向移动，按下式产生新的生新的X(q+1)，即，即X(q+1)=X(s)+0.5(X(q+1)X(s)这这个个新新点点X(q+1)实实际际就就是是X(s)与与原原X(q+1)两两点点连连线线的的中中点点，如如图图。若若新新的的X(q+1)点点仍仍为为非非可可行行点点，按按上上式式再再产产生生X(q+1)，使它更向，使它更向X(s)靠拢，最终使其成为可行点。靠拢，最终使其成为可行点。按按照照这这个个方方法法，同同样样使使X(q+2)、X(q+3)、X(K)都变为可行点，这都变为可行点，这K个点就构成了初始复合形。个点就构成了初始复合形。二、复合形法的迭代步骤二、复合形法的迭代步骤（1）构造初始复合形；）构造初始复合形；（2）计算各顶点的函数值）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好。选出好点点X(L)和坏点和坏点X(H)。（3）计算坏点外的其余各顶点的中心点）计算坏点外的其余各顶点的中心点X(0)。（4）计算映射点）计算映射点X(R)检查检查X(R)是否在可行域内。若是否在可行域内。若X(R)为非可行点，将映为非可行点，将映射系数减半后再按上式改变映射点，直到射系数减半后再按上式改变映射点，直到X(R)进入可行域进入可行域内为止。内为止。（5）构造新的复合形）构造新的复合形计算映射点的函数值计算映射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比较，可能存在两种情况：比较，可能存在两种情况：1）映射点优于坏点）映射点优于坏点F(X(R)F(X(H)在此情况，用在此情况，用X(R)代替代替X(H)，构成新的复合形。，构成新的复合形。若经过多次的映射系数减半，仍不能使映射点由于坏若经过多次的映射系数减半，仍不能使映射点由于坏点，则说明该映射方向不利，此时，应改变映射方向，点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点取对次坏点的映射。的映射。再转回本步骤的开始处，直到构成新的复合形。再转回本步骤的开始处，直到构成新的复合形。2）映射点次于坏点）映射点次于坏点F(X(R)F(X(H)这这种种情情况况由由于于映映射射点点过过远远引引起起的的，减减半半映映射射系系数数，若有若有F(X(R)F(X(H)，这又转化为第一种情况。，这又转化为第一种情况。(6)判断终止条件判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即各顶点与好点函数值之差的均方根值小于误差限，即2）各顶点与好点的函数值之差的平方和小于误差限，即）各顶点与好点的函数值之差的平方和小于误差限，即3）各顶点与好点函数值差的绝对值之和小于误差限，即）各顶点与好点函数值差的绝对值之和小于误差限，即如果不满足终止迭代条件，则返回步骤如果不满足终止迭代条件，则返回步骤2继续进行下继续进行下一次迭代；否则，可将最后复合形的好点一次迭代；否则，可将最后复合形的好点X(L)及其函数值及其函数值F(X(L)作为最优解输出。作为最优解输出。方法特点方法特点（1 1）复复复复合合合合形形形形法法法法是是是是求求求求解解解解约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种直直直直接接接接方方方方法法法法，仅仅仅仅通通通通过过过过选选选选取取取取各各各各顶顶顶顶点点点点并并并并比比比比较较较较各各各各点点点点处处处处函函函函数数数数值值值值的的的的大大大大小小小小，就就就就可可可可寻寻寻寻找找找找下下下下一一一一步步步步的的的的探探探探索索索索方方方方向向向向。但但但但复复复复合合合合形形形形各各各各顶顶顶顶点点点点的的的的选选选选择择择择和和和和替替替替换换换换，不不不不仅仅仅仅要要要要满满满满足足足足目目目目标标标标函函函函数数数数值值值值下下下下降降降降的的的的要求，还应当满足所有的约束条件。要求，还应当满足所有的约束条件。要求，还应当满足所有的约束条件。要求，还应当满足所有的约束条件。（2 2）复合形法适用于仅含不等式约束的问题。）复合形法适用于仅含不等式约束的问题。）复合形法适用于仅含不等式约束的问题。）复合形法适用于仅含不等式约束的问题。可可行行方方向向是是求求解解大大型型不不等等式式约约束束优优化化问问题题的的主主要要方方法之一。法之一。基基本本思思想想：这这种种方方法法的的基基本本原原理理是是在在可可行行域域内内选选择择一一个个初初始始点点，当当确确定定了了一一个个可可行行方方向向d和和适适当当的的步步长长后，按式后，按式:5-45-4 可行方向法可行方向法进行迭代计算进行迭代计算,迭代点既不超出可行域迭代点既不超出可行域,又使目标函又使目标函数的值有所下降。在不断调整可行方向的过程中，数的值有所下降。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。使迭代点逐步逼近约束最优点。可行方向法的搜索策略？可行方向法的搜索策略？即：即：Ox1x2Ox1x2a)极值点处于多角形的某一顶点上b)极值点处于等值线的中心c)极值点处于约束曲线与等值线的切点上d)极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0 xg2(x)0g3(x)0g4(x)0g1(x)0g2(x)0Ox1x2Ox1x2xg2(x)0 xg1(x)0g1(x)0图图图图1-101-101.可行方向法的搜索策略可行方向法的搜索策略第一步迭代都是从可行的初始点第一步迭代都是从可行的初始点出发，沿点的出发，沿点的负梯度负梯度方向，将初始点移动到某一个约束方向，将初始点移动到某一个约束面（只有一个起作用的约束时）上面（只有一个起作用的约束时）上,或约束面的交集或约束面的交集（有几个起作用的约束时）上。（有几个起作用的约束时）上。根据约束函数和目标函数的不同性状，分别采用根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索。以下几种策略继续搜索。1新点在可行域内的情况新点在可行域内的情况2新点在可行域外的情况新点在可行域外的情况3沿线性约束面的搜索沿线性约束面的搜索4沿非线性约束面的搜索沿非线性约束面的搜索2.产生可行方向的条件产生可行方向的条件可行方向是指沿该方向作微小移动后，所得到的可行方向是指沿该方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。新点是可行点，且目标函数值有所下降。可行方向应满足两个条件可行方向应满足两个条件:(1)可行可行;(2)下降下降。1）可行条件）可行条件方向的可行条件是指沿该方向作微小移动后，所得到方向的可行条件是指沿该方向作微小移动后，所得到的新点为可行点。的新点为可行点。2）下降条件）下降条件方向的下降条件是指沿该方向作微小移动后，所得方向的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。新点的目标函数值是下降的。满足可行和下降条件，即式满足可行和下降条件，即式:位于约束位于约束曲面在点曲面在点xk的切线和目的切线和目标函数等值标函数等值线在点线在点xk的的切线所围成切线所围成的扇形区内，的扇形区内，该扇形区称该扇形区称为可行下降为可行下降方向区方向区。同时成立的方向称可行方向。同时成立的方向称可行方向。3.可行方向的产生方法可行方向的产生方法满足可行、下降条件的方向位于可行下降扇满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向。本次迭代的搜索方向。（1 1）优选方向法）优选方向法由条件：由条件：求一个以搜索方向求一个以搜索方向d为设计变量的约束优化问题为设计变量的约束优化问题s.t.各函数均为设计变量各函数均为设计变量dk的线性函的线性函数，因此该式为一个（线性）数，因此该式为一个（线性）规划问题。规划问题。当当xk点点目目标标函函数数的的负负梯梯度度方方向向不不满满足足可可行行条条件件时时，可可将将方方向向投投影影到到约约束束面面（或或约约束束面面的的交交集集）上上，得到投影向量得到投影向量dk。xkdkg g1 1(x)=0)=0g g2 2(x)=0)=0g g3 3(x)=0)=0g g4 4(x)=0)=0P P投影算子，投影算子，为为nX Xn阶矩阵阶矩阵G 起作用约起作用约束函数的梯度矩束函数的梯度矩阵，阵，nX XJ阶矩阵；阶矩阵；（2）梯度投影法）梯度投影法4.4.步长的确定步长的确定 确定的确定的步步长应使新的迭代点为可行点，且目标函数应使新的迭代点为可行点，且目标函数具有最大的下降量具有最大的下降量约束一维搜索。约束一维搜索。1 1）取最优步长）取最优步长 从从xk点点出发，沿出发，沿dk方向进行一维最优方向进行一维最优化搜索，取得最优步长，计算新点化搜索，取得最优步长，计算新点x的值的值。(2)(2)取到约束边界的最大步长取到约束边界的最大步长 从从xk点出发，沿点出发，沿dk方向进行一维最优化搜索，方向进行一维最优化搜索，得到的新点得到的新点x为不可行点不可行点。改变步长，改变步长，使新点使新点x返回到返回到约束面上来。约束面上来。使新点使新点x恰好位恰好位于约束面上的于约束面上的步长称为最大步长称为最大步长步长,记作记作。的确定 1)试验步长将 在 处作泰勒展开,仅取到线性项:(1)定义目标函数相对下降量:(2)迭代公式(3)(4)将(2)、(3)代入(1)后整理得:迭代点在边界附近偏域内一侧时使 用,采用最有利的适用可行方向.2)按此法,直至使迭代点进入约束容差带或至域外为止.*1)为保证 是 的一个邻近点,的值不能取得太大.通常2）调整调整(将已出界的迭代点调回到将已出界的迭代点调回到边界上边界上)(1)约束边界容差带约束边界容差带在实际计算中在实际计算中,应给约束边界一个允应给约束边界一个允许的误差限许的误差限:式中式中,通常取通常取0.01-0.001;只要迭代点进只要迭代点进入容差带入容差带,即认为达到了边界即认为达到了边界.(2)调整步长因子调整步长因子因因与与很接近很接近,可认为可认为在这两点间按线性变化在这两点间按线性变化:(1)为使新迭代点落在容差带中部为使新迭代点落在容差带中部,取取(2)于是有于是有(3)*还需检验该点是否在容差带内还需检验该点是否在容差带内.若不满足若不满足,则则)若若 ,则则)若若 ,则则 重复以上步骤重复以上步骤,直至满足时止直至满足时止.收敛条件收敛条件2 2）设计点）设计点xk满足库恩满足库恩-塔克条件塔克条件l1）设计点）设计点xk及约束允差及约束允差满足满足例题例题5-1：用可行方向法求约束优化问题：用可行方向法求约束优化问题解解:(1)取取初初始始点点，则则取取作作用用约约束束集集:Jk=1(2)寻找最优方向，即解一个以可行方向为设计变量寻找最优方向，即解一个以可行方向为设计变量的规划问题：的规划问题：1d1d2用图解法：用图解法：最优方向：最优方向：(3)沿沿d0方向进行一维搜索方向进行一维搜索x1在约束边界在约束边界g3(x)=0上上:g3(x1)=0(4)第二次迭代，用梯度投影法确定可行方向第二次迭代，用梯度投影法确定可行方向,迭代点迭代点x的目标函数负梯度的目标函数负梯度不不满满足足方方向向的的可可行行条条件件，将将投投影影到到约约束束边边界界g3(x)=0上。上。投影算子：投影算子：由上式可由上式可求得：求得：本次本次迭代方向迭代方向D为沿为沿约束边界约束边界g3(x)=0的的方向，求最佳步长方向，求最佳步长求得：求得：g5(x)=068x1x2g4(x)=0g3(x)=0g2(x)=0g1(x)=0 x0d0（4）收敛判断：）收敛判断：由于由于Jk=3，5代入代入KT条件：条件：5-5 惩罚函数法惩罚函数法 惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和不等式约束函数经加权后，和原目标函数结合为新的目标函数惩罚函数。将约束优化问题转换为无约束优化问题。求解无约束优化问题的极小值，从而得到原约束优化问题的最优解。加权转化项 将将有有约约束束的的优优化化问问题题转转化化为为无无约约束束优优化化问问题题来来求求解解。前前提提：一一是是不不能能破破坏坏约约束束问问题题的的约约束束条条件件，二二是是使使它它归归结结到原约束问题的同一最优解上去。到原约束问题的同一最优解上去。构成一个新的目标函数，称为惩罚函数构成一个新的目标函数，称为惩罚函数从而有从而有惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质：求求解解该该新新目目标标函函数数的的无无约约束束极极小小值值，以以期期得得到到原原问问题题的的约约束束最最优优解解。按按一一定定的的法法则则改改变变罚罚因因子子r1和和r2的的值值，求求得得一一序序列列的的无无约约束束最最优优解解，不不断断地地逼逼近近原原约约束束优优化化问问题题的最优解。的最优解。根根据据约约束束形形式式和和定定义义的的泛泛函函及及罚罚因因子子的的递递推推方方法法等等不不同同，罚罚函函数数法法可可分分为为内内点点法法、外外点点法法和和混混合合罚罚函函数数法法三三种种。这这种种方方法法是是1968年年由由美美国国学学者者AVFiacco和和GPMcormick提提出出的的，把把不不等等式式约约束束引引入入数数学学模模型型中中，为为求求多多维维有有约约束束非非线线性性规规划划问问题题开开创创了一个新局面。了一个新局面。1.内点法内点法这这种种方方法法将将新新目目标标函函数数定定义义于于可可行行域域内内，序序列列迭迭代代点点在在可可行行域域内内逐逐步步逼逼近近约约束束边边界界上上的的最最优优点点。内内点法只能用来求解具有不等式约束的优化问题。点法只能用来求解具有不等式约束的优化问题。对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题：转化后的惩罚函数形式为：转化后的惩罚函数形式为：或：或：rk是是惩惩罚罚因因子子，它它是是一一个个由由大大到到小小且且趋趋近近于于0的的正正数数列列，即即:由由于于内内点点法法的的迭迭代代过过程程在在可可行行域域内内进进行行，“障障碍碍项项”的的作作用用是是阻阻止止迭迭代代点点越越出出可可行行域域。由由“障障碍碍项项”的的函函数数形形式式可可知知，当当迭迭代代点点靠靠近近某某一一约约束束边边界界时时，其其值值趋趋近近于于0，而而“障障碍碍项项”的的值值陡陡然然增增加加，并并趋趋近近于于无无穷穷大大，好好像像在在可可行行域域的的边边界界上上筑筑起起了了一一道道“高高墙墙”，使使迭代点始终不能越出可行域。显然，只有当惩罚因子迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。时，才能求得在约束边界上的最优解。罚罚因因子子的的作作用用是是：由由于于内内点点法法只只能能在在可可行行域域内内迭迭代代，而而最最优优解解很很可可能能在在可可行行域域内内靠靠近近边边界界处处或或就就在在边边界界上上，此此时时尽尽管管泛泛函函的的值值很很大大，但但罚罚因因子子是是不不断断递递减减的的正正值值，经经多多次次迭迭代代，接接近近最最优优解解时时，惩惩罚项已是很小的正值。罚项已是很小的正值。例例5-2用内点法求用内点法求的约束最优解。的约束最优解。解解:用内点法求解该问题时，首先构造内点惩罚函用内点法求解该问题时，首先构造内点惩罚函数数:用解析法求函数的极小值，运用极值条件：用解析法求函数的极小值，运用极值条件：联立求解得：联立求解得：时不满足约束条件时不满足约束条件应舍去应舍去。无约束极值点为无约束极值点为当当1）初始点初始点x0的选取的选取 使使用用内内点点法法时时，初初始始点点应应选选择择一一个个离离约约束束边边界界较较远远的的可可行行点点。如如太太靠靠近近某某一一约约束束边边界界，构构造造的的惩惩罚罚函函数数可可能能由由于于障障碍碍项项的的值值很很大大而而变变得得畸畸形形，使使求求解解无约束优化问题发生困难无约束优化问题发生困难.2）惩罚因子初值惩罚因子初值r0的选取的选取 惩惩罚罚因因子子的的初初值值应应适适当当，否否则则会会影影响响迭迭代代计计算算的的正正常常进进行行。一一般般而而言言，太太大大，将将增增加加迭迭代代次次数数；太太小小，会会使使惩惩罚罚函函数数的的性性态态变变坏坏，甚甚至至难难以以收收敛敛到到极极值值点点。无无一一般般性性的的有有效效方方法法。对对于于不不同同的的问问题题，都都要经过多次试算，才能决定一个适当要经过多次试算，才能决定一个适当r03)惩罚因子的缩减系数惩罚因子的缩减系数c的选取的选取 在在构构造造序序列列惩惩罚罚函函数数时时，惩惩罚罚因因子子r是是一一个个逐逐次次递递减到减到0的数列，相邻两次迭代的惩罚因子的关系为的数列，相邻两次迭代的惩罚因子的关系为:式式中中的的c称称为为惩惩罚罚因因子子的的缩缩减减系系数数，c为为小小于于1的的正正数数。一一般般的的看看法法是是，c值值的的大大小小在在迭迭代代过过程程中中不不起起决决定定性性作作用用，通常的取值范围在通常的取值范围在0.10.7之间。之间。4)收敛条件收敛条件算法步骤：算法步骤：算法步骤：算法步骤：1）选择可行域内初始点）选择可行域内初始点X(0);2）选取初始罚因子）选取初始罚因子r(0)与罚因子降低系数与罚因子降低系数c，并置，并置K0；3）求）求min(x(K),r(K)解出最优点解出最优点xK*；4）当）当K=0转步骤转步骤5），否则转步骤），否则转步骤6）；）；5）KK+1，r(K+1)r(K)，xK+10 xK*，并转步骤，并转步骤3）；）；6）按终止准则判别，若满足转步骤）按终止准则判别，若满足转步骤7），否则转步骤），否则转步骤5）；）；7）输出最优解（）输出最优解（X*，F*），停止计算），停止计算。2.外点法外点法 外点法是从可行域的外部构造一个点序列去逼近外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。等式约束的优化问题。外点惩罚函数的形式为：外点惩罚函数的形式为：r是惩罚因子是惩罚因子,外外点点法法的的迭迭代代过过程程在在可可行行域域之之外外进进行行，惩惩罚罚项项的的作作用用是是迫迫使使迭迭代代点点逼逼近近约约束束边边界界或或等等式式约约束束曲曲面面。由由惩惩罚罚项项的形式可知，当迭代点的形式可知，当迭代点x不可行时，惩罚项的值大于不可行时，惩罚项的值大于0。惩罚因子，它是由小到大。惩罚项 由惩罚项可知，当迭代点不可行时，惩罚项的值大于零。当迭代点离约束边界越远时，惩罚项愈大，这可看成是对迭代点不满足约束条件的一种惩罚。转化后的外点惩罚函数的形式为：例例5-3用外点法求解下列有约束优化问题用外点法求解下列有约束优化问题解：惩罚函数为：解：惩罚函数为：对上式求偏导，得对上式求偏导，得无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：当惩罚因子渐增时，由下表可看出收敛情况。当惩罚因子渐增时，由下表可看出收敛情况。r0.01-0.80975-50.00000-24.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.6582108/38/3例6-6 用外点法求问题约束最优解。首先构造外点惩罚函数：用解析法求解求解得外点法惩罚因子按下式递增递增系数，通常取c=5-10。与内点法相反计算r0 值。选取的r0 太大则会使惩罚函数等值线偏心或变形，难以取得极小值。但r0太小，势必增加迭代次数。经验计算一般取r0=1，c=10常常可以取得满意的效果。也可以通过经验公式获得r0 值内点法和外点法的简单比较内点法和外点法的简单比较内点法的特点：内点法的特点：（1）始点必须为严格内点）始点必须为严格内点（2）不适于具有等式约束的数学模型）不适于具有等式约束的数学模型（3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案（4）一般收敛较慢）一般收敛较慢（5）初始罚因子要选择得当）初始罚因子要选择得当（6）罚因子为递减，递减率）罚因子为递减，递减率c有有0c13.混合法混合法 混合法是用内点法处理不等式约束，用外点法处混合法是用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约束的优化理等式约束。可以用来求解含不等式和等式约束的优化问题。问题。混合惩罚函数的形式为：混合惩罚函数的形式为：r是惩罚因子是惩罚因子,混混合合法法具具有有内内点点法法的的特特点点，迭迭代代过过程程在在可可行行域域之之内内进行，参数的选择同内点法。进行，参数的选择同内点法。这种同时处理等式和不等式约束的惩罚函数法称为混合惩罚函数法。混合惩罚函数法与前述内点法和外点法一样，也属于序列无约束极小化(SUMT)方法中的种方法。惩罚函数法原理简单，算法易行，且惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点，分内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方法适用范围广。需要和有效的无约束优化方法结合使用。因此该方法也是应用较多的有约结合使用。因此该方法也是应用较多的有约束优化方法。束优化方法。5-6 5-6 5-6 5-6 拉格朗日乘子法拉格朗日乘子法拉格朗日乘子法拉格朗日乘子法一一.等式约束问题的拉格朗日乘子法等式约束问题的拉格朗日乘子法s.t.1.1.建立拉氏函数建立拉氏函数2.2.在最优点处有如下在最优点处有如下n+q n+q 个方程成立个方程成立其解为其解为s.t.二二.含不等式约束问题的拉格朗日乘子法含不等式约束问题的拉格朗日乘子法1.1.建立拉氏函数建立拉氏函数再用前述方法建立拉氏函数再用前述方法建立拉氏函数对不等式约束引入松弛变量对不等式约束引入松弛变量,使之成为等式约束使之成为等式约束:2.2.在最优点处有如下在最优点处有如下 n+q+2p n+q+2p 个方程成立个方程成立其解为其解为三三.增广拉格朗日乘子法增广拉格朗日乘子法 采采用用拉拉格格朗朗日日乘乘子子法法时时求求解解有有难难度度,而而罚罚函函数数法法当当迭迭代代点点接接近近边边界界时时函函数数常常有有病病态态,此此法法的的思思路路是是把把两两者者结结合起来合起来.其增广拉格朗日函数为其增广拉格朗日函数为:特点特点:1.初始点可为非可行点初始点可为非可行点;2.因因增增加加了了可可调调参参数数,其其收收敛敛速速度度和和稳稳定定性性都都优于罚函数法优于罚函数法.5-7 5-7 5-7 5-7 简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法思思路路：利利用用约约束束条条件件消消去去非非独独立立变变量量，使使问问题题简简化化，再再沿沿简简化化后后的的目目标函数的负梯度方向搜索标函数的负梯度方向搜索.一一 简约梯度法简约梯度法1.1.问题问题s.t.2 2.简约梯度简约梯度1）将问题降维将问题降维基向量（状态）基向量（状态）式中式中将将X X分成两部分分成两部分：非基向量非基向量（决策决策)对应的系数矩阵也分成两部分对应的系数矩阵也分成两部分式中式中，B B为对应于为对应于X XB B的的m m 阶方阵阶方阵，且必须为满秩矩阵且必须为满秩矩阵；C C为为对应于对应于X XN N的的 阶矩阵阶矩阵；于是于是，（1 1）故故2 2）求简约梯度）求简约梯度（2 2）式中式中,3 3.迭代计算迭代计算1 1）迭代公式）迭代公式（3 3）*(1)在迭代中需保证各分量值大于或等于零在迭代中需保证各分量值大于或等于零;(2)当当 且且时时,因因,必有必有,不可行不可行.写成分量的形式：写成分量的形式：（4 4）迭代方向应作修正迭代方向应作修正：(当当,时时)(在在一般情况下一般情况下)（5 5）2 2）步长因子的确定）步长因子的确定(1)若各分量值若各分量值大于零大于零,则只要则只要均能保证变均能保证变量量非负非负,此时可取最优步长此时可取最优步长(2)若若,由于必须使由于必须使（6 6）故故,于是有于是有3）确定确定的方法的方法由由(1)(1)有有*通过通过(3)(3)和和(7)(7)可完成一次完整的迭代可完成一次完整的迭代.（7 7）由由(3)(3)(允许部分变量的上允许部分变量的上下界为下界为 )二二 广义简约梯度法简介广义简约梯度法简介1 1.问题问题s.t.s.t.(可可引入松弛变量将不引入松弛变量将不等式约束变为等式约束等式约束变为等式约束)2 2.解法特点解法特点1)1)和和 之间的关系难以用简单的式子表达之间的关系难以用简单的式子表达,一般采用牛一般采用牛顿迭代法解非线性方程组获得顿迭代法解非线性方程组获得;2)2)求简约梯度用到的求简约梯度用到的 可用复合函数求导的方法求得可用复合函数求导的方法求得.