第九章非线性规划

1. ⾮线性规划

我们讨论过线性规划,其⽬标函数和约束条件都是⾃变量的线性函数。如果⽬标函数是⾮线性函数或⾄少有⼀个约束条件是⾮线性等式(不等式),则这⼀类数学规划就称为⾮线性规划。在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另⼀些问题属于⾮线性规划。由于⾮线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分⽀，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越⼴泛的应⽤。

⾮线性规划的研究始于三⼗年代末,是由W.卡鲁什⾸次进⾏的，40年代后期进⼊系统研究，1951年H.W.库恩和A.W.塔克提出带约束条件⾮线性规划最优化的判别条件,从⽽奠定了⾮线性规划的理论基础,后来在理论研究和实⽤算法⽅⾯都有很⼤的发展。

⾮线性规划求解⽅法可分为⽆约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后⼀问题的基础。⽆约束问题的求解⽅法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。关于带约束⾮线性规划的情况⽐较复杂，因为在迭代过程中除了要使⽬标函数下降外，还要考虑近似解的可⾏性。总的原则是设法将约束问题化为⽆约束问题；把⾮线性问题化为线性问题从⽽使复杂问题简单化。求解⽅法有可⾏⽅向法、约束集法、制约函数法、简约梯度法、约束变尺度法、⼆次规划法等。虽然这些⽅法都有较好的效果，但是尚未找到可以⽤于解决所有⾮线性规划的统⼀算法。1.1 ⾮线性规划举例

[库存管理问题] 考虑⾸都名酒专卖商店关于啤酒库存的年管理策略。假设该商店啤酒的年销售量为A 箱,每箱啤酒的平均库存成本为H 元,每次订货成本都为F 元。如果补货⽅式是可以在瞬间完成的,那么为了降低年库存管理费⽤,商店必须决定每年需要定多少次货,以及每次订货量。

我们以Q 表⽰每次定货数量,那么年定货次数可以为Q A ,年订货成本为QA

F ?。由于平均库存量为2Q ,所以,年持有成本为2Q

H ?,年库存成本可以表⽰为: Q HQ A F Q C ?+?=2

)( 将它表⽰为数学规划问题:min Q H Q A F Q C ?+?=2)( ..t s 0≥Q

其中Q 为决策变量,因为⽬标函数是⾮线性的,约束条件是⾮负约束,所以这是带约束条件的⾮线性规划问题。[数据拟合问题] 假设⼀年期国债利率在市场中的波动符合下述模型εααα+++=---332211n n n n R R R R

其中n R 表⽰⼀年期国债利率在周期n 开始时的利率,误差ε服从),0(2σN 。利率的历史观察数据为:

表1.9:⼀年期国债利率历史样本数据 1 234

5678910111213

4.28 4.14 3.85 4.07 4.18 4.66 4.51 4.54 4.59 4.48 4.47 4.47 4.72利⽤最⼩⼆乘法估算3,2,1,=i i α

由于在周期t 回归误差的平⽅为 23322112)(---++-=t t t t t R R R R e ααα,N t ,...5,4=⽐如说,当4=t 时,2

32124)28.414.485.307.4(ααα++-=e总回归误差为∑==Nt t e e 422

我们需要求解下述数学规划问题:min ∑=---++-=Nt t t t t R R R R e 423322112)(ααα

..t s 3,2,1),,(=+∞-∞∈i i α

其中i α3,2,1,=i 为决策变量,显然,这是⽆约束⾮线性规划问题。

[投资组合管理问题] 假设⾸都基⾦管理公司拥有⼤批量股票S ,并且希望在未来的N 天中将其全部卖出。股票S 在未来N 天的总期望价值为:∑==Nt t t q p S V 1)(

其中,N t q t ,...,2,1,=是基⾦公司在第t ⽇卖出股票S 的数量,N t p t ,...,2,1,=是在t ⽇股票S 的平均价格。同时,我们假设价格t p 具有下述动态特性:

N t q p p t t t ,...,2,1,1=?+=-α

那么基⾦管理公司应当如何确定股票S 每⽇卖出数量?

很显然,不同的卖出⽅案,基⾦管理公司获得的收益是不同的。所以⽬标函数是最⼤化股票S 的总期望价值。约束条件为N ⽇内卖出数量之和应当等于总持有量S ,价格动态特征,以及每⽇卖出数量⼤于等于零

。

我们可以把它表⽰为最优化问题:max ∑==Nt t t q p S V 1)(..t s

=≥=+==-=∑N t q N t q p p S q t t t t Nt t ,...,2,1,0,...,3,2,11α

其中t q ,N t ,...,2,1=,这是⽬标函数为⾮线性函数,约束条件是线性等式约束条件的⾮线性规划问题。

[⽣产管理问题] ⾸都电器制造⼚⽣产⼆款电视机,A 和B 。已知电视机A 每⽉最⼤的销售量为500台,电视机B 每⽉的最⼤销售量为400台。⼯⼚采⽤随销售量增加⽽递减销售价格的定价⽅式对电视机进⾏定价,那么单台电视机的利润是随着销售量的增加⽽递减。

我们分别以A X 和B X 表⽰电视机A 和B 的⽉销售量,那么电视机A 的销售收⼊可以表⽰为:2

)150(300A A X X -它说明第⼀部A 型电视机的利润为300元,最后⼀部(第500)A 型电视机的利润为150元。电视机B 的销售收⼊可以表⽰为:2

)400100(200B B X X -电视机的⽣产受到下下述条件限制:)1(

装配⼯时限制:每⽉最多可供使⽤的⼯时是1200⼩时,⽽装配⼀台电视机A 需要2⼯时,装配⼀台电视机B 需要1⼯时。)2( 机器加⼯能⼒限制:每⽇最多可供使⽤的机时是1350⼩时,加⼯⼀台电视机A 需要1机时,加⼯⼀台电视机B 需要3机时。

那么,如何决定每种电视机的⽉产量,使⽉销售收⼊最⼤。

如果我们以⼆款电视机的⽉销售收⼊之和作为⽬标函数,则电视机⽣产管理的最优化问题被表⽰为:max 2

225.02003.0300BB A A X X X X S -+-=..t s ≥≤≤≤+≤+0

,4005001350312002B A B A B A B A X X X X X X X X 这是⽬标函数为⼆次可分离函数,约束条件为线性不等式的⾮线性规划问题。

1.2 ⾮线性规划模型

现在,我们⾮线性规划问题的应⽤进⾏归纳,建⽴⾮线性规划通⽤数学模型。⾮线性规划的数学模型可表⽰为:)(min x f Xx ∈)1.1(其中:R R f n

→:是具有n 个⾃变量的连续(通常存在⼀阶导数)函数;nR X ?,是nR 的

⼦集合。通常称X 为⾮线性规划问题)1.1(的可⾏域,如果n

R X =,则⾮线性规划问题)1.1(就变为⽆约束条件的⾮线性规划问题;如果nR X ?,则⾮线性规划问题)1.1(为带约束⾮线性规划问题。

如果点X x ∈,则称x 为可⾏点。称)(x f 为⾮线性规划问题)1.1(的⽬标函数,使)(x f 在可⾏域X 上达到最⼩值的点*x 为最优解(极⼩点),对应的⽬标函数值)(*x f 为最优值

(极⼩值)。如果)(x f 是线性函数并且X 是n 维空间中的单纯形,⾮线性规划)1.1(就变成了线性规划问题。我们通常将⾮线性规划和线性规划区别对待,⾮线性规划的求解⽅法⽐线性规划复杂许多。为了⽅便讨论,我们定义带约束条件的⾮线性规划的标准模型如下:min )(x f

..t s .,...,2,1,0)(,...,2,1,0)(??=≤==sj x g mi x h j i )2.1(

其中:R R h n i →:和R R g n

j →:都是连续,可导函数。第⼀组约束,m i x h i ,...,2,1),(=称

为等式约束;第⼆组约束,s j x g j ,...,2,1),(=称为不等式约束。⾮线性规划模型)2.1(的可⾏域可以表⽰为:},...,2,1,0)(,,...,2,1,0)(|{s j x g m i x h R x X j i n =≥==∈=∶不难看出,带约束⾮线性规划模型)2.1(的可⾏域是nR 的⼦集合,所以它也是⾮线性规划模型

)1.1(的⼀个特例。

我们将根据⾮线性规划的标准模型)1.1(,给出⾮线性规划解的定义。[定义1.1] 设X x ∈*

,n

R X ?,R R f n→:

)1( 如果X x ∈*,并且存在*x 的邻域}0,||:||{)(**≥≤-∈=δδx x R x x N n 使得:)()(*x f x f ≤ )(*x N X x ?∈?则*

x 是⾮线性规划)1.1(的局部最优解或局部极⼩点,称)(*x f 是⾮线性规划)1.1(的局部

最优值或局部极⼩值。 )2( 如果X x ∈*,并且存在*x 的邻域}0,||:||{)(**≥≤-∈=δδx x R x x N n 使得:)()(*x f x f < }{))((**x ＼x N X x ?∈?则*

x 是⾮线性规划)1.1(的严格局部最优解或严格局部极⼩点,称)(*x f 是⾮线性规划

)1.1(的严格局部最优值或严格局部极⼩值。[定义1.2] 设X x ∈*,n

R X ?,R R f n→:

)1( 如果X x ∈*,使得:)()(*x f x f ≤ X x ∈?,则*x 是⾮线性规划)1.1(的全局最优解或全局极⼩点,称)(*

x f 是⾮线性规划)1.1(的全局最优值或全局极⼩值。

)2( 如果X x ∈*,使得:)()(*x f x f ≤ X x ∈?,则*x 是⾮线性规划)1.1(的严格全局最优解或严格全局极⼩点,称)(*

x f 是⾮线性规划)1.1(的严格全局最优值或严格全局极⼩值。 图)1.1(从⼏何上说明了局部极⼩点,严格局部极⼩点,和严格全局极⼩点之间的关系。

严格局部极⼩点 局部极⼩点 严格全局极⼩点图)1.1(

可以看出,对于⾮线性规划)1.1(,局部或严格局部极⼩点不是全局或严格全局极⼩点,反之全局或严格全局极⼩点⼀定是局部或严格局部极⼩点。

对于只有两个决策变量的⾮线性规划问题,我们可以通过图解法进⾏求解。考虑下述带等式约束的⾮线性规划问题:min 21)(x x x f +=..t s 0222

21=-+x x)3.1(

其可⾏域X 是以原点为中⼼,半径等于2的圆周长上的所有点,见图)2.1(:

图)2.1(

显然,由于⾮线性规划)3.1(的⽬标函数是直线,与可⾏域X 的最⼩相交点为)1,1(*--=x ,它是⾮线性规划)3.1(的全局最优解,全局最优值为2)(*-=x f 。

再考虑下述带等式约束的⾮线性规划问题:max 21)(x x x f =..t s 221=+x x)4.1(

显然,⾮线性规划)4.1(的可⾏域X 是连接点)0,2(和点)2,0(直线上的所有点,参见图)3.1(:

图)3.1(

⾮线性规划)4.1(的⽬标函数与可⾏域X 的交点为)1,1(*=x ,它是⾮线性规划)4.1(的全局最优解,全局最优值为1)(*=x f 。

1.3 凸集和凸函数

凸集合,以及凸,凹函数在⾮线性规划的研究中具有特别重要的作⽤. [定义1.3] 设nR S ?,如果S y x ∈?,,并且有:S y x ∈+-λλ)1( 10≤≤λ

则称S 为凸集。 图)4.1(给出了凸集和⾮凸集的例⼦.

凸集 ⾮凸集图)4.1(

不难看出,凸集的⼏何意义为,如果点S y x ∈,,那么连接点x 和y 的线段也属于S ,即S y x ∈],[。

[定义1.4] 函数R R x f n→:)(,如果nR y x ∈?,,都有:

)()()1())1((y f x f y x f λλλλ+-≤+- 10≤≤λ

则称)(x f 为凸函数。 如果)(x f -是凸函数,则称)(x f 为凹函数。

)(a 凸函数)(b 凹函数)(c ⾮凸,凹函数图)5.1(

对于凸函数,)(z f 的取值位于连接)(x f 和)(y f 连线的下⽅,见图)5.1(的)(a ;对于凹函数,)(z f 的取值位于连接)(x f 和)(y f 连线的上⽅,见图)5.1(的)(b 。凸(凹)函数具有以下性质:[定理1.1] 设n

R C ?是凸集,n i R C x f i ,...,2,1,:)(=→是凸(凹)函数)1( 对于n i i ,...,2,1,0=≥α,函数∑==ni i i x f x f 1

)()(α也是凸(凹)函数。

)2( 如果n i x f i ,...,2,1),(=是凸函数,则)}({max )(1x f x f i ni ≤≤=⼀定是凸函数; 如

果n i x f i ,...,2,1),(=是凹函数,则)}({min )(1x f x f i n

i ≤≤=⼀定是凹函数。 证明 我们只证明)2(的第⼀部分。对于任意C x x x n ∈,...,,21,我们有:∑∑∑∑====≤≤=ni i i ni i i in i ii in i i

i x f x f x f x f 1111)()()()(αα

αα,n i ,...,2,1=?

那么)(x f 是凸函数,证毕。[定义1.5] 函数R R x f n

→:)(,如果)(x f 是连续函数,且存在⼀阶偏导数,则称向量T

n

x x f x x f x x f x f ))(,...,)(,)((

)(21=? 为)(x f 在点x 处的⼀阶偏导数或梯度。[定理1.2] 设函数R R x f n→:)(在凸集nR X ?上⼀阶可微

)1( )(x f 是凸函数的充分必要条件是X y x ∈?,:)()()()(x y x f x f y f T -?+≥

)2( )(x f 是凹函数的充分必要条件是X y x ∈?,:)()()()(x y x f x f y f T -?+≤

定理]2.1[是判断可微函数)(x f 是否为凸(凹)函数的⼀个判别定理。从⼏何上来说, 函数)(x f 是凸函数的充分必要条件是)(x f 在图形上任⼀点处的切线都在曲线的下⽅,见图)6.1(。

[定理1.3] )1( 设R R x f n

→:)(是凸函数,*x 是局部极⼩点,那么*x ⼀定是全局极⼩点。)2(R R x f n→:)(是凹函数,*x 是局部极⼤点,那么*x ⼀定是全局极⼤点。

证明 我们只证明)(x f 为凸函数的情况)1(。如果*x 不是全局极⼩点,则存在x 使得

)()(*x f x f <。根据凸函数性质,对于所有)1,0(∈λ,)()()1()())1((***x f x f x f x x f <-+≤-+λλλλ

这表明在*x 和x 的连线上的点,其取值严格⼩于)(*x f ,所以*

x 不可能是局部极⼩点。)

2(证明过程与)1(类似,请⼤家⾃⼰完成,证毕。

)x y -图)6.1(

[定义1.6] 函数R R x f n

→:)(,如果)(x f 存在⼆阶偏导数,则称矩阵

=?22221

222222122122122122)()()()()()()()

()()(n n n n n x x f x x x f x x x f x x x f x x f xx x f x x x f x x x f x x f x f

为)(x f 在点x 处的⼆阶偏导数矩阵,通常称其为Hessian 矩阵。 [定理1.4] 设R R x f n→:)(是在凸集nR X ?上⼆阶可微

)1( )(x f 是凸函数的充分必要条件是)(x f 的⼆阶Hessian 矩阵)(2x f ?是半正定的。

)2( )(x f 是凹函数的充分必要条件是)(x f 的⼆阶Hessian 矩阵)(2x f ?是半负定的。

[例1.1] 判断下述函数的凸凹性:)1(x e x f =)(,R x ∈)2(21)(x x f =,R x ∈)3(22

2121212),(x x x x x x f --++=,2R x ∈ 解: )1( 0)(''≥=xe x

f ,所以)(x f 函数是凸集R 上的的凸函数.)2( 041

)(23''≤-=-x x f ,所以)(x f 函数是凸集R 上的的凹函数.)3( ),(21x x f 的Hessian 矩阵为:

--=?2002)(2x f

为了判断)(2

x f ?的半正(负)定性,计算:

----=-?λλλ2002))((2def I x f def0)2(2=--=λ

那么, 221-==λλ,所以矩阵)(2

x f ?为负定矩阵,)(x f 为凸集R 上的凹函数.

下⾯的定理说明了凸,凹函数与凸集,及凸集与凸集之间的关系. [定理1.5]

)1( 如果R R x f n →:)(是凸函数,对于任何R c ∈,集合})(:{c x f x L c ≤=是凸集。 )2( 如果R R x f n →:)(是凹函数,对于任何R c ∈,集合})(:{c x f x L c ≥=是凸集。)3( 如果n i C i ,...,2,1,=是凸集,那么i iC C I =也是凸集。

证明 我们只证明)1(。如果)(x f 是凸函数,对于任意c L x x ∈21,,有c x f ≤)(1,c x f ≤)(2。这表明:

c x f x f x x f ≤-+≤-+)()1()())1((2121λλλλ

所以L x x ∈-+))1((21λλ,根据21,x x 的任意性,c L 是凸集,证毕。

如果⾮线性规划问题的⽬标函数为凸或凹函数,约束条件的可⾏集为凸集,则这类⾮线性规划称为凸规划。[定义1.7] 设R C x f →:)(是凸函数,nR C ?是凸集,考虑下述两类⾮线性规划问题min )(x fmax -)(x f..t s C x ∈..t s C x ∈

那么,它们都是凸规划问题。

接下来,考虑带约束条件的⾮线性规划模型:min )(x f

..t s .,...,2,1,0)(,...,2,1,0)(??=≤==sj x g mi x h j i)5.1(

⾮线性规划模型)5.1(是凸规划的必要条件为:)1( R C x f →:)(是凸函数

)2( R R h n i →:,m i ,...,2,1=都是线性函数 )3( R R g n j →:,s j ,...,2,1=都是凸函数。1.4 ⾮线性规划应⽤

⾮线性规划模型在许多领域中都获得⼴泛应⽤,在本节中,我们将介绍⾮线性规划在⽣产管理,⾦融投资⽅⾯的应⽤.

1.4.1选址问题

⾸都电视机⼚的产品在n 个城市中销售。为了提供优质服务,现在打算建⽴服务中⼼,希望选择地址的位置使所有城市到服务中⼼的距离最短。以坐标),(b a 表⽰服务中⼼的位置,设第i 个城市的地址坐标为),(i i y x ,n i ,...,2,1=,该问题等价于找到能够覆盖所有城市半径最⼩的园,其⼏何意义见下图:

图)7.1(

数学规划模型为:min r..t s ?

≥=≤-+-0,...,2,1,)()(22r n

i r b y a x i i 这是⾮线性规划问题。1.4.2投资组合管理

设n i x i ,...,2,1,=为持有第i 种证券品种的⽐例,满⾜∑==ni ix1

1,n i r i ,...,2,1,= 为第i

种证券品种的收益率,ρ为投资组合的收益率,Q 为证券品种的⽅差-协⽅差矩阵,等于:

=nn n n n n q q q q q q q q q Q 2122221

11211 数学规划模型为:min ∑∑==nj ni ji ij x x q 11..t s

=≥=≥∑∑==n i x x x r i n i i n

i i i ,...,2,1,0111ρ 这是⽬标函数为⼆次函数,约束条件为线性函数的⾮线性规划问题。1.4.3指数化投资

指数化投资是根据⽬标指数中的成份证券的权重创建跟踪投资组合的投资⽅法。设B 为预算投资额,n i x i ,...,2,1,=为投资在第i种证券品种的投资额,那么:B xni i≤∑=1

设初始投资组合为n i x i ,...,2,1,00=≥,C 为现⾦,则:∑=+=ni i x C B 1设),(0i

i x x F 为从初始投资组合∑=ni ix

10到投资组合∑=ni ix1

的交易成本,所以:B xni i≤∑=1),(0i i x x F -设投资组合与⽬标指数的跟踪误差为:∑=-=Tt t t s r TE 12

)(1 其中t r 是跟踪组合的收益率,t s 为⽬标指数的收益率。它们的计算⽅法是根据过去⼀个阶段的历史指数点位和成份证券价格:

)/ln(1-=t t t I I s)ln(11,1,∑∑=-==ni t i ni ti t yy r)

/(,,,T i i t i t i P x P y =

其中t I 是指数的价格,t i P ,是第i 种证券在时刻t 的价格。T i i P x ,/是第i 种证券的数量。指数化投资中最⼩化跟踪误差的数学规划模型为:min ∑=-=Tt t ts rTE 12)(1

.st =≥-≤∑=ni x x x F B x i i i ni i ,...,2,1,0),(01

1.5 ⽆约束优化问题

考虑⽆约束的⾮线性规划问题:)(min x f nRx ∈)6.1(

⼀般来说,求解⽆约束⾮线性规划问题)6.1(将涉及到以下三个⽅⾯,⾸先,确定极⼩点n R x ∈*必须满⾜的条件,其次设计某种迭代算法来搜寻极⼩点*x ,最后,求解的最终⽬标⼀般是求全局极⼩点,⽽极⼩点*

x 满⾜的必要条件只能保证它是局部极⼩点,所以需要找出局部极⼩点也是全局极⼩点的条件。1.5.1 ⽆约束优化问题的最优性条件

如果R R x f →:)(是⼆次可微的⼀元函数,设R x ∈0,对于接近0x 的所有x ,有:

200''00'0))(())(()()(x x x f x x x f x f x f -+-+≈显然,极值点存在的条件为:)1( 必要条件: 0)(0'=x f

)2( 充分条件:如果0)(0'=x f 且0)(0''>x f ,0x 为极⼩点; 如果0)(0'=x f 且0)(0''