非线性规划的概念和原理

非线性规划的理论是在线性规划的基础上发展起来的。1951年，库恩（H.W.Kuhn）和塔克（A.W.Tucker）等人提出了非线性规划的最优性条件，为它的发展奠定了基础。以后随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。

一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。

5.1 非线性规划的实例及数学模型

[例题6.1] 投资问题：

假定国家的下一个五年计划内用于发展某种工业的总投资为b亿元，可供选择兴建的项目共有几个。已知第j个项目的投资为aj亿元，可得收益为cj亿元，问应如何进行投资，才能使盈利率（即单位投资可得到的收益）为最高？

解：令决策变量为xj，则xj应满足条件xjxj10

n同时xj应满足约束条件ajxjb

j1nc目标函数是要求盈利率fx1,x2,,xnj1njxj最大。

jaj1xj

[例题6.2] 厂址选择问题：

设有n个市场，第j个市场位置为pj,qj，它对某种货物的需要量为bjj1,2,,n。

现计划建立m个仓库，第i个仓库的存储容量为aii1,2,,m。试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。

解：设第i个仓库的位置为xi,yii1,2,,m，第i个仓库到第j个市场的货物供应量为ziji1,2,,m,j1,2,,n，则第i个仓库到第j个市场的距离为

dijxipjyiqj

mn22目标函数为

mni1j1zijdiji1j1zijxipjyiqj

22约束条件为：

（1） 每个仓库向各市场提供的货物量之和不能超过它的存储容量； （2） 每个市场从各仓库得到的货物量之和应等于它的需要量； （3） 运输量不能为负数。

因此，问题的数学模型为：

mnmini1j1nzijxipjyiqj 22s.t.

zj1mijai,i1,2,,m

zi1ijbj,j1,2,,n

zij0,i1,2,,m,j1,2,,n

一般非线性规划的数学模型可表示为：

minfx；

s.t. giX0 i1,2,,m, hjX0,j1,2,,l

式中Xx1,x2,,xnR是n维向量，f,gii1,2,,m，hjnTj1,2,,l都是

，且其中至少存在一个RR的映射（即自变量是n维向量，因变量是实数的函数关系）非线性映射。

与线性规划类似，把满足约束条件的解称为可行解。若记

n1XgiX0,i1,2,,m,hjX0,j1,2,,l

则称为可行域。因此上述模型可简记为

minfX

 s.t. X

当一个非线性规划问题的自变量X没有任何约束，或说可行域即是整个n维向量空间,

即Rn，则称这样的非线性规划问题为无约束问题：

fminfX或minnXRX

有约束问题与无约束问题是非线性规划的两大类问题，它们在处理方法上有明显的不同。

5.2 无约束非线性规划问题

5.2.1无约束极值条件

对于二阶可微的一元函数fx，如果x是局部极小点，则fx0，并且

fx0；反之，如果fx0，fx0，则x是局部极大点。关于多元函数，

也有与此类似的结果，这就是下述的各定理。

考虑无约束极值问题：

minfx，xEn

定理6.1 （必要条件）设fx是n元可微实函数，如果x是以上问题的局部极小解，则fx0。

定理6.2 （充分条件）设fx是n元二次可微实函数，如果x是上述问题的局部最小解，则fx0，2fx半正定；反之，如果在x点有fx0，2fx正定，则x为严格局部最小解。

定理6.3 设fx是n元可微凸函数，如果fx0，则x是上述问题的最小解。

[例题6.3] 试求二次函数fx1,x22x18x12x24x220的极小点。

22解：由极值存在的必要条件求出稳定点：

fx14x18，

fx24x24，则由fx0得x12，x21

再用充分条件进行检验：

fx1224，

fx22244，0，则由fx1x2x2x10ff2220为正定矩阵得 4极小点为x2,1。

T5.2.3无约束极值问题的解法

5.2.3.1梯度法

0（i）给定初始点X，0；

（ii）

Xk计算fXk和fX，若fXkk2，迭代停止，得近似极小点

和近似极小值fXk；否则，进行下一步；

（iii） 做一维搜索或取kXfX作为近似最佳步长，fXfXfXfkk2TkTkk并计算X

k1XkkfX，令kk1，转向第二步。

k[例题6.4] 求解无约束极值问题 minfXx12x21 解：取X0220,0，fTX02x12,2x21，则

4,2，f2TfXT0X0200 20XfX1，

fXfXfX2f002TT00X1X00f1X02,1，

TTfX0,0，

故X为极值点，极小值为fX110。

5.2.3.2牛顿法

对正定二次函数，fX12XAXBXc，其中A为n阶方阵，B为n维列向量，

TTc为常数，设X为其极小点，则fXAXB0，所以AXB；任给X(0)En，

fX0AX0B，消去B，得

fXAXAX00

所以 XX0Af1X，

0这说明，从任意近似点出发，沿A1fX点。

0方向搜索，步长为1，一步即可达极小

[例题6.5] 求解无约束极值问题minfXx15x2

22解：任取X02,1，fTX02T4,10，A001，A101200， 110XX0AfT1X0,00T

由fX0,0可知，x确实为极小点。

牛顿法与梯度法的搜索方向不同，优点是收敛速度快，但有时不好用而需采取改进措施，当维数较高时，A1的计算量很大。

5.3 约束非线性规划问题

前面我们介绍了无约束问题的最优化方法，但实际问题中，大多数都是有约束条件的问题。求解带有约束条件的问题比起无约束问题要困难得多，也复杂得多。在每次迭代时，不仅要使目标函数值有所下降，而且要使迭代点都落在可行域内（个别算法除外）。求解带有约束的极值问题常用方法是：将约束问题化为一个或一系列的无约束极值问题；将非线性规划化为近似的线性规划；将复杂问题变为较简单问题等等。

5.3.1凸规划问题

约束问题的情况较为复杂，先讨论其中的一种较为特殊的情况，即凸规划问题。 一般来说，非线性规划的局部最优解和全局最优解是不同的，但是，对凸规划问题，局部最优解就是全局最优解。

定义6.1设fX1X为定义在非空凸集SE上的实值函数，如果对于任意的两点

nS，X2S和任意实数0,1，恒有

fX11X2fX1fX

12则称fX为S上的凸函数。

定理6.4 设S是n维欧氏空间En上的一个开凸集，f续导数的函数，那么，ff2X是定义在S上的具有二阶连

X在

S上为凸函数的充要条件是：对所有XS，海赛矩阵

S，f2X都是半正定的；如果对所有的XX都是正定的，则fX在

S上

为严格凸函数。

定义6.2 非线性规划问题：

minfX，XEn

s.t. giX0,i1,2,,m

hjX0,中，如果fj1,2, ,pX和giX（i1,2,,m）为x的凸函数，hjX（j1,2,,p）为X

的线性函数，则称此问题为一凸规划问题。

凸规划具有两个重要性质：

1． 凸规划的可行集是凸集

证：设凸规划的可行集为S，即

SXgiX0,i1,2,,m;hjX0,j1,2,,p;XEn

其中giX（i1,2,,m）为X的凸函数，hjX（j1,2,,p）为X的线性函数。

对于任意的X的凸性，对XX1S，X2S和任意实数0,1，利用giX（i1,2,,m）

11X2，有

1X2giXigiX21gX1gX

12i但giX10，gX0

所以giX0 同理hjX0 因此，XX

11X2S，故S为凸集。

2． 凸规划的局部最小解就是它的全局最小解

证：用反证法。

设X是凸规划的一个局部最小解，X是它的全局最小解，但XX。 因为 XS，XS，所以0,1，XX1XS

由fX为凸函数得，fXfX1XfX1fX

因为X是一个全局最小解，所以

fXfX1fXfX1fXfX

此式对一切0,1都成立。当1时，则XX，即在X的邻域内还有比

fX小的值，与X为局部极小解的假设矛盾。

因此，凸规划的局部最小解就是它的全局最小解。

[例题6.6] 验证下述非线性规划为凸规划，并求出最优解。

minfXx1x24x14

22s.t. g1Xx1x220 g2Xx1x210

2g3Xg4Xx10 x20

解：第1，3，4三个约束条件为线性函数，因此也是凸函数； 第2个约束条件应写成g2Xx1x210

2g2Xx1g2X22x1，

g2Xx21

x122，

g2X2x220，

g2X2x1x20

因此海赛矩阵为g2X2200，半正定，g2X0为凸函数

同理，fX2200，正定，f2X也为凸函数。

所以，该非线性规划为凸规划。 用图解法得

8x2642x=(0.58,1.34)*T0-4-20246x18-2

X0.58,1.34为其唯一极小点，fTX3.8



5.3.2其它类型的约束非线性规划问题

考虑只含不等式约束条件下求极小值问题的数学模型：

minfX，XEn

s.t. giX0,i1,2,,m 或写成

minfXX

n其中可行域{X|XE,gi(X)0,i1,2,,m}。

定义6.3对于上述问题，设X，若有giX01im，则称不等式约束giX0为点X处的起作用约束；若有giXgiX0为点X处的不起作用约束。

01im，则称不等式约束

定义6.4对于上述非线性规划问题，如果可行点X处，各起作用约束的梯度向量线性无关，则称X是约束条件的一个正则点。

库恩－塔克条件是非线性规划领域中的重要理论成果之一，是确定某点为局部最优解的

一阶必要条件，只要是最优点就必满足这个条件。但一般来说它不是充分条件，即满足这个条件的点不一定是最优点。但对于凸规划，库恩塔克条件既是必要条件，也是充分条件。 对于只含有不等式约束的非线性规划问题，有定理如下：

定理6.5 设X是非线性规划问题

minfXnX

{X|XE,gi(X)0,i1,2,,m}

的极小点，若X起作用约束的梯度giX线性无关（即X是一个正则点），则

1,2,,m，使下式成立

Tm***f(X)igi(X)0i1**igi(X)0,i1,2,,m 0,i1,2,,mi对同时含有等式与不等式约束的问题

minfx；

s.t. giX0 i1,2,,m, hjX0,j1,2,,l

为了利用以上定理，将hjX0，用

hjX0 hjX0来代替。这样即可得到同时含有等式与不等式约束条件的库恩塔克条件如下：

设X为上述问题的极小点，若X起作用约束的梯度giX和hjX线性无关，则1,2,,m和1,2,,m，使下式成立

TTmm*****f(X)igi(X)jhj(X)0i1j1** igi(X)0,i1,2,,m0,i1,2,,mi

[例题6.7] 求下列非线性规划问题的K-T点：

minfX2x12x1x2x210x110x2

222x12x25s.t. 

3x1x26解：将上述问题的约束条件改写为giX0的形式：

22g1Xx1x250 g2X3x1x260设K-T点为Xx1,x2，有

TfX4x12x210， 2x2x1012g1X2x1 2x2g2X3 1304x12x2102x1122x2x2102x012215x2x20112由定理得 

263x1x200120求解上述方程组，即可求出1，2，x1,x2，则可得到满足K-T条件的点。上述方程组是非线性方程组，求解时一般都要利用松紧条件（即上述方程组中的第3，4个方程），其实质是分析X点处，哪些是不起作用约束，以便得到i0，这样分情况讨论求解较为容易：

（1）

假设两个约束均是X点处的不起作用约束，即有

10，20 4x12x2100则有 

2x2x10012x10解得 

x52但将该点代入约束条件，不满足giX0，因此该点不是可行点。 （2）

若g1X0是起作用约束，g2X0是不起作用约束，则有20，则

4x12x21021x102x12x21021x20 2215x1x2001x1x2解得 121210T

代入原问题约束条件中检验，可知该点X1,2是可行点，且满足K-T定理的条件，又是一个正则点，故它是一个K-T点。

因为g1X0是起作用约束，此时10，可以是10，也可以是10，若10也成立，则结果同（1），已知求出的解不是可行点。

（3）

若g1X0是不起作用约束，g2X0是起作用约束，即有10，代

入方程组，有

4x12x2103202x12x21020 63xx012202解上述方程组，可得20或210同情形（1）的结果。

25，而225不满足20条件，而20及

（4）

假设两个约束均起作用，这时10，20。故有 4x12x21021x13202x12x21021x220 225xx01263xx012求解上述方程组，得到的解不满足10与20，故舍去。 因此本题的K-T点为：X1,2。

T同时本题fX为凸函数，而g1X0为凸函数，g2X0为线性函数，也为凸函

T数，所以本题是凸规划。对凸规划K-T也是充分条件。因此X1,2也是本题的全局最小点。