ch3凹函数与非线性规划

第3章凹函数与非线性规划3.1向量和子空间投影定理3.2多元函数及其导数3.3数学规划模型的一般形式3.4凸集、凸函数和凸规划3.5非线性规划3.6海赛（Hessian）矩阵与二次型3.7更一般的提法及其在经济中的应用3.1向量和子空间投影定理(1)n维欧氏空间：Rn

点（向量）：x

Rn,x=(x1,x2,…,xn)T

分量xi

R(实数集)

方向（自由向量）：d

Rn,d0d=(d1,d2,…,dn)T

表示从0指向d的方向实用中，常用x+d表示从x点出发沿d方向移动d长度得到的点d0xx+(1/2)d3.1向量和子空间投影定理(2)向量运算：x,y

Rn

n

x,y的内积：xTy=xiyi=x1y1+x2y2+…+xnyn

i=1

x,y的距离：

‖x-y‖=[(x-y)T(x-y)](1/2)

x的长度：

‖x‖=[xTx](1/2)

三角不等式：

‖x+y‖≤‖x‖＋‖y‖

点列的收敛：设点列｛x(k)｝Rn

,xRn

点列｛x(k)｝收敛到x，记limx(k)=x

lim‖x(k)-x‖=0limxi(k)=xi,ikkkx+yyx3.1向量和子空间投影定理(3)子空间：设

d(1),d(2),…,d(m)

Rn,d(k)

0

m

记L(d(1),d(2),…,d(m))={x=

jd(j)

jR

}

j=1为由向量d(1),d(2),…,d(m)

生成的子空间，简记为L。正交子空间：设L

为Rn的子空间，其正交子空间为

L＝{xRn

xTy=0,

yL

}子空间投影定理：设L为Rn的子空间。那么

xRn，唯一xL,yL,使z=x+y,且x为问题

min‖z-u‖s.t.uL的唯一解，最优值为‖y‖。特别，L

＝Rn时，正交子空间L＝{0}（零空间）3.1向量和子空间投影定理规定：x,y

Rn，x≤yxi≤

yi，i

类似规定x≥y，x=y，x<y,x>y.一个有用的定理设xRn，R，L为Rn

的线性子空间，

(1)若xTy≤,

yRn

且y≥

0，

则x≤0，≥

0.(2)若xTy≤,

yLRn

，

则xL，≥

0.(特别,

L＝Rn时,x=0)定理的其他形式：“若xTy≤,

yRn

且y≤

0，则x≥0，≥

0.”“若xTy≥,

yRn

且y≥

0，则x≥0，≤

0.”“若xTy≥,

yRn

且y≤

0，则x≤0，≤

0.”“若xTy≥,

yLRn

，则xL，≤

0.”3.2多元函数及其导数(1)n元函数：f(x):Rn

R

线性函数：f(x)=cTx+b=cixi

+b

二次函数：f(x)=(1/2)xTQx+cTx+b=(1/2)ijaijxixj

+cixi

+b

向量值线性函数：F(x)=Ax+dRm其中A为mn矩阵，d为m维向量

F(x)=(f1(x),f2(x),…,fm(x))T记aiT为A的第i行向量，fi(x)=aiTx3.2多元函数及其导数(2)梯度（一阶偏导数向量）：

f(x)＝(f/x1,f/x2,…,f/xn)TRn

.

线性函数：f(x)=cTx+b,

f(x)=c

二次函数：f(x)=(1/2)xTQx+cTx+b

f(x)=Qx+c

向量值线性函数：F(x)=Ax+dRmF/x=AT3.2多元函数及其导数(3)Hesse阵（二阶偏导数矩阵）：

2f/x12

2f/x2x1

…2f/xnx1

2f(x)=

2f/x1x2

2f/x22

…2f/xnx2

…

…

……

2f/x1xn

2f/x2xn

…2f/xn2

线性函数：f(x)=cTx+b,

2f(x)=0

二次函数：f(x)=(1/2)xTQx+cTx+b,

2f(x)=Q3.2多元函数及其导数(4)n元函数的Taylor展开式及中值公式：

设f(x):Rn

R

，二阶可导。在x*的邻域内一阶Taylor展开式：

f(x)=f(x*)+fT(x*)(x-x*)+o‖x-x*‖二阶Taylor展开式：

f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x*)(x-x*)+o‖x-x*‖2一阶中值公式：对x,,使

f(x)=f(x*)+［f(x*+(x-x*))]T(x-x*)Lagrange余项：对x,,记xx*+(x-x*)

f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x)(x-x*)3.3数学规划模型的一般形式

maxf(x)

--------目标函数

s.t.xS

--------约束集合，可行集其中，SRn，f:SR，xS称（fS)的可行解最优解:x*S，满足f(x*)≤f(x),xS。则称

x*为(fS)的全局最优解(最优解),

记g.opt.(globaloptimum),简记opt.最优值:x*为(fS)的最优解,则称f*=f(x*)

为

(fS)的最优值(最优目标函数值)(fS)3.3数学规划模型的一般形式（续）局部最优解:x*S，x*的邻域N(x*)，使满足

f(x*)≤f(x),xSN(x*)

。则称x*为(fS)的局部最优解,记l.opt.(localoptimum)在上述定义中，当xx*时有严格不等式成立，则分别称x*

为(fS)的严格全局最优解和严格局部最优解。严格l.opt.严格g.opt.l.opt.3.3数学规划模型的一般形式（续）函数形式:

f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)

≤0,i=1,2,…,m

hj(x)=0,j=1,2,…,l矩阵形式:minf(x)，f(x)

:RnR(fgh)s.t.g(x)

≤0,g(x):RnRm

h(x)=0,h(x):RnRl

当f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。3.4凸集、凸函数和凸规划一、凸集1、凸集的概念：定义：设集合SRn，若x(1),x(2)S,[0,1]，必有

x(1)＋(1-)x(2)S，则称S为凸集。规定：单点集{x}为凸集，空集为凸集。注:x(1)＋(1-)x(2)=x(2)＋(x(1)-x(2))

是连接x(1)与x(2)的线段。凸集非凸集非凸集3.4凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：例:证明集合S={x∣Ax=b}是凸集。其中，A为mn矩阵，b为m维向量。凸组合：设

x(1),x(2),…,x(m)

Rn,j≥

0

mm

j=1,那么称

jx(j)为x(1),x(2),…,x(m)的

j=1j=1凸组合。

m比较:z=

jx(j)

j=1jR

—

构成线性组合——

线性子空间j≥0,

j>0—

构成半正组合——

凸锥j≥0,

j=0—

构成凸组合——

凸集3.4凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：定理：S是凸集S中任意有限点的凸组合属于S多胞形H(x(1),x(2),…,x(m))：由x(1),x(2),…,x(m)的所有凸组合构成。单纯形：若多胞形H(x(1),x(2),…,x(m))满足，

x(2)-x(1),x(3)-x(1),…,x(m)-

x(1)

线性无关。多胞形单纯形单纯形3.4凸集、凸函数和凸规划(续)一、凸集

2、凸集的性质：凸集的交集是凸集；（并？）凸集的内点集是凸集；（逆命题是否成立？）凸集的闭包是凸集。（逆命题是否成立？）分离与支撑：凸集边界上任意点存在支撑超平面两个互相不交的凸集之间存在分离超平面支撑强分离分离非正常分离3.4凸集、凸函数和凸规划(续)一、凸集3、凸锥：定义：C

Rn,若xC,>0

有xC,则称C是以0为顶点的锥。如果C还是凸集，则称为凸锥。集合{0}、Rn是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S03.4凸集、凸函数和凸规划(续)二、凸函数

1、凸函数及水平集定义:设集合SRn为凸集，函数f:SR

若x(1),x(2)S,(0,1)，均有

f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数3.4凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数，设1,2>0,1f1+2f2,1f1-2f2是否凸函数？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？

3.4凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定义：设集合SRn

，函数f:SR，R

，称S={xS∣f(x)≤

}

为f(x)

在S上的水平集。定理：设集合SRn

是凸集，函数f:SR是凸函数，则对R

，S

是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x≥0)或0(x<0)，函数非凸，但任意水平集是凸集。3.4凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：方向导数：设S

Rn为非空凸集，函数f:SR，再设x*

S,d为方向，使当

>0

充分小时有x*+d

S,

如果

lim

[f(x*+d)-f(x*)]/

存在（包括）

则称f(x)为在点沿方向的方向导数存在，记

f`(x*;d)=lim

[f(x*+d)-f(x*)]/

若f(x)在x*可导，则f`(x*;d)=[f(x*)]Td.3.4凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：以下设S

Rn为非空凸集，函数f:SR2）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。

例:f(x)＝2(当x=1)；f(x)＝x2(当x<1).

3）设f凸，则对任意方向方向导数存在。4）设S是开集，f在S上可微，则

f凸x*S，有f(x)≥f(x*)+fT(x*)(x-x*),xS.5)设S是开集，f在S上二次可微，则

a)

f凸xS，2f(x)半正定；

b)若xS，2f(x)正定，则f严格凸。3.4凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：例：

f(x)＝x12+2x1x2+2x22+10x1-4；

f(x)＝-3x12+x1x2-x22-2x32-2x2x3+26;

f(x)＝3x12+ax1x2+2x22-4x1+6(a=5,4.5)；3.4凸集、凸函数和凸规划(续)三、凸规划：当（fS）中，S为凸集，f是S上的凸函数（求min），称（fS）为凸规划；对于（fgh）,f,gi为凸函数，hj为线性函数时，（fgh）为凸规划。定理：设集合S

Rn为凸集，函数f:SRf(x)为凸集S上的凸函数。X*为问题（fs）的l.opt，则X*为g.opt；又如果f是严格凸函数，那么X*是（fs）的唯一g.opt。3.5非线性规划若目标函数或约束条件中至少有一个是变量的非线性函数，称这类规划问题为非线性规划问题（NonlinearProgramming;NP）。非线性规划的系统研究始于上个世纪四十年代末，1951年Kuhn和Tucker提出了著名的Kuhn-Tucker条件，加上电子计算机的迅速发展，使得非线性规划无论在基本理论还是实用算法都有了长足的发展，使之逐渐成为运筹学的一个非常重要的分支。特别是非线性规划问题对于目标函数和约束条件几乎没有任何限制，使得非线性规划越来越广泛地应用于经济管理、最优设计等各个领域。一般地，非线性规划（NP）问题的数学模型可表述其中，

是欧氏空间

中的向量。

以上（NP）模型称为非线性规划的一般形式。乘上“-1”即可将这种不等式的约束变成“”的形式。若模型的目标函数为极大化时，则可将其负值极小化;若若某个约束条件是“”形式，则只需要将不等式两端为3.5非线性规划又因为等式约束等价于以下两个不等式约束所以，非线性规划问题的数学模型又可写成3.5非线性规划例1考虑非线性规划问题图13.5非线性规划目标函数f(X)是旋转抛物面，约束条件是一个平面和一个抛物柱面所围部分。虽然它们的图形都可以画出来，但使用起来并不方便，所以常将它们表示在某一个平面上。若令f(X)=C（常数）表示相等的目标函数值的集合。一般地它表示一条曲线或一张曲面，通常称为等值线或等值面。如令

f(X)为4或20，便得到两条圆形等值线，如图1。半径越大的等值线，其上的点对应的目标函数值越大。由图1可知，该问题的可行域是抛物线段ABCD。3.5非线性规划注1：我们令动点从A点出发沿抛物线ABCD移动，动点从A点移动到B时，目标函数值减小。当动点从B点移动到C点时，目标函数值最大。由此可知，在可行域ABC这一范围内，B点的目标函数值最小，即B点是一个极小值点。而当动点从C点移动到D点时，目目标函数值又逐渐减小，且在D点的目标函数值值最小。这里，点B只是一部分可行域上的极小值点，称为局部极小点（或相对极小点），对应的目标函数值称为局部极小值（相对极小值）。而D点则是整个可行域上的极小值点，称为全局极小值点（最小值点）或绝对极小点，对应的目标函数值称为全局极小值（最小值）或绝对极小值。注2：约束条件自然对最优解是有影响的。若不考虑约束条件，便是无约束问题。它的最优解为x1*=2,x2*=1,f(X*)=0.3.5非线性规划定义1设f(X)为定义在n维欧氏空间En上的某一区域上R的n元实函数，X=(x1,x2,xn)T

。若f(X)在R上可微，令（1）则f(X)

称为f(X)的梯度向量，亦记作gradf。3.6海赛（Hessian）矩阵与二次型性质1函数f(X)在某点X*

处的梯度f(X)

（f(X)0）必与函数过该点的等值面（f(X)

=f(X*)的切平面垂直。性质2沿梯度的方向，函数值增加得最快，即该方向上函数变化率最大，而负梯度方向则是函数值减小最快的方向。3.6海赛（Hessian）矩阵与二次型为函数f(X)在X*点处的梯度。若在考察的区域内梯度是连续的，则有以下两个性质。特别地，称定义2设R是n维欧氏空间En上的某一开集，函数f(X)在R上具有连续的二阶偏导数，令（2）则称H(X)为函数f(X)的海赛矩阵（HessianMatrix）,亦记为2f(X)。3.6海赛（Hessian）矩阵与二次型注1：当f(X)的二阶混合偏导数连续时，二阶混合偏导数与取导数的顺序无关，即因而H(X)为对称矩阵。3.6海赛（Hessian）矩阵与二次型例如：设则梯度向量和海赛矩阵分别为：和定义3称n元二次齐次函数（3）为n元二次型。其中矩阵A=(aij)nn为对称矩阵。若A中所有元素均为实数，则该二次型为实二次型。

3.6海赛（Hessian）矩阵与二次型定义4设有实二次型f(X)=XTAX，(1)

若对任意X0，恒有f(X)<0，则称f(A)为负定二次型（或称f(X)为负定的），对应的矩阵A为负定矩阵；

(2)若对任意X0，恒有f(X)0，则称f(A)为半正定的（或称f(X)为非负定的），对应的矩阵A为半正定矩阵；(3)若对任意X0，恒有f(X)0，则称f(A)为半负定的（或称f(X)为非正定的），对应的矩阵A为半负定矩阵；(4)若存在某些X0

，有f(X)>0

，又存在某些X0

，有f(X)<0

，则称f(X)为不定的，对应的矩阵A为不定矩阵。3.6海赛（Hessian）矩阵与二次型注1：实二次型f(X)=XTAX为正定的充要条件是矩阵A的各阶顺序主子式均大于零，即注2：实二次型f(X)=XTAX

为负定的充要条件是阵A的各阶顺序主子式正负交替出现，即3.6海赛（Hessian）矩阵与二次型为正定矩阵。是正定二次型，对应的矩阵例如是负定二次型，对应的矩阵是负定矩阵。例如例

判定非线性函数的海赛矩阵H(X)的正定性。解：因为所以海赛矩阵H(X)正定。3.6海赛（Hessian）矩阵与二次型例

判定二次型的正定性。解：因为二次型的矩阵为所以A为负定的，故二次型为负定二次型。二次型的有定性在极值判定中的应用：显然，（1）若f(x1,x2,,xn)为正定（半正定）二次型，所以是的极小值；3.6海赛（Hessian）矩阵与二次型是的极大值；（2）若f(x1,x2,,xn)为负定（半负定）二次型，显然，所以二次型的有定性在极值判定中的应用：3.6海赛（Hessian）矩阵与二次型（3）若f(x1,x2,,xn)为不定二次型，显然不是的极值。3.6海赛（Hessian）矩阵与二次型二次型的有定性在极值判定中的应用：3.7更一般的提法及其在经济中的应用前面的各种说法在一般的高等数学中基本都能见到，为了使这些理论适合更一般地情况，在很多书上会用更抽象的表述方式。因此，本课程在将通俗的提法介绍完之后，本节给各位讲解一个在读或写论文中较为常见但却不易看懂的表述模式。实质上二者是一致的，希望各位能将它们联系起来，这样有利于对内容的深入理解，以便于将来的应用。3.7.1非线性规划“数学规划”或者“非线性规划”（NLP)是指求解约束优化问题的一些方法。一般地，最基本的规划问题可以表示为：

max{f(x;

)；x

C()｝(P)

x也就是说，给定某个参数，我们求解x使得f(·;

)在集合C()中取到极大值。在这个表达式中：．x=（x1，…，xn）

X

Rn称为决策变量(DecisionVariables)或者选择变量(ChoiceVariables)；3.7.1非线性规划一些解释（1）令表示所有可能的“环境”的集合，消费者在这些环境中都可以发现自己，参数的一个取值表示一个环境，令X表示消费者可以采取的行为的集合。给定的取值，消费者会发现他的选择被限制到X的某个子集C中（例如，消费者理论中的预算集）。=(1,…,p)Rp是给定数值的参数(Parameter)向量；C()X称为约束集(ConstraintSet)或可行集(FeasibleSet)它是对于给定的参数所有可行的x的集合；f是实值函数f

:Rn+p

XR，通常称为目标函数(ObjectiveFunction).（2）随着参数的改变，可行集也会改变，这可以表示为约束对应(ConstraintCorrespondence）C：

X。（3）函数f,X

R是消费者的目标函数f(x;)表示当消费者面对环境且采取行动x时消费者的支付。理性的消费者会选择一个最优的计划，所谓最优计划是指对于给定的参数值在约束集中使得目标函数取到极大值的点。最优行动的集合称为决策规则（DecisionRule)或者最佳反应对应S()：3.7.1非线性规划3.7.1非线性规划S：

X，其中S()=argmax{f(x;

);xC()｝

x即S()是由(P)的最优解x*组成的集合。若对的每个取值，(P)的解是惟一的，则这个对应变成一个函数，记为x*=x()。最优化的消费者的支付通过一个（极大）值函数V给出，V：

R定义为：V()=max{f(x;

);xC()｝=f(x*;

),其中x*S()x

给定参数向量的取值，V()给出了可得到的最高支付。显然,V()等于对于给定的目标函数f()在最优解x*处的函数值。在许多经济应用中，我们感兴趣的是比较静态和决策规则的性质。

：3.7.1非线性规划也就是说，我们希望知道，当环境（他面对的价格、他的收等）变化时消费者的行为将如何改变。arg是元素（变元）的英文缩写。

argmin就是使后面这个式子达到最小值时的x，t的取值

argmax就是使后面这个式子达到最大值时的x，t的取值S()=argmax{f(x;

);xC()｝x根据可行集的不同，我们考虑三种不同的规划问题：凸约束集（ConvexConstraintSet）

C是Rn中的凸集；特别的情形，没有约束的极大化，这里我们将C看成是整个Rn，以及另一种情形，极大值需满足非负的约束，即可行集就是Rn中的非负集合。拉格朗日问题(LagrangeProblem)

约束集是由等式约束组成的集合：3.7.1非线性规划库恩-塔克问题(Kuhn-TuckerProblem)

约束集是由一些不等式约束组成的集合：C()={xX;g(x;

)=0｝

C()={xX;g(x;

)0｝

3.7.2凸约束优化问题考虑问题：其中，C是Rn中的凸集，f：RnXR是C2函数。因为我们所关心的是对于给定的问题(P.C)的解，所以在讨论中可以省去参数。max{f(x);xC｝

x我们对这个问题的特别情形很熟悉。若C=Rn,则x*是f的极大点的必要条件是Df(x*)=0

。但在一般情形中，关于极大点这个条件既不是必要的也不是充分的。在图3.1给出了这样的例子。图3.1导数为0既不是最大点的必要条件也不是充分条件3.7.2凸约束优化问题3.7.2凸约束优化问题严格局部极大值。定理3.5

整体唯一性令x*是问题(P.C)的最优解，C是凸集。若f是严格拟凹函数，则x*是唯一的最优解。3.7.2凸约束优化问题问题7.1.12