第5章非线性规划选读.ppt

§5.9 等式约束下多元函数的寻优方法 前面给大家介绍了无约束非线性函数的寻优方法。但是在很多实际的非线性规划问题中，其变量的取值都有一定的限制，也就是说，非线性规划问题一般是有约束条件的寻优问题。约束条件可分为等式与不等式约束，处理等式约束问题与不等式约束问题的方法也有所不同。 对于有约束条件的寻优问题，到目前为止可以说还没有一种十分有效的方法。下面仅介绍几种有代表性的方法。 等式约束下多元函数的寻优方法 一、等式约束下的消元法 该方法的基本思路是：对于有n个变量、m个等式约束的非线性规划问题，通过约束等式将m个变量用另外n-m个变量表示出来，然后代入目标函数表达式，从而将一个n元函数的有约束最优化问题转化为一个n-m元函数的无约束最优化问题，这样就可利用前面介绍的无约束最优化问题的寻优方法进行求解。 设非线性规划问题的形式为： 等式约束下多元函数的寻优方法 如果能把gi(x1,x2,…,xn)=0改写为： xi=φi(xm+1, xm+2,…, xn) (i=1~m) 将上式代入目标函数式，化简后可得新的目标函数f1(xm+1, xm+2,…, xn) 。这样，就把一个求具有m个等式约束的n个变量的寻优问题，转化成为仅有n-m个变量的无约束的寻优问题。 等式约束下多元函数的寻优方法 二、拉格朗日(Lagrangian)乘子法 如上所述，消元法如果能用，是有效的。但要采用消元法，必须首先求解约束方程，而这一步往往是繁杂的，甚至多数情况下是难以做到的。下面介绍的拉格朗日乘子法是一种更为有效的方法。 1、等式约束时极值存在的必要条件 我们先来看二元函数的情况。对于二元函数来说，设目标函数为f(x1,x2)，等式约束为g(x1,x2)=0。在无约束时，极值点存在的必要条件为： 等式约束下多元函数的寻优方法 当有等式约束时，除了以上的关系式仍成立外，还必须满足： 这就是说，在等式约束下，使 f 极小的dxl与dx2已不能任意选取，必须满足式(2)。由式(1)和式(2)可得： 等式约束下多元函数的寻优方法 这就是在等式约束下使目标函数 f 为极小的必要条件。 等式约束下多元函数的寻优方法 2、拉格朗日乘子法的计算方法和步骤 式(3)可改写为： 令此值等于一个可正可负的常数 λ λ称为拉格朗日待定系数，或简称为拉格朗日乘子。由式(4)及g(xl,x2)得： 等式约束下多元函数的寻优方法 解此方程组可得x1*,x2*,λ，即求出极值点。方程组(5)相当于求解一个无约束的函数： L(x1,x2, λ)=f(x1,x2)- λg(x1,x2) (6) 等式约束下多元函数的寻优方法 的极值点。此函数极值点存在的必要条件为： 式(7)的结果即为式(5)。这个新定义的函数L称为拉格朗日函数。 综上所述，通过应用拉格朗日乘子，可使求等式约束条件下函数f的极小点转化为求拉格朗日函数L的驻点。这种引进待定乘子λ，将有等式约束的寻优问题转化为无约束寻优问题的做法，称为拉格朗日乘子法。 等式约束下多元函数的寻优方法 例：用拉格朗日乘子法求下列问题的极小点： 等式约束下多元函数的寻优方法 解此方程组可得：x1*=5，x2*=3，λ*=-3，f*=17。此即为所求问题的极小点。一般来说，对于简单的情况，消元法比较简单，但对于复杂的情形，拉格朗日乘子法是很有价值的。 对于目标函数为n元函数f(X)，且有m个等式约束的非线性规划问题： 等式约束下多元函数的寻优方法 拉格朗日函数为： 函数L为极小的必要条件为： 为m个拉格朗日乘子组成的行向量，g(X)为m个约束函数组成的列向量。 等式约束下多元函数的寻优方法 这里未知数xj(j=1~n)及λi(i=1~m)共有n+m个，而式(8)也正好有n+m个，故可以求解。由于引入了λi，使变量及方程的数目都增加了。对于f(X)和gi(X)比较复杂的情况，方程组(8)一般为非线性方程组，求解一般比较困难，这时一般采用直接寻优法求解拉格朗日函数的驻点。 为了便于在计算机上利用直接寻优法进行迭代计算，一般引入新的函数： 等式约束下多元函数的寻优方法 该式与式(8)是等价的。这样，有约束的原问题就转化为无约束的问题了。然后，利用无约束多变量函数的寻优方法对函数Z求极小值，即可得到原问题的最优解。 等式约束下多元函数的寻优方法 三、罚函数法 利用持定乘子求解有约束的寻优问题，还有一种近似、但经常使用的方法，即所谓罚函数法，也称惩罚函数法或代价函数法。 罚函数法的基本思想： 设原问题为： 等式约束下多元函数的寻优方法 我们知道，如果不考虑等式约束条件，仅用f(X)作为无约束问题求解的话，所得的点不是原问题的解，一般会相差很远。如果把约束条件作为一个“惩罚”一并考虑进来的话，结果可