1 / 18 第一章 非线性规划理论 2）第五节 无约束非线性规划常用解法第六节 约束非线性规划的最优性条件第七节 约束非线性规划的常用解法第五节 无约束非线性规划常用解法无约束极值问题可以表述为 29 ）在求解上述问题时常用迭代法，迭代法大体上可以分为两类：一类称为解读法，它会用到函数的一阶或二阶导数；另一类称为直接法，它主要在迭代过程中使用函数值而不是使用导数。一般说来，直接法的收敛速度较慢，只适于变量较少的情况，但是具有步骤简单，特别是适用于目标函数解读表达式十分复杂或导数难以计算的情况。下面介绍两种基本的解读法。 1、梯度法 最速下降法）梯度法是一种古老的方法，但由于它的迭代过程简单，使用方便，而且又是理解其它非线性最优化方法的基础，因此非常重要。假设目标函数具有一阶连续的偏导数，它存在极小点。以表示极小点的第次近似，为了求其第次近似，在点沿方向作射线 30 ）将在处作泰勒展开得，其中是函数在点的梯度，可以假设否则已是驻点），对于充分小的，是的高阶无穷小，此时，只要 31 ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 18 页2 / 18 即可保证。因此只要取下一个迭代点，就可以使目标函数值得到改善 降低）。下面我们设法寻找使 31）左端取最小的。因为 32）其中是向量和的夹角。当时，此时，且其值最小，这个方向是负梯度方向，它是函数值减小最快的方向，梯度法就是采用负梯度方向为搜索方向。为了得到下一个近似极小点，在选定了搜索方向之后，还要确定步长。选取步长的一种方法是通过试算，即先取一个验证下式是否满足： 33 ）若满足，就可以取这个进行迭代，若不满足，就减小使上式成立。由于采用了负梯度方向为搜索方向，满足 33）的总是存在的。另一种方法是： 34）这可以通过在负梯度方向的一维搜索来确定使最小的，这样得到的步长称为最佳步长，有时也称采用最佳步长时的梯度法为最速下降法。下面是梯度法求函数的极小点的步骤：1）给定初始点和允许的误差，令；2）计算和，若，停止迭代，得近似极小点和近似极小值；否则，转入下一步；3）作一维搜索：并计算，然后令，转回第 2）步。现设具有二阶连续偏导数，将在作泰勒展开：关于求导数，并令其等于零，即可得到近似最佳步长的计算公式： 35 ）有时将搜索方向的规格化为 1，即取精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 18 页3 / 18 36 ）此时式 35）就变为 37 ）例2 用梯度法求函数的极小点，取允许误差。解：取初始点，, 其海赛矩阵为，0.1124 ，故为近似极小点，此时。该问题的精确解是。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 18 页4 / 18 需要说明的是，最速下降法通常只是在考虑的某点的附近才具有快速下降的的性质，当接近于最优点时，收敛速度并不理想。 2、牛顿法首先考虑正定二次型， 38 ）此处是一个正定矩阵，为常数。假定该函数的极小点是，则必有从而。另外，对于任意点，函数在该点的梯度，消去得到，解出。这说明，对于正定二次函数，从任意近似点出发，沿方向搜索，以 1为步长，迭代一步即可达到极小点。这种方法即为牛顿法。现在考虑一般的元实函数，假设它有二阶连续的偏导数，为其极小点的某一个近似点，在这个点附近取的二阶泰勒多项式逼近： 39）其中。由39）求导数，注意到这个近似函数的极小点应满足一阶必要条件，即设的逆矩阵存在，可得 40 ）由于式子 39）是一个近似式，所以从 40）解得的是一个近似极小点。为了求得的极小点，可以为搜索方向 牛顿方向），按下述公式进行迭代： 41 ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 18 页5 / 18 这就是所谓的阻尼牛顿法 广义牛顿法），可用于求解非正定二次函数的极小点。牛顿法的优点是收敛速度快，缺点是有时无法进行下去需要采取改进措施。当维数较高时，计算的工作量很大。为了克服梯度法收敛速度慢及牛顿法有时失效和维数较高时计算工作量大的缺点，不少学者提出了更加使用的其它算法，如共轭梯度法、变尺法等。第六节 约束非线性规划的最优性条件约束极值问题可以表述为 5）在大多数情况下，实际问题都受到某些条件的限制，这些限制条件常常给寻优工作带来很大的困难。下面首先说明解的最优性条件，然后研究几种基本的解法。1、可行下降方向1）起作用约束假设是问题 5）的一个可行解，即它满足所有约束条件。对于某一个约束条件来说，满足有两种情况：一是，这时不在由这个约束条件形成的可行域的边界上，我们称这一约束为点的不起作用的约束 或无效约束）；另一种情况是，这时处于由这个约束条件形成的可行域的边界上，我们称这一约束为点的起作用的约束 或有效约束）。显然，等式约束条件对所有的可行点都起约束作用。2）可行方向设是任一个可行点，对某一方向它也是一个向量）来说，若存在实数，使得对于任意的均有下式成立：就称方向为点的可行方向。设精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 18 页6 / 18 即是点所有起作用约束下标的集合。显然，若为点的可行方向，则存在实数，使得对于任意的均有下式成立：，从而，另一方面，由泰勒公式对点的起作用的约束，当足够小时，只要， 41 ）就有，此外，对点的不起作用的约束，由的连续性，当足够小时，也有，从而，只要方向满足式子 41），即可保证为的可行方向。 3）下降方向设，对某一方向来说，若存在实数，使得对于任意的均有下式成立：，则称方向为点的一个下降方向。由泰勒公式当足够小时，只要精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 18 页7 / 18 42 ）就有，这说明只要方向满足42）时，即可保证是点的一个下降方向。4）可行下降方向若既是点的一个可行方向又是下降方向，则称为可行下降方向。设不是极小点，为了求其极小点，继续搜索时应当沿该点的可行下降方向进行。显然，对于某一点来说，若该点不存在可行下降方向，它就可能是局部极小点；若存在可行下降方向，它当然就不是极小点。下面的定理从另一个角度说明了这一问题。定理4 设是问题 5）的一个局部极小点，在处可微，而且在处可微，在处连续，则在点不存在可行下降方向，从而不存在同时满足， 43 ）其中2、库恩塔克 Kuhn-Tucker）条件库恩塔克 Kuhn-Tucker）条件是非线性规划领域中最重要的理论成果之一，具有很重要的理论价值。定理5 设是非线性规划 5）的局部极小点，）在点处有一阶连续的偏导数，而且处的所有起作用约束梯度线性无关，则存在数44）44）称为库恩塔克 Kuhn-Tucker）条件，满足该条件的点称为库恩塔克点或K-T点。构造Lagrange 函数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 18 页8 / 18 45 ），分别对求偏导数并令其为零即可得44）中的第一式。库恩塔克 Kuhn-Tucker）条件是确定某点为最优点的必要条件，只要是最优点，且此处其作用的约束的梯度是线性无关的，就必然满足这个条件。但是一般说来它不是充分条件，因而满足这个条件的点不一定是最优点。可是对于凸规划，这个条件是一个充分必要条件。例1 用库恩塔克条件解非线性规划解：先将其变为问题如下形式构造Lagrange 函数，分别对求导数有 ，）解该方程组，需分别考虑一下几种情况： 1）：无解； 2）：；3）：；4）：；对应于 2）、3）和4）我们的到了三个库恩塔克点，其中和是极大点，而为最大点，最大值为，为极小点。3 二次规划若某一个非线性规划的目标函数为自变量的二次函数，约束条件都是线性函数，则 O 1 4 6 x精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 18 页9 / 18 称为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解。二次规划的数学模型可以表述为式46）右端的第二项为二次型。如果该二次型正定或半正定），则目标函数为严格凸函数或凸函数），此外，二次规划的可行域为凸集，因而上述规划属于凸规划。我们知道，凸规划的局部极小值即为其全局极值，此时库恩塔克条件就成为极值点存在的充分必要条件。将库恩塔克条件中的第一个条件应用于二次规划，并用代替，就得到， 48）在式47）中引入松弛变量，该式即变为 假定）再将库恩塔克条件中的第二个条件应用于二次规划，并考虑到式49）可得到， 50） 51）联立48）和49），如果得到的解也满足式50）和。下面介绍两种方法：罚函数法或外点法）、障碍函数法 内点法）。1、罚函数法考虑非线性规划 5）构造函数 52 ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 18 页12 / 18 现在将某一约束函数视为，显然，当满足该约束时，从而；当不满足该约束时，；将各个约束条件的上述函数加到非线性规划 5）的目标函数上，得到一个新的函数如下 53 ）以式53）为新的目标函数，求解无约束问题： 54 ）假定问题 54）的极小点为，由式 52）可知必有对所有的），即。从而，不仅是问题 54）的极小点，它同时也是原来非线性规划5）的极小点。通过这种方法即可将解非线性规划5）转化为求解无约束极值问题54）。当时，如上构造的函数在处不连续，更没有导数，这就无法使用很多有效的方法进行求解。为此将该函数作如下修改 55 ）修改后的函数当时导数等于零，当时导数等于，而且和对任意都连续。当时仍有，当时，这时问题 54）的极小点不一定是原来非线性规划5）的极小点。但是，如果我们选取很大的实数，将式 53）改为 56 ）当时，；当时，由于很大，将使很大，从而使的值也很大，即惩罚越厉害注意对可行点没有也不应有惩罚作用）。由此可以想象，当足够大时，相应于这样的值，56）的无约束极小点，就会和精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 18 页13 / 18 原来的约束问题的极小点足够接近。而当时，它就成为原约束问题的极小点。这种方法称为 惩）罚函数法，称为惩）罚因子，为惩）罚项，为惩）罚函数。式56）也可以改写为另一种形式 57 ）和式56）一样，当时；当时我们有。显然，式 56）与57）等价。现在解释一下为什么将罚函数法称为外点法。设对于某一个罚因子有，就加大罚因子的值，随着罚因子数值的增加，惩罚函数中的惩罚项所起的作用随之增大，的解离可行域的“ 距离” 就会越来越近，当趋于无穷时，点列就从可行域的外部趋于原非线性规划问题的极小点。正是由于在达到最优解之前迭代点往往处于可行域之外，故常把上述罚函数法称为外点法。和不等式约束问题类似，对于等式约束问题，即 58 ）采用罚函数： 59 ）对于既包含等式约束又包含不等式约束的一般非线性规划问题，其罚函数可取： 60）对外点法可作如下经济解释：把目标函数看成一种 “ 价格” ，约束条件看作某种 “规定” ，采购人可在规定范围内购置物品。对违反规定采取某种“ 惩罚” 政策；若符合规定，罚款为零；反之征收罚款。此时，采购人付出的总代价应是价格和罚款的总和。采购人的目精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 18 页14 / 18 标是使总代价最小，这就是上述的无约束问题。当罚款规定得很苛刻时，违反规定支付的罚款很高，这就迫使采购人符合规定，在数学上表现为，当罚因子足够大时，上述无约束问题的最优解应满足约束条件，而成为约束问题的最优解。罚函数法的迭代步骤如下：1）取一个罚因子比如说取），允许误差，并令。2）求下述无约束极值问题的最优解：其中可取式 56）或57）。设其极小点为3）若存在某一个，有或存在某一个，有则取。然后转回第 2）部，否则停止迭代，得所要的。例 用罚函数法求解解：构造罚函数对固定的令对于不满足约束条件的点有从而，求得极小点如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 18 页15 / 18 当时，；当时，；当时，；当时，；说明原约束问题的极小点为。2、障碍函数法 内点法）罚函数法的一个重要特点是函数可以在整个空间内进行优化，可以任意选择初始点，这给计算带来了很大的方便。但是，由于迭代过程常常在可行域外部进行，因而不能以中间结果直接作为近似解使用。如果要求每次的近似解都是可行的，以便观察目标函数值的改善情况，这时就无法使用罚函数法。障碍函数法与罚函数法不同，它要求迭代过程始终在可行域内进行。可以仿照罚函数法，通过函数叠加的办法来改造原来约束极值问题的目标函数，是改造后的目标函数具有这种性质：在可行域的内部与边界较远的地方，其值与原来的目标函数值尽可能的相近；而在接近于边界面时可以达到任意值。如果将初始迭代点取在可行域内部内点），在进行无约束极小化时，这样的函数就会像障碍一样阻止迭代点到可行域的边界上去，而使迭代过程始终在可行域内部进行。经过这样改造后的新目标函数，称为障碍函数。可以想象，满足这种要求的障碍函数，其最小解自然不会在可行域边界上达到。这就是说，这时的极小化是在不包括可行域边界的可行开集上进行的，因而实际上是一种具有无约束性质的极值问题，可以利用无约束极小化的方法进行计算。考虑非线性规划 5）当点从可行域内部趋于其边界时，至少有某一个约束函数趋于零，从而下述倒数函数 61 ）和对数函数 62 ）都将无限增大。如果将式 61）或62）加到非线性规划 5）的目标函数上去，就能构造成我们所要求的新的目标函数。为了逐步逼近问题 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 18 页16 / 18 其中 (64 或 (65 此处，为所有严格内点的集合，即 66）式64）和65）右端的第二项称为障碍项，称为障碍因子。函数称为障碍函数。如果从某一点出发，按无约束极小化方法但在进行一维搜索时需注意控制步长，不要使迭代点越出）对问题 63）进行迭代，则随着障碍因子的逐渐减小，即障碍项所起的作用也越来越小，因而，求出的问题63）的解就会逐步逼近原约束问题5）的极小解。若 5）的极小点在可行域的边界上，则随着的逐渐减小， “ 障碍” 作用逐步降低，所求出的障碍函数的极小点就会不断靠近的边界，直到满足某一精度要求为止。障碍函数法的迭代步骤如下：1）取第一个障碍因子比如说取），允许误差，并令。2）构造障碍函数，障碍项可采取倒数函数，也可采用对数函数。3）求下述无约束极值问题的最优解：其中可取式 64）或65）。设其极小点为。4）检查是否满足收敛准则： 67 ）或 68 ）如果满足此准则，则以为原来约束问题的近似极小解，停止迭代。否则，取，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 18 页17 / 18 令，转回第 3）步，继续进行迭代。例 使用内点法解解：构造障碍函数联立上述两个方程得，如此得到最优解：如前所述，内点法的迭代过程必须由某一个严格的内点开始，在处理实际问题时，如果凭直观即可找到一个初始内点，这当然十分方便；如果找不到，则可是用下述方法。先任找一点，如果它以严格不等式满足所有约束，则可以它作为初始点。若该点以严格不等式满足一部分约束，而不能以严格不等式满足另外的约束，则以不能严格满足的这些约束函数为 假拟目标函数，而以严格满足的约束函数形成障碍项，构成一无约束性质的问题。求解这个问题，可得一新点，若仍不是内点，就如上继续进行，并减小障碍因子，直至求出一个初始内点为止。求初始内点的迭代步骤如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 18 页18 / 18 1）任取一点，比如说取），令。2）确定指标集和：3）检查是否为空集，若为空集，则取为初始点，迭代停止；否则，转下一步。4）构造函数 ）以为初始点求解其中。设求出的极小点为，则。令，令，转回第 2）步，继续进行迭代。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 18 页