第一章非线性计划理论

1、第一章非线性规划理论2） 第五节无约束非线性规划常用解法 第六节约束非线性规划的最优性条件 第七节约束非线性规划的常用解法第五节无约束非线性规划常用解法无约束极值问题可以表述为29)在求解上述问题时常用迭代法，迭代法大体上可以分为两类：一类称为解读法，它会用到函 数的一阶或二阶导数；另一类称为直接法，它主要在迭代过程中使用函数值而不是使用导数 。一般说来，直接法的收敛速度较慢，只适于变量较少的情况，但是具有步骤简单，特别是 适用于目标函数解读表达式十分复杂或导数难以计算的情况。下面介绍两种基本的解读法。1梯度法 最速下降法）梯度法是一种古老的方法，但由于它的迭代过程简单，使用方便，而且又是理解

2、其它非线性 最优化方法的基础，因此非常重要。假设目标函数 具有一阶连续的偏导数，它存在极小点。以I表示极小点的第 次近似，为了求其第 s次近似 ，在I点沿方向I作射线I30将.R在I处作泰勒展开得，其中是函数在I点的梯度，可以假设I 否则I已是驻点），对于充分小的，-是 的高阶无穷小，此时，只要即可保证,就可以因此只要取下一个迭代点 使目标函数值得到改善 降低）。下面我们设法寻找使31 ）左端取最小的回。因为其中是向量一:和丨的夹角。当1也时亠I ，此时， 且其 值最小，这个方向是负梯度方向，它是函数值减小最快的方向，梯度法就是采用负梯度方向 为搜索方向。为了得到下一个近似极小点，在选定了搜索

3、方向之后，还要确定步长。选取步长的一种方法是通过试算，即先取一个验证下式是否满足：若满足，就可以取这个 进行迭代，若不满足，就减小使上式成立。由于采用了负梯度方向为搜索方向，满足33 ）的 总是存在的。另一种方法是：这可以通过在负梯度方向的一维搜索来确定使1最小的，这样得到的步长称为最佳步长，有时也称采用最佳步长时的梯度法为最速下降法。 I ；，停止迭代，得近似极小点1和近下面是梯度法求函数14，的极小点的步骤：1）给定初始点 I和允许的误差,令2）计算一和 丨，若 I似极小值 I ;否则，转入下一步；3）作一维搜索：并计算，然后令二，转回第2）步现设冋 具有二阶连续偏导数，将一 在叵 作泰勒

4、展开:关于 求导数，并令其等于零，即可得到近似最佳步长的计算公式:有时将搜索方向1的规格化为1,即取36此时式35）就变为例2用梯度法求函数 T的极小点，取允许误差解：取初始点 :，II,其海赛矩阵为=0.1124为近似极小点，此时。该冋题的精确解是需要说明的是，最速下降法通常只是在考虑的某点的附近才具有快速下降的的性质，当接近 于最优点时，收敛速度并不理想。2、牛顿法首先考虑正定二次型38)此处是正定矩阵,为常数。假定该函数的极小点是，则必有从而 消去得到。另外，对于任意点二D，解出,函数在该点的梯度这说明，对于正定二次函数，从任意近似点I出发，沿方向搜索，以1为步长，迭代一步即可达到极小点

5、。这种方法即为牛顿法。现在考虑一般的元实函数，假设它有二阶连续的偏导数,一个近似点，在这个点附近取.R的二阶泰勒多项式逼近：1为其极小点的某39)其中由39）求导数，注意到这个近似函数的极小点应满足一阶必要条件，即的逆矩阵存在，可得由于式子39）是一个近似式，所以从40）解得的是一个近似极小点。为了求得 的极小点，可以一一为搜索方向 牛顿方向），按下述公式进行迭代：这就是所谓的阻尼牛顿法 广义牛顿法），可用于求解非正定二次函数的极小点。牛顿法的优点是收敛速度快，缺点是有时无法进行下去需要采取改进措施。当维数较高时， 计算 I 的工作量很大。为了克服梯度法收敛速度慢及牛顿法有时失效和维数较高时计

6、算工作量大的缺点，不少学者提出了更加使用的其它算法，如共轭梯度法、变尺法等。第六节约束非线性规划的最优性条件约束极值问题可以表述为5)在大多数情况下，实际问题都受到某些条件的限制，这些限制条件常常给寻优工作带来很大 的困难。下面首先说明解的最优性条件，然后研究几种基本的解法。1可行下降方向1）起作用约束假设I是问题5）的一个可行解，即它满足所有约束条件。对于某一个约束条件二口 来说，I满足有两种情况：一是，这时I不在由这个约束条件形成的可行域的边界=1上，我们称这一约束为I点的不起作用的约束 或无效约束）;另一种情况是，这时I处于由这个约束条件形成的可行域的边界丄U上，我们称这一约束为I点的起

7、作用的约束 或有效约束）。显然，等式约束条件对所有的可行点都起约束作用。2）可行方向设 I是任一个可行点，对某一方向它也是一个向量）来说，若存在实数I使得对于任意的 均有下式成立:就称方向为点-1的可行方向设即是-1点所有起作用约束下标的集合。显然，若 为点I的可行方向，则存在实数 下式成立：_1 ，从而I ，使得对于任意的 .F 均有另一方面，由泰勒公式对I点的起作用的约束，当足够小时，只要41)就有此外，对叵 点的不起作用的约束， ，也有_1， M，由W的连续性，当F足够小时从而，只要方向满足式子41），即可保证为I的可行方向3）下降方向设亠，对某一方向来说，若存在实数丨门，使得对于任意的

8、 均有下式成立:则称方向 为点I的一个下降方向由泰勒公式当F足够小时，只要42就有I，这说明只要方向满足42）时，即可保证 是点 7的一个下降方向。4）可行下降方向若 既是点I的一个可行方向又是下降方向，则称为可行下降方向。设I不是极小点，为了求其极小点，继续搜索时应当沿该点的可行下降方向进行。显然，对于某一点旦来说，若该点不存在可行下降方向，它就可能是局部极小点；若存在可行下降方向，它当然 就不是极小点。下面的定理从另一个角度说明了这一问题。定理4设是问题5）的一个局部极小点，IL在 处可微，而且在 处可微，rj河在处连续，F-J则在点不存在可行下降方向，从而不存在同时满足|， 43）其中2

9、、库恩塔克Kuhn-Tucker）条件库恩塔克Kuhn-Tucker）条件是非线性规划领域中最重要的理论成果之一，具有很重要的理论价值定理5设是非线性规划5）的局部极小点，二. I ）在点处有一阶连续的偏导数，而且处的所有起作用约束梯度线性无关，则存在数44)44）称为库恩塔克Kuhn-Tucker）条件，满足该条件的点称为库恩塔克点或K-T点构造Lagra nge函数45)，分别对求偏导数并令其为零即可得44）中的第一式库恩塔克Kuhn-Tucker）条件是确定某点为最优点的必要条件，只要是最优点，且此处其作用的约束的梯度 是线性无关的，就必然满足这个条件。但是一般说来它不是充分条件，因而满

10、足这个条件的 点不一定是最优点。可是对于凸规划，这个条件是一个充分必要条件。例1用库恩-塔克条件解非线性规划解：先将其变为问题如下形式I X I构造Lagra nge函数，分别对二J求导数有解该方程组，需分别考虑一下几种情况:1） :无解；2）:I3）:4）对应于2）、3）和4）我们的到了三个库恩一塔克点，其中二1和14是极大点，而亠 为最大点，最大值为，亠 为极小点3二次规划若某一个非线性规划的目标函数为自变量的二次函数，约束条件都是线性函数，则称为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解二次规划的数学模型可以表述为Ll式46）右端的第二项为二次型。如果该二次型正定 或半

11、正定），则目标函数为严格凸函数 或凸函数），此外，二次规划的可行域为凸集，因而上述规划属于凸规划。我们知道，凸 规划的局部极小值即为其全局极值，此时库恩-塔克条件就成为极值点存在的充分必要条件将库恩-塔克条件中的第一个条件应用于二次规划，并用门代替，就得到48)在式47）中引入松弛变量二，该式即变为 假定 一I ）49）可得到再将库恩-塔克条件中的第二个条件应用于二次规划，并考虑到式50)51)联立48）和49），如果得到的解也满足式50）和51），则这样的解就是原二次规 划的解。再引入人工变量旦 构造规划，则 二 就是若解得最优解为原二次规划问题的最优解例2求解二次规划解：将上述二次规划改写

12、为可知目标函数为严格凸函数。此外引入人工变量I三在前面取负号得到此外还应满足：一 一 J用线性规划的单纯形法求解得到该线性规划的解如下:由此得到原二次规划的问题的最优解:第七节约束非线性规划的常用解法制约函数法是通过构造某种制约函数，并将它加到非线性规划的目标函数上，从而将原来的约束极值问题，转化为无约束极值问题来求解。由于这里介绍的方法需要求解一系列无约束规划问题，故称为序列无约束极小化技术，简记为SUMT （seque ntial uncon strai nedmini mizatio ntechnique。下面介绍两种方法：罚函数法 或外点法）、障碍函数法 内点法）。1罚函数法 考虑非线

13、性规划构造函数现在将某一约束函数.疋 视为，显然，当L.满足该约束时，* ，从而丨II ；当不满足该约束时，IP， , I - II ；将各个约束条件的上述函数加到非线性规划5）的目标函数上，得到一个新的函数如下53以式53）为新的目标函数，求解无约束问题:54假定问题54）的极小点为 ，由式52）可知必有对所有的），艮卩 丨。从而，不仅是问题54）的极小点，它同时也是原来非线性规划 5）的极小点。通过这种方法即可将解非线性规划5）转化为求解无约束极值问题54）。当时，如上构造的函数 在处不连续，更没有导数，这就无法使用很多有效的方法进行求解。为此将该函数作如下修改修改后的函数 当 时导数等于

14、零，当时导数等于，而且 和 一对任意 都连续。当 F时仍有当亠时,这时问题54）的极小点不一定是原来非线性规划5）的极小点但是，如果我们选取很大的实数亠，将式53）改为56)当时， ；当g时，由于g很大，将使 x 很大,从而使 的值也很大，即惩罚越厉害 注意对可行点没有也不应有惩罚作用）。由此可以想象，当亠 足够大时，相应于这样的值，56）的无约束极小点 L-JI ，就会和原来的约束问题的极小点足够接近。而当 时，它就成为原约束问题的极小点称为 惩）罚因子,EHJ为 惩）罚项,这种方法称为 惩）罚函数法,L 为 惩）罚函数。式56）也可以改写为另一种形式57)和式56）一样，当一时 I ；当亠

15、时我们有显然，式56）与57）等价。现在解释一下为什么将罚函数法称为外点法。设对于某一个罚因子有就加大罚因子的值，随着罚因子数值的增加，惩罚函数 中的惩罚项H1所起的作用随之增大， I的解 一 离可行域的距离”就会越来越近，当1 =一 趋于无穷时，点列I就从可行域 的外部趋于原非线性规划问题的极小点。正是由于 在达到最优解之前迭代点往往处于可行域之外，故常把上述罚函数法称为外点法和不等式约束问题类似，对于等式约束问题，即58)采用罚函数:59)对于既包含等式约束又包含不等式约束的一般非线性规划问题，其罚函数可取:60)对外点法可作如下经济解释：把目标函数日 看成一种 价格”，约束条件看作某种规

16、定”，采购人可在规定范围内购置物品。对违反规定采取某种惩罚”政策；若符合规定，罚款为零；反之征收罚款。此时，采购人付出的总代价应是价格和罚款的总和。采购人的目标是使总代价最小，这就是上述的无约束问题。当罚款规定得很苛刻时，违反规定支付的罚款很高，这就迫使采购人符合规定，在数学上表现为，当罚因子丨足够大时，上述无约束问题的最优解应满足约束条件，而成为约束问题的最优解。罚函数法的迭代步骤如下：1）取一个罚因子亠 比如说取 W ），允许误差，并令亠。2）求下述无约束极值问题的最优解：其中.F 可取式56）或57）。设其极小点为 I3）若存在某一个亠，有I = 1或存在某一个二_0 ，有ri则取 I

17、。然后转回第2）部，否则停止迭代，得所要的I。例用罚函数法求解解：构造罚函数对固定的 令对于不满足约束条件的点有从而，求得极小点如下:当二I时， 乂 | ；当时，.|；说明原约束问题的极小点为一I2、障碍函数法 内点法）罚函数法的一个重要特点是函数I可以在整个 空间内进行优化，可以任意选择初始点，这给计算带来了很大的方便。但是，由于迭代过程常常在可行域外部进行，因而 不能以中间结果直接作为近似解使用。如果要求每次的近似解都是可行的，以便观察目标函 数值的改善情况，这时就无法使用罚函数法。障碍函数法与罚函数法不同，它要求迭代过程始终在可行域内进行。可以仿照罚函数法 ，通过函数叠加的办法来改造原来

18、约束极值问题的目标函数，是改造后的目标函数具有这种 性质：在可行域 的内部与边界较远的地方，其值与原来的目标函数值尽可能的相近；而在 接近于边界面时可以达到任意值。如果将初始迭代点取在可行域内部 内点），在进行无约束极小化时，这样的函数就会像障碍一样阻止迭代点到可行域的边界上去，而使迭代过程始终在可行域内部进行。经过这样改造后的新目标函数，称为障碍函数。可以想象，满足这 种要求的障碍函数，其最小解自然不会在可行域边界上达到。这就是说，这时的极小化是在不包括可行域边界的可行开集上进行的，因而实际上是一种具有无约束性质的极值问题， 可以利用无约束极小化的方法进行计算。考虑非线性规划5)当剧点从可行

19、域吕内部趋于其边界时，至少有某一个约束函数而下述倒数函数I= 1趋于零，从361和对数函数LE362都将无限增大。如果将式61 ）或62）加到非线性规划5）的目标函数上去，就能构 造成我们所要求的新的目标函数。为了逐步逼近问题 或!（65此处，为所有严格内点的集合，即_166）式64）和65）右端的第二项称为障碍项，称为障碍因子。函数I称为障碍函数。如果从某一点二出发，按无约束极小化方法 但在进行一维搜索时需注意控制步长，不要使迭代点越出）对问题63）进行迭代，贝U随着障碍因子的逐渐减小，即I障碍项所起的作用也越来越小，因而，求出的问题 63）的解 L 就会逐步逼近原约束问 题5）的极小解。若5）的极小点在可行域的边界上，则随着 的逐渐减小，障碍”作用逐 步