第3章-3信息经济学研究方法-非线性规划理论

第3章信息经济学研究方法博弈论基本概念规范研究实证研究非线性规划应用例证基础模型其他例证基本类型信息经济学的研究方法例证经典模型工程数学理论数学3.3非线性规划线性规划是研究在线性约束条件下求解线性目标函数的最小（或最大）的问题，即m,...,2,1i,0)x,...,x,x(g)x,...,x,x(minf)P(n21in21)x,...,x,x(fn21)x,...,x,x(gn21im,...,2,1im,...,2,1i,bxa)x,...,x,x(gxc)x,...,x,x(fn1jijijn21in1jjjn21式中，和，都是线性函数，即：3.3非线性规划所谓非线性规划问题，是指目标函数)x,...,x,x(fn21)x,...,x,x(gn21im,...,2,1i和约束函数，中至少有一个是非线性函数。上面形式的规划问题中，目标函数是求最小，而所有的约束均为不等式限制，我们称(P)为标准形式的规划问题。任何其它形式的规划问题都可以经过适当的数学上的处理，将它化为标准形式的规划问题。非线性规划同线性规划一样，也是运筹学的一个极为重要的分支。他在经济、管理、计划、统计，以及军事、生产过程自动化等方面都有着重要的应用。本节内容•基本概念•无约束极值问题•约束极值问题非线性规划的数学模型（1）非线性规划数学模型的一般形式是：min()()0(1,2,...,)()0(1,2,...,)iifXhXimgXjl其中，X=(x1,x2,…,xn)T是n维欧氏空间En中的点(向量)，目标函数f(X)和约束函数hi(X)、gj(X)为X的实函数。（2）有时，也将非线性规划的数学模型写成：min()()0(1,2,...,)jfXgXjl即约束条件中不出现等式，如果有某一约束条件为等式gj(X)=0，则可用如下两个不等式约束替代它：()0()0jjgXgX非线性规划的数学模型非线性规划的数学模型（3）模型(2)也常表示成另一种形式：min(),{|()0,(1,2,...,)}njfXXRERXgXjl其中，R为问题的可行域。二维问题的图解221221221212min()(2)(1)505000fXxxxxxxxxx当只有两个自变量时，求解非线性规划也可像对线性规划那样借助于图解法。如以下非线性规划问题：1x1x212354O0在x1Ox2坐标平面上画出目标函数的等值线，它是以点(2，1)为圆心的同心圆。二维问题的图解1x1x212354O0ABCD根据约束条件画出可行域，它是抛物线段ABCD分析：令动点从A出发沿抛物线ABCD移动，当动点从A移向B时，目标函数值下降；当动点由B移向C时，目标函数值上升。从而可知，在可行域AC这一范围内，B点的目标函数值f(B)最小，因而点B是一个极小点。当动点由C向D移动时，目标函数值再次下降，在D点(其坐标为(4，1))目标函数值最小。二维问题的图解目标函数值f(B)仅是目标函数f(X)在一部分可行域上的极小值，而不是在整个可行域上的极小值，这样的极小值称为局部极小值(或相对极小值)。像B这样的点称为局部极小点(或相对极小点)。f(D)是整个可行域上的极小值，称全局极小值(最小值)，或绝对极小值；像D这样的点称全局极小点(最小点)，或绝对极小点。全局极小点当然也是局部极小点，但局部极小点不一定是全局极小点。1x1x212354O0ABCD几个定义设f(X)为定义在n维欧氏空间En的某一区域R上的n元实函数(可记为f(X):REn→E1)，对于X*∈R，如果存在某个ε＞0，使所有与X*的距离小于ε的X∈R(即X∈R且‖X-X*‖＜ε)，都有f(X)≥f(X*)，则称X*为f(X)在R上的局部极小点，f(X*)为局部极小值。若对于所有X≠X*且与X*的距离小于ε的X∈R，都有f(X)＞f(X*)，则称X*为f(X)在R上的严格局部极小点，f(X*)为严格局部极小值。局部极小：几个定义设f(X)为定义在En的某一区域R上的n元实函数，若存在X*∈R，对所有X∈R都有f(X)≥f(X*)，则称X*为f(X)在R上的全局极小点，f(X*)为全局极小值。若对于所有X∈R且X≠X*，都有f(X)＞f(X*)，则称X*为f(X)在R上的严格全局极小点，f(X*)为严格全局极小值。全局极小：多元函数极值点存在的条件二阶可微的一元函数f(x)极值点存在的条件如下：必要条件：充分条件：对于极小点：且对于极大点：且0)(fx0)(fx0)(fx0)(fx0(x)f多元函数极值点存在的条件对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数极值点的相应条件类似。1.必要条件下述定理1给出了n元实函数f(X)在X*点取得极值的必要条件。定理1：设R是n维欧氏空间En上的某一开集，f(X)在R上有连续一阶偏导数，且在点X*∈R取得局部极值，则必有***12()()()...0nfXfXfXxxx或写成：*()0fX其中，****12()()()()(,,...,)TnfXfXfXfXxxx为函数f(X)在点X*处的梯度。多元函数极值点存在的条件函数f(X)的梯度▽f(X)有十分重要的性质：梯度向量的方向是函数值(在该点处)增加最快的方向，而负梯度方向则是函数值(在该点处)减少最快的方向。多元函数极值点存在的条件多元函数的泰勒(Taylor)公式设n元实函数f(X)在X(0)的某一邻域内有连续二阶偏导数，则可写出它在X(0)处的泰勒展开式如下：(0)(0)(0)(0)2(0)1()()()()()()()2TTfXfXfXXXXXfXXX其中，X=X(0)+θ(X-X(0)),0＜θ＜1多元函数极值点存在的条件多元函数的泰勒(Taylor)公式也可以写成：(0)(0)(0)(0)2(0)1()()()()()()()2TTfXfXfXXXXXfXXX2(0)(())XX其中，当X→X(0)时，o(‖X-X(0)‖2)是‖X-X(0)‖2的高阶无穷小，即：(0)2(0)2(0)()lim0XXXXXX多元函数极值点存在的条件多元函数的泰勒(Taylor)公式若以X=X(0)+P代入，则变为:(0)(0)(0)21()()()()2TTfXPfXfXPPfXP其中，X=X(0)+θP凸函数和凹函数设f(X)为定义在n维欧氏空间En中某个凸集Rc上的函数，若对任何实数α(0＜α＜1)以及Rc中的任意两点X(1)和X(2)，恒有f(αX(1)+(1-α)X(2))≤αf(X(1))+(1-α)f(X(2))则称f(X)为定义在Rc上的凸函数。对每一个α(0＜α＜1)和任意两点X(1)≠X(2)∈Rc，恒有f(αX(1)+(1-α)X(2))＜αf(X(1))+(1-α)f(X(2))则称f(X)为定义在Rc上的严格凸函数。反之即可得到凹函数和严格凹函数的定义。显然，若函数f(X)=-g(X)是凸函数(严格凸函数)，则g(X)一定是凹函数(严格凹函数)。定义：凸函数和凹函数凸函数的性质性质1设f(X)为定义在凸集Rc上的凸函数，则对任意实数β≥0，函数βf(X)也是定义在Rc上的凸函数。性质2设f1(X)和f2(X)为定义在凸集Rc上的两个凸函数，则这两个凸函数的和f(X)=f1(X)+f2(X)仍为定义在Rc上的凸函数。推论：有限个凸函数的非负线性组合β1f1(X)+β2f2(X)+…+βmfm(X)βi≥0（i=1,2,…,m）仍为凸函数。性质3设f(X)为定义在凸集Rc上的凸函数，则对每一实数β，集合(称为水平集)Sβ={X｜X∈Rc,f(X)≤β}是凸集。凸函数和凹函数凸函数的判定要判定一个函数是不是凸函数，可直接依据定义；对于可微凸函数，也可利用下述条件。一阶条件设Rc为En上的开凸集，f(X)在Rc上可微，则f(X)为Rc上的凸函数的充要条件是：对任意两点X(1)∈Rc和X(2)∈Rc，恒有f(X(2))≥f(X(1))+▽f(X(1))T(X(2)-X(1))若上式为严格不等式，它就是严格凸函数的充要条件。如将上式中的不等号反向，就可得到凹函数(严格不等号时为严格凹函数)的充要条件。凸函数和凹函数**()()0TfXXX凸函数的极值：设f(X)是定义在凸集Rc上的可微凸函数，如果存在点X*∈Rc，使得对于所有的X∈Rc，都有：则X*就是f(X)在Rc上的最小点(全局极小点)。*()0fX凸函数和凹函数现考虑非线性规划式：若其中的f(X)为凸函数，gj(X)(j=1,2,…，l)全是凹函数(即所有-gj(X)全为凸函数)，就称这种规划为凸规划。min()()0(1,2,...,)jfXgXjl凸规划凸函数和凹函数(1)可行解集为凸集。(2)最优解集为凸集(假定最优解存在)。(3)任何局部最优解也是其全局最优解。(4)若目标函数为严格凸函数，且最优解存在，则其最优解必惟一。凸规划的性质：凸函数和凹函数下降迭代算法：迭代法的基本思想是：我们并不期望一下子就能找到函数的最优点，而是从最优点的某一个初始估计X(0)出发，按照一定的规则(即所谓算法)，先找一个比X(0)更好的点X(1)(对极小化问题来说，f(X(1))比f(X(0))更小；对极大化问题来说，f(X(1))比f(X(0))更大)，再找比X(1)更好的点X(2)，…，如此继续，就产生了一个解点的序列{X(k)}。若该点列有一极限点X*，即()*lim0kkXX就称该点列收敛于X*。对于某一算法来说，我们要求它产生的点列{X(k)}中的某一点本身就是最优点，或者该点列的极限点X*是问题的最优点。非线性规划•基本概念•无约束极值问题•约束极值问题第1节最优性条件min()()0,1,2,,()0,1,2,,ijfXhXimgXjlmin()()0,1,2,,jfXgXjlmin(),()0,1,2,,jfXXREnRXgXjl大多数极值问题其变量的取值都会受到一定限制，这种限制由约束条件来体现。带有约束条件的极值问题称为约束极值问题。非线性规划的一般形式为或问题(7-2)也常写成(7-1)(7-2)(7-3)第1节最优性条件()(1,2,,;1,2,,)jgXimjl(0)X()0jgX(0)X()0jgX(0)X(0)X(0)X(0)()0jgX(0)X(0)X(0)X1.1起作用约束和可行下降方向的概念现考虑上述一般非线性规划，假定f(X)、hi(X)和具有一阶连续偏导数。设是非线性规划的一个可行解。现考虑某一不等式约束条件满足它有两种可能：其一为，这时，点不是处于由这一约束条件形成的可行域边界上，因而这一约束对点的微小摄动不起限制作用，从而称这个约束条件是点的不起作用约束(或无效约束)；其二是，这时点处于该约束条件形成的可行域边界上，它对的摄动起到了某种限制作用，故称这个约束是点的起作用约束(有效约束)。显而易见，等式约束对所有可行点来说都是起作用约束。第1节最优性条件0λ00λ0,λ(0)λXDR假定X(0)是非线性规划(7-3)式的一个可行点，现考虑此点的某一方向D，若存在实数，使对任意均有就称方向D是X(0)点的一个可行方向。第1节最优性条件()0jgX(0)T()0,jgXDjJ(0)(0)(0)T(λ)()λ()(λ)jjjgXDgXgXDo(0)T()0,jgXDjJ(0)(λ)0,jgXDjJ若D是可行点X(0)处的任一可行方向，则对该点的所有起作用约束均有其中J为这个点所有起作用约束下标的集合。另一方面，由泰勒公式对所有起作用约束，当λ0足够小时，只要就有此外，对X(0)点的不起作用约束，由约束函数的连续性，当λ