第六章约束优化方法课件

1 1首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院第六章第六章 约束优化方法约束优化方法4.1概述概述返回返回4.2随机方向法随机方向法4.3复合形法复合形法4.4可行方向法可行方向法重点4.5惩罚函数法惩罚函数法4.6增广乘子法增广乘子法4.74.8广义简约梯度法广义简约梯度法4.9二次规划法二次规划法自学 不作要求7/17/20247/17/20242 2首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院6.1 概述概述q问题的提出q机械优化设计中的问题，大多数属于约束优化设计问题，其一般数学模型为：q 求解上式的方法称为约束优化方法。7/17/20247/17/20243 3首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q直接解法和间接解法q根据有约束优化问题求解方式的不同，可分为直接解法，间接解法。q直解解法通常适用于仅含不等式约束的问题，基本思路如右图所示。直接解法的搜索路线7/17/20247/17/20244 4首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院即在 个不等式约束条件所确定的可行域内，选择一个初始点 ，然后决定可行搜索方向 ，且以适当的步长 ，沿方向进行搜索，得到一个使目标函数值下降的可行的新点 ，即完成一次迭代。再以新点为起点，重复上述搜索过程，满足收敛条件后，迭代终止。7/17/20247/17/20245 5首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院每次迭代计算均按以下基本迭代格式进行：式中 步长；可行搜索方向。可行搜索方向是指，当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。产生可行搜索方向的方法将由直接解法中的各种算法决定。7/17/20247/17/20246 6首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院直接解法的原理简单，方法实用。其特点是：由于整个求解过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得一个比初始点好的设计点。若目标函数为凸函数，可行域为凸集，则可保证获得全域最优解。否则，因存在多个局部最优解，当选择的初始点不相同时，可能搜索到不同的局部最优解。因此，常在可行域内选择几个差别较大的初始点分别进行计算，以便从求得的多个局部最优解中选择更好的最优解。要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函数有定义。7/17/20247/17/20247 7首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院间接解法有不同的求解策略。其中一种方法的基本思路是将约束优化问题中的约束函数进行特殊的加权处理，然后和目标函数结合，构成一个新的目标函数，即将原约束优化问题转化成为一个或一系列的无约束优化问虬再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解。7/17/20247/17/20248 8首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院因此间接解法的基本迭代过程是，首先将一般约束优化问题转化成新的无约束目标函数 式中 转换后的新目标函数；分别为约束函数 和 经过加权处理后构成的某种形式的复合函数或泛函数；加权因子。然后对 进行无约束极小化计算。7/17/20247/17/20249 9首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院由于在新目标函数中包含了各种约束条件，而且在求极值的过程中还将改变加权因子的大小。因此可以不断地调整设计点，使其逐步逼近约束边界。从而间接地求得原约束问题的最优解。间接解法框图7/17/20247/17/20241010首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院间接解法例题求约束优化问题 的最优解。解:易知该问题理论上的最优解为：由该问题的几何意义（右图）可知，约束最优点 为目标函数等值线与等式约束函数（直线）的切点，7/17/20247/17/20241111首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院用间接解法求解时，可取 ，转换后的新目标函数为从而可以用解析法求 的极小值，即令 得到方程组7/17/20247/17/20241212首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院解此方程组，求得的无约束最优解为：右图表示出最优点 为新目标函数等值线族的中心。7/17/20247/17/20241313首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院间接解法是目前在机械优化设计中得到广泛应用的一种有效方法。其特点是：由于无约束优化方法的研究日趋成熟，已经研究出不少有效的无约束最优化方法和程序，使得间接解法有了可靠的基础。目前，这类算法的计算效率和数值计算的稳定性也都有较大的提高。可以有效地处理具有等式约束的约束优化问题。间接解法存在的主要问题是，选取加权因子较为困难。加权因子选取不当，不但影响收敛速度和计算精度，甚至会导致计算失败。7/17/20247/17/20241414首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院求解约束优化设计问题的方法：属于直接解法的随机方向法、复合形法、可行方向法、广义简约梯度法；属于间接解法的惩罚函数法，增广乘子法；另一类解法线性逼近方法，二次规划法。返回返回7/17/20247/17/20241515首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院6.2 随机方向法随机方向法q概述q随机方向法是一种原理简单的直接解法。q它的基本思路是在可行域内选择一个初始点，利用随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为可行搜索方向，记作 。从初始点 出发，沿 方向以一定的步长进行搜索，得到新点 ，新点 应满足约束条件：，q 且 。至此完成一次迭代。然后，将起始点移至 ，即令 。重复以上过程，经过若干次迭代计算后，最终取得约束最优解。7/17/20247/17/20241616首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院随机方向法的算法原理7/17/20247/17/20241717首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院随机方向法的的特点：对目标函数的性态无特殊要求，程序设计简单，使用方便。由于可行搜索方向是从许多髓机方向中选择的使目标函数下降最快的方向，加之步长还可以灵活变动，所以此算法的收敛速度比较快。若能取得一个较好的初始点，迭代次数可以大大减少。是求解小型的机械优化设计问题的一种十分有效的算法。7/17/20247/17/20241818首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q随机数的产生q在随机方向法中，为产生可行的初始点及随机方向，需要用到大量的 和 区间内均匀分布的随机数。q在计算机内，随机数通常是按一定的数学模型进行计算后得到的。这样得到的随机数称伪随机数，它的特点是产生速度快，计算机的内存占用少，并且有较好的概率统计特性。7/17/20247/17/20241919首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院产生伪随机数的方法很多，下面是一种常用的产生伪随机数的数学模型。首先令 ，取 （为小于 的正奇数），然后按以下步骤计算令 若 ，则 ；若 ，则 ；若 ，则 ；则 即为 区间内的伪随机数。利用 ，容易求得任意区间 内的伪随机数，其计算公式为7/17/20247/17/20242020首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q初始点的选择q随机方向法的初始点 必须是一个可行点，即满足全部不等式约束条件：q 的点。q当约束条件较为复杂，用人工不易选择可行初始点时，可用随机选择的方法来产生。其计算步骤如下：q输人设计变量的下限值和上限值，即7/17/20247/17/20242121首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.在区间 内产生 个伪随机数 。3.计算随机点x的各分量4.判别随机点 是否可行，若随机点 为可行点，则取初始点 ；若随机点 为非可行点，则转步骤2重新计算，直到产生的随机点是可行点为止。7/17/20247/17/20242222首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q可行搜索方向的产生q在随机方向法中，产生可行搜索方向的方法是从 个随机方向中，选取一个较好的方向。其计算步骤为：q在 区间内产生伪随机数q 再按下式计算随机单位向量7/17/20247/17/20242323首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.取一试验步长 ，按下式计算 个随机点3.显然，个随机点分布在以初始点 为中心，以试验步长 为半径的超球面上。4.检验 个随机点 是否为可行点，除去非可行点，计算余下的可行随机点的目标函数值，比较其大小，选出目标函数值最小的点 。5.比较 和 两点的目标函数值，若 ，则取 和 的连线方向作为可行搜索方向；若 ，则将步长 缩小，转步骤1重新计算，直至 为止。如果 缩小到很小，仍然找不到一个 ，使 则说明 是一个局部极小点，此时可更换初始点，转步骤1。7/17/20247/17/20242424首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院综上所述，产生可行搜索方向的条件可概括为，当 点满足 则可行搜索方向为7/17/20247/17/20242525首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q搜索步长的确定q可行搜索方向 确定后，初始点移至 点，即 ，从 点出发沿 方向进行搜索，所用的步长 一般按加速步长法来确定。q加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算：q 式中 步长加速系数，可取 ；q 步长，初始步长取 。7/17/20247/17/20242626首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q随机方向法的计算步骤q随机方向法的计算步骤如下：q选择一个可行的初始点 ；q产生 个 维随机单位向量 ；q取试验步长 ，计算出 个随机点 ；q在 个随机点中，找出的随机点 ，产生可行搜索方向 。q从初始点 出发，沿可行搜索方向 以步长 进行迭代计算，直至搜索到一个满足全部约束条件，且目标函数值不再下降的新点 。7/17/20247/17/20242727首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院6.若收敛条件7.8.得到满足，迭代终止。约束最优解为9.。否则，令 转步骤2。7/17/20247/17/20242828首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院随机方向法的程序框图（P126）返回返回7/17/20247/17/20242929首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院6.3 复合形法复合形法q概述q复合形法的基本思路：q在可行域内构造一个具有是个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数值最大的顶点（称最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。7/17/20247/17/20243030首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院复合形法的特点由于复合形的形状不必保持规则的图形，对目标函数及约束函数的性状又无特殊要求，因此该法的适应性较强，在机械优化设计中得到广泛应用。初始复合形的形成初始复合形必须在可行域内生成（复合形的k个顶点必须都是可行点）生成初始复合形的方法由设计者自行决定k个初始点，构成初始复合形在设计变量较少、约束函数简单情况下适用。7/17/20247/17/20243131首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.由设计者选定一个可行点，其余的(k-1)个可行点用随机法产生3.顶点坐标的计算4.式中 复合形中的第 j 个顶点；5.设计变量的下限和上限；6.在(0，1)区间内的伪随机数。7.上式计算得到的(k-1)个随机点不一定都在可行域内，因此需要将非可行点移到可行域内。8.可以采用这样的方法：9.首先求出已经在可行域内的L个顶点的中心 xc7/17/20247/17/20243232首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院然后将非可行点向中心点移动若xL+1仍为不可行点，可以利用上式继续向中心点移动。只要中心点可行，xL+1点一定可以移到可行域内。(k-1)个点经过这样的处理后，全部成为可行点，并构成初始复合形。7/17/20247/17/20243333首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院只要可行域为凸集，其中心点必为可行点，用以上方法可以成功地在可行域内构成初始复合形。如果可行域为非凸集（如下图所示），中心点不一定在可行域之内。此时可以通过改变设计变量的下限和上限值，重新产生各顶点，并经过多次试算，就有可能在可行域内生成初始复合形。7/17/20247/17/20243434首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院3.由计算机自动生成初始复合形的全部顶点4.其方法是首先随机产生一个可行点，然后按第二种方法产生其余的(k-1)个可行点。这种方法对设计者来说最为简单，但因初始复合形在可行域内的位置不能控制，可能会给以后的计算带来困难。5.复合形法的搜索方法6.在可行域内生成初始复合形后，需要采用不同的搜索方法来改变其形状，使复合形逐步向约束最优点趋近。7/17/20247/17/20243535首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院改变复合形形状的搜索方法如下：反射反射是改变复合形形状的一种主要策略，其计算步骤为：计算复合形各顶点的目标函数值，并比较其大小，求出最好点xL、最坏点xH及次坏点xG7/17/20247/17/20243636首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.计算除去最坏点xH外的(k-1)个顶点的中心xc3.从统计的观点来看，一般情况下，最坏点xH和中心点xc的连线方向为目标函数下降的方向。可以以xc点为中心，将最坏点xH按一定比例进行反射，有希望找到一个比最坏点xH的目标函数值为小的新点xR（反射点）。4.式中 反射系数，一般取 。7/17/20247/17/20243737首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院4.判别反射点xR的位置：5.若xR为可行点，则比较xR和xH两点的目标函数值，6.如果 ，则用xR取代xH，构成新的复合形，完成一次迭代；7.如果 ，则将 缩小0.7倍，重新计算新的反射点，若仍不可行，继续缩小，直至 为止。8.若xR为非可行点，则将 缩小0.7倍，计算反射点xR，直至可行为止。9.然后重复以上步骤，即判别 和 的大小，一旦 ，就用xR取代xH完成一次迭代。7/17/20247/17/20243838首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院综上所述，反射成功的条件是：扩张当求得的反射点xR为可行点，且目标函数值下降较多，则沿反射方向继续移动，即采用扩张的方法，可能找到更好的新点xE，xE称为扩张点。其计算公式为 式中 扩张系数，一般取 。7/17/20247/17/20243939首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院若扩张点xE为可行点，且 ，则称扩张成功，用xE取代xR，构成新的复合形。否则称扩张失败，放弃扩张，仍用原反射点xR 取代xH，构成新的复合形。7/17/20247/17/20244040首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院3.收缩4.若在中心点xc以外找不到好的反射点，可以在xc以内，即采用收缩的方法寻找较好的新点xk，xk称为收缩点。5.其计算公式为 6.式中 收缩系数，一般取 。7.若 ，则收缩成功，用xk取代xH，构成新的复合形。7/17/20247/17/20244141首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院4.压缩5.若采用上述各种方法均无效，可以采取将复合形各顶点向最好点xL靠拢，采用压缩的方法来改变复合形的形状。压缩后的各顶点的计算公式为6.然后，再对压缩后的复合形采用反射、扩张或收缩等方法，继续改变复合形的形状。7/17/20247/17/20244242首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院还何以采用旋转等方法来改变复合形形状。采用改变复合形形状的方法越多，程序设计越复杂，可能降低计算效率及可靠性。在进行优化方法的程序设计时，需要针对具体情况采用某些有效的方法。7/17/20247/17/20244343首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q复合形法的计算步骤q基本的复合形法（只含有“反射”）的计算步骤为：q选择复合形的顶点数k，一般取n+1k2n，在可行域内构成具有k个顶点的初始复合形。q计算复合形各顶点的目标函数值，比较其大小，找出最好点xL、最坏点xH及次坏点xG。q计算除去最坏点xH以外的(k1)个顶点的中心xc并判别是否可行，若xc为可行点，则转步骤4；若xc为非可行点，则重新确定设计变量的下限和上限值，即令 q 然后转步骤1，重新构造初始复合形。7/17/20247/17/20244444首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院4.计算反射点xR，必要时改变反射系数 的值，直至反射成功。然后以xR取代xH，构成新的复合形。5.若收敛条件6.得到满足，计算终止。约束最优解为：7.否则，转步骤2。7/17/20247/17/20244545首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院复合形法的程序框图（P131）返回返回7/17/20247/17/20244646首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院6.4 可行方向法可行方向法q概述q约束优化问题的直接解法中，可行方向法是最大的一类，它也是求解大型约束优化问题的主要方法之一。q可行方向法的基本原理是在可行域内选择一个初始点 ，当确定了一个可行方向d和适当的步长后，按下式q 进行迭代计算。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。7/17/20247/17/20244747首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q可行方向法的搜索策略q可行方向法的第一步迭代都是从可行的初始点 出发，沿 点的负梯度方向 将初始点移动到某一个约束面（只有一个起作用的约束时）上或约束面的交集（有几个起作用的约束时）上。然后根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索：7/17/20247/17/20244848首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院7/17/20247/17/20244949首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.第二种情况如右图，沿可行方向 作一维搜索，所得到的新点 在可行域外，则设法将 点移动到约束面上，即取 和约束面的交点作为新的迭代点 。7/17/20247/17/20245050首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院3.第三种情况是沿约束面搜索4.对于只具有线性约束条件的非线性规划问题（如右图所示），从 点出发，沿约束面移动，在有限的几步内即可搜索到约束最优点；7/17/20247/17/20245151首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院对于非线性约束函数（如右图），沿约束面移动将会进入非可行域，因此需将进入非可行域的新点 设法调整到约束面上，然后才能进行下一次迭代。7/17/20247/17/20245252首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院调整的方法是先规定约束面容差 ，建立新的约束边界，然后将已离开约束面的 点，沿起作用约束函数的负梯度方向 返回到约束面上。其计算公式为 式中的 称为调整步长，可用试探法决定，或用下式估算7/17/20247/17/20245353首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q产生可行方向的条件q可行方向是指沿该方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。因此，可行方向应满足可行和下降两个条件。q可行条件q可行条件是指将某点沿可行方向作微小移动后，所得到的新点为可行点需满足的条件。7/17/20247/17/20245454首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院如右图，若 点在一个约束面上，过 点作约束面 的切线 ，显然满足可行条件的方向 应与起作用的约束函数在 点的梯度 的夹角大于或等于90。用向量关系式可表示为：7/17/20247/17/20245555首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院若 点在 个约束面的交集上（如右图所示），为保证方向 可行，要求 和 个约束函数在点的梯度 的夹角均大于等于90。则其向量关系可表示为7/17/20247/17/20245656首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.下降条件3.可行方向的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。7/17/20247/17/20245757首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院如右图所示，满足下降条件的方向 应和目标函数在 点的梯度 的夹角大于90。其向量关系可表示为7/17/20247/17/20245858首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院满足可行和下降条件（如右图所示），它位于约束曲面在 点的切线和目标函数等值线在 点的切线所围成的扇形区内，该扇形区称为可行下降方向区。7/17/20247/17/20245959首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院综上所述，当 点位于 个起作用的约束面上时，满足 的方向 称可行方向。7/17/20247/17/20246060首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q可行方向的产生方法q满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向，其方法主要有优选方向法和梯度投影法两种。q优选方向法q要求在可行下降扇形区内选择一个能使目标函数下降最快的方向作为迭代的方向，这可以看作是一个以搜索方向 为设计变量的约束优化问题。7/17/20247/17/20246161首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院这个新的约束优化问题的数学模型可写成：由于 和 为定值，上述各函数均为设计变量 的线性函数，采用线性规划的方法求解后，求得的最优解 即为本次迭代的可行方向，即 。7/17/20247/17/20246262首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.梯度投影法3.当 点目标函数的负梯度方向 不满足可行条件时，可将 方向投影到约束面（或约束面的交集）上，得到投影向量 （如下图所示），该投影向量显然满足方向的可行和下降条件。7/17/20247/17/20246363首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院梯度投影法就是取该方向作为本次迭代的可行方向。可行方向的计算公式为 式中 点的目标函数梯度；投影算子，为 阶矩阵 式中 单位矩阵，阶矩阵；起作用约束函数的梯度矩阵，阶矩阵；式中 起作用的约束函数个数。7/17/20247/17/20246464首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q步长的确定q可行方向 确定后，按下式计算新的迭代点q 但是由于目标函数及约束函数的性状不同，步长 的确定方法也不同，不论是用何种方法，都应使新的迭代点 为可行点，且目标函数具有最大的下降量。7/17/20247/17/20246565首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院确定步长 的常用方法有以下两种：取最优步长如右图所示，从 点出发，沿 方向进行一维搜索，取得最优步长 ，计算新点x的值若新点x为可行点，则本次迭代的步长取7/17/20247/17/20246666首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.取到约束边界的最大步长3.如右图所示，从 点沿 方向进行一维搜索，得到的新点 为不可行点，则应改变步长，使新点 返回到约束面上来。使新点 恰好位于约束面上的步长称为最大步长，记作 。则本次迭代的步长取 7/17/20247/17/20246767首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院由于实际上 的确定较为困难，可按以下步骤计算取一试验步长 ，计算试验点 。试验步长的值不能太大，以免因一步走得太远导致计算困难；也不能太小，使得计算效率太低。根据经验，试验步长 的值能使试验点 的目标函数值下降510，即 将目标函数 在 点展开成泰勒级数的线性式 则 7/17/20247/17/20246868首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院由此可得试验步长 计算公式因 为目标函数的下降方向，所以试验步长 恒为正值。试验步长选定后，试验点 按下式计算7/17/20247/17/20246969首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.判别试验点 的位置3.由试验步长 确定的试验点 可能在约束面上，也可能在可行域或非可行域。只要 不在约束面上，就要设法将其调整到约束面上来。要想使 到达约束面 是很困难的。为此，先确定一个约束允差 。当试验点xt满足4.若试验点 位于非可行域，则转步骤3。5.若试验点 位于可行域内，则应沿 方向以步长 继续向前搜索，直至新的试验点 到达约束面或越出可行域，再转步骤3。7/17/20247/17/20247070首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院3.将位于非可行域的试验点 调整到约束面上。4.若试验点 位于右图所示的位置，在 点处：5.显然应将 点调整到 的约束面上，因为对于 点来说，的约束违反量比 大。若设 为约束违反量最大的约束条件，则应满足约束违反量最大的约束条件7/17/20247/17/20247171首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院将试验点 调整到 的约束面上的方法有试探法和插值法两种。试探法的基本内容是当试验点位于非可行域时，将试验步长 缩短；当试验点位于可行域时，将试验步长 增加，即不断变化 的大小，直至满足允差条件时，即认为试验点 已被调整到约束面上了。7/17/20247/17/20247272首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.插值法是利用线性插值将位于非可行域的试验点 调整到约束面上。设试验步长为 时，求得可行试验点3.当试验步长为 时，求得非可行试验点4.并设试验点 和 的约束函数分别为7/17/20247/17/20247373首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院它们之间的位置关系如右图所示。若考虑约束允差 ，并按允差中心 作线性内插，可以得到将 点调整到约束面上的步长 。其计算公式为：本次迭代的步长取为7/17/20247/17/20247474首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q收敛条件 q按可行方向法的原理，将设计点调整到约束面上后，需要判断迭代是否收敛，即判断该迭代点是否为约束最优点。常用的收敛条件有以下两种：q设计点 及约束允差满足q 条件时，迭代收敛。7/17/20247/17/20247575首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.设计点 满足库恩塔克条件3.时，迭代收敛。4.可行方向法的计算步骤5.在可行域内选择一个初始点 ，给出约束允差 及收敛精度值 。6.令迭代次数 ，第一次迭代的搜索方向取 7.。8.估算试验步长 ，计算试验点 。7/17/20247/17/20247676首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院4.若试验点 满足 ，点必位于第 个约束面上，则转步骤6；若试验点 位于可行域内，则加大试验步长 ，重新计算新的试验点，直至 越出可出域，再转步骤5；若试验点位于非可行域，则直接转步骤5。5.确定约束违反量最大的约束函数 。用插值法计算调整步长 ，使试验点 返回到约束面上，则完成一次迭代。再令 ，转下步。6.在新的设计点 处产生新的可行方向 。7/17/20247/17/20247777首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院7.若 点满足收敛条件，则计算终止。约束最优解为 8.否则，改变允差 的值，即令9.再转步骤2。7/17/20247/17/20247878首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院可行方向法的程序框图返回返回7/17/20247/17/20247979首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院6.5 惩罚函数法惩罚函数法q概述q惩罚函数法（SUMT）是一种间接解法。把约束引入原函数无约束优化方法“惩罚”：给予无约束极值求解过程中企图违反约束的那些迭代点以很大的函数值，而子问题的目的是极小化目标函数，这样迫使无约束优化子问题的极小点趋于满足约束条件。重复地产生和求解一系列这样的子问题，它们的解在极限情况下趋向于原约束优化问题的约束极小值。7/17/20247/17/20248080首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院基本原理：将约束优化问题 中的不等式和等式约束函数经过加权转化后，和原目标函数结合成新的目标函数惩罚函数。求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。7/17/20247/17/20248181首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院这种方法按一定的法则改变加权因子 和 的值，构成一系列的无约束优化问题，求得一系列的无约束最优解，并不断地逼近原约束优化问题的最优解。惩罚函数中 和 称为加权转化项。根据它们在惩罚函数中的作用，又分别称为障碍项和惩罚项。障碍项的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可行域。惩罚项的作用是当迭代点在非可行域或不满足等式约夷条件时，在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。7/17/20247/17/20248282首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院根据迭代过程是否在可行域内进行，惩罚函数法又可分为内点惩罚函数法，外点惩罚函数法和混合惩罚函数法三种。7/17/20247/17/20248383首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q内点惩罚函数法（内点法）q特点：将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。q内点法只能用来求解具有不等式约束的优化问题。q对于只具有不等式约束的优化问题q转化后的惩罚函数形式为q 或7/17/20247/17/20248484首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院式中 惩罚因子，它是由大到小且趋近于0的数列，即 。或 障碍项。由于内点法的迭代过程在可行域内进行，障碍项的作用是阻止迭代点越出可行域。由障碍项的函数形式可知，当迭代点靠近某一约束边界时，其值趋近于0，而障碍项的值陡然增加，并趋近于无穷大，好象在可行域的边界上筑起了一道“围墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。7/17/20247/17/20248585首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院内点法中初始点 惩罚因子的初值 及其缩减系数c等重要参数的选取和收敛条件的确定初始点 的选取使用内点法时，初始点 应选择一个离约束边界较远的可行点。若 太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难。惩罚因子初值 的选取惩罚因子的初值 应适当，否则会影响迭代计算的正常进行。太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。对于不同的问题，都要经过试算取 ，根据试算的结果，决定增加或减小 的值。7/17/20247/17/20248686首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院2.按经验公式3.计算 值。4.惩罚因子的缩减系数c的选取5.在构造序列惩罚函数时，惩罚因子 是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为6.式中的c称为惩罚因子的缩减系数，c为小于1的正数。通常的取值范围在0.10.7之间。7/17/20247/17/20248787首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院4.收敛条件5.内点法的收敛条件为6.前式说明相邻两次迭代的惩罚函数的值相对变化量充分小，后式说明相邻两次迭代的无约束极小点已充分接近。满足收敛条件的无约束极小点 已逼近原问题的约束最优点，迭代终止。7/17/20247/17/20248888首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院内点法的计算步骤为：选取可行的初始点 ，惩罚因子的初值 ，缩减系数c以及收敛精度 。令迭代次数 。构造惩罚函数 ，选择适当的无约束优化方法，求函数 的无约束极值，得 点。判别迭代是否收敛，若满足收敛条件，迭代终止。约束最优解为 否则令 ，转步骤2。7/17/20247/17/20248989首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院内点法的程序框图（P144）7/17/20247/17/20249090首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q外点惩罚函数法（外点法）q这种方法和内点法相反。新目标函数定义在可行域之外，序列迭代点从可行域之外逐渐逼近约束边界上的最优点。q外点法可以求解含不等式、等式约束的优化问题。q对于约束优化问题q 7/17/20247/17/20249191首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院转化后的外点惩罚函数的形式为式中 惩罚因子，它是由小到大且趋近于 的数列，即 ；分别为对应于不等式约束和等式约束函数的惩罚项。7/17/20247/17/20249292首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院由于外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项的形式可知，当迭代点x不可行时，惩罚项的值大于0，使得惩罚函数 大于原目标函数。当迭代点离约束边界愈远，惩罚项的值愈大。但当迭代点不断接近约束边界和等式约束曲面时，惩罚项的值减小，且趋近于0，惩罚项的作用逐渐消失，迭代点也就趋近于约束边界上的最优点。7/17/20247/17/20249393首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院外点法中惩罚因子的确定外点法的惩罚因子按下式递增 式中 c 递增系数，通常取510。与内点法相反，惩罚因子的初值 若取相当大的值。会使惩罚函数的等值线变形或偏心，求 的极值将发生困难，但 取得过小，势必增加迭代次数。通常取 可以取得满意的结果。7/17/20247/17/20249494首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院有时也可以按下面的经验公式来计算 式中7/17/20247/17/20249595首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q混合惩罚函数法q混合惩罚函数法简称混合法。这种方法把内点法和外点法结合起来，用来求解同时具有等式约束和不等式约束函数的优化问题。q对于约束优化问题7/17/20247/17/20249696首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院转化之后混合函数的形式为式中 障碍项，惩罚因子r按内点法选取，即 。惩罚项，惩罚因子为 ，当 时，满足外点法对惩罚因子的要求。7/17/20247/17/20249797首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院混合法具有内点法的求解特点，即迭代过程在可行域内进行，因而初始点 x0，惩罚因子的初值 r0 均可按照内点法选取。7/17/20247/17/20249898首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院q例子：对于约束优化问题 q1）、用内点法构造惩罚函数的一般表达形式并且确定一个初始点 。q2）、若第K次迭代时,得无约束极小点 ,试用外点法写出下一次迭代时惩罚函数的一般表达形式。7/17/20247/17/20249999首页上页下页末页结束机械与材料学院机械与材料学院机械与材料学院机械与材料学院1）用内点法构造惩罚函数如下：其中：初始点必须是可行域内的点，即满足 和 例如：2）如果 ，则由于 ，所以，外点法构造下一次迭代时的惩罚函数如下：其中：7/17/20247/17/2024