非线性规划
南京航空航天大学经济与管理学院
教授、博士生导师
管理科学与工程系主任
非线性规划
如果目标函数或约束条件中含有一个或多个是变量的非线性函数，我们称这类规划问题为非线性规划（nonlinear programming，可简记为NP）。
一般地，解非线性规划问题要比解线性规划问题困难的多，因为它不像解线性规划问题有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，各个方法都有自己特定的应用范围。
非线性规划的基本概念和基本原理
第一节 非线性规划的数学模型
例：某金属制品厂要加工一批容积为1米3的长方形容器，按规格要求，上下底的材料为25元/m2，侧面的材料为40元/m2，试确定长、宽、高的尺寸，使这个容器的成本最低。
设容器的长为x1，宽为x2，则高为1/x1x2。
根据题意得：
例：某公司经营两种设备，第一种设备每件售价30元，第二种设备每件售价为450元，根据统计，售出一件第一种设备所需营业时间平均为小时，第二种设备为（2＋）小时，其中x2是第二种设备的售出数量，已知该公司在这段时间内的总营业时间为800小时，试决定使其营业额最大的营业计划。
由这两个例子可以看出，这两个例子在高等数学中代表了两类不同类型的极值问题。例1是无条件极值；例2是有条件极值。
第二节 极值问题
定理1：极值的必要条件
定理2：极值的充要条件
A
B
非线性规划的图解问题
图解法可以给人以直观概念，当只有两个自变量时，非线性规划也像线性规划一样，可以利用图解法。
例：用图解法求解非线性规划。
例：用图解法求解非线性规划。
A
B
D
C
第三节 凸函数及其性质
一、凸函数
凸集、凸函数是研究非线性规划问题所不可缺少的内容，有关凸集的概念参见线性规划部分，这里主要介绍凸函数的概念。
下面给出凸函数与凹函数的几何意义
即函数图形上任意两点的连线处处不在这个函数图形的下方，称它为凸函数，下凸的。
线性函数既是凸函数，又是凹函数。
X(1）
X(2)
凸函数
X(1）
X(2)
凹函数
下面介绍凸函数的性质
我们知道，一般来说，函数的局部极值并一定就是全局极值，而解非线性规划时，所求最优解必须是目标函数在某个可行域上的全部极值。但对于一类所给凸规划来说，下面将看到，其局部最优解必定是全局最优解。
A
第四节 下降迭代算法
对于求可微函数的最优解，从理论上讲，我们是首先令函数的梯度等于零( f(X)＝0 )，求得驻点，然后利用充分条件进行判别，求最优解。
但在实际中，对于一般的n元函数f(X)来说，由于 f(X)＝0得到的常常是一个非线性方程组，求它的解相当困难。另外很多实际问题的目标函数对各自变量的偏导数不存在，从而无法利用上面所说求它的驻点，因此这时常常使用迭代法。
所谓迭代法，就是从已知点X(0)出发，按照某种规则（即算法），求出比X(0)更好的解X(1) ，(若极小化问题， f(X(0))< f(X(1))),再按照此规则求出比X(1) 更好的点X(2) ，…如此重复这个过程，便产生一个点列{X(k)}，在一定条件下，下降迭代算法产生的点列收敛于原问题的解。即
称该点列{X(k)}收敛于X*.
由于算法产生的点列使目标函数值逐步减小，称这一算法为下降算法。
或
收敛速度
设算法产生的点列{x(k)},收敛到解X*,且X(k)≠X*， k，若存在>0,及一个与迭代次数k无关的常数q>0，使
1.线性收敛：当 ＝1, q>0时 称为线性收敛速度。
2.超线性收敛：当 1<<2, q>0，或＝1, q＝0时，称为超线性收敛速度
3.二阶收敛：当 =2 ，k充分大时有
一般地认为，具有超线性收敛或二阶收敛速度的算法是比较快速的算法。不过应该认识到，对任意一个算法，收敛性和收敛速度的理论结果并不保证算法在实际应用（执行）时一定有好的实际计算效果。一方面，由于这些理论结果本身不能保证算法一定有好的特性；另一方面是它们忽略了计算过程中十分重要的舍入误差的影响。
对于不同的问题，要根据具体情况来选择算法，因为我们事先并不知道最优解，迭代到什么时候停止呢？常用的准则是：
迭代中我们从一点出发沿下降可行方向找一个新的、性质有所改善的点。
△下降方向 ：
△可行方向：设 ∈S，d∈Rn,d≠0,若存在 ，使 ，称d 为 点的可行方向。
同时满足上述两个性质的方向称下降可行方向。
常用的搜索算法结构
模型算法
线性搜索求 ，
新点
使x(k+1)∈S
初始x(1) ∈S, k =1
对x(k)点选择下降
可行方向d(k)
是否满足停机条件？
停
k=k+1
yes
no
定理：设Ф：R→R 在[α，β ]上单峰，α≤λ＜μ≤ β 。那么
1°若Ф(λ)≥ Ф(μ)，则Ф(ρ) ≥Ф(μ)， ρ ∈[α，λ]；如左下图
2°若Ф(λ)＜ Ф(μ)，则Ф(ρ)≥Ф(λ)， ρ ∈[μ ， β]；如右下图
第五节 一维搜索
α λ μ β
α λ μ β
一、分数法（斐波那锲法）
分数法是寻找单峰函数极小点的一种方法。
a
b
X*
a1
b1
a
b
X*
a1
b1
通过上面的讨论，我们知道，只要在区间[a,b]内取两个不同的点，并算出这两点的函数值，加以比较，就能把搜索区间[a,b]缩小成[a,b1]或[a1,b]。
如果继续缩小区间[a,b1](或[a1,b])，就需要在区间[a,b1](或[a1,b])内取一点b2，并计算出f(b2)的值，并与f(a1)比较。
若 f(a1)< f(b2)， 则x* [a,b2]
f(a1) f(b2)，则x* [a1,b1]
这样如此继续下去，就能越来越精确地估计出x*的位置。当然，如果无限地搜索下去，可以精确地求出极小点x*。但实际计算时只能使x*包含在某个小区间内，且此时小区间的长度不超过某一给定的精度就可以了。如经过n次搜索以后，已知x*位于区间[an,bn]中，且| an－bn |<其中是事先给定的精度，这时区间[an,bn]中的点都可以作为x*的近似点。
因此，现在我们关心的是：进行n次搜索后，能把区间[a,b]缩小到什么程度？或者说，计算n次函数值以后能把多长的区间缩小成长度为1的区间？
用Fn表示计算n个函数值能缩短为单位区间的最大原区间长度，显然有
这是因为至少要计算两次函数值才能缩短区间，只计算零次或一次函数值是不能缩短区间长度的，故只有区间长度本身等于1时才行。
现考虑计算函数值两次的情形。
我们把计算函数值的点称为试算点或试点。
在区间[a,b]内任取两点a1和b1，计算函数值以缩短区间，缩短后的区间为[a,b1]或[a1,b]，显然，这两个区间长度之和必大于[a,b]区间的长度。也就是说，计算两次函数值一般无法把长度大于2的区间缩短成单位区间，但是对于长度为2的区间，可以用如图的方法选取试点a1和b1，图中为任意小的正数，缩短后的区间长度我1＋，故缩短后的区间长度近似等于1。由此得：
F2=2
根据同样的方法，可得
F3=3,F4=5,F5=8,F6=13…..
a
b
1-
1+
a1
b1
利用公式可计算出Fn的值如下：
144
11
89
10
1
1
55
9
34
8
21
7
13
6
8
5
5
4
3
3
2
2
1
0
Fn
n
这里的Fn就是通常所说的裴波那锲数。
由以上讨论知，计算n次函数值所能获得的最大缩短率（缩短后的长度与原区间长度的比）为1/Fn。
现在对于寻找近似极小点来说，如果希望误差不超过，只需将原区间[a,b]缩短为包含极小点而区间长度不超过的区间就可以了。这时计算函数值的次数n只要满足：
分数法求近似极小点的步骤
（1）给出精度，求出使Fn(b-a)/的最小整数n，
由Fn=Fn-1+Fn-2,定出两个试点x1=a+(b-a) Fn-2 / Fn-1， x1’=a+ (b-a) Fn-1 / Fn。
（2）计算f(x1)与f(x1’):
若f(x1)<f(x1’)，取a=a1, x1’=b1
并令x2=a1+ (b1-a1) Fn-3 / Fn-1
x2’= x1 。
若f(x1)f(x1’)，取x1 =a1, b=b1
并令x2= x1’
x2’=a1+ (b1-a1) Fn-2 / Fn-1。
（3）计算f(x2)与f(x2’)，比较它们的大小。方法同（2）。
（4）当迭代到k=n+1时，
xn-1= xn-1’=(an-2+bn-2)/2
这时无法比较函数值f(xn-1)与f( xn-1’)来确定最后的区间[an-1 , an-1] ，
6
5
4
2
bn
-2
-2
an
0
3
2
1
迭代次数
由上节讨论知，用分数法以n个试点来缩短某一区间时，区间长度的第一次缩短率为Fn-1 / Fn，其后各次分别为：Fn-2 / Fn-1 ，Fn-3 / Fn-2 ，…，F1 / F2，现将以上数列分为奇数项和偶数项，可以证明，这两个数量收敛于同一个极限
二、法（黄金分割法）
以不变的区间缩短率代替分数法每次不同的缩短率，就得到黄金分割法（法）。它可以看成是分数法的近似，实现起来比较容易，效果也好。
具体算法如下：
初始[α,β], ε>0
λ = α + （1-t）(β -α )
μ =α +t(β -α )
β -α <ε?
STOP;
λ* =(α+β)/2
yes
f（λ） - f（μ）>0?
No
α= λ, λ = μ
μ =α +t(β -α )
yes
Β= μ, μ= λ
λ = α + （1-t）(β -α )
No
α λ μ β
μ β
α λ μ β
α λ
例：为了提高某种化工产品的质量指标，需要在制作过程中加入某种原料，已知其最佳加入量在1000克到2000克之间的某一点，现在通过实验的方法找到该点。
按法来获取该点。
先做第一次试验，其加入量为
1000＋(2000－1000)=1382g
再做第二次试验，加入量为
1000＋(2000－1000)=1618g
比较这两次的试验结果。
1000
(1)
1382
(2)
1618
2000
如果第(2)点较第(1)点效果好，则去掉1000至1382这
段，然后在留下的一段中再找出第(2)点的对称点，做第三次试验，其加入量为
1382＋(2000－1382)=1764g
再比较第一次与第三次的试验结果。
1000
(1)
1382
(2)
1618
2000
(3)1764
如果仍然是第(2)点较第(3)点效果好，则去掉1764至2000这一段，然后在留下的一段中再找出第(4)点的对称点，做第四次试验，其加入量为
1382＋(1764－1382)=1528g
1000
(1)
1382
(2)
1618
2000
(3)
1764
(4)
1528
如果仍然是第(4)点较第(2)点效果好，则去掉1618至1764这一段，对留下的1382至1618这一段中继续试验下去就能找到最优点，这样可以用最少的试验次数找到最佳加入量。
例：用黄金分割法求函数
三、牛顿法（Newton）（切线法）
上面我们所讨论的方法，只是对一些点的函数值的大小进行比较，而函数本身并没有得到充分利用，至于函数的一些解析性质，更是毫无利用，下面介绍的牛顿法当函数性质具有较好的解析性质时，计算效果要比分数法、法更好。
现在仍设f(x)在[a,b]上仅有一个极小点的单峰函数，且具有二阶导数。
我们知道，如果函数f(x)在x*处取极小值，则必有
f′(x)=0，因此求此函数极小点，只需求出f′(x)在(a,b)内的零点即可。
对f 在x k 点展开：
f(x )= f(xk )+ f '(xk )(x- xk ) +f″ (xk )(x- xk )2 /2 + o (x- xk )2
取二次式（略去高阶项）：
qk(x) = f(xk) + f '(xk)(x-xk) + (f ″(xk)(x-xk)2)/2
用qk(x)作为f(x)的近似。
首先求qk(x)的导数，并令其等于零。
q′k(x)= f′(xk) +f″(xk)(x- xk )=0
得 xk +1=xk –f′(xk) / f″(xk)
取xk +1为新的迭代点。
以上过程即Newton法。
特点：二阶、局部收敛。 （算法框图见下页）
Newton法算法框图：
初始x1,ε1, ε2 >0
k=1
︱ f′ (xk ) ︱<ε1?
停；解xk
y
N
f″(xk ) >0?
N
停，失败
Y
xk +1= xk - f′ (xk ) ／ f″(xk )
| xk +1-xk |< ε2
Y
N
k=k+1
当f(x)在[a,b]上仅有三阶导数， f′(a) f′(b)<0,以及f″(x) >0,则切线法产生的点列收敛到f(x)在[a,b] 中的唯一极小点。。
当f(x)是具有极小点的二次函数时，牛顿法可以一步达到极小点。
当f(x)的三阶导数在[a,b]内大于零时，迭代的初始点x0应在b端点附近， f(x)的三阶导数在[a,b]内小于零时，迭代的初始点x0应在a端点附近.
例： 求 min f(x)=arctan t d t
解： f′ (x) =arctan x , f″(x)=1／(1+ x2)
迭代公式： xk +1= xk - (1+ x2) arctan xk
取x1= 1，计算结果：
k xk f′ (xk) 1／f″(xk )
1 1 2
2
3
4
x4≈ x* =0
取x1=2，计算结果如下：
k xk f′ (xk) 1／f″(xk )
1 2 5
2
3 不收敛。
1、插值法概念
假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法，称为插值方法或函数逼近法。
上面的牛顿法需要计算f(x)的一阶导数、二阶导数，当f(x)很复杂时，计算起来相当困难。抛物线法是一种多项式逼近，即用一个二次多项式p(x)来逼近所给的函数f(x)，并用p(x)的极小点来近似f (x)的极小点，在整个计算过程中，只需要计算f (x)的值。其基本思想就是用二次三项式来逼近目标函数。
四、抛物线法（插值法）：
试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是按照等比例缩短率确定的。而在插值法中，试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。
2、插值法与试探法的区别
3、二次插值法的概念
利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或抛物线法。
4、二次插值函数的构成
设一维目标函数的搜索区间为[a,b]，取三点x1、x2、x3，其中x1、x3取区间的端点，即
x1a ， x3 b
而x2为区间内的一个点，开始可以取区间的中点，即
x2= ( x1 + x3 )
计算函数值f 1=f (x1)、 f 2= f (x2)、 f 3= f (x3)
过函数曲线上的三点P1(x1 , f 1)、 P2(x2 , f 2)、 P3(x3 , f 3) 作二次插值多项式 p(x)=Ax2+Bx+C 它应满足条件
p(x1)=Ax12+Bx1+C 1=f 1
p(x2)=Ax22+Bx2+C = f 2
p(x3)=Ax32+Bx3+C = f 3
解方程组，得待定系数A、B、C分别为
p1
p2
p3
f(x)
p(x)
f1
f2
f3
x1=a
x2
x3=b
x*
xP*
二次插值函数图例
于是函数p(x)就是一个确定的二次多项式，称二次插值函数，如图所示，虚线部分即为二次插值函数
令插值函数p(x)的一阶导数为0，即
p´(x)=2Ax+B=0
得p(x)极小点为
xp* = B / 2 A
代入A、B得
则
令
注意：
若c2=0， 则
即
说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将x2、f2输出作为最优解。
5、区间的缩短
为求得满足收敛精度要求的最优点，往往需要多次进行插值计算，搜索区间不断缩短，使xp*不断逼近原函数的极小点x*。
第一次区间缩短的方法是，计算xp*点的函数值fp*，比较fp*与f2，取其中较小者所对应的点作为新的x2，以此点的左右两邻点作为新的x1和x3，得到缩短后的新区间[x1，x3]，如图所示。
新区间
x1=a
x2
x3=b
x*
xP*
x1
x2
x3
以后，根据fp*相对于x2的位置，并比较fp*与 f2 ，区间的缩短可以分为以下四种情况。
x1
x2
x3
xP*
f2
fP*
x1
x1
x1
x2
x2
x2
xP*
xP*
xP*
x3
x3
x3
f2
f2
f2
fP*
fP*
fP*
b
a
c
d
入口
xp*>x2?
f2*>fP*?
f2<fP*?
x1 xp*
f1 fP*
x3 x2 f3 f2
x2 xp* f2 fP*
x1 x2 f1 f2
x2 xp* f2 fP*
x3 xp*
f3 fP*
出口
Y
Y
Y
N
N
N
a
b
c
d
区间缩短流程图
6、终止准则
当满足给定精度时，计算终止，并令
x*xP*(k) , f * f (x*)
7、二次插值算法流程图
五、外推内插法
设f(x)在[a,b]上仅有一个单峰函数。
其基本原理和步骤：
1、给定初始区间，初始点x1及初始步长h0>0。
2、用加步长的外推法缩短初始区间。
x1
x2
x3
x4
h0
2h0
x1
x2
x3
x4
h0
2h0
h0
4h0
