第五章约束优化方法课件

章章章章约约束束束束优优化方法化方法化方法化方法约约束束束束优优化方法概述化方法概述化方法概述化方法概述 在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。一、约束优化问题的类型 根据约束条件类型的不同可以分为三种，其数学模型分别如下：1、不等式约束优化问题（IP型）2 2、等式约束优化问题（、等式约束优化问题（、等式约束优化问题（、等式约束优化问题（EPEP型）型）型）型）3 3、一般约束优化问题（、一般约束优化问题（、一般约束优化问题（、一般约束优化问题（GPGP型）型）型）型）二、约束优化方法的分类二、约束优化方法的分类约束优化方法按求解原理的不同可以分为约束优化方法按求解原理的不同可以分为直接法和间接法两类。直接法和间接法两类。1、直接法、直接法 只能求解不等式约束优化问题的最优只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。约束坐标轮换法、复合形法等。基本要点：选取初始点、确定搜索方基本要点：选取初始点、确定搜索方向及适当步长。向及适当步长。搜索原则：每次产生的迭代点必须满搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。足可行性与适用性两个条件。适用性：当前迭代点的目标函数值较前一点是下降的，即满适用性：当前迭代点的目标函数值较前一点是下降的，即满 F(xk+1)o，则，则称称gi(x)为可行点的不起作用约束。即只有为可行点的不起作用约束。即只有在可行域的边界上的点才有起作用约束，所在可行域的边界上的点才有起作用约束，所有约束对可行域内部的点都是不起作用约束。有约束对可行域内部的点都是不起作用约束。对于等式约束，凡是满足该约束的任对于等式约束，凡是满足该约束的任一可行点，该等式约束都是起作用约束。一可行点，该等式约束都是起作用约束。2 2、在可行设计点、在可行设计点、在可行设计点、在可行设计点x(k)x(k)处，处，处，处，起作用约束在该点的邻域内不起作用约束在该点的邻域内不起作用约束在该点的邻域内不起作用约束在该点的邻域内不但起限制可行域范围的作用，而且还可以提供可行搜索方但起限制可行域范围的作用，而且还可以提供可行搜索方但起限制可行域范围的作用，而且还可以提供可行搜索方但起限制可行域范围的作用，而且还可以提供可行搜索方向的信息。向的信息。向的信息。向的信息。3 3、由于约束最优点一般发生在起作用约束上，不起作用、由于约束最优点一般发生在起作用约束上，不起作用、由于约束最优点一般发生在起作用约束上，不起作用、由于约束最优点一般发生在起作用约束上，不起作用约束在求解最优点的过程中，可以认为是无任何影响，所约束在求解最优点的过程中，可以认为是无任何影响，所约束在求解最优点的过程中，可以认为是无任何影响，所约束在求解最优点的过程中，可以认为是无任何影响，所以可以略去不起作用约束，把所有起作用约束当作等式约以可以略去不起作用约束，把所有起作用约束当作等式约以可以略去不起作用约束，把所有起作用约束当作等式约以可以略去不起作用约束，把所有起作用约束当作等式约束问题求解最优点。束问题求解最优点。束问题求解最优点。束问题求解最优点。1 1、约束优化问题的最优解不仅与目标函数有关，而且与、约束优化问题的最优解不仅与目标函数有关，而且与、约束优化问题的最优解不仅与目标函数有关，而且与、约束优化问题的最优解不仅与目标函数有关，而且与约束集合的性质有关。约束集合的性质有关。约束集合的性质有关。约束集合的性质有关。5.2 5.2 约束优化问题极小点的条件约束优化问题极小点的条件约束优化问题极小点的条件约束优化问题极小点的条件 约束优化问题极小点的条件，是指在满足约束优化问题极小点的条件，是指在满足约束优化问题极小点的条件，是指在满足约束优化问题极小点的条件，是指在满足约束条件下，目标函数局部极小点的存在条件。约束条件下，目标函数局部极小点的存在条件。约束条件下，目标函数局部极小点的存在条件。约束条件下，目标函数局部极小点的存在条件。约束问题最优解的存在条件有两种：一是约束问题最优解的存在条件有两种：一是约束问题最优解的存在条件有两种：一是约束问题最优解的存在条件有两种：一是极小点在可行域内部，二是极小点在可行域的一极小点在可行域内部，二是极小点在可行域的一极小点在可行域内部，二是极小点在可行域的一极小点在可行域内部，二是极小点在可行域的一个或几个边界交汇处。个或几个边界交汇处。个或几个边界交汇处。个或几个边界交汇处。5.2.1 5.2.1 不等式约束问题解的必要条件不等式约束问题解的必要条件不等式约束问题解的必要条件不等式约束问题解的必要条件 第一种情况：如图所示，第一种情况：如图所示，第一种情况：如图所示，第一种情况：如图所示，g1(x*)=0 g1(x*)=0，g2(x*)0g2(x*)0，g3(x*)0 g3(x*)0。所以。所以。所以。所以g1(x)g1(x)为起作用约束，为起作用约束，为起作用约束，为起作用约束，g2(x)g2(x)、g3(x)g3(x)为不起作用约束。为不起作用约束。为不起作用约束。为不起作用约束。由于约束最优点是目标函数与约束由于约束最优点是目标函数与约束由于约束最优点是目标函数与约束由于约束最优点是目标函数与约束g1(x)g1(x)边边边边界的切点，故目标函数与约束函数的梯度必共线，界的切点，故目标函数与约束函数的梯度必共线，界的切点，故目标函数与约束函数的梯度必共线，界的切点，故目标函数与约束函数的梯度必共线，而且方向一致。而且方向一致。而且方向一致。而且方向一致。若取非负乘子若取非负乘子 1*1*0 0，则在，则在x*x*处存在如下关系处存在如下关系 F(x*)-F(x*)-1*1*g1(x*)=0 g1(x*)=0 x*g1(x*)g3(x)F(x*)g1(x)g2(x)第二种情况：如图所示，若最优点位于两约束的交第二种情况：如图所示，若最优点位于两约束的交第二种情况：如图所示，若最优点位于两约束的交第二种情况：如图所示，若最优点位于两约束的交点上，则目标函数的梯度矢量夹于两约束函数梯度矢量点上，则目标函数的梯度矢量夹于两约束函数梯度矢量点上，则目标函数的梯度矢量夹于两约束函数梯度矢量点上，则目标函数的梯度矢量夹于两约束函数梯度矢量之间。则目标函数的梯度可以表示为约束函数梯度的线之间。则目标函数的梯度可以表示为约束函数梯度的线之间。则目标函数的梯度可以表示为约束函数梯度的线之间。则目标函数的梯度可以表示为约束函数梯度的线性组合，若取非负乘子性组合，若取非负乘子性组合，若取非负乘子性组合，若取非负乘子 1*1*0 0，2*2*0 0，则在，则在，则在，则在x*x*处存处存处存处存在如下关系在如下关系在如下关系在如下关系 F(x*)=F(x*)=1*1*g1(x*)+g1(x*)+2*2*g2(x*)g2(x*)g1(x*)g2(x*)g2(x)g1(x)F(x*)结论：结论：结论：结论：对于不等式约束优化问题，其最优解的必要对于不等式约束优化问题，其最优解的必要对于不等式约束优化问题，其最优解的必要对于不等式约束优化问题，其最优解的必要条件为条件为条件为条件为 5.2.2 5.2.2 等式约束问题解的必要条件等式约束问题解的必要条件等式约束问题解的必要条件等式约束问题解的必要条件 如图所示，目标函数梯度矢量与约束函数梯度矢如图所示，目标函数梯度矢量与约束函数梯度矢如图所示，目标函数梯度矢量与约束函数梯度矢如图所示，目标函数梯度矢量与约束函数梯度矢量共线。因此，一定存在一个乘子，使得下式成量共线。因此，一定存在一个乘子，使得下式成量共线。因此，一定存在一个乘子，使得下式成量共线。因此，一定存在一个乘子，使得下式成立：立：立：立：F(x*)-F(x*)-*h(x*)=0 h(x*)=0 对于一般等式约束优化问题，其最优解必要条对于一般等式约束优化问题，其最优解必要条对于一般等式约束优化问题，其最优解必要条对于一般等式约束优化问题，其最优解必要条件为件为件为件为x*h(x)=0 F(x*)h(x*)5.2.3 一般约束问题解的必要条件一般约束问题解的必要条件 由上述不等式约束优化与等式约束优化问题解的必要由上述不等式约束优化与等式约束优化问题解的必要条件，可以推出一般约束优化问题最优解的条件：条件，可以推出一般约束优化问题最优解的条件：5.2.4 5.2.4 库恩库恩库恩库恩-塔克条件塔克条件塔克条件塔克条件 为判断可行迭代点为判断可行迭代点为判断可行迭代点为判断可行迭代点x(k)x(k)是否是约束最优点，是否是约束最优点，是否是约束最优点，是否是约束最优点，或者对输出的可行结果进行检查，观察其是否满或者对输出的可行结果进行检查，观察其是否满或者对输出的可行结果进行检查，观察其是否满或者对输出的可行结果进行检查，观察其是否满足约束最优解的必要条件，引入库恩足约束最优解的必要条件，引入库恩足约束最优解的必要条件，引入库恩足约束最优解的必要条件，引入库恩-塔克条件。塔克条件。塔克条件。塔克条件。u v u v称为拉格朗日乘子称为拉格朗日乘子称为拉格朗日乘子称为拉格朗日乘子 上式也称为约束优化问题局部最优点的必要条上式也称为约束优化问题局部最优点的必要条上式也称为约束优化问题局部最优点的必要条上式也称为约束优化问题局部最优点的必要条件。件。件。件。在迭代点在迭代点 处展开式的形式为处展开式的形式为一般情况下，其作用约束数一般情况下，其作用约束数J J不大于问题的维数不大于问题的维数其中其中 是待定系数矢量是待定系数矢量解上式，得一组解上式，得一组j j（j=1j=1，2J2J），如果），如果j j（j=1j=1，2J2J）均为非负，标志）均为非负，标志 满足满足K-TK-T条件。该条件条件。该条件是是 为极小点的必要条件。为极小点的必要条件。如果点如果点 是最优点，则必须满足是最优点，则必须满足K-TK-T条件；条件；反之，满足反之，满足K-TK-T条件的点则不一定是约束最优点。条件的点则不一定是约束最优点。只有当目标函数是凸函数，约束构成的可行域是凸集只有当目标函数是凸函数，约束构成的可行域是凸集时，则满足时，则满足K-TK-T条件的点条件的点 是全局极小点的必要而充是全局极小点的必要而充分条件。分条件。例题例题例题例题5.1 5.1 设约束优化问题设约束优化问题设约束优化问题设约束优化问题D D：它的当前迭代点为它的当前迭代点为 ，试用，试用K-TK-T条件判别它条件判别它是否为约束最优点。是否为约束最优点。解：解：解：解：计算计算计算计算 点的诸约束函数值点的诸约束函数值点的诸约束函数值点的诸约束函数值 点的起作用约束是点的起作用约束是点的起作用约束是点的起作用约束是求求求求 点的诸梯度点的诸梯度点的诸梯度点的诸梯度求拉格朗日乘子求拉格朗日乘子求拉格朗日乘子求拉格朗日乘子按按K-TK-T条件应有条件应有写成线性方程组写成线性方程组解得解得乘子均为非负，乘子均为非负，满足约束最优解一阶必要条件满足约束最优解一阶必要条件5.3.1 5.3.1 约约约约束坐束坐束坐束坐标轮换标轮换标轮换标轮换法法法法一、约束坐标轮换法与无约束坐标轮换法的区别一、约束坐标轮换法与无约束坐标轮换法的区别一、约束坐标轮换法与无约束坐标轮换法的区别一、约束坐标轮换法与无约束坐标轮换法的区别 约束坐标轮换法的基本思想与无约束坐约束坐标轮换法的基本思想与无约束坐约束坐标轮换法的基本思想与无约束坐约束坐标轮换法的基本思想与无约束坐标轮换法基本相同，其主要区别如下：标轮换法基本相同，其主要区别如下：标轮换法基本相同，其主要区别如下：标轮换法基本相同，其主要区别如下：1 1、沿坐标方向搜索的迭代步长采用加速、沿坐标方向搜索的迭代步长采用加速、沿坐标方向搜索的迭代步长采用加速、沿坐标方向搜索的迭代步长采用加速步长，而不是采用最优步长。因为按照最优步步长，而不是采用最优步长。因为按照最优步步长，而不是采用最优步长。因为按照最优步步长，而不是采用最优步长。因为按照最优步长所得到的迭代点往往超出了可行域。长所得到的迭代点往往超出了可行域。长所得到的迭代点往往超出了可行域。长所得到的迭代点往往超出了可行域。2 2、对于每一个迭代点，不仅要检查目标、对于每一个迭代点，不仅要检查目标、对于每一个迭代点，不仅要检查目标、对于每一个迭代点，不仅要检查目标函数值是否下降，而且必须检查是否在可行域函数值是否下降，而且必须检查是否在可行域函数值是否下降，而且必须检查是否在可行域函数值是否下降，而且必须检查是否在可行域内，即进行适用性和可行性的检查。内，即进行适用性和可行性的检查。内，即进行适用性和可行性的检查。内，即进行适用性和可行性的检查。5.3 5.3 常用约束优化方法常用约束优化方法约束坐标轮换法约束坐标轮换法一一一一 方法概要述方法概要述方法概要述方法概要述首先在可行域首先在可行域D D内任取内任取一初始点一初始点 ，并取迭代，并取迭代精度精度。以以 为起点，取一个适为起点，取一个适当的初步步长当的初步步长 按迭代式按迭代式取得沿取得沿x1x1坐标轴正向的第一个迭代点坐标轴正向的第一个迭代点 ，检查该点的，检查该点的适用性和可行性，即检查适用性和可行性，即检查如果两者均满足，则步长加倍如果两者均满足，则步长加倍再按迭代式再按迭代式获得沿获得沿x1x1正向的第二个迭代点正向的第二个迭代点 。下面的各次迭代，只。下面的各次迭代，只要对新迭代点的适用性和可行性的检查都通过，再倍增步要对新迭代点的适用性和可行性的检查都通过，再倍增步长后按迭代式长后按迭代式不断产生新迭代点不断产生新迭代点但是，当迭代点到达但是，当迭代点到达 时，该点已违反了可行性条件，时，该点已违反了可行性条件，于是返回到前一迭代点于是返回到前一迭代点 作为沿作为沿e1e1方向搜索的终点方向搜索的终点 。转而改沿转而改沿x2x2坐标轴正向进行搜索。在图示情况下，正向坐标轴正向进行搜索。在图示情况下，正向的第一个迭代点目标函数值增加，即不再满足适用性条的第一个迭代点目标函数值增加，即不再满足适用性条件，故改取该坐标轴的反方向，并取步长件，故改取该坐标轴的反方向，并取步长 进行进行迭代，迭代，以后的迭代方向与前述的相同，以加速步长继续迭代，以后的迭代方向与前述的相同，以加速步长继续迭代，直到至少违反适用性与可行性条件之一时，可确定沿直到至少违反适用性与可行性条件之一时，可确定沿e2e2方向的迭代终点方向的迭代终点 。如此反复的进行各坐标轴方向的迭代，点列将逐步逼近如此反复的进行各坐标轴方向的迭代，点列将逐步逼近最优点最优点x*x*。当迭代点到达当迭代点到达 ，如出现下面的情况：，如出现下面的情况：不论沿不论沿e1e1或或e2e2正、反方向以步长正、反方向以步长 进行搜索，所得进行搜索，所得 邻近的四个点邻近的四个点 当他们都不能同时满足当他们都不能同时满足适用性和可行性条件时，此适用性和可行性条件时，此 即可作为约束最优点输出。即可作为约束最优点输出。如果要获得精度更高些的解，还可以缩减初始步长如果要获得精度更高些的解，还可以缩减初始步长 。后在继续迭代，直至。后在继续迭代，直至 时，才输出最优时，才输出最优点，并停止计算。点，并停止计算。约束坐标轮换法算法约束坐标轮换法算法约束坐标轮换法算法约束坐标轮换法算法明了、迭代简单、便明了、迭代简单、便明了、迭代简单、便明了、迭代简单、便于掌握和运用。但是于掌握和运用。但是于掌握和运用。但是于掌握和运用。但是其收敛速度较慢，而其收敛速度较慢，而其收敛速度较慢，而其收敛速度较慢，而且在某些情况下，会且在某些情况下，会且在某些情况下，会且在某些情况下，会出现出现出现出现“死点死点死点死点”。如上图。如上图。如上图。如上图中的点中的点中的点中的点 xk xk，该点已经，该点已经，该点已经，该点已经逼近约束边界，其后逼近约束边界，其后逼近约束边界，其后逼近约束边界，其后的迭代点无论沿何方的迭代点无论沿何方的迭代点无论沿何方的迭代点无论沿何方向，都不可能同时满向，都不可能同时满向，都不可能同时满向，都不可能同时满足适用性及可行性的足适用性及可行性的足适用性及可行性的足适用性及可行性的要求。故要求。故要求。故要求。故xkxk点作为最点作为最点作为最点作为最优解输出，但显然它优解输出，但显然它优解输出，但显然它优解输出，但显然它就是一个伪最优点。就是一个伪最优点。就是一个伪最优点。就是一个伪最优点。为辨别输出最优为辨别输出最优为辨别输出最优为辨别输出最优点的真伪，可以用点的真伪，可以用点的真伪，可以用点的真伪，可以用K-TK-T条件检验。条件检验。条件检验。条件检验。5.3.2 约束随机方向法约束随机方向法参看右图参看右图预先选定可行初始点预先选定可行初始点 ，利用随机函数构成随机方利用随机函数构成随机方向向S1S1，按给定的初始步长，按给定的初始步长 ，沿，沿S1S1方向取得方向取得试探点试探点检查检查x x点的适用性和可行性点的适用性和可行性若满足若满足 继续按下面的迭代式在继续按下面的迭代式在S1S1方向上获取新点。重复上方向上获取新点。重复上述步骤，迭代点可沿述步骤，迭代点可沿S1S1方向前进。直至到达某迭代点不方向前进。直至到达某迭代点不能同时满足适用性和可行性条件时结束。退回到前一点能同时满足适用性和可行性条件时结束。退回到前一点作为该方向搜索中的最终成功点，记作作为该方向搜索中的最终成功点，记作 。转而，将转而，将 作为新的起点作为新的起点 再产生另一随机再产生另一随机方向方向S2S2，以步长，以步长 重复以上过程，得到沿重复以上过程，得到沿S2S2方向的方向的最终成功点最终成功点 。如此循环，点列必将逼近于约束最优点。如此循环，点列必将逼近于约束最优点x*x*。5.3.3 5.3.3 复合形法复合形法复合形法复合形法 复合形法是求解约束优化问题的一种重要的直接解法。复合形法是求解约束优化问题的一种重要的直接解法。一、复合形法的基本思想一、复合形法的基本思想 基本思路是在可行域内构造一个具有基本思路是在可行域内构造一个具有k k个顶点的初始复个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点目标函数值下降的可行的新点,并用此点代替最坏点，构并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最成新的复合形，复合形就向最优点移动一步，直至逼近最优点。优点。二、初始复合形的构成二、初始复合形的构成二、初始复合形的构成二、初始复合形的构成 要构成初始复合形，实际上就是确定要构成初始复合形，实际上就是确定要构成初始复合形，实际上就是确定要构成初始复合形，实际上就是确定k k个可个可个可个可行点作为复合形的顶点，顶点数目一般在行点作为复合形的顶点，顶点数目一般在行点作为复合形的顶点，顶点数目一般在行点作为复合形的顶点，顶点数目一般在n+1 n+1 k k 2n 2n范围内。对于维数较低的优化问题，范围内。对于维数较低的优化问题，范围内。对于维数较低的优化问题，范围内。对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行因顶点数目较少，可以由设计者自行凑出可行因顶点数目较少，可以由设计者自行凑出可行因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问点作为复合形顶点。但对于维数较高的优化问点作为复合形顶点。但对于维数较高的优化问点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。题，这种方法常常很困难。题，这种方法常常很困难。题，这种方法常常很困难。为此，提出构成复合形的随机方法。该方为此，提出构成复合形的随机方法。该方为此，提出构成复合形的随机方法。该方为此，提出构成复合形的随机方法。该方法是先产生法是先产生法是先产生法是先产生k k个随机点，然后再把那些非可行个随机点，然后再把那些非可行个随机点，然后再把那些非可行个随机点，然后再把那些非可行随机点调入可行域内，最终使随机点调入可行域内，最终使随机点调入可行域内，最终使随机点调入可行域内，最终使k k个随机点都成个随机点都成个随机点都成个随机点都成为可行点而构成初始复合形。为可行点而构成初始复合形。为可行点而构成初始复合形。为可行点而构成初始复合形。构成复合形的随机方法：构成复合形的随机方法：构成复合形的随机方法：构成复合形的随机方法：1 1、产生、产生、产生、产生k k个随机点个随机点个随机点个随机点 利用标准随机函数产生在（利用标准随机函数产生在（利用标准随机函数产生在（利用标准随机函数产生在（0 0，1 1）区间内均匀）区间内均匀）区间内均匀）区间内均匀分布的随机数分布的随机数分布的随机数分布的随机数i i，然后产生区间（，然后产生区间（，然后产生区间（，然后产生区间（aiai，bibi）内的随）内的随）内的随）内的随机变量机变量机变量机变量xixi，xi=ai+xi=ai+i i（bi-aibi-ai），），），），i=1i=1，2 2，n n。以这以这以这以这n n个随机变量为坐标构成随机点个随机变量为坐标构成随机点个随机变量为坐标构成随机点个随机变量为坐标构成随机点x,x,第一个点记作第一个点记作第一个点记作第一个点记作x(i)x(i)同理，再次产生在（同理，再次产生在（同理，再次产生在（同理，再次产生在（0 0，1 1）区间内均匀分布的）区间内均匀分布的）区间内均匀分布的）区间内均匀分布的随机数随机数随机数随机数i i，然后获得区间（，然后获得区间（，然后获得区间（，然后获得区间（aiai，bibi）内的随机点）内的随机点）内的随机点）内的随机点x x(2)(2)，依次类推，可以获得，依次类推，可以获得，依次类推，可以获得，依次类推，可以获得k k个随机点个随机点个随机点个随机点 x(1)x(1)、x(2)x(2)、x(3)x(3)、.、x(k)x(k)。可以看出，产生可以看出，产生可以看出，产生可以看出，产生k k个随机点总共需要产生个随机点总共需要产生个随机点总共需要产生个随机点总共需要产生k kn n个随机数。个随机数。个随机数。个随机数。2、将非可行点移入可行域、将非可行点移入可行域 用上述方法的随机点不一定是可行点。但是只要它们中用上述方法的随机点不一定是可行点。但是只要它们中至少有一个点在可行域内，就可以用一定的方法将非可行点至少有一个点在可行域内，就可以用一定的方法将非可行点移入可行域。如果移入可行域。如果k个随机点没有一个是可行点，则应重新个随机点没有一个是可行点，则应重新产生随机点，直至其中有至少一个是可行点为止。产生随机点，直至其中有至少一个是可行点为止。将非可行点移入可行域的方法：将非可行点移入可行域的方法：依次检查随机点依次检查随机点x(1)、x(2)、x(3)、.、x(k)的可的可行性。将查出的第一个可行点行性。将查出的第一个可行点x(j)与与x(1)对调，则新的对调，则新的x(1)点为可行点，然后检查随后的各点是否是可行点，若某点属点为可行点，然后检查随后的各点是否是可行点，若某点属于可行域，继续检查，直至出现不属于可行域的随机点，然于可行域，继续检查，直至出现不属于可行域的随机点，然后把此点移入可行域内。后把此点移入可行域内。若已知若已知k个随机顶点中前面个随机顶点中前面q个点都是可行个点都是可行点，而点，而x(q+1)为非可行点，则将为非可行点，则将x(q+1)移入可移入可行域的步骤为：行域的步骤为：(1)计算计算q个点的点集中心个点的点集中心x(s).(2)将第将第q+1个点朝个点朝x(s)点方向移动，并按下式点方向移动，并按下式产生新的点产生新的点 x(p)=x(s)+0.5(x(q+1)-x(s)此点实际上是此点实际上是x(s)与与x(q+1)两点的连线的中两点的连线的中点。若新点仍为非可行点，则按上式再产生一点。若新点仍为非可行点，则按上式再产生一个新点，直至个新点，直至 x(p)成为可行点为止。成为可行点为止。将非可行点调入可行域将非可行点调入可行域 3 3、构成初始复合形、构成初始复合形、构成初始复合形、构成初始复合形 将全部顶点变为可行点后，就构成了可行域将全部顶点变为可行点后，就构成了可行域将全部顶点变为可行点后，就构成了可行域将全部顶点变为可行点后，就构成了可行域内的初始复合形。内的初始复合形。内的初始复合形。内的初始复合形。三、复合形法的迭代步骤三、复合形法的迭代步骤三、复合形法的迭代步骤三、复合形法的迭代步骤 1 1、构成初始复合形、构成初始复合形、构成初始复合形、构成初始复合形 2 2、计算、计算、计算、计算k k个顶点函数值个顶点函数值个顶点函数值个顶点函数值F(x(j),j=1,2,kF(x(j),j=1,2,k，并选出，并选出，并选出，并选出好点好点好点好点x(L)x(L)与坏点与坏点与坏点与坏点x(H)x(H)。x(L):F(x(L)=minF(x(j),j=1,2,k x(L):F(x(L)=minF(x(j),j=1,2,k x(H):F(x(H)=maxF(x(j),j=1,2,k x(H):F(x(H)=maxF(x(j),j=1,2,k 3 3、计算除坏点外其余各点的中心点、计算除坏点外其余各点的中心点、计算除坏点外其余各点的中心点、计算除坏点外其余各点的中心点x0,x0,4 4、计算映射点、计算映射点、计算映射点、计算映射点x(R)x(R)=x0+x(R)x(R)=x0+(x0-x(H)(x0-x(H)通常取通常取通常取通常取=1.3=1.3，检查，检查，检查，检查x(R)x(R)是否在可行域，若为非是否在可行域，若为非是否在可行域，若为非是否在可行域，若为非可行点，将映射系数缩半并重新计算映射点，直可行点，将映射系数缩半并重新计算映射点，直可行点，将映射系数缩半并重新计算映射点，直可行点，将映射系数缩半并重新计算映射点，直到进入可行域。到进入可行域。到进入可行域。到进入可行域。5 5、构成新复合形、构成新复合形、构成新复合形、构成新复合形 计算映射点与坏点的目标函数值并进行比较，计算映射点与坏点的目标函数值并进行比较，计算映射点与坏点的目标函数值并进行比较，计算映射点与坏点的目标函数值并进行比较，若：若：若：若：（1 1）映射点优于坏点，即）映射点优于坏点，即）映射点优于坏点，即）映射点优于坏点，即F(x(R)F(x(H)F(x(R)F(x(H)F(x(R)F(x(H)，可，可，可，可用缩半映射系数的方法把映射点拉近。用缩半映射系数的方法把映射点拉近。用缩半映射系数的方法把映射点拉近。用缩半映射系数的方法把映射点拉近。但也有可能经过多次但也有可能经过多次但也有可能经过多次但也有可能经过多次的减半的减半的减半的减半,直到小于直到小于直到小于直到小于给定的很小正数时仍不能使映射点优于坏点给定的很小正数时仍不能使映射点优于坏点给定的很小正数时仍不能使映射点优于坏点给定的很小正数时仍不能使映射点优于坏点,则说则说则说则说明该映射方向不利明该映射方向不利明该映射方向不利明该映射方向不利.改变映射方向改变映射方向改变映射方向改变映射方向,取对次坏点取对次坏点取对次坏点取对次坏点 x(SH):F(x(SH)=maxF(x(j),j=1,2,k,jH x(SH):F(x(SH)=maxF(x(j),j=1,2,k,jH 的映射的映射的映射的映射.确定不包括确定不包括确定不包括确定不包括x(SH)x(SH)在内的复合形顶点中心在内的复合形顶点中心在内的复合形顶点中心在内的复合形顶点中心,并以此为映射轴心并以此为映射轴心并以此为映射轴心并以此为映射轴心,计算计算计算计算x(SH)x(SH)的影射点的影射点的影射点的影射点x(R)x(R)x(R)=x0+x(R)=x0+(x0-x(SH)(x0-x(SH)6、判定终止条件、判定终止条件 复合形在逼近最优点的过程中，当复合形缩得很小时，复合形在逼近最优点的过程中，当复合形缩得很小时，各顶点的目标函数值必然非常接近。故常用以下终止条件。各顶点的目标函数值必然非常接近。故常用以下终止条件。（1）各顶点与好点的函数值之差的均方根小于误差限，即）各顶点与好点的函数值之差的均方根小于误差限，即（2）各顶点与好点的函数值之差的平方和小于误差限，即）各顶点与好点的函数值之差的平方和小于误差限，即3 3）各顶点与好点的函数值之差的绝对值之和小于误差限，）各顶点与好点的函数值之差的绝对值之和小于误差限，即即若不满足终止条件，返回步骤若不满足终止条件，返回步骤2 2，否则，可将复合形得好点，否则，可将复合形得好点及其函数值作为最优解输出。及其函数值作为最优解输出。四、讨论四、讨论四、讨论四、讨论 在用直接法解决约束优化问题时，复合形法在用直接法解决约束优化问题时，复合形法在用直接法解决约束优化问题时，复合形法在用直接法解决约束优化问题时，复合形法是一种效果较好的方法。是一种效果较好的方法。是一种效果较好的方法。是一种效果较好的方法。这种方法不需要计算目标函数的导数，也不这种方法不需要计算目标函数的导数，也不这种方法不需要计算目标函数的导数，也不这种方法不需要计算目标函数的导数，也不进行一维搜索，因此对目标函数和约束函数无特进行一维搜索，因此对目标函数和约束函数无特进行一维搜索，因此对目标函数和约束函数无特进行一维搜索，因此对目标函数和约束函数无特殊要求，适用范围广，编程简单。但是收敛速度殊要求，适用范围广，编程简单。但是收敛速度殊要求，适用范围广，编程简单。但是收敛速度殊要求，适用范围广，编程简单。但是收敛速度较慢，不能用于解决具有等式约束的优化问题。较慢，不能用于解决具有等式约束的优化问题。较慢，不能用于解决具有等式约束的优化问题。较慢，不能用于解决具有等式约束的优化问题。5.3.4 惩罚函数法惩罚函数法简介惩罚函数法简介内点法内点法外点法外点法混合法混合法总结总结惩罚惩罚函数法函数法函数法函数法简简介介介介 惩罚函数法是一种使用很广泛、很有效的间接法。惩罚函数法是一种使用很广泛、很有效的间接法。基本原理：基本原理：把约束优化问题转化成无约束优化问题来求解。把约束优化问题转化成无约束优化问题来求解。两个前提条件：两个前提条件：一是不破坏原约束的约束条件一是不破坏原约束的约束条件二是最优解必须归结到原约束二是最优解必须归结到原约束问题的最优解上去问题的最优解上去按照惩罚函数的构成方式，惩罚函数法分为三种：按照惩罚函数的构成方式，惩罚函数法分为三种：外点法、内点法、混合法外点法、内点法、混合法惩罚项惩罚项惩罚项惩罚项r(k)r(k)、m(k)-m(k)-罚因子罚因子罚因子罚因子惩罚函数惩罚函数惩罚函数惩罚函数内点法内点法引例引例引例引例 设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型D：由图可见，目标函数的可行域为由图可见，目标函数的可行域为xbxb，在可行域内目标函数，在可行域内目标函数单调上升，它的最优解显然是单调上升，它的最优解显然是x*=b ，F*=ab对引例的惩罚函数进行分析，以对内点法有初步认识：对引例的惩罚函数进行分析，以对内点法有初步认识：本问题是不等式约束优化问题，故只有一项惩罚项本问题是不等式约束优化问题，故只有一项惩罚项本问题是不等式约束优化问题，故只有一项惩罚项本问题是不等式约束优化问题，故只有一项惩罚项 ，一个罚因子，一个罚因子，一个罚因子，一个罚因子规定罚因子规定罚因子规定罚因子规定罚因子 为某一正数，当迭代点是在可行域内为某一正数，当迭代点是在可行域内为某一正数，当迭代点是在可行域内为某一正数，当迭代点是在可行域内时，则惩罚项的值必为正值，因此必有时，则惩罚项的值必为正值，因此必有时，则惩罚项的值必为正值，因此必有时，则惩罚项的值必为正值，因此必有而且，当x越趋近于约束边界时，由于惩罚项增大，所以罚函数 的值越大。当xb时，罚函数的值将趋近于+。因此，当初始点取在可行域内，求函数 的极小值时，只要适当控制搜索步长，防止迭代点跨入非可行域，则所搜索到的无约束极小点x*必可保持在可行域内。若对于罚因子的取值由初始的若对于罚因子的取值由初始的若对于罚因子的取值由初始的若对于罚因子的取值由初始的 逐渐变小逐渐变小逐渐变小逐渐变小 时，惩罚函数时，惩罚函数时，惩罚函数时，惩罚函数 愈逼近与原目标函数愈逼近与原目标函数愈逼近与原目标函数愈逼近与原目标函数F F（x x），罚），罚），罚），罚函数曲线越来越接近于原函数曲线越来越接近于原函数曲线越来越接近于原函数曲线越来越接近于原F F（x x）=ax=ax直线，如上页图，对直线，如上页图，对直线，如上页图，对直线，如上页图，对应罚函数应罚函数应罚函数应罚函数 的最优点列的最优点列的最优点列的最优点列 不断趋近于原约不断趋近于原约不断趋近于原约不断趋近于原约束优化问题的最优点束优化问题的最优点束优化问题的最优点束优化问题的最优点x*=bx*=b内点罚数法的形式及特点内点罚数法的形式及特点内点罚数法的形式及特点内点罚数法的形式及特点具有不等式约束的优化问题的数学模型具有不等式约束的优化问题的数学模型具有不等式约束的优化问题的数学模型具有不等式约束的优化问题的数学模型u=1，2，p构造如下形式的内点罚函数构造如下形式的内点罚函数构造如下形式的内点罚函数构造如下形式的内点罚函数D：关于惩罚因子规定为正，即关于惩罚因子规定为正，即 。且在优化过程中。且在优化过程中 是减小的，为确保为递减数列，取常数是减小的，为确保为递减数列，取常数C C0C1称系数称系数C C为罚因子降低系数为罚因子降低系数=0或关于惩罚项关于惩罚项 ，由于在可行域内有，由于在可行域内有 ，且且 永远取正值，故在可行域内惩罚项永为正。永远取正值，故在可行域内惩罚项永为正。的的值越小则惩罚项的值越小。值越小则惩罚项的值越小。由于在约束边界上有由于在约束边界上有 ，因此，当设计点趋，因此，当设计点趋于边界时，惩罚项的值将趋于无穷大。由此可知，在可于边界时，惩罚项的值将趋于无穷大。由此可知，在可行域内，始终有行域内，始终有 。当当 时时 ，却有，却有 ，所以整个最，所以整个最优化的实质就是用罚函数优化的实质就是用罚函数 去逼近原目标函数去逼近原目标函数F(x);F(x);当设计点逐渐由内部趋近于边界时，由于惩罚项无穷当设计点逐渐由内部趋近于边界时，由于惩罚项无穷增大，则称罚函数也将无穷增大。增大，则称罚函数也将无穷增大。从函数图形上来看，犹如在可行域的边界上筑起一从函数图形上来看，犹如在可行域的边界上筑起一道陡峭的高墙，使迭代点自动保持在可行域内，用此办道陡峭的高墙，使迭代点自动保持在可行域内，用此办法来保证搜索过程自始至终不离开可行域。所以，内点法法来保证搜索过程自始至终不离开可行域。所以，内点法也常称为围墙函数法。也常称为围墙函数法。内点罚函数法的求解过程内点罚函数法的求解过程内点罚函数法的求解过程内点罚函数法的求解过程 为了用惩罚函数为了用惩罚函数 去逼近原目标函数去逼近原目标函数F(x)F(x)，则要用，则要用F(x)F(x)及及 构造一个无约束优化问题的数学模型构造一个无约束优化问题的数学模型 选取初始点（原约束优化问题的内点）选取初始点（原约束优化问题的内点），初始罚因，初始罚因子子 ，罚因子降低系数，罚因子降低系数C C。用无约束优化方法求上式无。用无约束优化方法求上式无约束优化问题的最优解。约束优化问题的最优解。所得解为所得解为 ；当；当k k在增大的过程中，得到惩罚函数的无在增大的过程中，得到惩罚函数的无约束最优点列为约束最优点列为点列中各点均在可行域内部，随着点列中各点均在可行域内部，随着kk的过程，的过程，点列将趋近于原约束问题的最优解点列将趋近于原约束问题的最优解x*x*。即。即=x*由此可知，内点法的序列无约束最优点由此可知，内点法的序列无约束最优点 是在可行域内是在可行域内部且趋近于约束最优点部且趋近于约束最优点x*x*的。的。内点罚函数还可以按如下形式构成内点罚函数还可以按如下形式构成初始点初始点初始点初始点x(0)x(0)的选取的选取的选取的选取 由于内点法的搜索是在可行域内进行，显然初始点必须由于内点法的搜索是在可行域内进行，显然初始点必须是域内可行点。须满足是域内可行点。须满足有两种方法有两种方法有两种方法有两种方法自定法。即根据设计者的经验或已有的计算资料自行决自定法。即根据设计者的经验或已有的计算资料自行决自定法。即根据设计者的经验或已有的计算资料自行决自定法。即根据设计者的经验或已有的计算资料自行决定某一可行点作为初始点。定某一可行点作为初始点。定某一可行点作为初始点。定某一可行点作为初始点。搜索法。任选一个设计点搜索法。任选一个设计点搜索法。任选一个设计点搜索法。任选一个设计点 为初始点。通过对初始点为初始点。通过对初始点为初始点。通过对初始点为初始点。通过对初始点约束函数值的检验，按其对每个约束的不满足程度加以调约束函数值的检验，按其对每个约束的不满足程度加以调约束函数值的检验，按其对每个约束的不满足程度加以调约束函数值的检验，按其对每个约束的不满足程度加以调整，将整，将整，将整，将 点逐步引入到可行域内，成为可行初始点，这点逐步引入到可行域内，成为可行初始点，这点逐步引入到可行域内，成为可行初始点，这点逐步引入到可行域内，成为可行初始点，这就是搜索法。就是搜索法。就是搜索法。就是搜索法。u=1，2，p关于几个参数的选择关于几个参数的选择关于几个参数的选择关于几个参数的选择初始罚因子初始罚因子初始罚因子初始罚因子r(0)r(0)的选取的选取的选取的选取 如果如果 值选得太大，则在一开始罚函数的惩罚项的值将值选得太大，则在一开始罚函数的惩罚项的值将远远超出原目标函数的值，因此，它的第一次无约束极小点远远超出原目标函数的值，因此，它的第一次无约束极小点将远离原问题的约束最优点。在以后的迭代中，需要很长时将远离原问题的约束最优点。在以后的迭代中，需要很长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。如果如果 值选得太小，则在一开始惩罚项的作用甚小，而值选得太小，则在一开始惩罚项的作用甚小，而在可行域内部惩罚函数在可行域内部惩罚函数 与原目标函数与原目标函数F(x)F(x)很相近，很相近，只在约束边界附近罚函数值才突然增高。这样，使其罚函数只在约束边界附近罚函数值才突然增高。这样，使其罚函数在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。如下图，对于有深沟谷地性态差的函数，不仅搜索所需的如下图，对于有深沟谷地性态差的函数，不仅搜索所需的时间长，而且很难使迭代点进入最优的邻域，以致极易使时间长，而且很难使迭代点进入最优的邻域，以致极易使迭代点落入非可行域而导致计算的失败。迭代点落入非可行域而导致计算的失败。r（0）=150或或递减系数递减系数递减系数递减系数C C的选择的选择的选择的选择 罚因子递减系数罚因子递减系数C C的选择，一般认为对算法的成败影响的选择，一般认为对算法的成败影响不大。规定不大。规定0C10C1。若若C C值选得较小，罚因子下降快，可以减少无约束优化值选得较小，罚因子下降快，可以减少无约束优化的次数，但因前后两次无约束最优点之间的距离较远，有的次数，但因前后两次无约束最优点之间的距离较远，有可能使后一次无约束优化本身的迭代次数增多，而且使序可能使后一次无约束优化本身的迭代次数增多，而且使序列最优点的间隔加大，这就对约束最优点的逼近不利。列最优点的间隔加大，这就对约束最优点的逼近不利。相反，若相反，若C C值取得较大，则无约束优化次数就要增多。值取得较大，则无约束优化次数就要增多。通常建议取通常建议取通常建议取通常建议取C=0.10.5C=0.10.5终止准则终止准则终止准则终止准则 随着罚因子随着罚因子 的值不断减小，罚函数的序列无约束最的值不断减小，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。优点将越来越趋近于原约束优化问题的最优点。设惩罚函数设惩罚函数 的无约束最优点列为的无约束最优点列为对应的罚函数值为对应的罚函数值为终止准则可用下述两者之一终止准则可用下述两者之一终止准则可用下述两者之一终止准则可用下述两者之一相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。设设11为收敛精度，一般取为收敛精度，一般取1=10-410-51=10-410-5，则需要满足，则需要满足相邻两次惩罚函数值得相对变化量已足够小。相邻两次惩罚函数值得相对变化量已足够小。相邻两次惩罚函数值得相对变化量已足够小。相邻两次惩罚函数值得相对变化量已足够小。设设22为收敛精度，一般取为收敛精度，一般取2=10-310-42=10-310-4，则需要满足，则需要满足算法步骤算法步骤算法步骤算法步骤构造内点惩罚函数构造内点惩罚函数选择可行初始点选择可行初始点 ，初始罚因子，初始罚因子 ，罚因子降低系，罚因子降低系数数C C，收敛精度，收敛精度 与与 ，置，置k0k0求无约束优化问题，求无约束优化问题，有最优点有最优点 。当当k=0k=0时转步骤时转步骤，否则转步骤，否则转步骤置置kk+1kk+1，并转步骤，并转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤，否则转，否则转 ,输出最优解输出最优解(x*,F*)(x*,F*)内点罚函数的特点内点罚函数的特点内点罚函数的特点内点罚函数的特点 内点法只适用于解不等式约束优化问题。由于内点法内点法只适用于解不等式约束优化问题。由于内点法需要在可行域内部进行搜索，所以初始点必须在可行域需要在可行域内部进行搜索，所以初始点必须在可行域内部选取可行设计点。内部选取可行设计点。内点法的突出优点在于每个迭代点都是可行点内点法的突出优点在于每个迭代点都是可行点内点法的突出优点在于每个迭代点都是可行点内点法的突出优点在于每个迭代点都是可行点因此，当迭代达到一定阶段时，尽管尚没有达到最优点，因此，当迭代达到一定阶段时，尽管尚没有达到最优点，但也可以被接受为一个较好的近似解。但也可以被接受为一个较好的近似解。外点法外点法外点法可以解不等式约束优化问题或等式约束优化问题外点法可以解不等式约束优化问题或等式约束优化问题引例引例引例引例 设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型D：用外点法构造惩罚函数，具体构造形式如下用外点法构造惩罚函数，具体构造形式如下xbx1C1，并令，并令=惩罚项惩罚项的含义可用另一形式表示的含义可用另一形式表示当gu(x)0 （xD）当gu(x)0,r(0)0,罚因子递增系数罚因子递增系数C1C1 对于对于r(k)r(k)为某一值，同过对惩罚函数的无约束求优，可为某一值，同过对惩罚函数的无约束求优，可得最优点得最优点 。随着。随着k k的增大，得无约束最优点列的增大，得无约束最优点列在在kk的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点实线为原目标实线为原目标函数等值线函数等值线虚线为罚函数虚线为罚函数等值线等值线总结总结总结总结 由上图可见，两种等值线在可行域内部及边界上是重合由上图可见，两种等值线在可行域内部及边界上是重合的；而在非可行域中，罚函数的等值线升高了。即只有在的；而在非可行域中，罚函数的等值线升高了。即只有在可行域外部惩罚项才起到惩罚的作用。可行域外部惩罚项才起到惩罚的作用。r(k)r(k)值越大，惩罚作值越大，惩罚作用越大。用越大。由上由上b b图可知，在起作用约束边界处罚函数等值线变得越图可知，在起作用约束边界处罚函数等值线变得越密集和越陡峭。随密集和越陡峭。随r(k)r(k)的增大，最优点列将越接近于原约束的增大，最优点列将越接近于原约束优化问题的最优点优化问题的最优点x*x*。但须注意，近似的最优点是落在边。但须注意，近似的最优点是落在边界处非可行域一侧。界处非可行域一侧。外点法罚函数常用形式除上面介绍的两种，还有对几个问题的讨论对几个问题的讨论对几个问题的讨论对几个问题的讨论（1 1）初始点）初始点）初始点）初始点x(0)x(0)的选取的选取的选取的选取在可行域及非可行域内均可。在可行域及非可行域内均可。（2 2）初始罚因子）初始罚因子）初始罚因子）初始罚因子r(0)r(0)和递增系数和递增系数和递增系数和递增系数C C的选取的选取的选取的选取 选取过小，则序贯无约束求解的次数就增多，收敛速度选取过小，则序贯无约束求解的次数就增多，收敛速度慢；反之，则在非可行域中，罚函数比原目标函数要大得多，慢；反之，则在非可行域中，罚函数比原目标函数要大得多，特别在起作用约束边界处产生尖点，函数性态变坏，从而限特别在起作用约束边界处产生尖点，函数性态变坏，从而限制了某些无约束优化方法的使用，致使计算失败。制了某些无约束优化方法的使用，致使计算失败。C C的选取影响不大，通常的选取影响不大，通常C=510C=510（3 3）约束容差带）约束容差带）约束容差带）约束容差带 最优点在非可行域内，即位一个非可行点，这对某些工最优点在非可行域内，即位一个非可行点，这对某些工程是不允许的。因此，可在约束边界可行域一侧加一条容程是不允许的。因此，可在约束边界可行域一侧加一条容差带。差带。相当于将约束条件改为相当于将约束条件改为是容差量，通常是容差量，通常终止准则终止准则终止准则终止准则 随着罚因子随着罚因子 的值不断增大，罚函数的序列无约束最的值不断增大，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。优点将越来越趋近于原约束优化问题的最优点。设惩罚函数设惩罚函数 的无约束最优点列为的无约束最优点列为对应的罚函数值为对应的罚函数值为终止准则可用下述两者之一终止准则可用下述两者之一终止准则可用下述两者之一终止准则可用下述两者之一相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。设设11为收敛精度，一般取为收敛精度，一般取1=10-410-51=10-410-5，则需要满足，则需要满足相邻两次惩罚函数值得相对变化量已足够小。相邻两次惩罚函数值得相对变化量已足够小。相邻两次惩罚函数值得相对变化量已足够小。相邻两次惩罚函数值得相对变化量已足够小。设设22为收敛精度，一般取为收敛精度，一般取2=10-310-42=10-310-4，则需要满足，则需要满足求求 ，得最优点，得最优点当当k=0k=0时转步骤时转步骤，否则转步骤，否则转步骤置置kk+1kk+1，并转步骤，并转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤，否则转，否则转 ,输出最优解输出最优解(x*,F*)(x*,F*)，停止计，停止计算。算。算法步骤算法步骤算法步骤算法步骤在在n n维空间任取初始点维空间任取初始点x x（0 0）选取初始罚因子选取初始罚因子r(0),r(0),递增系数递增系数C C，并置，并置k0k0用外点罚函数法解等式约束优化问题用外点罚函数法解等式约束优化问题用外点罚函数法解等式约束优化问题用外点罚函数法解等式约束优化问题设有二维约束优化问题设有二维约束优化问题D：h1(x)=x1+x2-10=0h1(x)=x1+x2-10=0如右图，如右图，h1h1（x x）为该约束）为该约束问题的可行域，这条直线以问题的可行域，这