第二章 最优化与数学规划.doc

第二章 最优化与数学规划大家知道，最优化问题始终是数学中的一类基本问题，同时也是现代经济学中用来刻划经济问题的基本方法之一。最优化问题是求目标函数在无约束或在等式约束下最优值的问题，而数学规划则是求目标函数在等式约束和不等式约束下最优值的问题。下面我们将分别加以讨论。在下面的两节中，先回忆一下高等数学中学过的无约束和等式约束下目标函数取得极值的必要条件与充分条件。2.1 无约束下最优化的必要条件与充分条件定理2.1 设yf（x），xD为一阶连续可微函数，若f（x）在D的内点处取得极值，则必须满足条件：。定理2.2 设yf（x），xD为二阶连续可微函数，若f（x）在D的内点处满足，且，则当 （1）时，处取得极小值； （2）时，处取得极大值。(图2.1) (图2.2)定理2.3 设为一阶连续可微的二元函数，若在D的内点处取得极值，则它的必要条件为 即 定理2.4 设为二阶连续可微的二元函数，若在D的内点处，满足即 令 ，则（1）当 时，处取得极小值；（2）当 时，处取得极大值。 证明：由二元函数的泰勒公式（取二阶近似）：因为 ，所以，对邻近的任意有其中 。由上式，若，则处取得极小值。为使，则关于t的一元二次方程无实根，故其判别式小于零，即， 或 (2.1)为了保证上述行列式为正，必须使 和 同号。所以，若，当时，有，即时，这时f在处取得极小值。若，泰勒展开式中只留下这一项二阶偏导数。则当时，f也在处取得极小值。同理，为使，即方程无实根，其判别式，即，当时，有，二阶偏导数项小于零，这时f在处取得极大值。定理2.3和定理2.4可以直接推广到下列n个自变量的定理2.5和定理2.6（不加证明）。定理2.5 设为一阶连续可微，则f在D的内点处取得极值的必要条件是：，即 (2.2)定理2.6 设为二阶连续可微的，若在D的内点处满足， 即 (2.3)以及对f的二阶偏导数的各阶主子式： ， (2.4) (2.5) 注：令，则由矩阵理论知，式(2.4)表示矩阵为正定，即时，f在x*处取得极小；式(2.5) 表示矩阵为负定，即时，f在x*处取得极大。2.2 等式约束下最优化的必要条件与充分条件现在来考察二元函数带等式约束的极值问题的必要条件。设极值问题为： ，其中f ，g都是一阶连续可微的二元函数，若在内点处取得极值，并设，则由微积分的隐函数定理，可在g(x1,x2)=0中确定了一个可导函数，满足，这样，就把带等式约束的极值问题转化为无约束的极值问题。由已知条件知 ，而 ，代入上式，得：，即 。写成行列式形式为 ，由行列式的性质，为使上式成立，行列式中的两行成比例，令比例系数为，则有，即 令 ，称为该极值问题的Lagrange函数，则上式可以改写成：将上述分析所得的结论写成下列的定理2.7。定理2.7 (Lagrange) 设二元函数在等式约束下的极值问题为： 其中，f和g为一阶连续可微的二元函数，它取得极值的必要条件是最大化它的Lagrange函数，即 (2.6)式(2.6)是对变量的无约束极值问题，它的必要条件为： (2.7)（注：本定理对极小值问题也一样！）再考察二元函数带等式约束的极值问题的充分条件。设极值问题： ，其中，f和g都是二阶连续可微函数，并设由隐函数所决定的一元可导函数为 。对 作全导数，得 ，所以 (2.8)对 作全导数，得 (2.9)对式(2.9)再求导得：令 L f +g，并变量求一阶、二阶导数，可得：， 令 (2.10) (2.11)在满足一阶必要的条件下有：，则 (2.12) (2.13)定理2.8 设为二元二阶连续可微函数， 在等式约束的条件下的极值问题： (2.14)若在处满足一阶必要条件（定理2.7），则(1) 当 时，f在 取得极小值； (2.15)(2) 当 时，f在 取得极大值。 (2.16)2.3 多元函数带等式约束极值问题在本节中，我们将把二元函数的带等式约束极值问题的结论推广到n元函数的极值问题中去。为此考虑下列极值问题： (2.17)其中 都是n元二阶连续可微函数。通过它的Lagrange函数可以把该极值问题化为下列的无条件极值问题： (2.18)则在内点处取得极值的一阶必要条件为：， 即 关于它的二阶充分条件，令 并令 ，我们有下列推广后的定理2.9 设为二阶连续可微的n元函数，为m个二阶连续可微的n元函数，在的约束条件下，目标函数在的内点处取得极值的一阶必要条件为，它的Lagrange函数的n个偏导数为零，即： (2.19) 若在处满足上述必要条件，则有 （1）若， (2.20)则f（x）在处取得极小值； （2）若， (2.21)则f（x）在处取得极大值。例2.1 在消费者理论中，消费者通常考虑在预算约束下求效用极大的问题（见第三章）： (2.22)其中为消费者的效用函数，m为收入预算，分别为商品的价格。它的Lagrange函数为 (2.23)因而，在内点处取得极值的一阶必要条件为： ，。若在处还满足： ，即 利用一阶必要条件代入（把，化掉），并除去得：， (2.24)这就是取得极大值的充分条件。例2.2 在厂商理论中，设为生产函数，其中为投入品，y为产出品。则生产者将考虑他的利润极大化问题： (2.25)其中，分别为投入品的价格，p为产出品y的价格。因而，在内点处取得极值的一阶必要条件为： (2.26) 若在处还满足：及 (2.27)则在处必取得极大值。2.4 带不等式约束的极值问题数学规划在前面几节中，我们在讨论的极值问题的条件时，都假设目标函数在定义域的内点处取得极值。然而在很多实际问题中，常常遇到极值问题的最优解可能发生在边界上。在这种情况下前面所得到的结论都不能用。在本节里，我们将研究极值问题的最优解可能发生在边界上的最优化条件Kuhn-Tucker条件。这时的约束条件中可能有不等式约束。在数学中，研究求目标函数在带有等式和不等式约束条件下最优化的数学分支称为数学规划。数学规划可分两类：目标函数及约束条件均为线性方程时，称为线性规划；目标函数及约束条件中出现非线性方程时，称为非线性规划。线性规划可以看作非线性规划的特例。一种典型的非线性规划为目标函数，在约束条件：下的极值问题： 其中，都是连续的实值函数。由不等式所刻画的集合D：称为约束集合或可行区域，D中元素称为可行点。例如在R2中由三个不等式约束：所构成的可行区域是分别由曲线划分出一侧和x1 0, x2 0共同的区域，如图2.3所示。 （图2.3）若最优解发生在可行区域内部的称为内部解；若最优解发生在可行区域边界上时称为角点解。在经济学中经常会遇到带不等式约束的非线性规划。所以本节的内容对学习经济学具有直接指导意义。让我们先来看一种最简单的情况：设f（x）为一元连续可微的实值函数。要求解目标函数f (x)在自变量x 0的条件下的最优解问题： (2.28)其中变量x 0的条件称为非负约束。我们分三种情况来考虑这个极大值问题：极大值点位于小于零处（如图2.3）；极大值点等于零（如图2.4）；和极大值点位于大于零处（如图2.5）。(图2.4) (图2.5) 由于f（x）的极大值问题受到的不等式约束的限制。（1）不等式约束条件下极大值点在处，这时；（2）不等式约束条件下极大值点在处，这时；（3）不等式约束条件下极大值点在处，这时。当x* 0时为内部解; 当x*= 0时为角点解。归纳上述三种情况，我们可以得出在处取得极大值的一阶必要条件为： (2.29)并称此一阶必要条件为该问题的Kuhn-Tucker 条件（简称KT条件）。例2.3 考虑下列问题：令，则。则它的最优解应满足KT条件：由(2)式，得。由(3)式，知是增根。而满足(1)，(3)式，所以，最优解为，这是角点解。用类似地方法，也可研究一元函数f (x)在自变量x为非负条件下的极小值问题： (2.30)它的一阶必要条件：KT条件为： (2.31)(图2.6)到此，我们可以将上面的结论归纳为下面的定理。定理2.10 设为n维的连续可微函数。 (1) 若为 的最优解，则应该满足的KT条件为：， (2.32)(2) 若为 的最优解，则应该满足的KT条件为：， (2.33)在经济学中最简单的最优化模型为（）： (2.34)它是目标函数和约束条件都是二元函数的非线性规划问题。所以，我们要将定理2.10推广到多元函数的情况。为此我们引进一种新的变量，称之为松弛变量。以(2.33)为例，这时可把不等式约束条件等价地改写为： (2.35)于是问题就转化成为： (2.36)我们可将等式约束的部分用来处理到目标函数中去，剩下的就只要处理松弛变量的不等式，即： (2.37)这时，对于变量和是无约束的，只有松弛变量x 是有非负约束条件：。因而，可以直接应用定理2.10，所以它的一阶必要条件：KT条件为： (2.38) 以及 (2.39)， 所以式(2.39)可以改为： (2.40)结合(2.38)和(2.40)，KT条件可改写为： (2.41)以上讨论对个变量的问题也适用。在有多个不等式约束时，每一个不等式约束都要引入相应的松弛变量。请看下面的定理。定理2.11 (Kuhn-Tucker定理) 设为元连续可微函数，在约束条件：下的极值问题： (2.42)其中的定义域为，设为极值问题的最优解，且是线性无关的，则必存在唯一的，使满足Kuhn-Tucker条件： (2.43)在经济学中，很多经济模型的目标函数是严格拟凹函数，而约束条件往往是拟凹函数或线性函数。对于这类经济的最优化模型，我们有更为适用的最优解的判定定理。 定理2.14 （ArrowEnthoven）设, 为元连续的拟凹函数，在约束条件：下的拟凹规划问题： (2.44)该规划的可行域为设为该极值问题的最优解，则必存在一个，使满足一阶必要条件： (2.45)定理2.14的结论(2.45)是拟凹规划取得最优解的必要条件。要使必要条件变为充分条件，请看下面的定理。定理2.15 在定理2.14的假设下，如果还满足以下