第五章-惩罚函数法课件.ppt

5.3.4 5.3.4 惩罚函数法惩罚函数法惩罚函数法简介惩罚函数法简介内点法内点法外点法外点法混合法混合法总结总结惩罚函数法简介惩罚函数法简介 惩罚函数法是一种使用很广泛、很有效的间接法。惩罚函数法是一种使用很广泛、很有效的间接法。基本原理：基本原理：基本原理：基本原理：把约束优化问题转化成无约束优化问题来求解。把约束优化问题转化成无约束优化问题来求解。把约束优化问题转化成无约束优化问题来求解。把约束优化问题转化成无约束优化问题来求解。两个前提条件：两个前提条件：两个前提条件：两个前提条件：一是不破坏原约束的约束条件一是不破坏原约束的约束条件一是不破坏原约束的约束条件一是不破坏原约束的约束条件二是最优解必须归结到原约束问题的最优解上去二是最优解必须归结到原约束问题的最优解上去二是最优解必须归结到原约束问题的最优解上去二是最优解必须归结到原约束问题的最优解上去按照惩罚函数的构成方式，惩罚函数法分为三种：按照惩罚函数的构成方式，惩罚函数法分为三种：按照惩罚函数的构成方式，惩罚函数法分为三种：按照惩罚函数的构成方式，惩罚函数法分为三种：外点法、内点法、混合法外点法、内点法、混合法外点法、内点法、混合法外点法、内点法、混合法惩罚项惩罚项惩罚项惩罚项r r r r(k)(k)(k)(k)、m m m m(k)(k)(k)(k)-罚因子罚因子罚因子罚因子惩罚函数惩罚函数惩罚函数惩罚函数由图可见，目标函数的可行域为由图可见，目标函数的可行域为由图可见，目标函数的可行域为由图可见，目标函数的可行域为xbxbxbxb，在可行域内目标函数，在可行域内目标函数，在可行域内目标函数，在可行域内目标函数单调上升，它的最优解显然是单调上升，它的最优解显然是单调上升，它的最优解显然是单调上升，它的最优解显然是x x*=b=b，F F*=ab=ab对引例的惩罚函数进行分析，以对内点法有初步认识：对引例的惩罚函数进行分析，以对内点法有初步认识：对引例的惩罚函数进行分析，以对内点法有初步认识：对引例的惩罚函数进行分析，以对内点法有初步认识：本问题是不等式约束优化问题，故只有一项惩罚项本问题是不等式约束优化问题，故只有一项惩罚项本问题是不等式约束优化问题，故只有一项惩罚项本问题是不等式约束优化问题，故只有一项惩罚项 ，一个罚因子，一个罚因子，一个罚因子，一个罚因子规定罚因子规定罚因子规定罚因子规定罚因子 为某一正数，当迭代点是在可行域内为某一正数，当迭代点是在可行域内为某一正数，当迭代点是在可行域内为某一正数，当迭代点是在可行域内时，则惩罚项的值必为正值，因此必有时，则惩罚项的值必为正值，因此必有时，则惩罚项的值必为正值，因此必有时，则惩罚项的值必为正值，因此必有而且，当而且，当x x越趋近于约束边界时，由于惩罚项越趋近于约束边界时，由于惩罚项增大，所以罚函数增大，所以罚函数 的值越大。当的值越大。当xbxb时，罚函时，罚函数的值将趋近于数的值将趋近于+。因此，当初始点取在可行域内，求。因此，当初始点取在可行域内，求函数函数 的极小值时，只要适当控制搜索步长，的极小值时，只要适当控制搜索步长，防止迭代点跨入非可行域，则所搜索到的无约束极小点防止迭代点跨入非可行域，则所搜索到的无约束极小点x*x*必可保持在可行域内。必可保持在可行域内。若对于罚因子的取值由初始的若对于罚因子的取值由初始的 逐渐变小逐渐变小 时，惩罚函数时，惩罚函数 愈逼近于原目标函数愈逼近于原目标函数F F（x x），罚），罚函数曲线越来越接近于原函数曲线越来越接近于原F F（x x）=ax=ax直线，如图所示，对直线，如图所示，对应罚函数应罚函数 的最优点列的最优点列 不断趋近于原约不断趋近于原约束优化问题的最优点束优化问题的最优点x*=bx*=b小结小结小结小结 由以上可见，如果选择一个可行点作初由以上可见，如果选择一个可行点作初始点始点 ，令其罚因子，令其罚因子 由大变小，由大变小，通过求罚函数通过求罚函数 的一系列最优点，的一系列最优点，显见，无约束最优点序列将逐渐趋近于原约显见，无约束最优点序列将逐渐趋近于原约束优化问题的最优点束优化问题的最优点x x*。关于惩罚因子规定为正，即关于惩罚因子规定为正，即关于惩罚因子规定为正，即关于惩罚因子规定为正，即 。且在优化过程中。且在优化过程中。且在优化过程中。且在优化过程中 是减小的，为确保为递减数列，取常数是减小的，为确保为递减数列，取常数是减小的，为确保为递减数列，取常数是减小的，为确保为递减数列，取常数C C C C0C10C1称系数称系数称系数称系数C C C C为为为为罚因子降低系数罚因子降低系数罚因子降低系数罚因子降低系数=0=0或或关于惩罚项关于惩罚项关于惩罚项关于惩罚项 ，由于在可行域内有，由于在可行域内有，由于在可行域内有，由于在可行域内有 ，且且且且 永远取正值，故在可行域内惩罚项永为正。永远取正值，故在可行域内惩罚项永为正。永远取正值，故在可行域内惩罚项永为正。永远取正值，故在可行域内惩罚项永为正。的值越小则惩罚项的值越小。的值越小则惩罚项的值越小。的值越小则惩罚项的值越小。的值越小则惩罚项的值越小。内点罚函数法的求解过程内点罚函数法的求解过程内点罚函数法的求解过程内点罚函数法的求解过程 为了用惩罚函数为了用惩罚函数为了用惩罚函数为了用惩罚函数 去逼近原目标函数去逼近原目标函数去逼近原目标函数去逼近原目标函数F(x)F(x)F(x)F(x)，则要用则要用则要用则要用F(x)F(x)F(x)F(x)及及及及 构造一个无约束优化问题的数学模型构造一个无约束优化问题的数学模型构造一个无约束优化问题的数学模型构造一个无约束优化问题的数学模型 选取初始点（原约束优化问题的内点）选取初始点（原约束优化问题的内点）选取初始点（原约束优化问题的内点）选取初始点（原约束优化问题的内点），初始罚，初始罚，初始罚，初始罚因子因子因子因子 ，罚因子降低系数，罚因子降低系数，罚因子降低系数，罚因子降低系数C C C C。用无约束优化方法求上式无。用无约束优化方法求上式无。用无约束优化方法求上式无。用无约束优化方法求上式无约束优化问题的最优解。约束优化问题的最优解。约束优化问题的最优解。约束优化问题的最优解。初始点初始点初始点初始点x x x x(0)(0)(0)(0)的选取的选取的选取的选取 由于内点法的搜索是在可行域内进行，显然初始点必须由于内点法的搜索是在可行域内进行，显然初始点必须由于内点法的搜索是在可行域内进行，显然初始点必须由于内点法的搜索是在可行域内进行，显然初始点必须是域内可行点。须满足是域内可行点。须满足是域内可行点。须满足是域内可行点。须满足确定初始点常用如下两种方法确定初始点常用如下两种方法确定初始点常用如下两种方法确定初始点常用如下两种方法自定法自定法自定法自定法 即根据设计者的经验或已有的计算资料自行决即根据设计者的经验或已有的计算资料自行决即根据设计者的经验或已有的计算资料自行决即根据设计者的经验或已有的计算资料自行决定某一可行点作为初始点。定某一可行点作为初始点。定某一可行点作为初始点。定某一可行点作为初始点。搜索法搜索法搜索法搜索法 任选一个设计点任选一个设计点任选一个设计点任选一个设计点 为初始点。通过对初始点为初始点。通过对初始点为初始点。通过对初始点为初始点。通过对初始点约束函数值的检验，按其对每个约束的不满足程度加以调约束函数值的检验，按其对每个约束的不满足程度加以调约束函数值的检验，按其对每个约束的不满足程度加以调约束函数值的检验，按其对每个约束的不满足程度加以调整，将整，将整，将整，将 点逐步引入到可行域内，成为可行初始点，点逐步引入到可行域内，成为可行初始点，点逐步引入到可行域内，成为可行初始点，点逐步引入到可行域内，成为可行初始点，这就是搜索法。这就是搜索法。这就是搜索法。这就是搜索法。关于几个参数的选择关于几个参数的选择关于几个参数的选择关于几个参数的选择初始罚因子初始罚因子初始罚因子初始罚因子r r r r(0)(0)(0)(0)的选取的选取的选取的选取 如果如果如果如果 值选得值选得值选得值选得太大太大太大太大，则在一开始罚函数的惩罚项的，则在一开始罚函数的惩罚项的，则在一开始罚函数的惩罚项的，则在一开始罚函数的惩罚项的值将远远超出原目标函数的值，因此，它的第一次无约束极值将远远超出原目标函数的值，因此，它的第一次无约束极值将远远超出原目标函数的值，因此，它的第一次无约束极值将远远超出原目标函数的值，因此，它的第一次无约束极小点将远离原问题的约束最优点。在以后的迭代中，需要很小点将远离原问题的约束最优点。在以后的迭代中，需要很小点将远离原问题的约束最优点。在以后的迭代中，需要很小点将远离原问题的约束最优点。在以后的迭代中，需要很长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。如果如果如果如果 值选得值选得值选得值选得太小太小太小太小，则在一开始惩罚项的作用甚小，则在一开始惩罚项的作用甚小，则在一开始惩罚项的作用甚小，则在一开始惩罚项的作用甚小，而在可行域内部惩罚函数而在可行域内部惩罚函数而在可行域内部惩罚函数而在可行域内部惩罚函数 与原目标函数与原目标函数与原目标函数与原目标函数F(x)F(x)F(x)F(x)很相近，很相近，很相近，很相近，只在约束边界附近罚函数值才突然增高。这样，使其罚函数只在约束边界附近罚函数值才突然增高。这样，使其罚函数只在约束边界附近罚函数值才突然增高。这样，使其罚函数只在约束边界附近罚函数值才突然增高。这样，使其罚函数在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。如下图，对于有深沟谷地性态差的函数，不仅搜索所需的如下图，对于有深沟谷地性态差的函数，不仅搜索所需的如下图，对于有深沟谷地性态差的函数，不仅搜索所需的如下图，对于有深沟谷地性态差的函数，不仅搜索所需的时间长，而且很难使迭代点进入最优的邻域，以致极易使时间长，而且很难使迭代点进入最优的邻域，以致极易使时间长，而且很难使迭代点进入最优的邻域，以致极易使时间长，而且很难使迭代点进入最优的邻域，以致极易使迭代点落入非可行域而导致计算的失败。迭代点落入非可行域而导致计算的失败。迭代点落入非可行域而导致计算的失败。迭代点落入非可行域而导致计算的失败。r（0）=150或或递减系数递减系数递减系数递减系数C C C C的选择的选择的选择的选择 罚因子递减系数罚因子递减系数罚因子递减系数罚因子递减系数C C C C的选择，一般认为对算法的成败影响的选择，一般认为对算法的成败影响的选择，一般认为对算法的成败影响的选择，一般认为对算法的成败影响不大。规定不大。规定不大。规定不大。规定0C10C10C10C1。若若若若C C C C值选得值选得值选得值选得较小较小较小较小，罚因子下降快，可以减少无约束优化，罚因子下降快，可以减少无约束优化，罚因子下降快，可以减少无约束优化，罚因子下降快，可以减少无约束优化的次数，但因前后两次无约束最优点之间的距离较远，有的次数，但因前后两次无约束最优点之间的距离较远，有的次数，但因前后两次无约束最优点之间的距离较远，有的次数，但因前后两次无约束最优点之间的距离较远，有可能使后一次无约束优化本身的迭代次数增多，而且使序可能使后一次无约束优化本身的迭代次数增多，而且使序可能使后一次无约束优化本身的迭代次数增多，而且使序可能使后一次无约束优化本身的迭代次数增多，而且使序列最优点的间隔加大，对约束最优点的逼近不利。列最优点的间隔加大，对约束最优点的逼近不利。列最优点的间隔加大，对约束最优点的逼近不利。列最优点的间隔加大，对约束最优点的逼近不利。相反，若相反，若相反，若相反，若C C C C值取得值取得值取得值取得较大较大较大较大，则无约束优化次数就要增多。，则无约束优化次数就要增多。，则无约束优化次数就要增多。，则无约束优化次数就要增多。通常建议取通常建议取通常建议取通常建议取C=0.1-0.5C=0.1-0.5C=0.1-0.5C=0.1-0.5终止准则终止准则终止准则终止准则 随着罚因子随着罚因子随着罚因子随着罚因子 的值不断减小，罚函数的序列无约的值不断减小，罚函数的序列无约的值不断减小，罚函数的序列无约的值不断减小，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。束最优点将越来越趋近于原约束优化问题的最优点。束最优点将越来越趋近于原约束优化问题的最优点。束最优点将越来越趋近于原约束优化问题的最优点。设惩罚函数设惩罚函数设惩罚函数设惩罚函数 的无约束最优点列为的无约束最优点列为的无约束最优点列为的无约束最优点列为对应的罚函数值为对应的罚函数值为对应的罚函数值为对应的罚函数值为算法步骤算法步骤算法步骤算法步骤构造内点惩罚函数构造内点惩罚函数构造内点惩罚函数构造内点惩罚函数选择可行初始点选择可行初始点选择可行初始点选择可行初始点 ，初始罚因子，初始罚因子，初始罚因子，初始罚因子 ，罚因子降低系，罚因子降低系，罚因子降低系，罚因子降低系数数数数C C C C，收敛精度，收敛精度，收敛精度，收敛精度 与与与与 ，置，置，置，置k0k0k0k0求无约束优化问题，求无约束优化问题，求无约束优化问题，求无约束优化问题，有最优点有最优点有最优点有最优点 。当当当当k=0k=0k=0k=0时转步骤时转步骤时转步骤时转步骤，否则转步骤，否则转步骤，否则转步骤，否则转步骤置置置置kk+1kk+1kk+1kk+1，并转步骤，并转步骤，并转步骤，并转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤，否则转，否则转，否则转，否则转 ,输出最优解输出最优解输出最优解输出最优解(x(x(x(x*,F,F,F,F*)内内内内点点点点法法法法流流流流程程程程图图图图给定：给定：给定：给定：x x(0)(0)D,rD,r(0)(0),C,C,1 1,2 2k0k0K=0?K=0?入口入口入口入口用无约束优化方法求罚函数用无约束优化方法求罚函数用无约束优化方法求罚函数用无约束优化方法求罚函数的优化点的优化点的优化点的优化点出口出口出口出口+-5.3.4.2 5.3.4.2 外点法外点法外点法可以解不等式约束优化问题或等式约束优化问题外点法可以解不等式约束优化问题或等式约束优化问题外点法可以解不等式约束优化问题或等式约束优化问题外点法可以解不等式约束优化问题或等式约束优化问题引例引例引例引例 设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型用外点法构造惩罚函数，具体构造形式如下用外点法构造惩罚函数，具体构造形式如下用外点法构造惩罚函数，具体构造形式如下用外点法构造惩罚函数，具体构造形式如下xbxbxbx1C1C1C1，并令，并令，并令，并令=惩罚项惩罚项惩罚项惩罚项的含义可用另一形式表示的含义可用另一形式表示的含义可用另一形式表示的含义可用另一形式表示当当g gu u(x)0 (x)0 （x xDD）当当g gu u(x)0 (x)0 （x xDD）在可行域内在可行域内在可行域内在可行域内（包括边界）（包括边界）（包括边界）（包括边界）在非可行域，在非可行域，在非可行域，在非可行域，为递增函数为递增函数为递增函数为递增函数在在在在kkkk的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点实线为原目标实线为原目标函数等值线函数等值线虚线为罚函数虚线为罚函数等值线等值线总结总结总结总结 由上图可见，两种等值线在可行域内部及边界上是重合由上图可见，两种等值线在可行域内部及边界上是重合由上图可见，两种等值线在可行域内部及边界上是重合由上图可见，两种等值线在可行域内部及边界上是重合的；而在非可行域中，罚函数的等值线升高了。即的；而在非可行域中，罚函数的等值线升高了。即的；而在非可行域中，罚函数的等值线升高了。即的；而在非可行域中，罚函数的等值线升高了。即只有在只有在只有在只有在可行域外部惩罚项才起到惩罚的作用可行域外部惩罚项才起到惩罚的作用可行域外部惩罚项才起到惩罚的作用可行域外部惩罚项才起到惩罚的作用。r r r r(k)(k)(k)(k)值越大，惩罚作值越大，惩罚作值越大，惩罚作值越大，惩罚作用越大。用越大。用越大。用越大。由上由上由上由上b b b b图可知，在起作用约束边界处罚函数等值线变得越图可知，在起作用约束边界处罚函数等值线变得越图可知，在起作用约束边界处罚函数等值线变得越图可知，在起作用约束边界处罚函数等值线变得越密集和越陡峭。随密集和越陡峭。随密集和越陡峭。随密集和越陡峭。随r r r r(k)(k)(k)(k)的增大，最优点列将越接近于原约束的增大，最优点列将越接近于原约束的增大，最优点列将越接近于原约束的增大，最优点列将越接近于原约束优化问题的最优点优化问题的最优点优化问题的最优点优化问题的最优点x x x x*。但须注意，。但须注意，。但须注意，。但须注意，近似的最优点是落在边近似的最优点是落在边近似的最优点是落在边近似的最优点是落在边界处非可行域一侧界处非可行域一侧界处非可行域一侧界处非可行域一侧。对几个问题的讨论对几个问题的讨论对几个问题的讨论对几个问题的讨论（1 1 1 1）初始点）初始点）初始点）初始点x x x x(0)(0)(0)(0)的选取的选取的选取的选取在可行域及非可行域内均可。在可行域及非可行域内均可。在可行域及非可行域内均可。在可行域及非可行域内均可。（2 2 2 2）初始罚因子）初始罚因子）初始罚因子）初始罚因子r r r r(0)(0)(0)(0)和递增系数和递增系数和递增系数和递增系数C C C C的选取的选取的选取的选取外点法中，这两者的选择对算法的成败和计算速度有显著外点法中，这两者的选择对算法的成败和计算速度有显著外点法中，这两者的选择对算法的成败和计算速度有显著外点法中，这两者的选择对算法的成败和计算速度有显著的影响。的影响。的影响。的影响。选取过小，则序贯选取过小，则序贯选取过小，则序贯选取过小，则序贯无约束求解的次数就增无约束求解的次数就增无约束求解的次数就增无约束求解的次数就增多，收敛速度慢；反之，多，收敛速度慢；反之，多，收敛速度慢；反之，多，收敛速度慢；反之，则在非可行域中，发函则在非可行域中，发函则在非可行域中，发函则在非可行域中，发函数比原目标函数要大得数比原目标函数要大得数比原目标函数要大得数比原目标函数要大得多，特别在起作用约束多，特别在起作用约束多，特别在起作用约束多，特别在起作用约束边界处产生尖点，函数边界处产生尖点，函数边界处产生尖点，函数边界处产生尖点，函数性态变坏，从而限制了性态变坏，从而限制了性态变坏，从而限制了性态变坏，从而限制了某些无约束优化方法的某些无约束优化方法的某些无约束优化方法的某些无约束优化方法的使用，致使计算失使用，致使计算失使用，致使计算失使用，致使计算失败。败。败。败。C C C C的选取影响不大，通的选取影响不大，通的选取影响不大，通的选取影响不大，通常常常常C=5-10C=5-10C=5-10C=5-10（3 3 3 3）约束容差带）约束容差带）约束容差带）约束容差带 最优点在非可行域内，是一个非可行点，这对某些工最优点在非可行域内，是一个非可行点，这对某些工最优点在非可行域内，是一个非可行点，这对某些工最优点在非可行域内，是一个非可行点，这对某些工程是不允许的。因此，可在约束边界可行域一侧加一条容程是不允许的。因此，可在约束边界可行域一侧加一条容程是不允许的。因此，可在约束边界可行域一侧加一条容程是不允许的。因此，可在约束边界可行域一侧加一条容差带。差带。差带。差带。相当于将约束条件改为相当于将约束条件改为相当于将约束条件改为相当于将约束条件改为是容差量，通常是容差量，通常是容差量，通常是容差量，通常终止准则终止准则终止准则终止准则 随着罚因子随着罚因子随着罚因子随着罚因子 的值不断增大，罚函数的序列无约束最的值不断增大，罚函数的序列无约束最的值不断增大，罚函数的序列无约束最的值不断增大，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。优点将越来越趋近于原约束优化问题的最优点。优点将越来越趋近于原约束优化问题的最优点。优点将越来越趋近于原约束优化问题的最优点。设惩罚函数设惩罚函数设惩罚函数设惩罚函数 的无约束最优点列为的无约束最优点列为的无约束最优点列为的无约束最优点列为对应的罚函数值为对应的罚函数值为对应的罚函数值为对应的罚函数值为终止准则可用下述两者之一终止准则可用下述两者之一终止准则可用下述两者之一终止准则可用下述两者之一相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。相邻两次惩罚函数无约束最优点之间的距离已足够的小。设设设设1 1 1 1为收敛精度，一般取为收敛精度，一般取为收敛精度，一般取为收敛精度，一般取1 1 1 1=10=10=10=10-4-4-4-4-10-10-10-10-5-5-5-5，则需要满足则需要满足则需要满足则需要满足相邻两次惩罚函数值的相对变化量已足够小。相邻两次惩罚函数值的相对变化量已足够小。相邻两次惩罚函数值的相对变化量已足够小。相邻两次惩罚函数值的相对变化量已足够小。设设设设2 2 2 2为收敛精度，一般取为收敛精度，一般取为收敛精度，一般取为收敛精度，一般取2 2 2 2=10=10=10=10-3-3-3-3-10-10-10-10-4-4-4-4，则需要满足则需要满足则需要满足则需要满足外外外外点点点点法法法法流流流流程程程程图图图图给定：给定：给定：给定：x x x x(0)(0)(0)(0)RRRR,r,r,r,r(0)(0)(0)(0),C C C C,1 1 1 1,2 2 2 2k0k0k0k0k=0?k=0?k=0?k=0?入口入口入口入口用无约束优化方法求罚函数用无约束优化方法求罚函数用无约束优化方法求罚函数用无约束优化方法求罚函数的优化点的优化点的优化点的优化点出口出口出口出口+-算法步骤与流程图算法步骤与流程图算法步骤与流程图算法步骤与流程图求求求求 ，得最优点，得最优点，得最优点，得最优点当当当当k=0k=0k=0k=0时转步骤时转步骤时转步骤时转步骤，否则转步骤，否则转步骤，否则转步骤，否则转步骤置置置置kk+1kk+1kk+1kk+1，并转步骤，并转步骤，并转步骤，并转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤由终止准则，若满足则转步骤，否则转，否则转，否则转，否则转 ,输出最优解输出最优解输出最优解输出最优解(x(x(x(x*,F,F,F,F*)，停止计算。，停止计算。，停止计算。，停止计算。算法步骤算法步骤算法步骤算法步骤在在在在n n n n维空间任取初始点维空间任取初始点维空间任取初始点维空间任取初始点x x x x（0 0 0 0）选取初始罚因子选取初始罚因子选取初始罚因子选取初始罚因子r r r r(0)(0)(0)(0),递增系数递增系数递增系数递增系数C C C C，并置，并置，并置，并置k0k0k0k0用外点罚函数法解等式约束优化问题用外点罚函数法解等式约束优化问题用外点罚函数法解等式约束优化问题用外点罚函数法解等式约束优化问题设有二维约束优化问题设有二维约束优化问题设有二维约束优化问题设有二维约束优化问题h h h h1 1 1 1(x)=(x)=(x)=(x)=x x x x1 1 1 1+x+x+x+x2 2 2 2-10=0-10=0-10=0-10=0如右图，如右图，如右图，如右图，h h h h1 1 1 1(x)(x)(x)(x)为该约束为该约束为该约束为该约束问题的可行域，这条直线以问题的可行域，这条直线以问题的可行域，这条直线以问题的可行域，这条直线以外的整个外的整个外的整个外的整个x x x x1 1 1 1oxoxoxox2 2 2 2平面为非可平面为非可平面为非可平面为非可行域。目标函数等值线与该行域。目标函数等值线与该行域。目标函数等值线与该行域。目标函数等值线与该直线的切点为最优点直线的切点为最优点直线的切点为最优点直线的切点为最优点最优点最优点最优点最优点S.T.:按外点法的基本思想，构造惩罚函数按外点法的基本思想，构造惩罚函数按外点法的基本思想，构造惩罚函数按外点法的基本思想，构造惩罚函数xDxDxDxDxDxDxDxD 在可行域上，惩罚项的值为零，惩罚函数值与原目标函数在可行域上，惩罚项的值为零，惩罚函数值与原目标函数在可行域上，惩罚项的值为零，惩罚函数值与原目标函数在可行域上，惩罚项的值为零，惩罚函数值与原目标函数值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于原目标函数，即在可行域外惩罚项起到了惩罚作用。原目标函数，即在可行域外惩罚项起到了惩罚作用。原目标函数，即在可行域外惩罚项起到了惩罚作用。原目标函数，即在可行域外惩罚项起到了惩罚作用。在在在在kkkk的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点的过程中，点列将趋近于原问题的最优点 对于对于对于对于m m m m(k)(k)(k)(k)，随着，随着，随着，随着k k k k的增大，得无约束最优点列的增大，得无约束最优点列的增大，得无约束最优点列的增大，得无约束最优点列推广到具有一般的等式约束优化问题推广到具有一般的等式约束优化问题推广到具有一般的等式约束优化问题推广到具有一般的等式约束优化问题首先构造如下形式的外点惩罚函数首先构造如下形式的外点惩罚函数首先构造如下形式的外点惩罚函数首先构造如下形式的外点惩罚函数惩罚因子惩罚因子惩罚因子惩罚因子m m m m（k k k k）规定取正，规定取正，规定取正，规定取正，m m m m(0)(0)(0)(0)mmmm(1)(1)(1)(1)1C1C1C1在可行域上值为零，非可行域上，值恒大于零在可行域上值为零，非可行域上，值恒大于零在可行域上值为零，非可行域上，值恒大于零在可行域上值为零，非可行域上，值恒大于零S.T.:5.3.4.3 5.3.4.3 混合法混合法 用罚函数法解决有等式约束和不等式约束的一般约束用罚函数法解决有等式约束和不等式约束的一般约束用罚函数法解决有等式约束和不等式约束的一般约束用罚函数法解决有等式约束和不等式约束的一般约束（GPGPGPGP型）优化问题的方法，把它称为型）优化问题的方法，把它称为型）优化问题的方法，把它称为型）优化问题的方法，把它称为混合惩罚函数法，混合惩罚函数法，混合惩罚函数法，混合惩罚函数法，简称混合法。简称混合法。简称混合法。简称混合法。1 1 1 1 混合法惩罚函数的形式及特点混合法惩罚函数的形式及特点混合法惩罚函数的形式及特点混合法惩罚函数的形式及特点一般约束问题的优化模型一般约束问题的优化模型一般约束问题的优化模型一般约束问题的优化模型S.T.:用惩罚函数法将其转化为无约束优化问题用惩罚函数法将其转化为无约束优化问题用惩罚函数法将其转化为无约束优化问题用惩罚函数法将其转化为无约束优化问题 惩罚函数是由原目标函数及包含约束函数的惩罚项组惩罚函数是由原目标函数及包含约束函数的惩罚项组惩罚函数是由原目标函数及包含约束函数的惩罚项组惩罚函数是由原目标函数及包含约束函数的惩罚项组成。由于该问题的约束条件包含不等式约束与等式约束成。由于该问题的约束条件包含不等式约束与等式约束成。由于该问题的约束条件包含不等式约束与等式约束成。由于该问题的约束条件包含不等式约束与等式约束两部分。因此，惩罚项也应由对应的两部分组成。对应两部分。因此，惩罚项也应由对应的两部分组成。对应两部分。因此，惩罚项也应由对应的两部分组成。对应两部分。因此，惩罚项也应由对应的两部分组成。对应等式约束部分的只有外点法一种形式，而对应不等式等式约束部分的只有外点法一种形式，而对应不等式等式约束部分的只有外点法一种形式，而对应不等式等式约束部分的只有外点法一种形式，而对应不等式的约束部分有内点法或外点法两种形式。因此按照对不的约束部分有内点法或外点法两种形式。因此按照对不的约束部分有内点法或外点法两种形式。因此按照对不的约束部分有内点法或外点法两种形式。因此按照对不等式约束处理的方法不同，混合法惩罚函数也具有两种等式约束处理的方法不同，混合法惩罚函数也具有两种等式约束处理的方法不同，混合法惩罚函数也具有两种等式约束处理的方法不同，混合法惩罚函数也具有两种形式。形式。形式。形式。内点形式的混合法内点形式的混合法内点形式的混合法内点形式的混合法 不等式约束部分按内点法形式处理的混合法，惩罚函数不等式约束部分按内点法形式处理的混合法，惩罚函数不等式约束部分按内点法形式处理的混合法，惩罚函数不等式约束部分按内点法形式处理的混合法，惩罚函数形式为形式为形式为形式为是递增序列是递增序列是递增序列是递增序列 为了统一用一个罚因子为了统一用一个罚因子为了统一用一个罚因子为了统一用一个罚因子r r r r（k k k k），），），），且又按内点法形式，即且又按内点法形式，即且又按内点法形式，即且又按内点法形式，即0C10C10C10C1C1C1C1初始点可在初始点可在初始点可在初始点可在R R R Rn n n n空间内任选，初始罚因子及递增系数参照空间内任选，初始罚因子及递增系数参照空间内任选，初始罚因子及递增系数参照空间内任选，初始罚因子及递增系数参照外点法选取。外点法选取。外点法选取。外点法选取。2 2 2 2 算法步骤及流程图算法步骤及流程图算法步骤及流程图算法步骤及流程图参照内点法与外点法。（参照内点法与外点法。（参照内点法与外点法。（参照内点法与外点法。（外点法外点法外点法外点法，内点法内点法内点法内点法）例题例题例题例题设有二维一般约束优化问题，数学模型为设有二维一般约束优化问题，数学模型为设有二维一般约束优化问题，数学模型为设有二维一般约束优化问题，数学模型为S.T.:目标函数等值线及约束曲线见下图。目标函数等值线及约束曲线见下图。目标函数等值线及约束曲线见下图。目标函数等值线及约束曲线见下图。最优点最优点最优点最优点x*x*x*x*既要在不等式既要在不等式既要在不等式既要在不等式约束包括的范围内，同时约束包括的范围内，同时约束包括的范围内，同时约束包括的范围内，同时又必须在等式约束又必须在等式约束又必须在等式约束又必须在等式约束 h(x)=0 h(x)=0 h(x)=0 h(x)=0的直线上，试求该约束优化的直线上，试求该约束优化的直线上，试求该约束优化的直线上，试求该约束优化问题的最优解。问题的最优解。问题的最优解。问题的最优解。解：首先写出罚函数解：首先写出罚函数解：首先写出罚函数解：首先写出罚函数用内点形式的混合法写出罚函数有用内点形式的混合法写出罚函数有用内点形式的混合法写出罚函数有用内点形式的混合法写出罚函数有用外点形式的混合法写出罚函数有用外点形式的混合法写出罚函数有用外点形式的混合法写出罚函数有用外点形式的混合法写出罚函数有将例题中的目标函数及约束条件代入内点形式混合法或将例题中的目标函数及约束条件代入内点形式混合法或将例题中的目标函数及约束条件代入内点形式混合法或将例题中的目标函数及约束条件代入内点形式混合法或外点形式混合法罚函数中即可。外点形式混合法罚函数中即可。外点形式混合法罚函数中即可。外点形式混合法罚函数中即可。惩罚函数法总结惩罚函数法总结其统一形式其统一形式其统一形式其统一形式式中式中式中式中（内点形式）（内点形式）（内点形式）（内点形式）（外点形式）（外点形式）（外点形式）（外点形式）不论哪一种形式，惩罚项的函数总为正。因此，惩罚不论哪一种形式，惩罚项的函数总为正。因此，惩罚不论哪一种形式，惩罚项的函数总为正。因此，惩罚不论哪一种形式，惩罚项的函数总为正。因此，惩罚函数函数函数函数 的值始终大于原目标函数的值始终大于原目标函数的值始终大于原目标函数的值始终大于原目标函数F(x)F(x)F(x)F(x)的值。为的值。为的值。为的值。为使惩罚函数最终能收敛到与原目标函数的同一最优解，使惩罚函数最终能收敛到与原目标函数的同一最优解，使惩罚函数最终能收敛到与原目标函数的同一最优解，使惩罚函数最终能收敛到与原目标函数的同一最优解，可通过对参数可通过对参数可通过对参数可通过对参数r r r r(k)(k)(k)(k)，m m m m(k)(k)(k)(k)的不断调整，使其惩罚项对的不断调整，使其惩罚项对的不断调整，使其惩罚项对的不断调整，使其惩罚项对F(x)F(x)F(x)F(x)的的的的惩罚作用在搜索过程中趋于减弱并最终消失。为此，惩罚项惩罚作用在搜索过程中趋于减弱并最终消失。为此，惩罚项惩罚作用在搜索过程中趋于减弱并最终消失。为此，惩罚项惩罚作用在搜索过程中趋于减弱并最终消失。为此，惩罚项必须有如下性质必须有如下性质必须有如下性质必须有如下性质从而，存在如下关系从而，存在如下关系从而，存在如下关系从而，存在如下关系