东北财经大学：《运筹学》课程教学资源（教案讲义）第三篇 非线性规划 第一章 凸分析基础

第三篇非线性规划 第一章凸分析基础 §1非线性规划的一般形式 (一)非线性规划的例子 在决策和物理等科学中常常提出含有非线性函数的优化问题,请看下面的几个例子。 例1、某饲养场拟建一排五间的猪舍,平面布置如图1所示。由于资金及材料的限制,围墙和 隔墙的总长度不能超过54米,为使猪舍面积最大,应如何选择长宽尺寸? 设猪舍长为x1米,宽为x2米。根据题意,变量x1、x2应满足约束条件 2x1+6x2≤54 x1≥0,x2≥0 我们的目标是使总面积最大,即 max(x 2 于是化为如下规划问题 2x1+6x,≤54 x≥0,x2≥0 这里与线性规划不同的是,目标函数 f(x,x2)=xx2 是关于变量x12x2的非线性函数 例2、(确定经验公式)在经济或物理学中经常要根据实际或实验的观测值来确定出各种量之间 关系的公式来(称为经验公式)。假设变量Q随时间t变化,根据观测,我们得到如下一组数据及坐 标纸上的点(图2) t ee e2 e3 O 152

152 第三篇 非线性规划 第一章 凸分析基础 §1.非线性规划的一般形式 （一）非线性规划的例子 在决策和物理等科学中常常提出含有非线性函数的优化问题，请看下面的几个例子。 例 1、某饲养场拟建一排五间的猪舍，平面布置如图 1 所示。由于资金及材料的限制，围墙和 隔墙的总长度不能超过 54 米，为使猪舍面积最大，应如何选择长宽尺寸？ 1 x 2 x 图 1 设猪舍长为 1 x 米，宽为 2 x 米。根据题意，变量 1 x 、 2 x 应满足约束条件 1 2 1 2 2 6 54 0, 0 x x x x +    我们的目标是使总面积最大，即 max x x ( 1 2 ) 于是化为如下规划问题： ( 1 2 ) 1 2 1 2 2 6 54 0, 0 max x x x x x x +    这里与线性规划不同的是，目标函数 1 2 1 2 f x x x x ( , ) = 是关于变量 1 2 x x, 的非线性函数。 例 2、（确定经验公式）在经济或物理学中经常要根据实际或实验的观测值来确定出各种量之间 关系的公式来（称为经验公式）。假设变量 Q 随时间 t 变化，根据观测，我们得到如下一组数据及坐 标纸上的点（图 2）。 t 1 t 2 t 3 t i t m t Q Q1 Q2 Q3 Qi Qm

图2 注意随着时间的延伸,量Q的变化趋于平稳(即近似为常数),我们可以设想从如下形式的曲 线中找出一条曲线作为它的近似: x -xe 其中x1、x2、x为参数,根据图2可要求x、x2、x3>0,并希望 ne=0 (1) 实际上,由于观测数据有误差,当m>3时,不管如何选择x、x2、x3,(1)式一般都不会成立。 只能退而求其次,即选择那样的x、x2、巧使得由(1)算得的理论值与实际值尽量接近。通常大 多采用最小平方和意义下的求解方法。即求解如下的规划问题 m∑Q-(x-x2e)2 (2) x1x2,x3>0 (2)中的目标函数也是非线性的 例3、(最优存贮问题)设各种商品的年需求量为D,l=1…,n,为节约资金,减少存贮量,宜 分批进货。已知每次订货费为C1,年单位存贮费为C2,仓库容量为0,各种产品的单位价格为P, 希望存贮和订货的总费用不超过f°,问如何安排批量Q,使之占用的资金总额S最少 容易看出,占用资金总额等于年均存贮量(/2)与价格之积 而总费用为订货费与存贮费之和 分3, 若用v表示单位第i中材料所占用仓库容量,则有如下的模型:

153 1 t 2 t m 0 t t Q 图 2 注意随着时间的延伸，量 Q 的变化趋于平稳（即近似为常数），我们可以设想从如下形式的曲 线中找出一条曲线作为它的近似： 3 1 2 { } x t x x e − + − 其中 1 x 、 2 x 、 3 x 为参数，根据图 2 可要求 1 x 、 2 x 、 3 x >0，并希望 3 1 2 , 1, , i x t i x x e Q i m − − = = （1） 实际上，由于观测数据有误差，当 m>3 时，不管如何选择 1 x 、 2 x 、 3 x ，（1）式一般都不会成立。 只能退而求其次，即选择那样的 1 x 、 2 x 、 3 x 使得由（1）算得的理论值与实际值尽量接近。通常大 多采用最小平方和意义下的求解方法。即求解如下的规划问题： 3 2 1 2 1 1 2 3 [ ( )] , , 0 i m x t i i min Q x x e x x x − =   − −      （2） （2）中的目标函数也是非线性的。 例 3、（最优存贮问题）设各种商品的年需求量为 , 1, , D i n i = ，为节约资金，减少存贮量，宜 分批进货。已知每次订货费为 C1i ，年单位存贮费为 C2i ，仓库容量为 0 V ，各种产品的单位价格为 Pi ， 希望存贮和订货的总费用不超过 0 f ，问如何安排批量 Qi ，使之占用的资金总额 S 最少。 容易看出，占用资金总额等于年均存贮量 ( ) 2 Qi 与价格之积： 1 2 n i i i PQ S = =  而总费用为订货费与存贮费之和： 1 2 1 ( ) 2 n i i i i i i D Q f C C = Q = +  若用 i v 表示单位第 i 中材料所占用仓库容量，则有如下的模型：

min s= D ∑vQ≤ Q≥0,i=1,2,…,n (3)中的一个约束函数∑(、D+C2)是非线性的 (二)一般形式 上面叙述的几个例子都是求一组变量,例如n个变量x,x2…xn,使其在满足由一些等式或不 等式所限定的约束条件下,求某一个目标函数∫(x,x2,…xn)的最大值或最小值。并且,其中目标 函数和约束函数里至少有一个是非线性的。这样的规划问题称为非线性规划。它的一般形式为: min f(x) 81(x < (4) h(x)=0,j=1…,l 其中x∈R",f,8,h都是多元函数:R”→R,它们中至少有一个是非线性的。记(4)的可行解 集为S S={xg(x)≤0.,=1,…,mh(x)=0,J=1,…,l} (5) 则(4)可简写成 min f(x) (6) x∈ScRn 求极大可以转换成求极小 max f(x)=-mink-f(x)] 众所周知,整个世界在本质上是非线性的,因此实际中的非线性规划问题相对的要比线性规划 问题更多、更普遍,也更复杂。因此,对它们的研究也显得更重要。非线性规划,又称最优化方法, 其实际应用很广泛,主要表现在以下几个方面: A最有控制,B结构设计,C机械设计,D电子网络,E水资源管理,F随机资源分配,G设施 位置确定等 (三)最优解 关于最优解,有以下定义 定义1、设∫:ScR"→R,x∈S,若存在数>0,x∈O(x,d)∩S,都有 f(x)≤f(x) (7) 则称x为∫(x)的局部最优解。其中O(x',δ)是x的δ_邻域。特别如果对于x≠x,都有

154 1 0 1 2 1 0 1 2 . . ( ) 2 0, 1,2, , n i i i n i i i i i i n i i i i PQ min S D Q s t C C f Q v Q V Q i n = = =  =     +          =    （3） （3）中的一个约束函数 1 2 1 ( ) 2 n i i i i i i D Q C C = Q  + 是非线性的。 （二）一般形式 上面叙述的几个例子都是求一组变量，例如 n 个变量 1 2 , , , n x x x ，使其在满足由一些等式或不 等式所限定的约束条件下，求某一个目标函数 1 2 ( , , , )n f x x x 的最大值或最小值。并且，其中目标 函数和约束函数里至少有一个是非线性的。这样的规划问题称为非线性规划。它的一般形式为： ( ) . . ( ) 0, 1, , ( ) 0, 1, , i j min f x s t g x i m h x j l     =  = =  （4） 其中 n x R  ， , ,i j f g h 都是多元函数： n R R → ，它们中至少有一个是非线性的。记（4）的可行解 集为 S ： { | ( ) 0, 1, , , ( ) 0, 1, , } S x g x i m h x j l =  = = = i j （5） 则（4）可简写成 ( ) n min f x x S R   （6） 求极大可以转换成求极小： max ( ) min[ ( )] x S x S f x f x   = − − 众所周知，整个世界在本质上是非线性的，因此实际中的非线性规划问题相对的要比线性规划 问题更多、更普遍，也更复杂。因此，对它们的研究也显得更重要。非线性规划，又称最优化方法， 其实际应用很广泛，主要表现在以下几个方面： A 最有控制，B 结构设计，C 机械设计，D 电子网络，E 水资源管理，F 随机资源分配，G 设施 位置确定等。 （三）最优解 关于最优解，有以下定义。 定义 1、设 : n f S R R  → ， x S   ，若存在数   0， x O x S ( , )      ，都有 f x f x ( ) ( )   （7） 则称 x  为 f x( ) 的局部最优解。其中 O x( , )   是 x  的  _邻域。特别如果对于 x x   ，都有

f(x<f(x), xEO(,Ons (8) 则称x为∫(x)的严格局部极小点或严格局部最优解。 若(⑦)式对Ⅴx∈S都成立,则称x为全局(或整体)极小点或全局最优解。若(8)式对Ⅵx∈S x≠x都成立,则称x*为严格全局极小点 实际问题都是求全局极小点,但目前大多都是用求局部极小点近似代替之。 §2多元函数和向量值函数 在微积分中已介绍过多元函数。例如对二元函数a=f(x)=f(x12x2),其可微性定义为 △=f(x+△x,x2+△x2)-f(x42,x2) A△x1+BAx2+O (9) 上式可等价的写成 △M=LP+o(P") (9) 其中L=(A,By,P=(Ax,Ax2y,叫=A+Ax,(9)及(9)的含义是 dy vonn (r+Ar, x,+Ax2,)-f(x x%)-(AAx+ BAx2) 2→0 △x2+Ax2 f(x+P)-f(x°)-LP m 0 据此,对多元函数a=f(x)=f(x1…xn),自然可以给出如下形式的可微性定义: 定义2:设f:ScR"→R,且x°∈S,如果存在L∈R",VP∈R"都有 f(x+P)-f(x°)-LP (10) 成立,则称∫(x)在x°可微 (有的文献称上述可微性为F-可微,还有所谓G-可微:Vh≠0,h∈R",t∈R, mf(x+h)-/(x)-m=0 由F可微→G_可微,反之则不然)。(10)的等价形式为 55

155 f x f x ( ) ( )   ， x O x S ( , )     （8） 则称 x  为 f x( ) 的严格局部极小点或严格局部最优解。 若（7）式对  x S 都成立，则称 x  为全局（或整体）极小点或全局最优解。若（8）式对  x S ， x x   都成立，则称 x  为严格全局极小点。 实际问题都是求全局极小点，但目前大多都是用求局部极小点近似代替之。 §2.多元函数和向量值函数 在微积分中已介绍过多元函数。例如对二元函数 1 2 u f x f x x = = ( ) ( , ) ，其可微性定义为 0 0 0 0 1 1 2 2 1 2  = +  +  − u f x x x x f x x ( , ) ( , ) ＝ 2 2 1 2 1 2 A x B x o x x  +  +  +  ( ) （9） 上式可等价的写成 ( ) T  = + u L P o P （ 9 ） 其中 ( , )T L A B = ， 1 2 ( , )T P x x =   ， 2 2 P x x =  +  1 2 ，（9）及（ 9 ）的含义是 1 2 0 0 0 0 1 1 2 2 1 2 1 2 0, 0 2 2 1 2 ( , ) ( , ) ( ) lim x x f x x x x f x x A x B x x x  →  → +  +  − −  +   +  ＝ 0 0 0 ( ) ( ) lim 0 T P f x P f x L P → P + − − = 据此，对多元函数 1 ( ) ( , , ) u f x f x x = = n ，自然可以给出如下形式的可微性定义： 定义 2：设 f : S  R n → R 1 ,且x 0  S,如果存在L R n ,P  R n都有 0 ( ) ( lim 0 0 0 = + − − → P f x P f x L P T P ） （10） 成立，则称 f (x) 在 0 x 可微。 （有的文献称上述可微性为 F-可微，还有所谓 G-可微： h  0，h  R n ，t  R， 0 ( ) ( ) lim 0 0 0 = + − − → t f x th f x L th T t 由 F−可微  G− 可微，反之则不然）。（10）的等价形式为

f(r+ P)-f(r)=LP+o(PD (11) 易证L(x)=(9(x2….9(x2 (12) 称L(x0)为f(x)在点x0的导数或梯度,记为v(x°),于是(11)变成 f(X°+P)=F(X)+V(X°)yP+oP (13) 定义(3)设F:ScR"→R,且x∈S,如果F(X)的所有分量f(x)i=1.…,m在x0点都可微,则称 向量值函数F(X)在x点可微,即 f(x)-Vf(x°)P 它等价于 lm F(x +P)-F(r)-VF()P 0 其中称VF(x°)为向量值函数F(X)在点x0的导数或 Jacobi矩阵,其具体形式如下: 1(X)骈.. VF(X on(x)an(x)an(X°) 令g(x)=V(x)=(…,y,则gx定义了一个在区域ScR→的向量值函数,若gX)于S上可 微,则对于多元函数f(X)而言,它便在S上二次可微,Vg(x)就是fx)的二阶导数,由(15)得: a(x) a(x a(x) Vg(X)=Vf(x)= (16) a(x) 8/( a(x) 故f(x)的二阶导数是n阶矩阵,称(16)为f(x)的Hese矩阵,记为H(x)=v2f(x) 当八(x)的所有二阶偏导数连续时,O=可,/=1… ax, ar, ar ax, 此时H(X)对称 例1 次函数 f()=XAX+bx+C=2a,xx+2bx,+C 其中,A是对称矩阵,则Vf(x)=Ax+b,V2f(x)=A 例2已知o(x)=f(X+P),其中∫:R"→R,g=R2→R,P∈R",求证 o'(a)=V(X+AP)'P o'()=PV(+AP)P 证:由连锁规则得 56

156 ( ) ( ) ( ) 0 0 f X P f X L P P T + − = + （11） 易证 T n x f X x f X L X ) ( ) , , ( ) ( ) ( 0 1 0 0     =  （12） 称 ( ) 0 L X 为 f (X ) 在点 0 X 的导数或梯度，记为 ( ) 0 f X ，于是（11）变成 ( ) ( ) ( ) ( ) 0 0 0 f X P F X f X P o P T + = +  + （13） 定义（3）设 n m F : S  R → R ，且 X S 0 ，如果 F(X)的所有分量 f i (X),i =1,  ,m 在 0 X 点都可微，则称 向量值函数 F(X)在 0 X 点可微，即 i m P f X P f X f X P T i I i P 0 1, ( ) ( ) ( ) lim 0 0 0 0 = = + − −  → (14) 它等价于 0 ( ) ( ) ( ) lim 0 0 0 0 = + − −  → P F X P F X F X P P 其中称 ( ) 0 F X 为向量值函数 F(X)在点 0 X 的导数或 Jacobi 矩阵，其具体形式如下：                              = n m m m n x f X x f X x f X x f X x f X x f X F X ( ) ( ) ( ) ( ) ( ) ( ) ( ) 0 2 0 1 0 0 1 2 0 1 1 0 1 0      (15) 令 T n x f x f g(x) f (x) ( , , ) 1     =  =  ，则 g(x)定义了一个在区域 n n S  R → R 的向量值函数，若 g(X)于 S 上可 微，则对于多元函数 f(X)而言，它便在 S 上二次可微， g(X ) 就是 f(X)的二阶导数，由（15）得：                                    =  = 2 2 2 2 1 2 0 2 2 1 2 2 1 2 0 2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) n n n n x f X x x f X x x f X x x f X x x f X x f X g X f X      (16) 故 f (X ) 的二阶导数是 n 阶矩阵，称(16)为 f (X ) 的 Hesse 矩阵，记为 ( ) ( ) 2 H X =  f X 当 f (X ) 的所有二阶偏导数连续时， i j n x x f x x f i j j i , , 1, , 2 2 =     =    此时 H (X ) 对称。 例1， 二次函数 f X X AX b X C a x x b x C i i j i i i j i j T T = + + =  +  + 2 , 1 2 1 ( ) 其中，A 是对称矩阵，则 ( ) , ( ) . 2 f x = Ax + b  f x = A 例 2 已知 () = f (X + P) ，其中 1 f : R R n → ， 1 1  = R → R , n P  R ,求证: f X P P T () =  ( +  ) (17) P f X P P T ( ) ( ) 2   =  +  (18) 证：由连锁规则得：