2007-11-16
天津大学研究生精品课程运筹学——
运筹学 A、运筹学 B、管理运筹学
-运筹学 A是针对管理专业本科没学过运筹学的学生开设的学位课
-运筹学 B是针对管理专业本科已学过运筹学的学生开设的学位课
-管理运筹学是针对非管理专业的学生开设的选修课
http://www.tju.edu.cn
第一章非线性规划第一章非线性规划
(Nonlinear Programming)
1.1 基本概念
1.2 无约束极值问题
1.3 约束极值问题
http://www.tju.edu.cn
第一章非线性规划请回顾线性规划:,其目标与约束函数均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。
非线性规划（Nonlinear Programming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。
≥
≤
=
0
..
X
bAX
ts
CXMaxz
http://www.tju.edu.cn
第一章非线性规划
1.1 基本概念一、非线性规划问题与模型
1.问题
⑴生产计划问题
max ( ) ( ) ( )
() 0
..
() 0
i
j
f xxPxxCx
gx
st
hx
=?
≥
=
x:产量 ;P(x):价格 ;C(x):成本
http://www.tju.edu.cn
第一章非线性规划
⑵投资决策问题
111
1
::
::
max ( )
..
0
jj
j
ij
nnn
jj ijij
jij
n
jj
j
j
xj Pj
Bj
ij
fx x xx
Px B
st
x
μ
βσ
μβ σ
===
=
=?
≤
≥
∑∑∑
∑
第 种股票的购买量； 第 种股票的价格总资金； 第 种股票的每股平均收益风险系数； 第 种与第 种股票收益的协方差
http://www.tju.edu.cn
第一章非线性规划
2.模型
1
min ( )
()0,1,,
().
()0,1,,
[,,]
{ |()0,()0}
min ( )
i
j
T
n
n
ij
XD
n
n
fX
hX i m
NLP st
gX j l
Xx x
DXRhX gX
NLP f X
DNLP
DR NLP
D R NLP
∈
==
≥=
=
=∈ = ≥
≠
null
null
null其中记则（ ）也可以表示为其中 称为（ ）的约束集或可行域。
当 ＝ 时，（ ）称做无约束极值问题；
当 时，（ ）称做约束极值问题。
http://www.tju.edu.cn
第一章非线性规划二,模型的解及相关概念
1.可行解与最优解
★可行解：约束集D中的 X。
★最优解：如果有,对于任意的,
都有,则称 为（NLP ）的最优解，也称为全局最小值点。
*
X D∈
X D∈
*
() ()f XfX≤
*
X
★局部最优解：如果对于,使得在 的邻域 中的任意都有,则称 为（NLP）的局部最优解，也称为局部最小值点。
0
X D∈
0
X
X D∈
0
() ()f XfX≤
00
(,){| }BX X X Xε ε=?<nullnull
0
X
http://www.tju.edu.cn
第一章非线性规划例：考虑非线性优化问题
22
12
12
min ( ) ( 2) ( 2)
,,6
fX x x
st x x
=?+?
+=
2
x
1
x
6
6
3
3
如果约束改为呢？
12
6xx+ ≤
http://www.tju.edu.cn
第一章非线性规划
2.梯度、海塞阵与泰勒公式
★梯度
00
00
00
0
1
() ()
() ( )
() ()
()[ ]
T
n
f XX f XX n
fX X fX
fX fX
fX
xx
null
若 在 的邻域内有连续一阶偏导数，则称 在 点对个变元的偏导数组成的向量为 在 的梯度，记为,
即＝，
00
()XfXX
几何意义：
梯度是过 点且与 在 的切平面垂直的向量，
梯度向量的方向是函数值在该点增加最快的方向。
http://www.tju.edu.cn
第一章非线性规划
★海塞阵
00
0
0
00
00
11
00
1
2
22
2
22
2
() ()
()
()
() ()[ ]
() ()
() ()
ij
n
nn
nn
f XX f XX n
fX X
fX
HX HX
xx
fX fX
xxx
fX fX
xx x
×
…
=
nullnullnull
null
若 在 的邻域内有连续二阶偏导数，则称 在 点对个变元两两组合的二阶偏导数组成的矩阵为 在 的海赛阵，
记为,即 =
http://www.tju.edu.cn
第一章非线性规划
★泰勒公式
00
00 0 000
2
0
22
000
() ()
() () ()
1
()()()
2
( )
()
TT
fX X fX X
fX fX fX XX XX HXXX
oXX
oXX X X XX
+? +
+
→?
nullnull
nullnull nullnull
若 在 的邻域内有连续二阶偏导数，则可写出 在 点的（二阶）泰勒展开式：
＝ （－）
－
其中,是当 时 的高阶无穷小。
http://www.tju.edu.cn
第一章非线性规划例：写出 在 点的二阶泰勒展开式。
2
12
()3 sinfX x x= +
0
[0,0]
T
X =
12 0
0
2
()[6 ( )[0 1 cos ],]
60 60
(),( )
0sin 00
TT
fX x fXx
HX HX
x
=? =
==
解:
211
12
22
() 0[0 1
60
1
][ ] ()
002
xx
fX xxoX=+
++
nullnull
2
0
2
12
()
( ) 3
()fX
fX x
oX X
x=
nullnull如果忽略了 在，则 点的近似表达式为
+
http://www.tju.edu.cn
第一章非线性规划
3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n( n>1)元函数 与一元函数 的极值条件加以对比并归纳如下：
()fX ()fx
充分条件必要条件
00
()X x或 是极小点
()f x一元函数
()f Xn元函数
0
'( ) 0fx=
0
()0fX? =
00
'()0,'()0fx fx= >且
00
()0 ()0fX HX?= >且
0
()0HX >注,表示海赛阵正定。如果一个方阵的各阶主子式均大于零，则可以判定该方阵是正定的。
http://www.tju.edu.cn
第一章非线性规划例：求 的极小值点。
22
1122
() 2 2840fX x xxx=? +?+
解
12
12
0
()[
()0
][4 8 4 4]
[2 1]
TT
T
ff
fX
xx
fX X
xx
=
=
＝
＝,解得驻点令
0
0
40
(),( )0
04
HX HX
X
= >
又故 是极小值点。
http://www.tju.edu.cn
第一章非线性规划
4.凸规划
★凸函数：f (X)是定义在凸集D上且满足对任意有下式成立的函数：
121 2
()((1 ) ) (1 ) ( )fX fXX f Xααα α≤+? +?
12
,,X XD∈
[0,1]α∈
若不等式中严格不等号成立，则称f (X)为严格凸函数注：判断一个可导函数f (X)是否是凸函数的方法一元函数f (x),二阶导大于等于零;
多元函数f (X),海塞阵半正定。
http://www.tju.edu.cn
第一章非线性规划
★凸规划性质：★约束集是凸集；
★最优解集是凸集；
★任何局部最优解也是全局最优解；
★若目标函数是严格凸函数，且最优解存在，则其最优解是唯一的。
在非线性规划模型（NLP ）中，若目标函数f （ X）是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（NLP ）是一个凸规划。
( ),1,,
j
gX j l= null
(),1,,
i
hX i m= null
http://www.tju.edu.cn
第一章非线性规划例：判断下面的非线性规划是否为凸规划
12
22
12
12
max ( )
1
..
,0
fX xx
xx
st
xx
= +
+≤
≥
12
22
112
21
32
min( ( ))
()1 0
.,( ) 0
() 0
fX xx
gX x x
st g X x
gX x
=
=≥
=≥
=≥
一般化
1
23
()
00 20
0,( ) 0
00 02
00
() () 0
00
fg
gg
HX HX
HXHX
=
≥=>
==≥
计算
123
() () () ()fX gX gX gX?说明 是凸函数,、,是凹函数因此，本模型是凸规划。
http://www.tju.edu.cn
第一章非线性规划
1.2 无约束极值问题
★一般模型：
min ( )
n
XR
f X
∈
★求解：当f (X)可微，可应用极值条件求解，但往往得到一个非线性的方程组，求解十分困难。因此，一般采用迭代的方法，称为下降类算法。
http://www.tju.edu.cn
第一章非线性规划一、下降类算法的基本步骤与算法收敛性
1.基本思想
0
0
1
12
()fX
X
P
X
PX
基本思想是使 逐步下降，逐渐趋近其最小值。迭代方式是从一个初始点 出发，选取某一搜索方向,沿该方向搜索到下一个点 。若达到与最优解误差的精度要求，则停止，否则再沿该点的某一方向 搜索下一个点 。
这一过程如图所示：
0
P
1
P
2
P
0
X
1
X
3
X
2
X
http://www.tju.edu.cn
第一章非线性规划
2.基本步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；
(1)
(),(),
3
kkk
k
XfXfX
X
ε<nullnull对于点,计算 若 则停止,
得到近似最优解,否则转（）；
(2)
kk
XP从 出发，确定搜索方向 ；
(3)
1
,
,,1,2)
kk
kkkk
PXXP
XX Pkk
λ λ
λ
+
+
+=+
沿 方向搜索，即由 ＝ 确定搜索步长得到下一个点 ＝ 令 转( 。
(4)
注：不同的搜索方向，就形成了不同的算法，不同的算法所产生的点列收敛于最优解的速度也不一样。
http://www.tju.edu.cn
第一章非线性规划
3.收敛性衡量标准：
*
1
*
lim
k
k
k
XX
XX
α
β
+
→∞
=
nullnull
nullnull
1,0 1,{ }
k
Xα β=<<则称 是线性收敛的；
①
1,0,{ }
k
Xα β==则称 是超线性收敛的；
②
2,0,{ }
k
Xα β=≤<+∞则称 是二阶收敛的。
③
二阶收敛 超线性收敛 线性收敛
null
null
http://www.tju.edu.cn
第一章非线性规划二、一维搜索
:
精确搜索：
一维搜索分数法近似搜索 0.168法其他方法（导数信息）
0
min ( ),
kk
k
f XP
λ
λ
λ
≥
+通过求极值得到最佳步长
k
λ
求上面极值的近似值得到近似最佳步长
http://www.tju.edu.cn
第一章非线性规划
1.分数法（斐波那契法）
2
t
⑴基本思想
*
t
0
a
b
'
1
t
1
t
()f t
t
怎样在区间中取点最好？
'
11
() ()f tft<若
12
() ()f tft<若
http://www.tju.edu.cn
第一章非线性规划
[,],0
nn
nabε >设第 次缩短后的小区间为 给定的精度要求为
★满足绝对精度：
★满足相对精度：
||
nn
baε? <
||
nn
ba
ba
ε
<
★斐波那契数：
12
01
1
nn n
FF F
FF
=+
==
55342113853211
9876543210
n
F
n
1
(1 )( )
n
n
F
aba
F
+
1
()
n
n
F
aba
F
+?
a b
1
t
'
1
t
''
1
11 1
1
'
12 2
1
1
11 1
'
121 -11
12 21
132
[,],
(1 - )( - )
[,],
()
[,] -1 [,]
1
(-)
n
n
n
nnnnn
n
nn n
n
nn
nn
nn
F
tt tb
F
F
ba
FFFFF
tat
F
FF F
ba
F
at t t n a b
FF FF
ba
FF FF F
==
=inulli
1
若按 的比例在区间中对称地取点 和,经比较后去掉则 在 中所占的比例为 再按比例在 中取 与 对称，这样反复 次后所得的小区间长缩短为 (),
1
()
11
-
n
n
n
ba
ba
F
Fn
ba F F
ε
=<
与原区间长之比为：
，恰为相对精度表达式。于是，开始可由 解出,
⑵步骤
①
1;
n
n
F
ε由所给精度 和 定
11
1
'''
1
1111
11
(1 - )( - )
() max{ }
,[,]
nn
n
n
FF
tba
F
tbaftft ftft
F
ab
由 的比例在区间[a,b]中对称地取点 =a+ 和
=a+,比较 ( )和 ( )，去掉 ( ),( )相应点以外的区间得到新区间 ；
②
2
11 2
1
'
211
22
[,] ( )
() min{(),()}
[,]
n
n
F
ab t
F
ft ft ft
ab
在 中按 的比例取点 与区间中所剩的点对称比较 和,去掉较大者对应点以外的区间，得到新区间 ；
③
3
22 3
2
*
1
-1 1
2
[,]
[,]
n
n
nn
F
ab t
F
F
ab t
F
在 中按 的比例取点 再比较、再缩短，直到取完
，最后的小区间 中的任意一点可作为 的近似值。
④
http://www.tju.edu.cn
第一章非线性规划例：
2
() 2 [ 1,3]
8
ft t t=?+?用分数法求 在区间 上的近似极小点，
要求缩短后的区间长度不大于原区间长的 ％。
**
''( ) 2 0,
'( ) 2 1 0
1
1.75
2
ft
ft
ft t
tft
= >
=
解 由于所以（）是严格的凸函数。
由 ＝ －＝,
解得 是极小点，（ ）＝
http://www.tju.edu.cn
第一章非线性规划
5
6
11
''
1
4
11
5
2
21
11 8
0.08 12.5,6,
0.08 13
8
1 (1 )[3 ( 1)] 0.538,( ) 1.751
13
8
1 [3 ( 1)] 1.462,( ) 2.675 ( )
13
5
[,] [ 1,1.462],
8
5
1 (1 )[1.462 ( 1)] 0.077,
8
( ) 2.083 ( ),
n
n
F
Fn
FF
tft
ft
F
ab
F
t
ft ft
≤≥= ==
=? + = =
=? + = = >
=? =
=? + =?
=>
由 知 查表得故
22
55
[,] [ 0.077,1.462]
0.538 ( ) 1.751
ab
tft
=?
=
故依此进行，得 ＝ 为近似极小点，
http://www.tju.edu.cn
第一章非线性规划
2,0.618法
★区别：每次取点得比例是定值0,618，即每次区间内两点的位置均在新区间长度的0.382和0,618处。
★特点：简单，更易于应用；
效果也比较好。
http://www.tju.edu.cn
第一章非线性规划
3.近似最佳步长公式
2
()
1
( ) () () ()
2
TT
kk k kk k kk
fX
f XPf X f XP PHXPλλλ+≈ +? +
设 存在连续的二阶偏导数，则有泰勒展开式
0
() () 0
TT
kk k kk
df
fX P PHX P
d
λ
λ
λ
≈?+ =
对 求导，并令导数为,得
()
()
T
kk
T
kkk
f XP
PHX P
λ
－
解得,＝
k
fXλ上式即为 的近似最佳步长公式。当（ ）为二次函数时，此公式是精确的。
http://www.tju.edu.cn
第一章非线性规划例：
22
12
()( 1) ( 1),[0 0],( )
T
kkk
k
f Xx x X P fX
λ
=?+? = =?设－
用近似最佳步长公式求 。
12
( ) [2( 1) 2( 1)],( ) [2 2]
20
() ( )
02
2
[2 2]
2
1
20 2
2
[2 2]
022
TT
k
k
fX x x fX
HX HX
λ
==
==
==
解
()
k
fX λ由于 是二次函数，故所求 是精确的。
三、梯度法和共轭梯度法
1.梯度法
()
( ) () ()
T
kk k kk
fX
fX P fX fX Pλλ+? ≈?
设 有连续的二阶偏导数，则有泰勒展开式
0,
() () cos 0
()
,()()
2
cos 1,,
T
kk k k
kk
kk k
fX P fX P
fX P
fX P fX
λ
θ
θ
π
θλ
θθπ
>
<
>+?
nullnullinullnull
由于 应使
＝
其中 为向量 和 的夹角。为使上式成立，
应使 又为使 的绝对值尽量大，应使 ＝- 即 ＝
() ()
kk
k
PfXX fX
P
故 ＝ 即在 点的负梯度方向是使 下降最快的方向。以负梯度作为搜索方向 的下降类算法称为梯度法或最速下降法。
() ( ) ( )0
kkk
pfX fXPfXλ+? <思想：怎样选取 可使 下降最快？即使 且左边差额尽量大。
http://www.tju.edu.cn
第一章非线性规划
★一般步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；(1)
(),(),
3)
kkk
k
XfXfX
X
ε<nullnull对于点,计算 若 则停止计算,
得到近似最优解,否则转( ；
(2)
1
(),
kkk k
kkk
PfXP
XXP
λ
λ
+
=
=+
取 沿 进行一维搜索，得到 和下一个点；
(3)
1
:1,2)
k
fX k k
+
=+计算 （ ），置 转( 。(4)
http://www.tju.edu.cn
第一章非线性规划例:
22
12
0
()( 1) ( 1) 0.1
[0 0]
T
fX x x
X
ε=?+?
=
用梯度法求 的极小点，取 ＝
初始点 。
12 0
22
0
( ) [2( 1) 2( 1)],( ) [2 2]
() (2)(2) 8
T
fX x x fX
fX ε
= =
=?+?=>nullnull
解,
0
0
2
[2 2]
20
2
1
()
20 2
02 2
[2 2]
022
HX
λ
λ
= ==
由近似最佳步长公式求,
,
100 0
*
1
1
( ) [0 0] [ 2 2] [1 1]
2
( ) [0 0],( ) 0
[1 1]
TTT
T
T
XX fX
fX fX
XX
λ
ε
= ==
=? =<
==
nullnull
故
http://www.tju.edu.cn
第一章非线性规划上例中，目标函数是同心圆族。无论初始点选在何处
，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。
但对于一般的函数，若每次迭代均采用负梯度方向，
则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的,拉锯,现象，
收敛速度很慢。可以证明，梯度法是线性收敛的。
注：
http://www.tju.edu.cn
第一章非线性规划
2.共轭梯度法
⑴基本概念
0
,
T
XY n An XAY
XY A AI XY
=
=
设 与 均为 维向量,是 阶对称正定阵。若,
则称 与 关于 共轭。当 则 与 正交。关于共轭，
有下述重要性质：
11
11
1
,0,
1,,,0
0,0
1
nn
nn i
TT
iii
T
ii i n
nnPPA PP
P PR
P Ai n PAP A
PAP P P
nn A
ααα
α
α
+ +=∈
=
>=
+
nullnull
null
null
null
若 个非零 维向量,,关于 共轭，则,,
线性无关。事实上 只需考虑两边分别左乘 （ ）则有 ＝,而正定，即 故,说明,,线性无关。
这一性质也说明不可能有 个 维向量关于 共轭。
★
http://www.tju.edu.cn
第一章非线性规划
1
1
1
2
n
TT
n
nPPH H
fX XHX CX P P
n
=+
null
null
若非零 维向量,,关于 共轭，则以 为二次系数阵的二次函数（ ） 沿,,（称为共轭方向）进行精确一维搜索，至多经 次便可得极小点。
★
这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。
http://www.tju.edu.cn
第一章非线性规划
⑵一般步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；
①
1
min ( ),
kkkkkkk
XfXPXXP
λ
λ λλ
+
+ =+对求解 得和 ；
③
②
00
PfX=取（）；
11
11
:1,3
kkk
T
kk
k
T
kk
PfXPkk
fX fX
fX fX
β
β
++
++
= + = +
取（），置转
（）（）
其中,＝ （F-R法）
（）（）
⑤
④
*
11
0
(),,1,
1,
n
fX X X k n
kn X X
n
ε
++
<=<?
=? =
nullnull若 则停止,否则，若 转,
若,重置 转 ；（重置的原因是由于计算中的舍入误差可能造成 步未终止。）
⑤
②
http://www.tju.edu.cn
第一章非线性规划例：
22
12121 0
31
() 2 [2 4]
22
T
fX x x xx x X=+ =?求 的极小点，取 。
11
12
22
12 21
000
31
1
() [ ] [2 0]
112
( ) [3 2 ]
( ) [ 12 6],( ) [12 6]
T
TT
xx
fX xx
fX x x x x
fX P fX
=
=? ==?
解
00
0
00
12
[12 6]
6
() 5
3112
17
[12 6]
11 6
T
T
PfX
PHP
λ
= ==
10 0
5238
[2 4] [12 6] [ ]
17 17 17
TTT
XX Pλ=+ =? +?=
1
612
()[ ]
17 17
T
fX?=
http://www.tju.edu.cn
第一章非线性规划
11
0
00
6
612
17
[ ]
17 17 12
1
17
12
289
[12 6]
6
T
T
fX fX
fX fX
β
==
（）（）
＝
（）（）
110
11
121
11
6 12 1 90 210
() [ ] [12 6] [ ]
17 17 289 289 289
()17
,[1 1]
10
TTT
T
T
T
PfX P
PfX
XX P
PHP
β
λλ
= + =? +? =
===+=
22
( ) [0 0] [1 1]
TT
fX X?由于 ＝,故 ＝ 即极小点，计算经两步终止。
http://www.tju.edu.cn
第一章非线性规划四、牛顿法与拟牛顿法
1.牛顿法
⑴牛顿方向
() ()
1
() () ()( ) ( ) ()( )
2
TT
kk k kkk
fX fX
fX fX fX XX XX HXXX=++
设 有连续的二阶偏导数，由泰勒展开式,可近似表示为
() ( ) ( )( )
kkk
f XfXHXXX
f
=? +?
从而
当 为二次函数时，上式为精确表达式。
http://www.tju.edu.cn
第一章非线性规划
11
k1
() ( )0
( ) ( )( ) 0
kk
kk k
XfX fX
fX HX X X
+
＋
＋
取 使 达到极小，应有 ＝,即
＋＝
1
k1
1
()
() ()
() (),
k
kk k
kkk
HX
XXHX fX
PHX fX
=
－
＋
－
当 可逆，可解得
＝
记 称为牛顿方向。
()
1
()
k
fX
X
fX
对于正定二次函数,采用牛顿方向作搜索方向，
步长取为，从任意点 出发一步即可得极小点。对于一般函数,在一定条件下，也可采用牛顿方向，
所形成的算法称为牛顿法。
http://www.tju.edu.cn
第一章非线性规划
⑵一般步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；
①
③
1
1
() min( )
kkk kk
kk kkk
PHX fX fXP
XXP
λ
λ
λλ
+
= +
=+
取（）,由求出和；
②
(),
kk
XfXε? <nullnull对于点,若 则停止,否则转3；
当一维搜索是精确的，牛顿法为二阶收敛。
1
:1,
k
fX k k
+
=+计算 （ ），置 转 。
④
②
http://www.tju.edu.cn
第一章非线性规划改进：
构造一个矩阵 代替牛顿方向中的,使 满足：
k
H
k
HX
-1
（）
k
H
k
H
★正定
★ 只用到f (X)的一阶导信息
k
H
★随着k 的增加,充分接近于
*
HX
-1
（）
k
H
称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。
1
()
k
HX
k
H
k
H
缺点：
★计算海赛阵的逆的工作量很大。
★要求f (X)的二阶导存在且海赛阵是正定的( 以保证H
的逆阵存在和算法是下降的);
http://www.tju.edu.cn
第一章非线性规划
2.拟牛顿法
★拟牛顿法是尺度阵 满足的一类变尺度法;
11
(() ( )
kk k k k
XX HfX fX
=
k
H
★拟牛顿法一般是超线性收敛的;
★DFP 是一种著名的拟牛顿法 ;
★当f (X)为二次函数时，DFP 法是共扼方向法，且具有二次终止性。
http://www.tju.edu.cn
第一章非线性规划
DFP方法的一般步骤
0
:0,0
X HHI
k ε
=
=>
选取初始点,和初始对称正定阵,可取（ ）
令 确定精度 ；
①
③
1
11 1111
1
11 111
111 1
,
,
kkkk kkkk
TT
kk kkkk
kk
kk kkk
kkkk k k
P HfX P X X P
XX HGGH
HH
XG GHG
XXXG fX fX
λ λ
+
= = +
ΔΔ ΔΔ
=+?
ΔΔ Δ Δ
Δ=? Δ
取（）沿 进行一维搜索，得 和其中：
＝ （ ）- （ ）
②
(),
kk
XfXε? <nullnull对于点,若 则停止,否则转 ；
③
1
:1,
k
fX k k
+
=+计算 （ ），置 转 。
④
②
例:
22
12121 0
31
() 2 [2 4]
22
T
fX x x xx x X=+ =?求 的极小点，取 。
0
00
0
00
12
[12 6]
6
() 5
3112
17
[12 6]
11 6
T
T
P
fX P
PHP
λ
== =
沿 一维搜索，由共轭方向最佳步长公式可得
11
12
22
12 21 0
0000 0
31
1
() [ ] [2 0]
112
( ) [3 2 ],( ) [ 12 6]
10 12 3 1
,( ),( )
01 6 1 1
TT
xx
fX xx
fX x x x x fX
HPHfXHX
= =?
= = =
解
取＝
1000
1
5238
[ 2 4] [12 6] =[ ]
17 17 17
612
[ ]
17 17
TTT
T
XX P
fX
λ=+ =? +?
=（）
http://www.tju.edu.cn
第一章非线性规划
00 0000
10
00 000
60 210
10 10
60 30 210 90
17 17
30 17 17 0 1 90 17 17 0 1
10
17 17
210
01
60 30
17
17 17 90
17
TT
XX HGGH
HH
XG GHG
ΔΔ ΔΔ
=+?
ΔΔ Δ Δ
=+?
210
10
210 90
17
17 17 0 1 90
17
385 241
1
241 891986
=
010 0 1 0
60 30 210 90
[ ],[ ]
17 17 17 17
X X X G fX fXΔ=?=? Δ =?＝（）-（）
111
69
385 241
1
17 29
()
241 891 12 21986
17 29
PHfX
= =? =?
1
11
1
11
9
612
29
17 17 21
() 29
29
9
17
31
921
29
29 29 1 1 21
29
T
T
P
fX P
PHP
λ
=? =
沿 一维搜索，由共轭方向最佳步长公式
－
＝
2111 2
2
[1 1],( ) [0 0]
[1 1]
TT
T
XX P fX
X
λ=+ =? =
=故 是极小点。
http://www.tju.edu.cn
第一章非线性规划
1.3 约束极值问题
★一般模型
min ( )
()0,1,,
().
()0,1,,
{ |()0,()0}
min ( )
i
j
n
ij
XD
fX
hX i m
NLP st
gX j l
DXRhX gX
NLP f X
∈
==
≥=
= ∈=≥
null
null
记
则（ ）也可以表示为
http://www.tju.edu.cn
第一章非线性规划一、基本概念和性质
1.起作用约束
00 0
,XDX X
XX
∈对于点 在 点等于零的约束称为对 起作用的约束，
在 点不等于零的约束称为对 不起作用的约束。
0
0
()0,1,,
()0,{1,,} ()0( )
X
i
jj
Xhm
gX jJ l gX jJ
==
∈? ≥ ∈
null
null
0
在 点起作用的约束包括全体等式约束 和满足 ＝ 的不等式约束 。
几何意义,位于这些约束的边界上。
00
0
()0
()0( )
j
j
XgX
gX jJ
X
>
≥∈
0
在 的不起作用的约束包括 的不等式约束
。
几何意义,位于这些约束的内部。
http://www.tju.edu.cn
第一章非线性规划
2.可行下降方向
0
000
[0,]
n
PR X D
XPDλλλλ
∈∈
∈∈
方向 在点 称为是可行的
是指存在正数,使对一切 都有 + ;
0
000
()()0
n
PR X D
XPDfXPfXλλ
∈∈
+ ∈+?<
方向 在点 称为下降的
是指存在,有
*
*
NLPX
X
如果 是（ ）的极小点，
则在 不存在可行下降方向。
http://www.tju.edu.cn
第一章非线性规划
3.可行下降方向的条件
()0
()0 ()0
()0
i
ii
j
hX
hX hX
gX
=
≥≤
≥
由于等式约束 可以化为两个不等式约束
,来表示，所以讨论约束条件时可只考虑不等式约束 。
0
0
00
0
()0(1,,)
()-()0
j
PX
gX P j l
fX P fX
PX
λ
λ
+≥=
+<
null
由可行下降方向的定义，某方向 在 点若满足则 是 的可行下降方向。
http://www.tju.edu.cn
第一章非线性规划
000
000
0
( ) ( ) ( ) ( 1,,)
( ) ( ) ( )
T
jjj
T
gX P gX gX P j l
fX P fX fX P
XPD
λλ+≈ +? =
+? ≈?
+∈
null
由泰勒公式其中 是足够小的正数（保证 ）
0
0
() 0
()
0
T
j
T
gX P
P
fX P
P
>
<
不难看出，只要,便保证 是可行下降的。
这可作为 可行下降的充分条件。
00
0
00
() ()
()-()
j
j
PgX P fX
XP
gX fX
几何意义是,与 夹锐角，同时 与- 也夹锐角。
由此可知，如果在 不存在可行下降方向，则一定不存在 同时与 和 夹锐角。
http://www.tju.edu.cn
第一章非线性规划二、最优性条件（ K-T条件）
*
NLP ( ) ( )
NLP
j
fX gX
X
考虑只含有不等式约束的（ ）。设 与 均为连续可微函数,是（ ）的最优解。
**
*
()0
XD X
fX?
如果 是 的内点，即约束对 是不起作用的，则由无约束极值问题的极值必要条件，有 ＝ 。
*
1
**
11
*
*
()0
()0 ( )
()
XgX
gX X gX
fX P
PX
≥
≥?
如果 是某一个约束 的边界点，
即 对 起作用，则必有与- 反向，否则必有 与二者同夹锐角，即 是 的可行下降方向，矛盾。
1
()gX
*
1
()gX?
*
()fX?-
*
X
** * *
1 1
() () () ()g X f X f X g Xγγ ≥
11
故 与 同向，即存在 0，使 ＝ 。
http://www.tju.edu.cn
第一章非线性规划
*
12
**
12
**
12
** *
12
()0 ()0
()0 ()0 ( )
() ()
() () ()
XgXgX
gX gX X fX
gX gX P
fX gX gX
P
≥≥
≥≥?
如果 位于某两个约束 和 的交点，
即 和 均对 起作用，则必有位于 和 的夹角内部，否则也会有 与
－,和 同夹锐角，即存在可行下降方向,矛盾。
*
X
1
()gX
2
()gX
*
()f X?
*
1
()gX?
*
2
()gX?
12
** *
11 2 2
12
() () ()
,0
fX gX gX
γγ
γγ
γγ
≥
故有 和 使下式成立：
＝＋
http://www.tju.edu.cn
第一章非线性规划
*
**
()0
() ()
0
j
jj
jJ
j
XgXjJ
fX gX
jJ
γ
γ
∈
≥∈
≥∈
∑
依此类推，若 点起作用约束为,,
则有 ＝
，
**
1
*
( ) ( )
( ) 0 ( 1,,)
0 ( 1,,)
l
jj
j
jj
j
fX gX
gX j l
jl
γ
γ
γ
==
≥=
∑
null
null
＝
或表示为
＝
*
*
()0
jj
gX
X
γ =其中条件 是为了在梯度组合式中去掉不起作用约束，称为松紧条件。这时要求 点各起作用约束的梯度线性无关。
http://www.tju.edu.cn
第一章非线性规划定理 (K-T条件 )
**
** * ** *
11
*****
11
*
()(1,,) ()
[,,] [,,]
() () ()
( ) 0 1,,
01,,
ij
ml
ii jj
ij
jj
j
XNLP X
hX i m g X j J
fX hX gX
gX j l
jl
λλ γγ
λγ
γ
γ
=? ∈
Λ= Γ=
==
≥=
∑∑
null
nullnull
null
null
＝＝
设 是（ ）的最优解，且在 点各起作用约束的梯度和,线性无关，则存在向量 和 使下式成立：
＝＋
（）
，（ ）
****
11ml
λλγγnullnullK-T条件中的,,和,,称为广义拉格朗日乘子或
K-T乘子。满足K-T条件表达式的可行点称为K-T点。可以证明
K-T条件对凸规划是充要的。
注：关于 K-T定理的证明首先证明 Gordan引理：
其次证明 F-J定理：
*
** *
01
** * *
0
1
*
() ()0
( ) 0 1,,
01,,
l
l
jj
j
jj
j
XNLP
fX g X
gX j l
jl
γγγ
γγ
γ
γ
=
==
≥=
∑
null
null
null
＝
设 是（ ）（只考虑不等式约束）的极小点，
则存在不全为0的数,使下式成立：
-
（）
，（ ）
γ
γ ≠
0
0
如果 =0则定理失效。
为了保证 0，增加了起作用约束的梯度无关的条件（为什么），
便成为K-T条件。
1
1
,...,0,1,...,
,...,0.
T
lj
l
ljj
j
AAln PAP j l
Aμμ μ
=
<=
=
∑1
设 是 个 维向量，不存在向量 使 成立的充要条件是，存在不全为0的非负实数 使
http://www.tju.edu.cn
第一章非线性规划例：利用 K－ T条件求解下面的非线性规划
2
min ( ) ( 3)
.,0 5
fX x
st x
=?
≤≤
2
1
2
min ( ) ( 3)
,,( ) 0
( ) 5 0
fX x
st g X x
gX x
=?
=≥
=?≥
解 原问题可写为
12
12
"( ) 2 0," ( ) " ( ) 0
() () ()
fX gX g X
fX gX gX
=> = =因为故 解为凸函数,和 均为凹函数，
此问题为凸规划。
http://www.tju.edu.cn
第一章非线性规划为解此方程组，可分几种情况考虑：
12
12
1
2
12
()2 3 ()1,() 1
23 0
0
(5 ) 0
,0
fX x gX gX
KT
x
x
x
γγ
γ
γ
γγ
=?=?
=
=
≥
＝（ ）,
条件表达式为
（）－＋＝
**
3()0xfx= =由于此问题为凸规划，故 是最有解，相应最优值 。
12
0γ γ≠ ≠0且,无解；
①
12
03,xKTγ γ= =＝,解得 满足约束，是 － 点；
④
12 2
00 5,4,γ γγ= ≠==且,解得 － 不是 － 点；
③
12 1
0 0 0,6,xKTγ ≠ ==且 ＝,解得 － 不是 － 点；
②
http://www.tju.edu.cn
第一章非线性规划例,考虑非线性规划并验证它为凸规划，用 K－ T条件求解。
12
12
12
max ( ) ln( 1)
23
,,
,0
f Xxx
xx
st
xx
= +
+≤
≥
12
112
21
22
min ( ) ln( 1)
,,( ) 3 2 0
( ) 0
( ) 0
f Xxx
st g X x x
gX x
gX x
=?+?
=≥
=≥
=≥
解 原问题可写为
http://www.tju.edu.cn
第一章非线性规划计算目标和约束函数的海赛阵
12
1
3
1
( ) 1 ( ) [ 2 1],( ) [1 0],
(1)
()[0 1]
-
T
TT
T
fX gX gX
x
gX
KT
= = =
+
=
，
表达式为：
123
2
1
1
0
0 0
(1)() 0,() () () 0
0 0
0 0
fggg
xHX HX HX HX
+=≥===≤
故此问题是凸规划。
http://www.tju.edu.cn
第一章非线性规划
1112
13
0030
00
xx
x
γ γ
γ
≠若 ＝,则无解，于是,有 ＝
令＝，＝，则有
12
1
2
0
1
30x
γγ
γ
=
1－2 ＋ ＝
－＝0
（）
12 12
0xxγγ
T
解得 ＝0,＝3,＝ ＝,显然[0 3]是可行点，从而是极小点。
12
1
12
112
21
32
123
1
2
(1)
1
32 0
0
0
,,0
x
xx
x
x
γ γ
γγ
γ
γ
γ
γγγ
+
=
=
=
≥
＝- ＋
＝- ＋
（）
http://www.tju.edu.cn
第一章非线性规划三、二次规划
★一般模型
min ( )
1
2
0
,,
0
,
TT
fX XHX CX
AX b
st
X
Amn bm Cn
= +
+≥
≥
×其中 为 阶矩阵； 为 维非负向量； 为 维向量。
0K-TH ≥
由于二次规划的约束是线性的，从而是凸集，故当目标的二次项系数矩阵 （半正定）时为凸规划，可用 条件求解。
http://www.tju.edu.cn
第一章非线性规划
11
22
( )
( ) 0
( ) 0
fX HX C
gX A g AX b m
gX I g X n
=+
= +≥
= ≥
则梯度：
与约束 （ 个）相对应，
与约束 （ 个）相对应。
min ( )
1
2
0
,,
0
TT
fX XHX CX
AX b
st
X
= +
+≥
≥
[]
[]
111
22
() -
() -,-
T
m
T
mmn
g
g
XKT Yyy
XKT Yy y KT
++
null
null
记相应于 的 乘子为 ＝,相应于的 乘子为 ＝ 则由 条件及约束条件，有：
http://www.tju.edu.cn
第一章非线性规划
12
1
2
12
0
0
0
,,0
T
T
T
TT
HX C A YIY
YAXb
YX
AX b
XY Y
+ +
+
+≥
≥
＝
（）＝
＝
上面的一组式子中，若不考虑两个松紧条件，则其余均为线性表达式，即：
12
12
0
,,0
T
TT
HX A CYIY
AX b
XY Y
+ +
+≥
≥
＝
思考,能否在此基础上构想基于线性规划求解的方法?
http://www.tju.edu.cn
第一章非线性规划
[ ]
1
0
T
n
Z zznull如果在上面第一式中增加人工变量 ＝ （为使出现单位阵），并增加使人工变量之和极小化的目标函数
（为使人工变量最后均为 ），则可构造一个线性规划：
1
12
12
min
sgn( )
,,
,,,,0
sgn( )
n
T
s
TT
s
s
HX A C
zz z
YIY CZ
st AX X b
XY Y ZX
CZ Z C
X
+
=++
++
+=
≥
null
＝
其中 表示 中各分量的符号与 中相应分量的符号相同，是为了保证出现单位阵； 是松弛变量。
用单纯形法求解该规划的单纯形初表为下表。
http://www.tju.edu.cn
第一章非线性规划
12
1
2
12
,,
0
0
T
s
T
s
XY Y
YX
YX
YX YX
为使所求得的 还满足松紧条件
＝
＝
应在每次单纯形表的迭代中保证 与 以及 与的相应分量不同时为基变量。
B
X
1
Bb
X
s
X
1
Y
2
Y
Z
Z C H? 0
T
A
sgn( )CI
s
X
b
A? I
0
0
0
I
http://www.tju.edu.cn
第一章非线性规划例,求解二次规划
22
12 1 2
12
12
min ( )
1
(2 2 ) 8 10
2
63 2 0
,.
0,0
fX x xxx
xx
st
xx
= +
≥
≥≥
112 23
2 0
,[ 3 2],[ 8 10],6
0 2
,[ ]
0,K-T
T
T
HA C b
YyY yy
H
====
==
>显然有 故此问题是凸规划。可用 条件求解。
解
http://www.tju.edu.cn
第一章非线性规划
12
211
1
322
1
3
2
sgn( )
2 0 3 8
0 2 2 10
[3 2] 6
T
s
HX A YIY CZ
yxz
y C
y
x
AX X x b
x
+ ++
=?++?==
+= +==
12
1121
2132
123
12312 312
13 21 32
2
2
3
min
38
0
,,
26
,,,,,,,0
00,0
x
x
x
zzz
yyz
yyz
st
xx
xxxyyyzz
yx yx yx
=+
+?+=
+?+=
++=
≥
相应的线性规划为求解时还要满足松紧条件 ＝,＝,＝ 。
11
3/13-2/13-4/3914/130
9/26-3/13-9/263/132/13133/130
132/130
2/31-2/3-4/9-26/9
31/32/3120
33/131-2/3-12/34/9[26/9]22/31
1/3-1/31-2/9-4/94/30
11-51/3-2/3
1/32/3120
51-122101
4/31-1[3]-2/3-4/341
11-5-2-2
212[3]60
1-122101
41-13281
1100000
0
B
C
B
X
1
B b
θ
1
x
1
x
1
x
1
x
2
x
2
x
3
x
3
x
1
y
1
y
1
y
2
y
3
y
1
z
1
z
1
z
2
z
2
z
2
z
2
z
1
z
http://www.tju.edu.cn
第一章非线性规划求得的结果是：
12 31 23
433 32
,,0,,0,0
13 13 13
xxxyyy======
1
3131
*
433
[ ]
13 13
T
y
xyxx
X =
在每一次单纯行表迭代中都考虑了松紧条件，如在第一张表中，按通常规则应让 进基，但考虑到与它构成松紧式的 已在基中，并且 进基也不会使 出基，故选择 进基，
从而所得解 满足松紧条件，是原来二次规划的最优解。
http://www.tju.edu.cn
第一章非线性规划四、罚函数法基本思想：将约束与目标组合在一起，化为无约束极值问题求解。
★
内点法：从可行域的内部逐步逼近最优解。★
外点法：从可行域的外部逐步逼近最优解。★
http://www.tju.edu.cn
第一章非线性规划外点法的关键是基于（ NLP）构造一个新的目标函数
P（ X,M），称为罚函数。
22
11
(,) () [min(0,())] ()
lm
ji
ji
PXM f X M g X M h X
M
M
==
=+ +
∑∑
式中 是一个充分大的正数，称做罚因子。
含 的项称 为罚项。
当 X是可行点时，罚项为 0
当 X不是可行点时，罚项是很大的正数。
对 P（ X,M）求极小，可采用无约束优化方法，罚项能保证 X逐步趋近可行域。
http://www.tju.edu.cn
第一章非线性规划一般步骤：
0,,1,0Mkε>=>
1
选取初始罚因子 令 ；①
min (,),
kkk
M PXM X对于,求解无约束极值问题 得 ；②
1
|( )| ( 1,,)
( ) ( 1,,)
NLP,
1,2
k
ik
ik
kkk
X
hX i m
gX j l
XMM
kk
ε
ε
≤=
≥? =
>
+
null
null
＋
若 满足可行性的精度要求
则停止,即为（ ）的近似最优解，否则，取置＝ 转。
③
,PXM
M →+∞
用罚函数法求解一些简单的非线性规划时，可先求出（ ）
的驻点，然后令 。
http://www.tju.edu.cn
第一章非线性规划例：求解非线性规划
3
12
1
2
min ( )
1
(1)
3
10
,.
0
fX x x
x
st
x
= + +
≥
≥
322
12 1
1
(,) ( 1) [min(0,1)] [min(0,)]
3
PXM x x M x M x=+++?+
解 构造罚函数
2
11
1
2
2
( 1) 2 [min(0,1)] 0
1 2 [min(0,)] 0
P
xMx
x
P
Mx
x
= ++?=
=+ =
令
11 2
10 1,0 10xx x?≥ =? ≥当,不可行；当,由第二式有＝,矛盾，
说明可行域内无驻点。
http://www.tju.edu.cn
第一章非线性规划
12
2
1
2
10,0,
41
1
2
xx
xM MM
x
M
< <
+
=?
对于可行域外的点（满足 ）可解得驻点
＝
1
2( 1) 2 0
0
02
xM
H
M
++
=>
在该点，海赛阵
说明该驻点是极小点。
[]
T
1
2
1
M,
0
x
x
→
→+∞
→
令 则,而 1 0 满足约 束，是最优解。
http://www.tju.edu.cn
第一章非线性规划例：求解非线性规划
22 2
12 12 1
(,) [min(0,)] [min(0,)]PXM x x M x x M x=++?+ +
解 构造罚函数
2
12 1 1
1
2
12
2
1 2 [min(0,)]( 2 ) 2 [min(0,)] 0
1 2 [min(0,)] 0
P
MxxxMx
x
P
Mxx
x
=+? +? + =
=+? + =
考察其驻点，令
12
2
12
1
min ( )
0
,.
0
fX x x
xx
st
x
= +
+≥
≥
http://www.tju.edu.cn
第一章非线性规划
12
2
12 1 1
2
12
10,0,
12 ( )(2)2 0
12 ( ) 0
xx
Mx x x Mx
Mx x
< <
+?+?+ =
+?+=
对于可行域外的点（满足 ） 可解得驻点
[]
T
1
2
0
,
0
x
M
x
→
→+∞
→
令 则,而 0 0 是可行点，故是最优解。
1
2
2
1
2( 1)
11
4( 1) 2
x
M
x
M M
+
=?
+
＝
解得
天津大学研究生精品课程运筹学——
运筹学 A、运筹学 B、管理运筹学
-运筹学 A是针对管理专业本科没学过运筹学的学生开设的学位课
-运筹学 B是针对管理专业本科已学过运筹学的学生开设的学位课
-管理运筹学是针对非管理专业的学生开设的选修课
http://www.tju.edu.cn
第一章非线性规划第一章非线性规划
(Nonlinear Programming)
1.1 基本概念
1.2 无约束极值问题
1.3 约束极值问题
http://www.tju.edu.cn
第一章非线性规划请回顾线性规划:,其目标与约束函数均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。
非线性规划（Nonlinear Programming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。
≥
≤
=
0
..
X
bAX
ts
CXMaxz
http://www.tju.edu.cn
第一章非线性规划
1.1 基本概念一、非线性规划问题与模型
1.问题
⑴生产计划问题
max ( ) ( ) ( )
() 0
..
() 0
i
j
f xxPxxCx
gx
st
hx
=?
≥
=
x:产量 ;P(x):价格 ;C(x):成本
http://www.tju.edu.cn
第一章非线性规划
⑵投资决策问题
111
1
::
::
max ( )
..
0
jj
j
ij
nnn
jj ijij
jij
n
jj
j
j
xj Pj
Bj
ij
fx x xx
Px B
st
x
μ
βσ
μβ σ
===
=
=?
≤
≥
∑∑∑
∑
第 种股票的购买量； 第 种股票的价格总资金； 第 种股票的每股平均收益风险系数； 第 种与第 种股票收益的协方差
http://www.tju.edu.cn
第一章非线性规划
2.模型
1
min ( )
()0,1,,
().
()0,1,,
[,,]
{ |()0,()0}
min ( )
i
j
T
n
n
ij
XD
n
n
fX
hX i m
NLP st
gX j l
Xx x
DXRhX gX
NLP f X
DNLP
DR NLP
D R NLP
∈
==
≥=
=
=∈ = ≥
≠
null
null
null其中记则（ ）也可以表示为其中 称为（ ）的约束集或可行域。
当 ＝ 时，（ ）称做无约束极值问题；
当 时，（ ）称做约束极值问题。
http://www.tju.edu.cn
第一章非线性规划二,模型的解及相关概念
1.可行解与最优解
★可行解：约束集D中的 X。
★最优解：如果有,对于任意的,
都有,则称 为（NLP ）的最优解，也称为全局最小值点。
*
X D∈
X D∈
*
() ()f XfX≤
*
X
★局部最优解：如果对于,使得在 的邻域 中的任意都有,则称 为（NLP）的局部最优解，也称为局部最小值点。
0
X D∈
0
X
X D∈
0
() ()f XfX≤
00
(,){| }BX X X Xε ε=?<nullnull
0
X
http://www.tju.edu.cn
第一章非线性规划例：考虑非线性优化问题
22
12
12
min ( ) ( 2) ( 2)
,,6
fX x x
st x x
=?+?
+=
2
x
1
x
6
6
3
3
如果约束改为呢？
12
6xx+ ≤
http://www.tju.edu.cn
第一章非线性规划
2.梯度、海塞阵与泰勒公式
★梯度
00
00
00
0
1
() ()
() ( )
() ()
()[ ]
T
n
f XX f XX n
fX X fX
fX fX
fX
xx
null
若 在 的邻域内有连续一阶偏导数，则称 在 点对个变元的偏导数组成的向量为 在 的梯度，记为,
即＝，
00
()XfXX
几何意义：
梯度是过 点且与 在 的切平面垂直的向量，
梯度向量的方向是函数值在该点增加最快的方向。
http://www.tju.edu.cn
第一章非线性规划
★海塞阵
00
0
0
00
00
11
00
1
2
22
2
22
2
() ()
()
()
() ()[ ]
() ()
() ()
ij
n
nn
nn
f XX f XX n
fX X
fX
HX HX
xx
fX fX
xxx
fX fX
xx x
×
…
=
nullnullnull
null
若 在 的邻域内有连续二阶偏导数，则称 在 点对个变元两两组合的二阶偏导数组成的矩阵为 在 的海赛阵，
记为,即 =
http://www.tju.edu.cn
第一章非线性规划
★泰勒公式
00
00 0 000
2
0
22
000
() ()
() () ()
1
()()()
2
( )
()
TT
fX X fX X
fX fX fX XX XX HXXX
oXX
oXX X X XX
+? +
+
→?
nullnull
nullnull nullnull
若 在 的邻域内有连续二阶偏导数，则可写出 在 点的（二阶）泰勒展开式：
＝ （－）
－
其中,是当 时 的高阶无穷小。
http://www.tju.edu.cn
第一章非线性规划例：写出 在 点的二阶泰勒展开式。
2
12
()3 sinfX x x= +
0
[0,0]
T
X =
12 0
0
2
()[6 ( )[0 1 cos ],]
60 60
(),( )
0sin 00
TT
fX x fXx
HX HX
x
=? =
==
解:
211
12
22
() 0[0 1
60
1
][ ] ()
002
xx
fX xxoX=+
++
nullnull
2
0
2
12
()
( ) 3
()fX
fX x
oX X
x=
nullnull如果忽略了 在，则 点的近似表达式为
+
http://www.tju.edu.cn
第一章非线性规划
3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n( n>1)元函数 与一元函数 的极值条件加以对比并归纳如下：
()fX ()fx
充分条件必要条件
00
()X x或 是极小点
()f x一元函数
()f Xn元函数
0
'( ) 0fx=
0
()0fX? =
00
'()0,'()0fx fx= >且
00
()0 ()0fX HX?= >且
0
()0HX >注,表示海赛阵正定。如果一个方阵的各阶主子式均大于零，则可以判定该方阵是正定的。
http://www.tju.edu.cn
第一章非线性规划例：求 的极小值点。
22
1122
() 2 2840fX x xxx=? +?+
解
12
12
0
()[
()0
][4 8 4 4]
[2 1]
TT
T
ff
fX
xx
fX X
xx
=
=
＝
＝,解得驻点令
0
0
40
(),( )0
04
HX HX
X
= >
又故 是极小值点。
http://www.tju.edu.cn
第一章非线性规划
4.凸规划
★凸函数：f (X)是定义在凸集D上且满足对任意有下式成立的函数：
121 2
()((1 ) ) (1 ) ( )fX fXX f Xααα α≤+? +?
12
,,X XD∈
[0,1]α∈
若不等式中严格不等号成立，则称f (X)为严格凸函数注：判断一个可导函数f (X)是否是凸函数的方法一元函数f (x),二阶导大于等于零;
多元函数f (X),海塞阵半正定。
http://www.tju.edu.cn
第一章非线性规划
★凸规划性质：★约束集是凸集；
★最优解集是凸集；
★任何局部最优解也是全局最优解；
★若目标函数是严格凸函数，且最优解存在，则其最优解是唯一的。
在非线性规划模型（NLP ）中，若目标函数f （ X）是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（NLP ）是一个凸规划。
( ),1,,
j
gX j l= null
(),1,,
i
hX i m= null
http://www.tju.edu.cn
第一章非线性规划例：判断下面的非线性规划是否为凸规划
12
22
12
12
max ( )
1
..
,0
fX xx
xx
st
xx
= +
+≤
≥
12
22
112
21
32
min( ( ))
()1 0
.,( ) 0
() 0
fX xx
gX x x
st g X x
gX x
=
=≥
=≥
=≥
一般化
1
23
()
00 20
0,( ) 0
00 02
00
() () 0
00
fg
gg
HX HX
HXHX
=
≥=>
==≥
计算
123
() () () ()fX gX gX gX?说明 是凸函数,、,是凹函数因此，本模型是凸规划。
http://www.tju.edu.cn
第一章非线性规划
1.2 无约束极值问题
★一般模型：
min ( )
n
XR
f X
∈
★求解：当f (X)可微，可应用极值条件求解，但往往得到一个非线性的方程组，求解十分困难。因此，一般采用迭代的方法，称为下降类算法。
http://www.tju.edu.cn
第一章非线性规划一、下降类算法的基本步骤与算法收敛性
1.基本思想
0
0
1
12
()fX
X
P
X
PX
基本思想是使 逐步下降，逐渐趋近其最小值。迭代方式是从一个初始点 出发，选取某一搜索方向,沿该方向搜索到下一个点 。若达到与最优解误差的精度要求，则停止，否则再沿该点的某一方向 搜索下一个点 。
这一过程如图所示：
0
P
1
P
2
P
0
X
1
X
3
X
2
X
http://www.tju.edu.cn
第一章非线性规划
2.基本步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；
(1)
(),(),
3
kkk
k
XfXfX
X
ε<nullnull对于点,计算 若 则停止,
得到近似最优解,否则转（）；
(2)
kk
XP从 出发，确定搜索方向 ；
(3)
1
,
,,1,2)
kk
kkkk
PXXP
XX Pkk
λ λ
λ
+
+
+=+
沿 方向搜索，即由 ＝ 确定搜索步长得到下一个点 ＝ 令 转( 。
(4)
注：不同的搜索方向，就形成了不同的算法，不同的算法所产生的点列收敛于最优解的速度也不一样。
http://www.tju.edu.cn
第一章非线性规划
3.收敛性衡量标准：
*
1
*
lim
k
k
k
XX
XX
α
β
+
→∞
=
nullnull
nullnull
1,0 1,{ }
k
Xα β=<<则称 是线性收敛的；
①
1,0,{ }
k
Xα β==则称 是超线性收敛的；
②
2,0,{ }
k
Xα β=≤<+∞则称 是二阶收敛的。
③
二阶收敛 超线性收敛 线性收敛
null
null
http://www.tju.edu.cn
第一章非线性规划二、一维搜索
:
精确搜索：
一维搜索分数法近似搜索 0.168法其他方法（导数信息）
0
min ( ),
kk
k
f XP
λ
λ
λ
≥
+通过求极值得到最佳步长
k
λ
求上面极值的近似值得到近似最佳步长
http://www.tju.edu.cn
第一章非线性规划
1.分数法（斐波那契法）
2
t
⑴基本思想
*
t
0
a
b
'
1
t
1
t
()f t
t
怎样在区间中取点最好？
'
11
() ()f tft<若
12
() ()f tft<若
http://www.tju.edu.cn
第一章非线性规划
[,],0
nn
nabε >设第 次缩短后的小区间为 给定的精度要求为
★满足绝对精度：
★满足相对精度：
||
nn
baε? <
||
nn
ba
ba
ε
<
★斐波那契数：
12
01
1
nn n
FF F
FF
=+
==
55342113853211
9876543210
n
F
n
1
(1 )( )
n
n
F
aba
F
+
1
()
n
n
F
aba
F
+?
a b
1
t
'
1
t
''
1
11 1
1
'
12 2
1
1
11 1
'
121 -11
12 21
132
[,],
(1 - )( - )
[,],
()
[,] -1 [,]
1
(-)
n
n
n
nnnnn
n
nn n
n
nn
nn
nn
F
tt tb
F
F
ba
FFFFF
tat
F
FF F
ba
F
at t t n a b
FF FF
ba
FF FF F
==
=inulli
1
若按 的比例在区间中对称地取点 和,经比较后去掉则 在 中所占的比例为 再按比例在 中取 与 对称，这样反复 次后所得的小区间长缩短为 (),
1
()
11
-
n
n
n
ba
ba
F
Fn
ba F F
ε
=<
与原区间长之比为：
，恰为相对精度表达式。于是，开始可由 解出,
⑵步骤
①
1;
n
n
F
ε由所给精度 和 定
11
1
'''
1
1111
11
(1 - )( - )
() max{ }
,[,]
nn
n
n
FF
tba
F
tbaftft ftft
F
ab
由 的比例在区间[a,b]中对称地取点 =a+ 和
=a+,比较 ( )和 ( )，去掉 ( ),( )相应点以外的区间得到新区间 ；
②
2
11 2
1
'
211
22
[,] ( )
() min{(),()}
[,]
n
n
F
ab t
F
ft ft ft
ab
在 中按 的比例取点 与区间中所剩的点对称比较 和,去掉较大者对应点以外的区间，得到新区间 ；
③
3
22 3
2
*
1
-1 1
2
[,]
[,]
n
n
nn
F
ab t
F
F
ab t
F
在 中按 的比例取点 再比较、再缩短，直到取完
，最后的小区间 中的任意一点可作为 的近似值。
④
http://www.tju.edu.cn
第一章非线性规划例：
2
() 2 [ 1,3]
8
ft t t=?+?用分数法求 在区间 上的近似极小点，
要求缩短后的区间长度不大于原区间长的 ％。
**
''( ) 2 0,
'( ) 2 1 0
1
1.75
2
ft
ft
ft t
tft
= >
=
解 由于所以（）是严格的凸函数。
由 ＝ －＝,
解得 是极小点，（ ）＝
http://www.tju.edu.cn
第一章非线性规划
5
6
11
''
1
4
11
5
2
21
11 8
0.08 12.5,6,
0.08 13
8
1 (1 )[3 ( 1)] 0.538,( ) 1.751
13
8
1 [3 ( 1)] 1.462,( ) 2.675 ( )
13
5
[,] [ 1,1.462],
8
5
1 (1 )[1.462 ( 1)] 0.077,
8
( ) 2.083 ( ),
n
n
F
Fn
FF
tft
ft
F
ab
F
t
ft ft
≤≥= ==
=? + = =
=? + = = >
=? =
=? + =?
=>
由 知 查表得故
22
55
[,] [ 0.077,1.462]
0.538 ( ) 1.751
ab
tft
=?
=
故依此进行，得 ＝ 为近似极小点，
http://www.tju.edu.cn
第一章非线性规划
2,0.618法
★区别：每次取点得比例是定值0,618，即每次区间内两点的位置均在新区间长度的0.382和0,618处。
★特点：简单，更易于应用；
效果也比较好。
http://www.tju.edu.cn
第一章非线性规划
3.近似最佳步长公式
2
()
1
( ) () () ()
2
TT
kk k kk k kk
fX
f XPf X f XP PHXPλλλ+≈ +? +
设 存在连续的二阶偏导数，则有泰勒展开式
0
() () 0
TT
kk k kk
df
fX P PHX P
d
λ
λ
λ
≈?+ =
对 求导，并令导数为,得
()
()
T
kk
T
kkk
f XP
PHX P
λ
－
解得,＝
k
fXλ上式即为 的近似最佳步长公式。当（ ）为二次函数时，此公式是精确的。
http://www.tju.edu.cn
第一章非线性规划例：
22
12
()( 1) ( 1),[0 0],( )
T
kkk
k
f Xx x X P fX
λ
=?+? = =?设－
用近似最佳步长公式求 。
12
( ) [2( 1) 2( 1)],( ) [2 2]
20
() ( )
02
2
[2 2]
2
1
20 2
2
[2 2]
022
TT
k
k
fX x x fX
HX HX
λ
==
==
==
解
()
k
fX λ由于 是二次函数，故所求 是精确的。
三、梯度法和共轭梯度法
1.梯度法
()
( ) () ()
T
kk k kk
fX
fX P fX fX Pλλ+? ≈?
设 有连续的二阶偏导数，则有泰勒展开式
0,
() () cos 0
()
,()()
2
cos 1,,
T
kk k k
kk
kk k
fX P fX P
fX P
fX P fX
λ
θ
θ
π
θλ
θθπ
>
<
>+?
nullnullinullnull
由于 应使
＝
其中 为向量 和 的夹角。为使上式成立，
应使 又为使 的绝对值尽量大，应使 ＝- 即 ＝
() ()
kk
k
PfXX fX
P
故 ＝ 即在 点的负梯度方向是使 下降最快的方向。以负梯度作为搜索方向 的下降类算法称为梯度法或最速下降法。
() ( ) ( )0
kkk
pfX fXPfXλ+? <思想：怎样选取 可使 下降最快？即使 且左边差额尽量大。
http://www.tju.edu.cn
第一章非线性规划
★一般步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；(1)
(),(),
3)
kkk
k
XfXfX
X
ε<nullnull对于点,计算 若 则停止计算,
得到近似最优解,否则转( ；
(2)
1
(),
kkk k
kkk
PfXP
XXP
λ
λ
+
=
=+
取 沿 进行一维搜索，得到 和下一个点；
(3)
1
:1,2)
k
fX k k
+
=+计算 （ ），置 转( 。(4)
http://www.tju.edu.cn
第一章非线性规划例:
22
12
0
()( 1) ( 1) 0.1
[0 0]
T
fX x x
X
ε=?+?
=
用梯度法求 的极小点，取 ＝
初始点 。
12 0
22
0
( ) [2( 1) 2( 1)],( ) [2 2]
() (2)(2) 8
T
fX x x fX
fX ε
= =
=?+?=>nullnull
解,
0
0
2
[2 2]
20
2
1
()
20 2
02 2
[2 2]
022
HX
λ
λ
= ==
由近似最佳步长公式求,
,
100 0
*
1
1
( ) [0 0] [ 2 2] [1 1]
2
( ) [0 0],( ) 0
[1 1]
TTT
T
T
XX fX
fX fX
XX
λ
ε
= ==
=? =<
==
nullnull
故
http://www.tju.edu.cn
第一章非线性规划上例中，目标函数是同心圆族。无论初始点选在何处
，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。
但对于一般的函数，若每次迭代均采用负梯度方向，
则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的,拉锯,现象，
收敛速度很慢。可以证明，梯度法是线性收敛的。
注：
http://www.tju.edu.cn
第一章非线性规划
2.共轭梯度法
⑴基本概念
0
,
T
XY n An XAY
XY A AI XY
=
=
设 与 均为 维向量,是 阶对称正定阵。若,
则称 与 关于 共轭。当 则 与 正交。关于共轭，
有下述重要性质：
11
11
1
,0,
1,,,0
0,0
1
nn
nn i
TT
iii
T
ii i n
nnPPA PP
P PR
P Ai n PAP A
PAP P P
nn A
ααα
α
α
+ +=∈
=
>=
+
nullnull
null
null
null
若 个非零 维向量,,关于 共轭，则,,
线性无关。事实上 只需考虑两边分别左乘 （ ）则有 ＝,而正定，即 故,说明,,线性无关。
这一性质也说明不可能有 个 维向量关于 共轭。
★
http://www.tju.edu.cn
第一章非线性规划
1
1
1
2
n
TT
n
nPPH H
fX XHX CX P P
n
=+
null
null
若非零 维向量,,关于 共轭，则以 为二次系数阵的二次函数（ ） 沿,,（称为共轭方向）进行精确一维搜索，至多经 次便可得极小点。
★
这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。
http://www.tju.edu.cn
第一章非线性规划
⑵一般步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；
①
1
min ( ),
kkkkkkk
XfXPXXP
λ
λ λλ
+
+ =+对求解 得和 ；
③
②
00
PfX=取（）；
11
11
:1,3
kkk
T
kk
k
T
kk
PfXPkk
fX fX
fX fX
β
β
++
++
= + = +
取（），置转
（）（）
其中,＝ （F-R法）
（）（）
⑤
④
*
11
0
(),,1,
1,
n
fX X X k n
kn X X
n
ε
++
<=<?
=? =
nullnull若 则停止,否则，若 转,
若,重置 转 ；（重置的原因是由于计算中的舍入误差可能造成 步未终止。）
⑤
②
http://www.tju.edu.cn
第一章非线性规划例：
22
12121 0
31
() 2 [2 4]
22
T
fX x x xx x X=+ =?求 的极小点，取 。
11
12
22
12 21
000
31
1
() [ ] [2 0]
112
( ) [3 2 ]
( ) [ 12 6],( ) [12 6]
T
TT
xx
fX xx
fX x x x x
fX P fX
=
=? ==?
解
00
0
00
12
[12 6]
6
() 5
3112
17
[12 6]
11 6
T
T
PfX
PHP
λ
= ==
10 0
5238
[2 4] [12 6] [ ]
17 17 17
TTT
XX Pλ=+ =? +?=
1
612
()[ ]
17 17
T
fX?=
http://www.tju.edu.cn
第一章非线性规划
11
0
00
6
612
17
[ ]
17 17 12
1
17
12
289
[12 6]
6
T
T
fX fX
fX fX
β
==
（）（）
＝
（）（）
110
11
121
11
6 12 1 90 210
() [ ] [12 6] [ ]
17 17 289 289 289
()17
,[1 1]
10
TTT
T
T
T
PfX P
PfX
XX P
PHP
β
λλ
= + =? +? =
===+=
22
( ) [0 0] [1 1]
TT
fX X?由于 ＝,故 ＝ 即极小点，计算经两步终止。
http://www.tju.edu.cn
第一章非线性规划四、牛顿法与拟牛顿法
1.牛顿法
⑴牛顿方向
() ()
1
() () ()( ) ( ) ()( )
2
TT
kk k kkk
fX fX
fX fX fX XX XX HXXX=++
设 有连续的二阶偏导数，由泰勒展开式,可近似表示为
() ( ) ( )( )
kkk
f XfXHXXX
f
=? +?
从而
当 为二次函数时，上式为精确表达式。
http://www.tju.edu.cn
第一章非线性规划
11
k1
() ( )0
( ) ( )( ) 0
kk
kk k
XfX fX
fX HX X X
+
＋
＋
取 使 达到极小，应有 ＝,即
＋＝
1
k1
1
()
() ()
() (),
k
kk k
kkk
HX
XXHX fX
PHX fX
=
－
＋
－
当 可逆，可解得
＝
记 称为牛顿方向。
()
1
()
k
fX
X
fX
对于正定二次函数,采用牛顿方向作搜索方向，
步长取为，从任意点 出发一步即可得极小点。对于一般函数,在一定条件下，也可采用牛顿方向，
所形成的算法称为牛顿法。
http://www.tju.edu.cn
第一章非线性规划
⑵一般步骤
0
:0,0Xk ε= >选取初始点,令 确定精度 ；
①
③
1
1
() min( )
kkk kk
kk kkk
PHX fX fXP
XXP
λ
λ
λλ
+
= +
=+
取（）,由求出和；
②
(),
kk
XfXε? <nullnull对于点,若 则停止,否则转3；
当一维搜索是精确的，牛顿法为二阶收敛。
1
:1,
k
fX k k
+
=+计算 （ ），置 转 。
④
②
http://www.tju.edu.cn
第一章非线性规划改进：
构造一个矩阵 代替牛顿方向中的,使 满足：
k
H
k
HX
-1
（）
k
H
k
H
★正定
★ 只用到f (X)的一阶导信息
k
H
★随着k 的增加,充分接近于
*
HX
-1
（）
k
H
称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。
1
()
k
HX
k
H
k
H
缺点：
★计算海赛阵的逆的工作量很大。
★要求f (X)的二阶导存在且海赛阵是正定的( 以保证H
的逆阵存在和算法是下降的);
http://www.tju.edu.cn
第一章非线性规划
2.拟牛顿法
★拟牛顿法是尺度阵 满足的一类变尺度法;
11
(() ( )
kk k k k
XX HfX fX
=
k
H
★拟牛顿法一般是超线性收敛的;
★DFP 是一种著名的拟牛顿法 ;
★当f (X)为二次函数时，DFP 法是共扼方向法，且具有二次终止性。
http://www.tju.edu.cn
第一章非线性规划
DFP方法的一般步骤
0
:0,0
X HHI
k ε
=
=>
选取初始点,和初始对称正定阵,可取（ ）
令 确定精度 ；
①
③
1
11 1111
1
11 111
111 1
,
,
kkkk kkkk
TT
kk kkkk
kk
kk kkk
kkkk k k
P HfX P X X P
XX HGGH
HH
XG GHG
XXXG fX fX
λ λ
+
= = +
ΔΔ ΔΔ
=+?
ΔΔ Δ Δ
Δ=? Δ
取（）沿 进行一维搜索，得 和其中：
＝ （ ）- （ ）
②
(),
kk
XfXε? <nullnull对于点,若 则停止,否则转 ；
③
1
:1,
k
fX k k
+
=+计算 （ ），置 转 。
④
②
例:
22
12121 0
31
() 2 [2 4]
22
T
fX x x xx x X=+ =?求 的极小点，取 。
0
00
0
00
12
[12 6]
6
() 5
3112
17
[12 6]
11 6
T
T
P
fX P
PHP
λ
== =
沿 一维搜索，由共轭方向最佳步长公式可得
11
12
22
12 21 0
0000 0
31
1
() [ ] [2 0]
112
( ) [3 2 ],( ) [ 12 6]
10 12 3 1
,( ),( )
01 6 1 1
TT
xx
fX xx
fX x x x x fX
HPHfXHX
= =?
= = =
解
取＝
1000
1
5238
[ 2 4] [12 6] =[ ]
17 17 17
612
[ ]
17 17
TTT
T
XX P
fX
λ=+ =? +?
=（）
http://www.tju.edu.cn
第一章非线性规划
00 0000
10
00 000
60 210
10 10
60 30 210 90
17 17
30 17 17 0 1 90 17 17 0 1
10
17 17
210
01
60 30
17
17 17 90
17
TT
XX HGGH
HH
XG GHG
ΔΔ ΔΔ
=+?
ΔΔ Δ Δ
=+?
210
10
210 90
17
17 17 0 1 90
17
385 241
1
241 891986
=
010 0 1 0
60 30 210 90
[ ],[ ]
17 17 17 17
X X X G fX fXΔ=?=? Δ =?＝（）-（）
111
69
385 241
1
17 29
()
241 891 12 21986
17 29
PHfX
= =? =?
1
11
1
11
9
612
29
17 17 21
() 29
29
9
17
31
921
29
29 29 1 1 21
29
T
T
P
fX P
PHP
λ
=? =
沿 一维搜索，由共轭方向最佳步长公式
－
＝
2111 2
2
[1 1],( ) [0 0]
[1 1]
TT
T
XX P fX
X
λ=+ =? =
=故 是极小点。
http://www.tju.edu.cn
第一章非线性规划
1.3 约束极值问题
★一般模型
min ( )
()0,1,,
().
()0,1,,
{ |()0,()0}
min ( )
i
j
n
ij
XD
fX
hX i m
NLP st
gX j l
DXRhX gX
NLP f X
∈
==
≥=
= ∈=≥
null
null
记
则（ ）也可以表示为
http://www.tju.edu.cn
第一章非线性规划一、基本概念和性质
1.起作用约束
00 0
,XDX X
XX
∈对于点 在 点等于零的约束称为对 起作用的约束，
在 点不等于零的约束称为对 不起作用的约束。
0
0
()0,1,,
()0,{1,,} ()0( )
X
i
jj
Xhm
gX jJ l gX jJ
==
∈? ≥ ∈
null
null
0
在 点起作用的约束包括全体等式约束 和满足 ＝ 的不等式约束 。
几何意义,位于这些约束的边界上。
00
0
()0
()0( )
j
j
XgX
gX jJ
X
>
≥∈
0
在 的不起作用的约束包括 的不等式约束
。
几何意义,位于这些约束的内部。
http://www.tju.edu.cn
第一章非线性规划
2.可行下降方向
0
000
[0,]
n
PR X D
XPDλλλλ
∈∈
∈∈
方向 在点 称为是可行的
是指存在正数,使对一切 都有 + ;
0
000
()()0
n
PR X D
XPDfXPfXλλ
∈∈
+ ∈+?<
方向 在点 称为下降的
是指存在,有
*
*
NLPX
X
如果 是（ ）的极小点，
则在 不存在可行下降方向。
http://www.tju.edu.cn
第一章非线性规划
3.可行下降方向的条件
()0
()0 ()0
()0
i
ii
j
hX
hX hX
gX
=
≥≤
≥
由于等式约束 可以化为两个不等式约束
,来表示，所以讨论约束条件时可只考虑不等式约束 。
0
0
00
0
()0(1,,)
()-()0
j
PX
gX P j l
fX P fX
PX
λ
λ
+≥=
+<
null
由可行下降方向的定义，某方向 在 点若满足则 是 的可行下降方向。
http://www.tju.edu.cn
第一章非线性规划
000
000
0
( ) ( ) ( ) ( 1,,)
( ) ( ) ( )
T
jjj
T
gX P gX gX P j l
fX P fX fX P
XPD
λλ+≈ +? =
+? ≈?
+∈
null
由泰勒公式其中 是足够小的正数（保证 ）
0
0
() 0
()
0
T
j
T
gX P
P
fX P
P
>
<
不难看出，只要,便保证 是可行下降的。
这可作为 可行下降的充分条件。
00
0
00
() ()
()-()
j
j
PgX P fX
XP
gX fX
几何意义是,与 夹锐角，同时 与- 也夹锐角。
由此可知，如果在 不存在可行下降方向，则一定不存在 同时与 和 夹锐角。
http://www.tju.edu.cn
第一章非线性规划二、最优性条件（ K-T条件）
*
NLP ( ) ( )
NLP
j
fX gX
X
考虑只含有不等式约束的（ ）。设 与 均为连续可微函数,是（ ）的最优解。
**
*
()0
XD X
fX?
如果 是 的内点，即约束对 是不起作用的，则由无约束极值问题的极值必要条件，有 ＝ 。
*
1
**
11
*
*
()0
()0 ( )
()
XgX
gX X gX
fX P
PX
≥
≥?
如果 是某一个约束 的边界点，
即 对 起作用，则必有与- 反向，否则必有 与二者同夹锐角，即 是 的可行下降方向，矛盾。
1
()gX
*
1
()gX?
*
()fX?-
*
X
** * *
1 1
() () () ()g X f X f X g Xγγ ≥
11
故 与 同向，即存在 0，使 ＝ 。
http://www.tju.edu.cn
第一章非线性规划
*
12
**
12
**
12
** *
12
()0 ()0
()0 ()0 ( )
() ()
() () ()
XgXgX
gX gX X fX
gX gX P
fX gX gX
P
≥≥
≥≥?
如果 位于某两个约束 和 的交点，
即 和 均对 起作用，则必有位于 和 的夹角内部，否则也会有 与
－,和 同夹锐角，即存在可行下降方向,矛盾。
*
X
1
()gX
2
()gX
*
()f X?
*
1
()gX?
*
2
()gX?
12
** *
11 2 2
12
() () ()
,0
fX gX gX
γγ
γγ
γγ
≥
故有 和 使下式成立：
＝＋
http://www.tju.edu.cn
第一章非线性规划
*
**
()0
() ()
0
j
jj
jJ
j
XgXjJ
fX gX
jJ
γ
γ
∈
≥∈
≥∈
∑
依此类推，若 点起作用约束为,,
则有 ＝
，
**
1
*
( ) ( )
( ) 0 ( 1,,)
0 ( 1,,)
l
jj
j
jj
j
fX gX
gX j l
jl
γ
γ
γ
==
≥=
∑
null
null
＝
或表示为
＝
*
*
()0
jj
gX
X
γ =其中条件 是为了在梯度组合式中去掉不起作用约束，称为松紧条件。这时要求 点各起作用约束的梯度线性无关。
http://www.tju.edu.cn
第一章非线性规划定理 (K-T条件 )
**
** * ** *
11
*****
11
*
()(1,,) ()
[,,] [,,]
() () ()
( ) 0 1,,
01,,
ij
ml
ii jj
ij
jj
j
XNLP X
hX i m g X j J
fX hX gX
gX j l
jl
λλ γγ
λγ
γ
γ
=? ∈
Λ= Γ=
==
≥=
∑∑
null
nullnull
null
null
＝＝
设 是（ ）的最优解，且在 点各起作用约束的梯度和,线性无关，则存在向量 和 使下式成立：
＝＋
（）
，（ ）
****
11ml
λλγγnullnullK-T条件中的,,和,,称为广义拉格朗日乘子或
K-T乘子。满足K-T条件表达式的可行点称为K-T点。可以证明
K-T条件对凸规划是充要的。
注：关于 K-T定理的证明首先证明 Gordan引理：
其次证明 F-J定理：
*
** *
01
** * *
0
1
*
() ()0
( ) 0 1,,
01,,
l
l
jj
j
jj
j
XNLP
fX g X
gX j l
jl
γγγ
γγ
γ
γ
=
==
≥=
∑
null
null
null
＝
设 是（ ）（只考虑不等式约束）的极小点，
则存在不全为0的数,使下式成立：
-
（）
，（ ）
γ
γ ≠
0
0
如果 =0则定理失效。
为了保证 0，增加了起作用约束的梯度无关的条件（为什么），
便成为K-T条件。
1
1
,...,0,1,...,
,...,0.
T
lj
l
ljj
j
AAln PAP j l
Aμμ μ
=
<=
=
∑1
设 是 个 维向量，不存在向量 使 成立的充要条件是，存在不全为0的非负实数 使
http://www.tju.edu.cn
第一章非线性规划例：利用 K－ T条件求解下面的非线性规划
2
min ( ) ( 3)
.,0 5
fX x
st x
=?
≤≤
2
1
2
min ( ) ( 3)
,,( ) 0
( ) 5 0
fX x
st g X x
gX x
=?
=≥
=?≥
解 原问题可写为
12
12
"( ) 2 0," ( ) " ( ) 0
() () ()
fX gX g X
fX gX gX
=> = =因为故 解为凸函数,和 均为凹函数，
此问题为凸规划。
http://www.tju.edu.cn
第一章非线性规划为解此方程组，可分几种情况考虑：
12
12
1
2
12
()2 3 ()1,() 1
23 0
0
(5 ) 0
,0
fX x gX gX
KT
x
x
x
γγ
γ
γ
γγ
=?=?
=
=
≥
＝（ ）,
条件表达式为
（）－＋＝
**
3()0xfx= =由于此问题为凸规划，故 是最有解，相应最优值 。
12
0γ γ≠ ≠0且,无解；
①
12
03,xKTγ γ= =＝,解得 满足约束，是 － 点；
④
12 2
00 5,4,γ γγ= ≠==且,解得 － 不是 － 点；
③
12 1
0 0 0,6,xKTγ ≠ ==且 ＝,解得 － 不是 － 点；
②
http://www.tju.edu.cn
第一章非线性规划例,考虑非线性规划并验证它为凸规划，用 K－ T条件求解。
12
12
12
max ( ) ln( 1)
23
,,
,0
f Xxx
xx
st
xx
= +
+≤
≥
12
112
21
22
min ( ) ln( 1)
,,( ) 3 2 0
( ) 0
( ) 0
f Xxx
st g X x x
gX x
gX x
=?+?
=≥
=≥
=≥
解 原问题可写为
http://www.tju.edu.cn
第一章非线性规划计算目标和约束函数的海赛阵
12
1
3
1
( ) 1 ( ) [ 2 1],( ) [1 0],
(1)
()[0 1]
-
T
TT
T
fX gX gX
x
gX
KT
= = =
+
=
，
表达式为：
123
2
1
1
0
0 0
(1)() 0,() () () 0
0 0
0 0
fggg
xHX HX HX HX
+=≥===≤
故此问题是凸规划。
http://www.tju.edu.cn
第一章非线性规划
1112
13
0030
00
xx
x
γ γ
γ
≠若 ＝,则无解，于是,有 ＝
令＝，＝，则有
12
1
2
0
1
30x
γγ
γ
=
1－2 ＋ ＝
－＝0
（）
12 12
0xxγγ
T
解得 ＝0,＝3,＝ ＝,显然[0 3]是可行点，从而是极小点。
12
1
12
112
21
32
123
1
2
(1)
1
32 0
0
0
,,0
x
xx
x
x
γ γ
γγ
γ
γ
γ
γγγ
+
=
=
=
≥
＝- ＋
＝- ＋
（）
http://www.tju.edu.cn
第一章非线性规划三、二次规划
★一般模型
min ( )
1
2
0
,,
0
,
TT
fX XHX CX
AX b
st
X
Amn bm Cn
= +
+≥
≥
×其中 为 阶矩阵； 为 维非负向量； 为 维向量。
0K-TH ≥
由于二次规划的约束是线性的，从而是凸集，故当目标的二次项系数矩阵 （半正定）时为凸规划，可用 条件求解。
http://www.tju.edu.cn
第一章非线性规划
11
22
( )
( ) 0
( ) 0
fX HX C
gX A g AX b m
gX I g X n
=+
= +≥
= ≥
则梯度：
与约束 （ 个）相对应，
与约束 （ 个）相对应。
min ( )
1
2
0
,,
0
TT
fX XHX CX
AX b
st
X
= +
+≥
≥
[]
[]
111
22
() -
() -,-
T
m
T
mmn
g
g
XKT Yyy
XKT Yy y KT
++
null
null
记相应于 的 乘子为 ＝,相应于的 乘子为 ＝ 则由 条件及约束条件，有：
http://www.tju.edu.cn
第一章非线性规划
12
1
2
12
0
0
0
,,0
T
T
T
TT
HX C A YIY
YAXb
YX
AX b
XY Y
+ +
+
+≥
≥
＝
（）＝
＝
上面的一组式子中，若不考虑两个松紧条件，则其余均为线性表达式，即：
12
12
0
,,0
T
TT
HX A CYIY
AX b
XY Y
+ +
+≥
≥
＝
思考,能否在此基础上构想基于线性规划求解的方法?
http://www.tju.edu.cn
第一章非线性规划
[ ]
1
0
T
n
Z zznull如果在上面第一式中增加人工变量 ＝ （为使出现单位阵），并增加使人工变量之和极小化的目标函数
（为使人工变量最后均为 ），则可构造一个线性规划：
1
12
12
min
sgn( )
,,
,,,,0
sgn( )
n
T
s
TT
s
s
HX A C
zz z
YIY CZ
st AX X b
XY Y ZX
CZ Z C
X
+
=++
++
+=
≥
null
＝
其中 表示 中各分量的符号与 中相应分量的符号相同，是为了保证出现单位阵； 是松弛变量。
用单纯形法求解该规划的单纯形初表为下表。
http://www.tju.edu.cn
第一章非线性规划
12
1
2
12
,,
0
0
T
s
T
s
XY Y
YX
YX
YX YX
为使所求得的 还满足松紧条件
＝
＝
应在每次单纯形表的迭代中保证 与 以及 与的相应分量不同时为基变量。
B
X
1
Bb
X
s
X
1
Y
2
Y
Z
Z C H? 0
T
A
sgn( )CI
s
X
b
A? I
0
0
0
I
http://www.tju.edu.cn
第一章非线性规划例,求解二次规划
22
12 1 2
12
12
min ( )
1
(2 2 ) 8 10
2
63 2 0
,.
0,0
fX x xxx
xx
st
xx
= +
≥
≥≥
112 23
2 0
,[ 3 2],[ 8 10],6
0 2
,[ ]
0,K-T
T
T
HA C b
YyY yy
H
====
==
>显然有 故此问题是凸规划。可用 条件求解。
解
http://www.tju.edu.cn
第一章非线性规划
12
211
1
322
1
3
2
sgn( )
2 0 3 8
0 2 2 10
[3 2] 6
T
s
HX A YIY CZ
yxz
y C
y
x
AX X x b
x
+ ++
=?++?==
+= +==
12
1121
2132
123
12312 312
13 21 32
2
2
3
min
38
0
,,
26
,,,,,,,0
00,0
x
x
x
zzz
yyz
yyz
st
xx
xxxyyyzz
yx yx yx
=+
+?+=
+?+=
++=
≥
相应的线性规划为求解时还要满足松紧条件 ＝,＝,＝ 。
11
3/13-2/13-4/3914/130
9/26-3/13-9/263/132/13133/130
132/130
2/31-2/3-4/9-26/9
31/32/3120
33/131-2/3-12/34/9[26/9]22/31
1/3-1/31-2/9-4/94/30
11-51/3-2/3
1/32/3120
51-122101
4/31-1[3]-2/3-4/341
11-5-2-2
212[3]60
1-122101
41-13281
1100000
0
B
C
B
X
1
B b
θ
1
x
1
x
1
x
1
x
2
x
2
x
3
x
3
x
1
y
1
y
1
y
2
y
3
y
1
z
1
z
1
z
2
z
2
z
2
z
2
z
1
z
http://www.tju.edu.cn
第一章非线性规划求得的结果是：
12 31 23
433 32
,,0,,0,0
13 13 13
xxxyyy======
1
3131
*
433
[ ]
13 13
T
y
xyxx
X =
在每一次单纯行表迭代中都考虑了松紧条件，如在第一张表中，按通常规则应让 进基，但考虑到与它构成松紧式的 已在基中，并且 进基也不会使 出基，故选择 进基，
从而所得解 满足松紧条件，是原来二次规划的最优解。
http://www.tju.edu.cn
第一章非线性规划四、罚函数法基本思想：将约束与目标组合在一起，化为无约束极值问题求解。
★
内点法：从可行域的内部逐步逼近最优解。★
外点法：从可行域的外部逐步逼近最优解。★
http://www.tju.edu.cn
第一章非线性规划外点法的关键是基于（ NLP）构造一个新的目标函数
P（ X,M），称为罚函数。
22
11
(,) () [min(0,())] ()
lm
ji
ji
PXM f X M g X M h X
M
M
==
=+ +
∑∑
式中 是一个充分大的正数，称做罚因子。
含 的项称 为罚项。
当 X是可行点时，罚项为 0
当 X不是可行点时，罚项是很大的正数。
对 P（ X,M）求极小，可采用无约束优化方法，罚项能保证 X逐步趋近可行域。
http://www.tju.edu.cn
第一章非线性规划一般步骤：
0,,1,0Mkε>=>
1
选取初始罚因子 令 ；①
min (,),
kkk
M PXM X对于,求解无约束极值问题 得 ；②
1
|( )| ( 1,,)
( ) ( 1,,)
NLP,
1,2
k
ik
ik
kkk
X
hX i m
gX j l
XMM
kk
ε
ε
≤=
≥? =
>
+
null
null
＋
若 满足可行性的精度要求
则停止,即为（ ）的近似最优解，否则，取置＝ 转。
③
,PXM
M →+∞
用罚函数法求解一些简单的非线性规划时，可先求出（ ）
的驻点，然后令 。
http://www.tju.edu.cn
第一章非线性规划例：求解非线性规划
3
12
1
2
min ( )
1
(1)
3
10
,.
0
fX x x
x
st
x
= + +
≥
≥
322
12 1
1
(,) ( 1) [min(0,1)] [min(0,)]
3
PXM x x M x M x=+++?+
解 构造罚函数
2
11
1
2
2
( 1) 2 [min(0,1)] 0
1 2 [min(0,)] 0
P
xMx
x
P
Mx
x
= ++?=
=+ =
令
11 2
10 1,0 10xx x?≥ =? ≥当,不可行；当,由第二式有＝,矛盾，
说明可行域内无驻点。
http://www.tju.edu.cn
第一章非线性规划
12
2
1
2
10,0,
41
1
2
xx
xM MM
x
M
< <
+
=?
对于可行域外的点（满足 ）可解得驻点
＝
1
2( 1) 2 0
0
02
xM
H
M
++
=>
在该点，海赛阵
说明该驻点是极小点。
[]
T
1
2
1
M,
0
x
x
→
→+∞
→
令 则,而 1 0 满足约 束，是最优解。
http://www.tju.edu.cn
第一章非线性规划例：求解非线性规划
22 2
12 12 1
(,) [min(0,)] [min(0,)]PXM x x M x x M x=++?+ +
解 构造罚函数
2
12 1 1
1
2
12
2
1 2 [min(0,)]( 2 ) 2 [min(0,)] 0
1 2 [min(0,)] 0
P
MxxxMx
x
P
Mxx
x
=+? +? + =
=+? + =
考察其驻点，令
12
2
12
1
min ( )
0
,.
0
fX x x
xx
st
x
= +
+≥
≥
http://www.tju.edu.cn
第一章非线性规划
12
2
12 1 1
2
12
10,0,
12 ( )(2)2 0
12 ( ) 0
xx
Mx x x Mx
Mx x
< <
+?+?+ =
+?+=
对于可行域外的点（满足 ） 可解得驻点
[]
T
1
2
0
,
0
x
M
x
→
→+∞
→
令 则,而 0 0 是可行点，故是最优解。
1
2
2
1
2( 1)
11
4( 1) 2
x
M
x
M M
+
=?
+
＝
解得
