第三章 非线性规划请回顾线性规划,,其目标与约束函数均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。
非线性规划（ Nonlinear Programming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。
0
..
X
bAX
ts
CXM a xz
第一节 基本概念一、非线性规划问题与模型
1,问题
⑴ 生产计划问题
m a x ( ) ( ) ( )
( ) 0
..
( ) 0
i
j
f x x P x x C x
gx
st
hx
x:产量 ;P(x):价格 ;C(x)成本
⑵投资决策问题
1 1 1
1
::
::
::
m a x ( )
..
0
jj
j
ij
n n n
j j i j
j i j
n
jj
j
j
x j P j
Bj
ij
f x x x x
P x B
st
x
第 种股票的购买量； 第 种股票的价格总资金； 第 种股票的每股平均收益风险系数； 第 种与第 种股票收益的协方差
2.模型
1
n
n
m in ( )
( ) 0,1,,
( ),,
( ) 0,1,,
[,,]
{ | ( ) 0,( ) 0 }
m i n ( )
D NL P
D R NL P
D R NL P
i
j
T
n
n
ij
XD
fX
h X i m
N L P s t
g X j l
X x x
D X R h X g X
N L P f X
其 中记则 （ ） 也 可 以 表 示 为其 中 称 为 （ ） 的 约 束 集 或 可 行 域 。
当 ＝ 时,（ ） 称 做 无 约 束 极 值 问 题 ；
当 时,（ ） 称 做 约 束 极 值 问 题 。
二,模型的解及相关概念
1.可行解与最优解
★ 可行解：约束集 D中的 X。
★ 最优解：如果有,对于任意的,
都有,则称 为（ NLP） 的最优解，也称为全局最小值点。
*XD? XD?
*( ) ( )f X f X? *X
★ 局部最优解：如果对于,使得在 的邻域 中的任意都有,则称 为（ NLP） 的局部最优 解，也称为局部最小值点。
0XD? 0X
XD?
0( ) ( )f X f X?
00(,) { | }B X X X X
0X
例 1：考虑非线性问题
22
12
12
m i n ( ) ( 2 ) ( 2 )
,,6
f X x x
s t x x
2 x
1 x
6
6
3
3
如果约束改为呢
？
12 6xx
2.梯度、海塞阵与泰勒公式
★ 梯度
00
00
00
0
1
( ) ( )
( ) ( )
( ) ( )
( ) [ ]
T
n
f X X f X X
f X X f X
f X f X
fX
xx
若 在 的邻域内有连续一阶偏导数，则称 在 点对n
个变元的偏导数组成的向量为 在 的梯度，记为,
即 ＝,,
00 ()X f X X
几何意义：
梯度是过 点且与 在 的切平面垂直的向量，
梯度向量的方向是函数值在该点增加最快的方向。
★海塞阵
00
0
0
00
00
11
00
1
2
22
2
22
2
( ) ( )
()
()
( ) ( ) [ ]
( ) ( )
( ) ( )
ij
n
nn
nn
f X X f X X n
f X X
fX
H X H X
xx
f X f X
x x x
f X f X
x x x
若 在 的邻域内有连续二阶偏导数，则称 在 点对个变元两两组合的二阶偏导数组成的矩阵为 在 的海赛阵，
记为,即 =
★泰勒公式
00
0 0 0 0 0 0
2
0
22
0 0 0
( ) ( )
( ) ( ) ( )
1
( ) ( ) ( )
2
( )
()
TT
f X X f X X
f X f X f X X X X X H X X X
o X X
o X X X X X X
若 在 的邻域内有连续二阶偏导数，则可写出 在 点的（二阶）泰勒展开式：
＝ （ － ）
－
其中,是当 时 的高阶无穷小。
例 2：写出 在 点的二阶泰勒展开式2
12( ) 3 sinf X x x 0 [ 0,0] TX?
1 2 0
0
2
( ) [ 6 ( ) [ 0 1 c os ],]
60 60
( ),( )
0 si n 00
TTf X x f Xx
H X H X
x
解,
211
12
22
( ) 0 [ 0 1
60 1] [ ] ( )
002
xx
f X x x o X
2
0
2
12
()
( ) 3
() fX
f X x
o X X
x?
如果忽略了 在,则 点的近似表达式为
+
3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将 n(n>1)元函数 与一元函数 的极值条件加以对比并归纳如下：
()fX ()fx
00()X x或 是极小点
()fx一元函数
()fXn元函数
0'( ) 0fx?
0( ) 0fX
00'( ) 0,''( ) 0f x f x且
00( ) 0 ( ) 0f X H X且充分条件必要条件
0( ) 0HX?注,表 示 海 赛 阵 正 定 。 如 果 一 个 方 阵 的各 阶 主 子 式 均 大 于 零,则 可 以 判 定 该 方 阵 是 正 定 的 。
例 3：求 的极小值点22
1 1 2 2( ) 2 28 4 20f X x xxx
解
12
12
0
( ) [
( ) 0
] [ 4 8 4 4 ]
[ 2 1 ]
TT
T
ff
fX
xx
f X X
xx
＝
＝,解得驻点令
0
0
40
( ),( ) 0
04
H X H X
X
又故 是 极 小 值 点 。
4.凸规划
★凸函数,f(X)是定义在凸集 D上且满足对任意有下式成立的函数：
1 2 1 2( ) (( 1 ) ) ( 1 ) ( )f X f XX f X
12,,X X D?
[0,1]
若不等式中严格不等号成立，则称 f(X)为严格凸函数注：判断一个可导函数 f(X)是否是凸函数的方法一元函数 f(x),二阶导大于等于零 ;
多元函数 f(X),海塞阵半正定。
★凸规划性质：★约束集是凸集；
★最优解集是凸集；
★任何局部最优解也是全局最优解；
★若目标函数是严格凸函数，且最优解存在，则其最优解是唯一的。
在非线性规划模型（ NLP） 中，若目标函数 f（ X） 是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（ NLP） 是一个凸规划。
( ) 1,,jg X j l?
( ) 1,,ih X i m?
例 4：判断下面的非线性规划是否为凸规划
12
22
12
12
max ( )
1
..
,0
fX xx
xx
st
xx
12
22
1 1 2
21
32
m in( ( ) )
( ) 1 0
.,( ) 0
( ) 0
fX xx
g X x x
s t g X x
g X x
标准化
1
23
()
0 0 2 0
0,( ) 0
0 0 0 2
00
( ) ( ) 0
00
fg
gg
HX HX
H X H X
计算
1 2 3() ( ) ( ) ( )fX g X g X g X?说 明 是 凸 函 数,,,是 凹 函 数因 此,本 模 型 是 凸 规 划 。
第二节 无约束极值问题
★一般模型,mi n ( )
n
fX
XR?其中
★求解（ f(X)可微）：应用极值条件求解，往往得到一个非线性的方程组，求解十分困难。因此，求 解无约束问题一般采用迭代法，称为下降类算法。
一、下降类算法的基本步骤与算法收敛性
1.基本思想
0
0
1
12
()fX
X
P
X
PX
基本思想是使 逐步下降，逐渐趋近其最小值。迭代方式是从一个初始点 出发，选取某一搜索方向,沿该方向搜索到下一个点 。若达到与最优解误差的精度要求，则停止，否则再沿该点的某一方向 搜索下一个点 。
这一过程如图所示：
0P
1P
2P
0X
1X
3X
2X
2.基本步骤
0,0,0Xk选取初始点,令 确定精度 ；
(1)
( ),( ),
3
k k k
k
X f X f X
X
对 于 点,计 算 若 则 停 止,
得 到 近 似 最 优 解,否 则 转 （ ） ；
(2)
kkXP从 出发，确定搜索方向 ；
(3)
1
,
,,1,2 )
k k k k
k k k k
P X X P
X X P k k
沿 方 向 搜 索,即 由 ＝ 确 定 搜 索 步 长得 到 下 一 个 点 ＝ 令 转 ( 。
(4)
注：不同的搜索方向，就形成了不同的算法，不同的算法所产生的点列收敛于最优解的速度也不一样。
3.收敛性衡量标准,*
1
*l i m
k
k k
XX
XX
1,0 1,{ }kX 则称 是线性收敛的；①
1,0,{ }kX 则称 是超线性收敛的；②
2,0,{ }kX 则称 是二阶收敛的。③
二阶收敛 >超线性收敛 >线性收敛二、一维搜索
:
精确搜索：
一维搜索分数法近似搜索 0,1 6 8 法其他方法（导数信息）
0
m in ( ),kk
k
f X P
通过求极值得到最佳步长
k
求上面极值的近似值得到近似最佳步长
1.分数法 （斐波那契法）
2t
⑴基本思想
*tO a b'
1t1t
()ft
t
怎样在区间中取点最好？
'11( ) ( )f t f t?若
12( ) ( )f t f t?若
⑵基本概念
[,],0nnn a b记第 次缩短后的小区间为 给定的精度要求为
★满足绝对精度：
★满足相对精度：
||nnba
||nnba
ba?
★斐波那契数：
12
01 1
n n nF F F
FF
55342113853211
9876543210
nF
n
1(1 ) ( )n
n
Fa b a
F
1 ()n
n
Fa b a
F
a b1t '
1t
''1
1 1 1
1
' 1 2 2
1
1
1 1 1
'
1 2 1 - 1 1
12 21
1 3 2
[,],
( 1 - ) ( - )
[,],
()
[,] - 1 [,]
1
( - )
n
n
n
n n n n n
n
n n n
n
nn
nn
nn
F
t t t b
F
F
ba
F F F F F
t a t
F F F F
ba
F
a t t t n a b
FF FF
ba
F F F F F
1
若 按 的 比 例 在 区 间 中 对 称 地 取 点 和,经 比 较 后 去 掉则 在 中 所 占 的 比 例 为 再 按比 例 在 中 取 与 对 称,这 样 反 复 次 后 所 得 的 小 区 间长 缩 短 为 ( ),
1
()
11
-
n
n
n
nn
ba
ba
F
Fn
b a F F
与 原 区 间 长 之 比 为,
,恰 为 相 对 精 度 表 达 式 。 于 是,开 始 可 由 解 出,
⑶步骤
① 1;
n
nF?由所给精度 和 定 11
1
' ' '1
1 1 1 1 1
11
( 1 - ) ( - )
( ) m a x { }
,[,]
nn
n
n
FF
t b a
F
t b a t t t t
F
ab
由 的 比 例 在 区 间 [a,b] 中 对 称 地 取 点 =a+ 和
=a+,比 较 f ( ) 和 f ( ),去 掉 f ( ),f ( ) 相 应点 以 外 的 区 间 得 到 新 区 间 ；
②
2
1 1 2
1
'
2 1 1
22
[,] ( )
( ) m i n { ( ),( ) }
[,]
n
n
F
a b t
F
f t f t f t
ab
在 中按 的比例取点 与区间中所剩的点对称比较 和,去掉较大者对应点以外的区间，得到新区间 ；
③
3
2 2 3
2
*1
- 1 1
2
[,]
[,]
n
n
nn
F
a b t
F
F
a b t
F
在 中 按 的 比 例 取 点 再 比 较,再 缩 短,直 到 取 完
,最 后 的 小 区 间 中 的 任 意 一 点 可 作 为 的 近 似 值 。
④
例 5：
2( ) 2 [ 1,3 ]
8
f t t t用 分 数 法 求 在 区 间 上 的 近 似 极 小 点,
要 求 缩 短 后 的 区 间 长 度 不 大 于 原 区 间 长 的 ％ 。
**
''( ) 2 0,
1'( ) 2 1 0 1.7 5
2
f t f t
f t t t f t
解 由 于 所 以 （ ） 是 严 格 的 凸 函 数 。
由 ＝ － ＝,解 得 是 极 小 点,（ ） ＝
5
6
11
''
1 1 1
4
11
5
2
21
1 1 8
0.0 8 12,5,6,
0.0 8 13
8
1 ( 1 ) [ 3 ( 1 ) ] 0.5 38,( ) 1.7 51
13
8
1 [ 3 ( 1 ) ] 1.4 62,( ) 2.6 75 ( )
13
5
[,] [ 1,1.4 62],
8
5
1 ( 1 ) [ 1.4 62 ( 1 ) ] 0.0 77,
8
( ) 2.0 83 ( ),
n
n
F
Fn
FF
t f t
t f t f t
F
ab
F
t
f t f t
由 知 查表得故
22
55
[,] [ 0.0 77,1.4 62]
0.5 38 ( ) 1.7 51
ab
t f t
故依此进行，得 ＝ 为近似极小点，
2,0.618法
★区别：每次取点得比例是定值 0.168，即每次区间内两点得位置均在区间相对长度得 0.328和 0.168处。
★特点：简单，更易于应用；
效果也比较好。
3.近似最佳步长公式
2
()
1( ) ( ) ( ) ( )
2
TT
k k k k k k k k
fX
f X P f X f X P P H X P
设 存在连续的二阶偏导数，则有泰勒展开式
0
( ) ( ) 0TTk k k k kdf f X P P H X P
d
对 求导，并令导数为,得
()
()
T
kk
T
k k k
f X P
P H X P?
－解得,＝
k fX?上式即为 的近似最佳步长公式。当（ ）为二次函数时，此公式是精确的。
例 6：
22
12( ) ( 1 ) ( 1 ),[ 0 0 ],( )
T
k k k
k
f X x x X P f X
设－
用近似最佳步长公式求 。
12
( ) [ 2 ( 1 ) 2 ( 1 ) ],( ) [ 2 2 ]
20
( ) ( )
02
2
[ 2 2 ]
2 1
2 0 2 2
[ 2 2 ]
0 2 2
TT
k
k
f X x x f X
H X H X
解
() kfX?由于 是二次函数，故所求 是精确的。
三、梯度法和共轭梯度法
1.梯度法
()
( ) ( ) ( ) Tk k k k k
fX
f X P f X f X P
设 有连续的二阶偏导数，则有泰勒展开式
0,
( ) ( ) c o s 0
()
,( ) ( )
2
c o s 1,,
T
k k k k
kk
k k k
f X P f X P
f X P
f X P f X
由 于 应 使
＝
其 中 为 向 量 和 的 夹 角 。 为 使 上 式 成 立,
应 使 又 为 使 的 绝 对 值 尽量 大,应 使 ＝ - 即 ＝
( ) ( )kk
k
P f X X f X
P
故 ＝ 即在 点的负梯度方向是使 下降最快的方向。以负梯度作为搜索方向 的下降类算法称为梯度法或最速下降法。
( ) 0) )(( kkk kf X P XpX ff思 想,怎 样 选 取 可 使 下 且 左 边 差降 最 额快？ 即 使 尽 量 大 。
★一般步骤
0,0,0Xk选取初始点,令 确定精度 ；
(1)
( ),( ),
3)
k k k
k
X f X f X
X
对 于 点,计 算 若 则 停 止 计 算,
得 到 近 似 最 优 解,否 则 转 ( ；
(2)
1
( ),k k k k
k k k k
P f X P
X X P
取 沿 进行一维搜索，得到 和下一个点；
(3)
1,1,2 )kf X k k计 算 （ ）,置 转 ( 。
(4)
例 7:
22
12
0
( ) ( 1 ) ( 1 ) 0,1
[0 0 ] T
f X x x
X
用梯度法求 的极小点，取 ＝
初始点 。
1 2 0
22
0
( ) [ 2( 1 ) 2( 1 ) ],( ) [ 2 2]
( ) ( 2) ( 2) 8
Tf X x x f X
fX?
解,
0
0
2
[ 2 2 ]
20 2 1
()
2 0 202 2
[ 2 2 ]
0 2 2
HX
由 近 似 最 佳 步 长 公 式 求,
,
1 0 0 0
10
*
1
1
( ) [ 0 0] [ 2 2] [ 1 1 ]
2
( ) [ 0 0],( ) 0
[ 1 1 ]
T T T
T
T
X X f X
f X f X
XX
故上例中，目标函数是同心圆族。无论初始点选在何处
，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。
但对于一般的函数，若每次迭代均采用负梯度方向，
则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象
，收敛速度很慢。可以证明，梯度法是线性收敛的。
注：
2.共轭梯度法
⑴基本概念
0
,
TX Y n A n X A Y
X Y A A I X Y
设 与 均为 维向量,是 阶对称正定阵。若,
则称 与 关于 共轭。当 则 与 正交。关于共轭，
有下述重要性质：
11
11
1
,0,
1,,,0
0,0
1
nn
n n i
TT
i i i i
T
i i i n
n n P P A P P
P P R
P A i n P A P A
P A P P P
n n A
若 个非零 维向量,,关于 共轭，则,,
线性无关。事实上 只需考虑两边分别左乘 （ ）则有 ＝,而正定，即 故,说明,,线性无关。
这一性质也说明不可能有 个 维向量关于 共轭。
★
1
1
1
2
n
TT
n
n P P H H
f X X H X C X P P
n
若非零 维向量,,关于 共轭，则以 为二次系数阵的二次函数（ ） 沿,,（称为共轭方向）进行精确一维搜索，至多经次便可得极小点。
★
这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。
⑵一般步骤
0,0,0Xk选取初始点,令 确定精度 ；
①
1m i n ( ),k k k k k k k kX f X P X X P对 求解 得 和 ；
③
②
00P f X取 （ ）；
④
*
11
0
( ),,1,5
1,2
kk
n
f X X X k n
k n X X
若 则 停 止,否 则,若 转,
若,重 置 转 ； （ 重 置 的 原 因 是 由 于 计 算中 的 舍 入 误 差 可 能 造 成 n 步 未 终 止 。 ）
11
11
,1,3
k k k k
T
kk
k T
kk
P f X P k k
f X f X
f X f X
取 （ ）,置 转
（ ） （ ）
其 中,＝ （ F-R 法 ）
（ ） （ ）
⑤
( ),( )TTf f X X H X C X f X H X C1当 正 定,时,有2
11( ) ( ) ( ) ( )k k k k k k k k k kf X f X H X X H X P X H P
,TkP两边同时左乘 有
()TTk k k k kP f X P H P
k
k1 ( ) 0
T
k
PH
P f X
可以证明，按此方向构造的 是关于 共轭的，并且有
()Tkk
k T
kk
P f X
P H P
从而有例 8：
22
1 2 1 2 1 0
31( ) 2 [ 2 4 ]
22
Tf X x x x x x X求 的极小点，取 。
11
12
22
1 2 2 1
0 0 0
311
( ) [ ] [ 2 0 ]
112
( ) [ 3 2 ]
( ) [ 1 2 6 ],( ) [ 1 2 6 ]
T
TT
xx
f X x x
xx
f X x x x x
f X P f X
解
00
0
00
12
[ 12 6]
6() 5
3 1 12 17
[ 12 6]
1 1 6
T
T
P f X
P H P
1 0 0
5 2 6 3 8[ 2 4 ] [ 1 2 6 ] [ ]
1 7 1 7 1 7
T T TX X P
1
6 1 2( ) [ ]
1 7 1 7
TfX
11
0
00
6
6 1 2 17
[ ]
1 7 1 7 1 2
117
12 289
[ 1 2 6 ]
6
T
T
f X f X
f X f X
（ ） （ ）
＝
（ ） （ ）
1 1 0 0
11
1 2 1 1 1
11
6 1 2 1 9 0 2 1 0
( ) [ ] [ 1 2 6 ] [ ]
1 7 1 7 2 8 9 2 8 9 2 8 9
() 17
,[ 1 1 ]
10
T T T
T
T
T
P f X P
P f X
X X P
P H P
22( ) [ 0 0] [ 1 1 ]TTf X X?由 于 ＝,故 ＝ 即 极 小 点,计 算 经 两 步 终 止 。
四、牛顿法与拟牛顿法
1.牛顿法
⑴牛顿方向
( ) ( )
1( ) ( ) ( ) ( ) ( ) ( ) ( )
2
TT
k k k k k k
f X f X
f X f X f X X X X X H X X X
设 有 连 续 的 二 阶 偏 导 数,由 泰 勒 展 开 式,可 近 似 表 示 为
( ) ( ) ( ) ( )k k kf X f X H X X X
f
从 而当 为 二 次 函 数 时,上 式 为 精 确 表 达 式 。
11
k1
( ) ( ) 0
( ) ( ) ( ) 0
kk
k k k
X f X f X
f X H X X X
＋
＋
取 使 达 到 极 小,应 有 ＝,即
＋ ＝
1
k1
1
()
( ) ( )
( ) ( ),
k
k k k
k k k
HX
X X H X f X
P H X f X
－
＋
－
当 可逆，可解得
＝
记 称为牛顿方向。
()
1
()
k
fX
X
fX
对 于 正 定 二 次 函 数,采 用 牛 顿 方 向 作 搜 索 方 向,
步 长 取 为,从 任 意 点 出 发 一 步 即 可 得 极 小 点 。 对于 一 般 函 数,在 一 定 条 件 下,也 可 采 用 牛 顿 方 向,
所 形 成 的 算 法 称 为 牛 顿 法 。
⑵一般步骤
0,0,0Xk选取初始点,令 确定精度 ；
①
③
1
1
( ) m in ( )k k k k k
k k k k k
P H X f X f X P
X X P
取 （ ）,由 求出和；
1,1,kf X k k计 算 （ ）,置 转 2 。
④
② ( ),
kkX f X对于点,若 则停止,否则转3 ；
当一维搜索是精确的，牛顿法为二阶收敛。
缺点：
★计算海赛阵的逆的工作量很大。
★要求 f(X)的二阶导存在且海赛阵是正定的 (以保证 H
的逆阵存在和算法是下降的 );
改进：
构造一个矩阵 代替牛顿方向中的,使 满足：
kH kHX -1（） kH
kH
★ 正定
★ 只用到 f(X)的一阶导信息
kH
★随着 k的增加,充分接近于 *HX -1（）
kH
称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。1()
kHX?
kHkH
2.拟牛顿法
★拟牛顿法是尺度阵 满足的一类变尺度法 ;
1 1 1( ( ) ( ) )k k k k kX X H f X f XkH
★拟牛顿法一般是超线性收敛的 ;
★ DFP是一种著名的拟牛顿法 ;
★当 f(X)为二次函数时,DFP法是共扼方向法，且具有二次终止性。
DFP方法的一般步骤
0
,0,0
X H H I
k?
选取初始点,和初始对称正定阵,可取（ ）
令 确定精度 ；
①
③ 1
1 1 1 1 1 1
1
1 1 1 1 1
1 1 1 1
,
,
k k k k k k k k k
TT
k k k k k k
kk TT
k k k k k
k k k k k k
P H f X P X X P
X X H G G H
HH
X G G H G
X X X G f X f X
取 （ ）沿 进行一维搜索，得 和其中：
＝ （ ）- （ ）
② ( ),
kkX f X对于点,若 则停止,否则转3 ；
1,1,kf X k k计 算 （ ）,置 转 2 。
④
例 9:
22
1 2 1 2 1 0
31( ) 2 [ 2 4 ]
22
Tf X x x x x x X求 的极小点，取 。
0
00
0
00
12
[ 1 2 6 ]
6() 5
3 1 1 2 17
[ 1 2 6 ]
1 1 6
T
T
P
f X P
P H P
一维搜索，由共轭方向最佳步长公式可得沿
11
12
22
1 2 2 1 0
0 0 0 0 0
311
( ) [ ] [ 2 0]
112
( ) [ 3 2 ],( ) [ 12 6]
1 0 12 3 1
,( ),( )
0 1 6 1 1
TT
xx
f X x x
xx
f X x x x x f X
H P H f X H X
解取＝
1 0 0 0
1
5 2 6 3 8
[ 2 4 ] [ 1 2 6 ] = [ ]
1 7 1 7 1 7
6 1 2
[ ]
1 7 1 7
T T T
T
X X P
fX
（）
0 0 0 0 0 0
10
0 0 0 0 0
60 210
1 0 1 060 30 210 90
17 17
30 17 17 0 1 90 17 17 0 1
10
17 17
21001
60 30 17
17 17 90
17
TT
TT
X X H G G H
HH
X G G H G
210
10210 90
17
17 17 0 1 90
17
385 2411
241 891986
0 1 0 0 1 0
6 0 3 0 2 1 0 9 0[ ],[ ]
1 7 1 7 1 7 1 7
TTX X X G f X f X＝ （ ）- （ ）
1 1 1
69
38 5 24 11 17 29
()
24 1 89 1 12 21986
17 29
P H f X
1
11
1
11
9
6 12 29
17 17 21
() 2929
9 17
319 21 29
29 29 1 1 21
29
T
T
P
f X P
P H P
沿 一维搜索，由共轭方向最佳步长公式
－
＝
2 1 1 1 2
2
[ 1 1 ],( ) [0 0 ]
[ 1 1 ]
TT
T
X X P f X
X
故 是极小点。
第三节 约束极值问题
★一般模型 m in ( )
( ) 0,1,,
( ),,
( ) 0,1,,
{ | ( ) 0,( ) 0 }
m in ( )
i
j
n
ij
XD
fX
h X i m
NL P s t
g X j l
D X R h X g X
NL P f X
记则（ ）也可以表示为
1.基本概念和性质
⑴起作用约束
0 0 0
00
,X D X X
XX
对于点 在 点等于零的约束称为对 起作用的约束，
在 点不等于零的约束称为对 不起作用的约束。
0
0 ( ) 0,1,,
( ) 0,{ 1,,} ( ) 0( )
X
i
jj
h X i m
g X j J l g X J
X
j
0
在 点 起 作 用 的 约
＝ 的 不 等 式 约 束 。
几 何 意 义,
束 包 括 全 体 等 式 约 束 和满 足位 于 这 些 约 束 的 边 界 上 。
0
0
0 ( ) 0
( ) 0 ( )
X
j
j
gX
gj
X
XJ
0
的 不 等 式 约 束
。
几 何 意 义,
在位的 不 起 作 用 的 约 束 包于 这 些 约 束括的 内 部 。
⑵可行下降方向
0
0 0 0
P
[0,]
XD
X
n方 向 R 在 点 称 为 是 可 行 的是 指 存 在 正 数,使 对 一 切 都 有 + P D ;
0
0 0 0( ) ( ) 0
nP R X D
X P D f X P f X
方 向 在 点 称 为 下 降 的是 指 存 在,有
*
*
N L PX
X
如 果 是 （ ） 的 极 小 点,
则 在 不 存 在 可 行 下 降 方 向 。
⑶可行下降方向的条件
( ) 0
( ) 0 ( ) 0
( ) 0
i
ii
j
hX
h X h X
gX
可 以 化 为 两 个 不 等 式 约 束
,来 表 示,所 以 讨 论 约 束 条 件时 可 只 考 虑由 于 等不 等 式 约 束式 约 束
。
0
0
00
0
( ) 0 ( 1,,)
( ) - ( ) 0
j
PX
g X P j l
f X P f X
PX
由 可 行 下 降 方 向 的 定 义,某 方 向 在 点 若 满 足则 是 的 可 行 下 降 方 向 。
0 0 0
0 0 0
0
( ) ( ) ( ) ( 1,,)
( ) ( ) ( )
T
j j j
T
g X P g X g X P j l
f X P f X f X P
X P D
由泰勒公式其中 是足够小的正数（保证 ）
0
0
( ) 0
( ) 0
T
j
T
g X P
P
f X P
P
不 难 看 出,只 要 便 保 证 是 可 行 下 降 的 。
这 可 作 为 可 行 下 降 的 充 分 条 件 。
00
0
00
( ) ( )
( ) - ( )
j
j
P g X P f X
XP
g X f X
几何意义是,与 夹锐角，同时 与- 也夹锐角。
由此可知，如果在 不存在可行下降方向，则一定不存在同时与 和 夹锐角。
2.最优性条件 （ K-T条件）
0
*
N L P ( ) ( )
N L P
jf X g X
X
考 虑 只 含 有 不 等 式 约 束 的 （ ） 。 设 与 均 为连 续 可 微 函 数,是 （ ） 的 最 有 解 。
**
0
D
( ) 0
XX
fX?
如 果 是 的 内 点,即 约 束 对 是 不 起 作 用 的,则 由 无 约 束极 值 问 题 的 极 值 必 要 条 件,有 ＝ 。
*
1
**
11
*
*
( ) 0
( ) 0 ( )
( ) P
P
X g X
g X X g X
fX
X
如 果 是 某 一 个 约 束 的 边 界 点,
即 对 起 作 用,则 必 有与 - 反 向,否 则 必 有 与 二 者 同 夹锐 角,即 是 的 可 行 下 降 方 向,矛 盾 。
1()gX
*1 ()gX?
*()fX?-
*X
* * * *11( ) ( ) ( ) ( )g X f X f X g X11故 与 同 向,即 存 在 0,使 ＝ 。
*
12
**
12
**
12
* * *
12
( ) 0 ( ) 0
( ) 0 ( ) 0 ( )
( ) ( ) P
( ) ( ) ( )
P
X g X g X
g X g X X f X
g X g X
f X g X g X
如果 位于某两个约束 和 的交点，
即 和 均对 起作用，则必有位于 和 的夹角内部，否则也会有 与
－,和 同夹锐角，即存在可行下降方向,矛盾。
*X
1()gX
2()gX
*()fX?
*1()gX? *
2 ()gX?
12
* * *
1 1 2 2
12
( ) ( ) ( )
,0
f X g X g X
故有 和 使下式成立：
＝＋
*
**
( ) 0
( ) ( )
0
j
jj
jJ
j
X g X j J
f X g X
jJ
依此类推，若 点起作用约束为,,
则有 ＝
，
*
*
( ) 0jjgX
X
其 中 条 件 是 为 了 在 梯 度 组 合 式 中 去 掉 不 起作 用 约 束,称 为 松 紧 条 件 。 这 时 要 求 点 各 起 作 用 约 束 的梯 度 线 性 无 关 。
**
1
*
( ) ( )
( ) 0 ( 1,,)
0 ( 1,,)
l
jj
j
jj
j
f X g X
g X j l
jl
＝
或 表 示 为
＝
定理 (K-T条件 )
**
**
* * * * * *
11
* * * * *
11
*
( ) ( 1,,) ( )
[ ] [ ]
( ) ( ) ( )
( ) 0 1,,
0 1,,
ij
ml
ml
i i j j
ij
jj
j
X N L P X
h X i m g X j J
f X h X g X
g X j l
jl
＝ ＝
设 是 （ ） 的 最 有 解,且 在 点 各 起 作 用 约 束 的 梯 度和,线 性 无 关,则 存 在 向量 和 使 下 式 成 立,
＝ ＋
（ ）
,（ ）
* * * *
11 mlK-T 条 件 中 的,,和,,称 为 广 义 拉 格 朗 日 乘 子 或
K-T 乘 子 。 满 足 K-T 条 件 表 达 式 的 可 行 点 称 为 K-T 点 。 可 以 证 明
K-T 条 件 对 凸 规 划 是 充 要 的 。
例 10：利用 K－ T条件求解下面的非线性规划
2m i n ( ) ( 3 )
.,0 5
f X x
s t x
2
1
2
m i n ( ) ( 3 )
,,( ) 0
( ) 5 0
f X x
s t g X x
g X x
解 原问题可写为
12
12
" ( ) 2 0," ( ) " ( ) 0
( ) ( ) ( )
f X g X g X
f X g X g X
因 为故 解 为 凸 函 数,和 均 为 凹 函 数,
此 问 题 为 凸 规 划 。
为解此方程组，可分几种情况考虑：
12
12
1
2
12
( ) 2 3 ( ) 1,( ) 1
2 3 0
0
( 5 ) 0
,0
f X x g X g X
KT
x
x
x
＝ （ ）,
条 件 表 达 式 为
（ ） － ＋ ＝
**3 ( ) 0x f x由 于 此 问 题 为 凸 规 划,故 是 最 有 解,相 应 最 优 值 。
12 00 且,无 解 ；
①
12 0 3,x K T＝,解 得 满 足 约 束,是 － 点 ；
④
1 2 20 0 5,4,x K T且,解 得 － 不 是 － 点 ；
③
1 2 10 0 0,6,x K T且 ＝,解 得 － 不 是 － 点 ；
②
例 11:考虑非线性规划并验证它为凸规划，用 K－ T条件求解
12
12
12
m a x ( ) l n( 1 )
23
,,
,0
f X x x
xx
st
xx
12
1 1 2
21
22
m i n ( ) l n( 1 )
,,( ) 3 2 0
( ) 0
( ) 0
f X x x
s t g X x x
g X x
g X x
解 原 问 题 可 写 为计算目标和约束函数的海赛阵
12
1
3
1
( ) 1 ( ) [ 2 1 ],( ) [ 1 0],
( 1 )
( ) [ 0 1 ]
-
T
TT
T
f X g X g X
x
gX
KT
，
表达式为：
1 2 3
2
1
1
0 0 0
( 1 )( ) 0,( ) ( ) ( ) 0
0 0
0 0
f g g g
xH X H X H X H X
故此问题是凸规划。
1 1 1 2
13
0 0 3 2 0
00
xx
x
＝,则 无 解,于 是,有 ＝
令 ＝,＝
若
,则 有
12
1
2
0
1
30x
1 － 2 ＋ ＝
－ ＝ 0
（ ）
1 2 1 2 0xx T＝0,＝3,＝ ＝,显然[0 3 ] 是可行点，从而解得 是极小点。
12
1
12
1 1 2
21
32
1 2 3
1
2
( 1 )
1
3 2 0
0
0
,,0
x
xx
x
x
＝ - ＋
＝ - ＋
（ ）
3.二次规划
★一般模型
m i n ( )
1
2
0
,,
0
,
TT
fX X H X C X
A X b
st
X
A m n b m C n
其中 为 阶矩阵； 为 维非负向量； 为 维向量。
0 K - TH?
由 于 二 次 规 划 的 约 束 是 线 性 的,从 而 是 凸 集,故 当 目 标 的 二 次 项系 数 矩 阵 （ 半 正 定 ） 时 为 凸 规 划,可 用 条 件 求 解 。
11
22
( )
( ) 0
( ) 0
f X H X C
g X A g AX b m
g X I g X n
则 梯 度,
与 约 束 （ 个 ） 相 对 应,
与 约 束 （ 个 ） 相 对 应 。
m in ( )
1
2
0
,,
0
TT
fX X H X C X
A X b
st
X
1 1 1
2 2 1
( ) -
( ) -,-
T
m
T
m m n
g
g
X K T Y y y
X K T Y y y K T
记 相 应 于 的 乘 子 为 ＝,相 应 于的 乘 子 为 ＝ 则 由 条 件及 约 束 条 件,有,
12
1
2
12
0
0
0
,,0
T
T
T
TT
H X C A Y IY
Y A X b
YX
A X b
X Y Y
＝
（ ）＝
＝
上 面 的 一 组 式 子 中,若 不 考 虑 两 个 松 紧 条 件,则 其 余 均 为 线 性表 达 式,即,
12
12
0
,,0
T
TT
H X A CY I Y
A X b
X Y Y
＝
思考,能否在此基础上构想基于线性规划求解的方法?
1
0
T
nZ zz如 果 在 上 面 第 一 式 中 增 加 人 工 变 量 ＝ （ 为 使 出 现单 位 阵 ）,并 增 加 使 人 工 变 量 之 和 极 小 化 的 目 标 函 数
（ 为 使 人 工 变 量 最 后 均 为 ）,则 可 构 造 一 个 线 性 规 划,
1
12
12
m in
sg n ( )
,,
,,,,0
sg n ( )
n
T
s
TT
s
s
H X A C
z z z
Y I Y C Z
s t A X X b
X Y Y Z X
C Z Z C
X
＝
其 中 表 示 中 各 分 量 的 符 号 与 中 相 应 分 量 的符 号 相 同,是 为 了 保 证 出 现 单 位 阵 ； 是 松 弛 变 量 。
用 单 纯 形 法 求 解 该 规 划 的 单 纯 形 初 表 为 下 表 。
BX
1Bb? X
sX 1Y 2Y
Z
Z C H? 0 TA I sgn( )CI
sX b
A? I 0 0 0
12
1
2
12
,,
0
0
T
s
T
s
X Y Y
YX
YX
Y X Y X
为使所求得的 还满足松紧条件
＝
＝
应在每次单纯形表的迭代中保证 与 以及 与的相应分量不同时为基变量。
例 12,求解二次规划
22
1 2 1 2
12
12
m in ( )
1
( 2 2 ) 8 1 0
2
6 3 2 0
,,
0,0
fX x x x x
xx
st
xx
1 1 2 2 3
2 0
,[ 3 2],[ 8 10 ],6
0 2
,[ ]
0,K - T
T
T
H A C b
Y y Y y y
H
显然有 故此问题是凸规划。可用 条件求解。
解
12
211
1
322
1
3
2
sgn ( )
2 0 3 8
0 2 2 10
[ 3 2] 6
T
s
H X A Y I Y C Z
yxz
yC
yxz
x
AX X x b
x
12
1 1 2 1
2 1 3 2
1 2 3
1 2 3 1 2 3 1 2
1 3 2 1 3 2
2
2
3
m in
38
2 1 0
,,
26
,,,,,,,0
0 0,0
x
x
x
z z z
y y z
y y z
st
xx
x x x y y y z z
y x y x y x
相应的线性规划为求解时还要满足松紧条件 ＝,＝,＝ 。
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
BC BX
1Bb
1x
1x
1x
1x
2x
2x
3x
3x
1y
1y
1y 2y 3y
1z
1z
1z
2z
2z
2z
2z
求得的结果是：
1 2 3 1 2 3
4 3 3 3 2,,0,,0,0
1 3 1 3 1 3x x x y y y
1
3 1 3 1
*
4 3 3
[ ]
1 3 1 3
T
y
x y x x
X?
在 每 一 次 单 纯 行 表 迭 代 中 都 考 虑 了 松 紧 条 件,如 在 第 一 张表 中,按 通 常 规 则 应 让 进 基,但 考 虑 到 与 它 构 成 松 紧 式的 已 在 基 中,并 且 进 基 也 不 会 使 出 基,故 选 择 进 基,
从 而 所 得 解 满 足 松 紧 条 件,是 原 来 二 次 规 划的 最 优 解 。
4.罚函数基本思想：将约束与目标组合在一起，化为无约束极值问题求解。
★
内点法：从可行域的内部逐步逼近最优解。★
外点法：从可行域的外部逐步逼近最优解。★
外点法的关键是基于（ NLP） 构造一个新的目标函数
P（ X,M）,称为罚函数。
22
11
(,) ( ) [ m in( 0,( ) ) ] ( )
lm
ji
ji
P X M f X M g X M h X
M
M
式 中 是 一 个 充 分 大 的 正 数,称 做 罚 因 子 。
含 的 项 称 为 罚 项 。
当 X是可行点时，罚项为 0
当 X不是可行点时，罚项是很大的整数。
对 P（ X,M） 求极小，可采用无约束优化方法，罚项能保证 X逐步趋近可行域。
一般步骤：
0,,1,0Mk1选 取 初 始 罚 因 子 令 ；①
m in (,),k k kM P X M X对于,求解无约束极值问题 得 ；②
1
| ( ) | ( 1,,)
( ) ( 1,,)
N L P,
1,2
k
ik
ik
k k k
X
h X i m
g X j l
X M M
kk
＋
若 满 足 可 行 性 的 精 度 要 求则 停 止,即 为 （ ） 的 近 似 最 优 解,否 则,取置 ＝ 转 。
③
,P X M
M
用 罚 函 数 法 求 解 一 些 简 单 的 非 线 性 规 划 时,可 先 求 出 （ ）
的 驻 点,然 后 令 。
例 13：求解非线性规划
3
12
1
2
m in ( )
1
( 1 )
3
10
,,
0
fX xx
x
st
x
3 2 2
1 2 1 2
1(,) ( 1 ) [ m i n (0,1 ) ] [ m i n (0,) ]
3P X M x x M x M x
解 构造罚函数
2
11
1
2
2
( 1 ) 2 [ m in( 0,1 ) ] 0
1 2 [ m in( 0,) ] 0
P
x M x
x
P
Mx
x
令
1 1 21 0 1,0 1 0x x x当,不可行；当,由第二式有＝,矛盾，
说明可行域内无驻点。
12
2
1
2
1 0,0,
41
1
2
xx
x M M M
x
M
对于可行域外的点（满足 ）可解得驻点
＝
1
2( 1 ) 2 0
0
02
xM
H
M
在该点，海赛阵说明该驻点是极小点。
T1
2
1M,
0
x
x
令 则,而 1 0 满足约束，是最优解。
例 14：求解非线性规划
2 2 21 2 1 2 1(,) [ m in( 0,) ] [ m in( 0,) ]P X M x x M x x M x
解 构造罚函数
2
1 2 1 1
1
2
12
2
1 2 [ m in( 0,) ] ( 2 ) 2 [ m in( 0,) ] 0
1 2 [ m in( 0,) ] 0
P
M x x x M x
x
P
M x x
x
考察其驻点，令
12
2
12
1
mi n ( )
0
,,
0
fX xx
xx
st
x
12
2
1 2 1 1
2
12
1 0,0,
1 2 ( ) ( 2 ) 2 0
1 2 ( ) 0
xx
M x x x M x
M x x
对于可行域外的点（满足 ）可解得驻点
T1
2
0,
0
xM
x
令 则,而 0 0 是 可 行 点,故 是 最 优 解 。
1
2 2
1
2( 1 )
11
4( 1 ) 2
x
M
x
MM
＝
解得
非线性规划（ Nonlinear Programming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。
0
..
X
bAX
ts
CXM a xz
第一节 基本概念一、非线性规划问题与模型
1,问题
⑴ 生产计划问题
m a x ( ) ( ) ( )
( ) 0
..
( ) 0
i
j
f x x P x x C x
gx
st
hx
x:产量 ;P(x):价格 ;C(x)成本
⑵投资决策问题
1 1 1
1
::
::
::
m a x ( )
..
0
jj
j
ij
n n n
j j i j
j i j
n
jj
j
j
x j P j
Bj
ij
f x x x x
P x B
st
x
第 种股票的购买量； 第 种股票的价格总资金； 第 种股票的每股平均收益风险系数； 第 种与第 种股票收益的协方差
2.模型
1
n
n
m in ( )
( ) 0,1,,
( ),,
( ) 0,1,,
[,,]
{ | ( ) 0,( ) 0 }
m i n ( )
D NL P
D R NL P
D R NL P
i
j
T
n
n
ij
XD
fX
h X i m
N L P s t
g X j l
X x x
D X R h X g X
N L P f X
其 中记则 （ ） 也 可 以 表 示 为其 中 称 为 （ ） 的 约 束 集 或 可 行 域 。
当 ＝ 时,（ ） 称 做 无 约 束 极 值 问 题 ；
当 时,（ ） 称 做 约 束 极 值 问 题 。
二,模型的解及相关概念
1.可行解与最优解
★ 可行解：约束集 D中的 X。
★ 最优解：如果有,对于任意的,
都有,则称 为（ NLP） 的最优解，也称为全局最小值点。
*XD? XD?
*( ) ( )f X f X? *X
★ 局部最优解：如果对于,使得在 的邻域 中的任意都有,则称 为（ NLP） 的局部最优 解，也称为局部最小值点。
0XD? 0X
XD?
0( ) ( )f X f X?
00(,) { | }B X X X X
0X
例 1：考虑非线性问题
22
12
12
m i n ( ) ( 2 ) ( 2 )
,,6
f X x x
s t x x
2 x
1 x
6
6
3
3
如果约束改为呢
？
12 6xx
2.梯度、海塞阵与泰勒公式
★ 梯度
00
00
00
0
1
( ) ( )
( ) ( )
( ) ( )
( ) [ ]
T
n
f X X f X X
f X X f X
f X f X
fX
xx
若 在 的邻域内有连续一阶偏导数，则称 在 点对n
个变元的偏导数组成的向量为 在 的梯度，记为,
即 ＝,,
00 ()X f X X
几何意义：
梯度是过 点且与 在 的切平面垂直的向量，
梯度向量的方向是函数值在该点增加最快的方向。
★海塞阵
00
0
0
00
00
11
00
1
2
22
2
22
2
( ) ( )
()
()
( ) ( ) [ ]
( ) ( )
( ) ( )
ij
n
nn
nn
f X X f X X n
f X X
fX
H X H X
xx
f X f X
x x x
f X f X
x x x
若 在 的邻域内有连续二阶偏导数，则称 在 点对个变元两两组合的二阶偏导数组成的矩阵为 在 的海赛阵，
记为,即 =
★泰勒公式
00
0 0 0 0 0 0
2
0
22
0 0 0
( ) ( )
( ) ( ) ( )
1
( ) ( ) ( )
2
( )
()
TT
f X X f X X
f X f X f X X X X X H X X X
o X X
o X X X X X X
若 在 的邻域内有连续二阶偏导数，则可写出 在 点的（二阶）泰勒展开式：
＝ （ － ）
－
其中,是当 时 的高阶无穷小。
例 2：写出 在 点的二阶泰勒展开式2
12( ) 3 sinf X x x 0 [ 0,0] TX?
1 2 0
0
2
( ) [ 6 ( ) [ 0 1 c os ],]
60 60
( ),( )
0 si n 00
TTf X x f Xx
H X H X
x
解,
211
12
22
( ) 0 [ 0 1
60 1] [ ] ( )
002
xx
f X x x o X
2
0
2
12
()
( ) 3
() fX
f X x
o X X
x?
如果忽略了 在,则 点的近似表达式为
+
3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将 n(n>1)元函数 与一元函数 的极值条件加以对比并归纳如下：
()fX ()fx
00()X x或 是极小点
()fx一元函数
()fXn元函数
0'( ) 0fx?
0( ) 0fX
00'( ) 0,''( ) 0f x f x且
00( ) 0 ( ) 0f X H X且充分条件必要条件
0( ) 0HX?注,表 示 海 赛 阵 正 定 。 如 果 一 个 方 阵 的各 阶 主 子 式 均 大 于 零,则 可 以 判 定 该 方 阵 是 正 定 的 。
例 3：求 的极小值点22
1 1 2 2( ) 2 28 4 20f X x xxx
解
12
12
0
( ) [
( ) 0
] [ 4 8 4 4 ]
[ 2 1 ]
TT
T
ff
fX
xx
f X X
xx
＝
＝,解得驻点令
0
0
40
( ),( ) 0
04
H X H X
X
又故 是 极 小 值 点 。
4.凸规划
★凸函数,f(X)是定义在凸集 D上且满足对任意有下式成立的函数：
1 2 1 2( ) (( 1 ) ) ( 1 ) ( )f X f XX f X
12,,X X D?
[0,1]
若不等式中严格不等号成立，则称 f(X)为严格凸函数注：判断一个可导函数 f(X)是否是凸函数的方法一元函数 f(x),二阶导大于等于零 ;
多元函数 f(X),海塞阵半正定。
★凸规划性质：★约束集是凸集；
★最优解集是凸集；
★任何局部最优解也是全局最优解；
★若目标函数是严格凸函数，且最优解存在，则其最优解是唯一的。
在非线性规划模型（ NLP） 中，若目标函数 f（ X） 是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（ NLP） 是一个凸规划。
( ) 1,,jg X j l?
( ) 1,,ih X i m?
例 4：判断下面的非线性规划是否为凸规划
12
22
12
12
max ( )
1
..
,0
fX xx
xx
st
xx
12
22
1 1 2
21
32
m in( ( ) )
( ) 1 0
.,( ) 0
( ) 0
fX xx
g X x x
s t g X x
g X x
标准化
1
23
()
0 0 2 0
0,( ) 0
0 0 0 2
00
( ) ( ) 0
00
fg
gg
HX HX
H X H X
计算
1 2 3() ( ) ( ) ( )fX g X g X g X?说 明 是 凸 函 数,,,是 凹 函 数因 此,本 模 型 是 凸 规 划 。
第二节 无约束极值问题
★一般模型,mi n ( )
n
fX
XR?其中
★求解（ f(X)可微）：应用极值条件求解，往往得到一个非线性的方程组，求解十分困难。因此，求 解无约束问题一般采用迭代法，称为下降类算法。
一、下降类算法的基本步骤与算法收敛性
1.基本思想
0
0
1
12
()fX
X
P
X
PX
基本思想是使 逐步下降，逐渐趋近其最小值。迭代方式是从一个初始点 出发，选取某一搜索方向,沿该方向搜索到下一个点 。若达到与最优解误差的精度要求，则停止，否则再沿该点的某一方向 搜索下一个点 。
这一过程如图所示：
0P
1P
2P
0X
1X
3X
2X
2.基本步骤
0,0,0Xk选取初始点,令 确定精度 ；
(1)
( ),( ),
3
k k k
k
X f X f X
X
对 于 点,计 算 若 则 停 止,
得 到 近 似 最 优 解,否 则 转 （ ） ；
(2)
kkXP从 出发，确定搜索方向 ；
(3)
1
,
,,1,2 )
k k k k
k k k k
P X X P
X X P k k
沿 方 向 搜 索,即 由 ＝ 确 定 搜 索 步 长得 到 下 一 个 点 ＝ 令 转 ( 。
(4)
注：不同的搜索方向，就形成了不同的算法，不同的算法所产生的点列收敛于最优解的速度也不一样。
3.收敛性衡量标准,*
1
*l i m
k
k k
XX
XX
1,0 1,{ }kX 则称 是线性收敛的；①
1,0,{ }kX 则称 是超线性收敛的；②
2,0,{ }kX 则称 是二阶收敛的。③
二阶收敛 >超线性收敛 >线性收敛二、一维搜索
:
精确搜索：
一维搜索分数法近似搜索 0,1 6 8 法其他方法（导数信息）
0
m in ( ),kk
k
f X P
通过求极值得到最佳步长
k
求上面极值的近似值得到近似最佳步长
1.分数法 （斐波那契法）
2t
⑴基本思想
*tO a b'
1t1t
()ft
t
怎样在区间中取点最好？
'11( ) ( )f t f t?若
12( ) ( )f t f t?若
⑵基本概念
[,],0nnn a b记第 次缩短后的小区间为 给定的精度要求为
★满足绝对精度：
★满足相对精度：
||nnba
||nnba
ba?
★斐波那契数：
12
01 1
n n nF F F
FF
55342113853211
9876543210
nF
n
1(1 ) ( )n
n
Fa b a
F
1 ()n
n
Fa b a
F
a b1t '
1t
''1
1 1 1
1
' 1 2 2
1
1
1 1 1
'
1 2 1 - 1 1
12 21
1 3 2
[,],
( 1 - ) ( - )
[,],
()
[,] - 1 [,]
1
( - )
n
n
n
n n n n n
n
n n n
n
nn
nn
nn
F
t t t b
F
F
ba
F F F F F
t a t
F F F F
ba
F
a t t t n a b
FF FF
ba
F F F F F
1
若 按 的 比 例 在 区 间 中 对 称 地 取 点 和,经 比 较 后 去 掉则 在 中 所 占 的 比 例 为 再 按比 例 在 中 取 与 对 称,这 样 反 复 次 后 所 得 的 小 区 间长 缩 短 为 ( ),
1
()
11
-
n
n
n
nn
ba
ba
F
Fn
b a F F
与 原 区 间 长 之 比 为,
,恰 为 相 对 精 度 表 达 式 。 于 是,开 始 可 由 解 出,
⑶步骤
① 1;
n
nF?由所给精度 和 定 11
1
' ' '1
1 1 1 1 1
11
( 1 - ) ( - )
( ) m a x { }
,[,]
nn
n
n
FF
t b a
F
t b a t t t t
F
ab
由 的 比 例 在 区 间 [a,b] 中 对 称 地 取 点 =a+ 和
=a+,比 较 f ( ) 和 f ( ),去 掉 f ( ),f ( ) 相 应点 以 外 的 区 间 得 到 新 区 间 ；
②
2
1 1 2
1
'
2 1 1
22
[,] ( )
( ) m i n { ( ),( ) }
[,]
n
n
F
a b t
F
f t f t f t
ab
在 中按 的比例取点 与区间中所剩的点对称比较 和,去掉较大者对应点以外的区间，得到新区间 ；
③
3
2 2 3
2
*1
- 1 1
2
[,]
[,]
n
n
nn
F
a b t
F
F
a b t
F
在 中 按 的 比 例 取 点 再 比 较,再 缩 短,直 到 取 完
,最 后 的 小 区 间 中 的 任 意 一 点 可 作 为 的 近 似 值 。
④
例 5：
2( ) 2 [ 1,3 ]
8
f t t t用 分 数 法 求 在 区 间 上 的 近 似 极 小 点,
要 求 缩 短 后 的 区 间 长 度 不 大 于 原 区 间 长 的 ％ 。
**
''( ) 2 0,
1'( ) 2 1 0 1.7 5
2
f t f t
f t t t f t
解 由 于 所 以 （ ） 是 严 格 的 凸 函 数 。
由 ＝ － ＝,解 得 是 极 小 点,（ ） ＝
5
6
11
''
1 1 1
4
11
5
2
21
1 1 8
0.0 8 12,5,6,
0.0 8 13
8
1 ( 1 ) [ 3 ( 1 ) ] 0.5 38,( ) 1.7 51
13
8
1 [ 3 ( 1 ) ] 1.4 62,( ) 2.6 75 ( )
13
5
[,] [ 1,1.4 62],
8
5
1 ( 1 ) [ 1.4 62 ( 1 ) ] 0.0 77,
8
( ) 2.0 83 ( ),
n
n
F
Fn
FF
t f t
t f t f t
F
ab
F
t
f t f t
由 知 查表得故
22
55
[,] [ 0.0 77,1.4 62]
0.5 38 ( ) 1.7 51
ab
t f t
故依此进行，得 ＝ 为近似极小点，
2,0.618法
★区别：每次取点得比例是定值 0.168，即每次区间内两点得位置均在区间相对长度得 0.328和 0.168处。
★特点：简单，更易于应用；
效果也比较好。
3.近似最佳步长公式
2
()
1( ) ( ) ( ) ( )
2
TT
k k k k k k k k
fX
f X P f X f X P P H X P
设 存在连续的二阶偏导数，则有泰勒展开式
0
( ) ( ) 0TTk k k k kdf f X P P H X P
d
对 求导，并令导数为,得
()
()
T
kk
T
k k k
f X P
P H X P?
－解得,＝
k fX?上式即为 的近似最佳步长公式。当（ ）为二次函数时，此公式是精确的。
例 6：
22
12( ) ( 1 ) ( 1 ),[ 0 0 ],( )
T
k k k
k
f X x x X P f X
设－
用近似最佳步长公式求 。
12
( ) [ 2 ( 1 ) 2 ( 1 ) ],( ) [ 2 2 ]
20
( ) ( )
02
2
[ 2 2 ]
2 1
2 0 2 2
[ 2 2 ]
0 2 2
TT
k
k
f X x x f X
H X H X
解
() kfX?由于 是二次函数，故所求 是精确的。
三、梯度法和共轭梯度法
1.梯度法
()
( ) ( ) ( ) Tk k k k k
fX
f X P f X f X P
设 有连续的二阶偏导数，则有泰勒展开式
0,
( ) ( ) c o s 0
()
,( ) ( )
2
c o s 1,,
T
k k k k
kk
k k k
f X P f X P
f X P
f X P f X
由 于 应 使
＝
其 中 为 向 量 和 的 夹 角 。 为 使 上 式 成 立,
应 使 又 为 使 的 绝 对 值 尽量 大,应 使 ＝ - 即 ＝
( ) ( )kk
k
P f X X f X
P
故 ＝ 即在 点的负梯度方向是使 下降最快的方向。以负梯度作为搜索方向 的下降类算法称为梯度法或最速下降法。
( ) 0) )(( kkk kf X P XpX ff思 想,怎 样 选 取 可 使 下 且 左 边 差降 最 额快？ 即 使 尽 量 大 。
★一般步骤
0,0,0Xk选取初始点,令 确定精度 ；
(1)
( ),( ),
3)
k k k
k
X f X f X
X
对 于 点,计 算 若 则 停 止 计 算,
得 到 近 似 最 优 解,否 则 转 ( ；
(2)
1
( ),k k k k
k k k k
P f X P
X X P
取 沿 进行一维搜索，得到 和下一个点；
(3)
1,1,2 )kf X k k计 算 （ ）,置 转 ( 。
(4)
例 7:
22
12
0
( ) ( 1 ) ( 1 ) 0,1
[0 0 ] T
f X x x
X
用梯度法求 的极小点，取 ＝
初始点 。
1 2 0
22
0
( ) [ 2( 1 ) 2( 1 ) ],( ) [ 2 2]
( ) ( 2) ( 2) 8
Tf X x x f X
fX?
解,
0
0
2
[ 2 2 ]
20 2 1
()
2 0 202 2
[ 2 2 ]
0 2 2
HX
由 近 似 最 佳 步 长 公 式 求,
,
1 0 0 0
10
*
1
1
( ) [ 0 0] [ 2 2] [ 1 1 ]
2
( ) [ 0 0],( ) 0
[ 1 1 ]
T T T
T
T
X X f X
f X f X
XX
故上例中，目标函数是同心圆族。无论初始点选在何处
，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。
但对于一般的函数，若每次迭代均采用负梯度方向，
则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象
，收敛速度很慢。可以证明，梯度法是线性收敛的。
注：
2.共轭梯度法
⑴基本概念
0
,
TX Y n A n X A Y
X Y A A I X Y
设 与 均为 维向量,是 阶对称正定阵。若,
则称 与 关于 共轭。当 则 与 正交。关于共轭，
有下述重要性质：
11
11
1
,0,
1,,,0
0,0
1
nn
n n i
TT
i i i i
T
i i i n
n n P P A P P
P P R
P A i n P A P A
P A P P P
n n A
若 个非零 维向量,,关于 共轭，则,,
线性无关。事实上 只需考虑两边分别左乘 （ ）则有 ＝,而正定，即 故,说明,,线性无关。
这一性质也说明不可能有 个 维向量关于 共轭。
★
1
1
1
2
n
TT
n
n P P H H
f X X H X C X P P
n
若非零 维向量,,关于 共轭，则以 为二次系数阵的二次函数（ ） 沿,,（称为共轭方向）进行精确一维搜索，至多经次便可得极小点。
★
这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。
⑵一般步骤
0,0,0Xk选取初始点,令 确定精度 ；
①
1m i n ( ),k k k k k k k kX f X P X X P对 求解 得 和 ；
③
②
00P f X取 （ ）；
④
*
11
0
( ),,1,5
1,2
kk
n
f X X X k n
k n X X
若 则 停 止,否 则,若 转,
若,重 置 转 ； （ 重 置 的 原 因 是 由 于 计 算中 的 舍 入 误 差 可 能 造 成 n 步 未 终 止 。 ）
11
11
,1,3
k k k k
T
kk
k T
kk
P f X P k k
f X f X
f X f X
取 （ ）,置 转
（ ） （ ）
其 中,＝ （ F-R 法 ）
（ ） （ ）
⑤
( ),( )TTf f X X H X C X f X H X C1当 正 定,时,有2
11( ) ( ) ( ) ( )k k k k k k k k k kf X f X H X X H X P X H P
,TkP两边同时左乘 有
()TTk k k k kP f X P H P
k
k1 ( ) 0
T
k
PH
P f X
可以证明，按此方向构造的 是关于 共轭的，并且有
()Tkk
k T
kk
P f X
P H P
从而有例 8：
22
1 2 1 2 1 0
31( ) 2 [ 2 4 ]
22
Tf X x x x x x X求 的极小点，取 。
11
12
22
1 2 2 1
0 0 0
311
( ) [ ] [ 2 0 ]
112
( ) [ 3 2 ]
( ) [ 1 2 6 ],( ) [ 1 2 6 ]
T
TT
xx
f X x x
xx
f X x x x x
f X P f X
解
00
0
00
12
[ 12 6]
6() 5
3 1 12 17
[ 12 6]
1 1 6
T
T
P f X
P H P
1 0 0
5 2 6 3 8[ 2 4 ] [ 1 2 6 ] [ ]
1 7 1 7 1 7
T T TX X P
1
6 1 2( ) [ ]
1 7 1 7
TfX
11
0
00
6
6 1 2 17
[ ]
1 7 1 7 1 2
117
12 289
[ 1 2 6 ]
6
T
T
f X f X
f X f X
（ ） （ ）
＝
（ ） （ ）
1 1 0 0
11
1 2 1 1 1
11
6 1 2 1 9 0 2 1 0
( ) [ ] [ 1 2 6 ] [ ]
1 7 1 7 2 8 9 2 8 9 2 8 9
() 17
,[ 1 1 ]
10
T T T
T
T
T
P f X P
P f X
X X P
P H P
22( ) [ 0 0] [ 1 1 ]TTf X X?由 于 ＝,故 ＝ 即 极 小 点,计 算 经 两 步 终 止 。
四、牛顿法与拟牛顿法
1.牛顿法
⑴牛顿方向
( ) ( )
1( ) ( ) ( ) ( ) ( ) ( ) ( )
2
TT
k k k k k k
f X f X
f X f X f X X X X X H X X X
设 有 连 续 的 二 阶 偏 导 数,由 泰 勒 展 开 式,可 近 似 表 示 为
( ) ( ) ( ) ( )k k kf X f X H X X X
f
从 而当 为 二 次 函 数 时,上 式 为 精 确 表 达 式 。
11
k1
( ) ( ) 0
( ) ( ) ( ) 0
kk
k k k
X f X f X
f X H X X X
＋
＋
取 使 达 到 极 小,应 有 ＝,即
＋ ＝
1
k1
1
()
( ) ( )
( ) ( ),
k
k k k
k k k
HX
X X H X f X
P H X f X
－
＋
－
当 可逆，可解得
＝
记 称为牛顿方向。
()
1
()
k
fX
X
fX
对 于 正 定 二 次 函 数,采 用 牛 顿 方 向 作 搜 索 方 向,
步 长 取 为,从 任 意 点 出 发 一 步 即 可 得 极 小 点 。 对于 一 般 函 数,在 一 定 条 件 下,也 可 采 用 牛 顿 方 向,
所 形 成 的 算 法 称 为 牛 顿 法 。
⑵一般步骤
0,0,0Xk选取初始点,令 确定精度 ；
①
③
1
1
( ) m in ( )k k k k k
k k k k k
P H X f X f X P
X X P
取 （ ）,由 求出和；
1,1,kf X k k计 算 （ ）,置 转 2 。
④
② ( ),
kkX f X对于点,若 则停止,否则转3 ；
当一维搜索是精确的，牛顿法为二阶收敛。
缺点：
★计算海赛阵的逆的工作量很大。
★要求 f(X)的二阶导存在且海赛阵是正定的 (以保证 H
的逆阵存在和算法是下降的 );
改进：
构造一个矩阵 代替牛顿方向中的,使 满足：
kH kHX -1（） kH
kH
★ 正定
★ 只用到 f(X)的一阶导信息
kH
★随着 k的增加,充分接近于 *HX -1（）
kH
称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。1()
kHX?
kHkH
2.拟牛顿法
★拟牛顿法是尺度阵 满足的一类变尺度法 ;
1 1 1( ( ) ( ) )k k k k kX X H f X f XkH
★拟牛顿法一般是超线性收敛的 ;
★ DFP是一种著名的拟牛顿法 ;
★当 f(X)为二次函数时,DFP法是共扼方向法，且具有二次终止性。
DFP方法的一般步骤
0
,0,0
X H H I
k?
选取初始点,和初始对称正定阵,可取（ ）
令 确定精度 ；
①
③ 1
1 1 1 1 1 1
1
1 1 1 1 1
1 1 1 1
,
,
k k k k k k k k k
TT
k k k k k k
kk TT
k k k k k
k k k k k k
P H f X P X X P
X X H G G H
HH
X G G H G
X X X G f X f X
取 （ ）沿 进行一维搜索，得 和其中：
＝ （ ）- （ ）
② ( ),
kkX f X对于点,若 则停止,否则转3 ；
1,1,kf X k k计 算 （ ）,置 转 2 。
④
例 9:
22
1 2 1 2 1 0
31( ) 2 [ 2 4 ]
22
Tf X x x x x x X求 的极小点，取 。
0
00
0
00
12
[ 1 2 6 ]
6() 5
3 1 1 2 17
[ 1 2 6 ]
1 1 6
T
T
P
f X P
P H P
一维搜索，由共轭方向最佳步长公式可得沿
11
12
22
1 2 2 1 0
0 0 0 0 0
311
( ) [ ] [ 2 0]
112
( ) [ 3 2 ],( ) [ 12 6]
1 0 12 3 1
,( ),( )
0 1 6 1 1
TT
xx
f X x x
xx
f X x x x x f X
H P H f X H X
解取＝
1 0 0 0
1
5 2 6 3 8
[ 2 4 ] [ 1 2 6 ] = [ ]
1 7 1 7 1 7
6 1 2
[ ]
1 7 1 7
T T T
T
X X P
fX
（）
0 0 0 0 0 0
10
0 0 0 0 0
60 210
1 0 1 060 30 210 90
17 17
30 17 17 0 1 90 17 17 0 1
10
17 17
21001
60 30 17
17 17 90
17
TT
TT
X X H G G H
HH
X G G H G
210
10210 90
17
17 17 0 1 90
17
385 2411
241 891986
0 1 0 0 1 0
6 0 3 0 2 1 0 9 0[ ],[ ]
1 7 1 7 1 7 1 7
TTX X X G f X f X＝ （ ）- （ ）
1 1 1
69
38 5 24 11 17 29
()
24 1 89 1 12 21986
17 29
P H f X
1
11
1
11
9
6 12 29
17 17 21
() 2929
9 17
319 21 29
29 29 1 1 21
29
T
T
P
f X P
P H P
沿 一维搜索，由共轭方向最佳步长公式
－
＝
2 1 1 1 2
2
[ 1 1 ],( ) [0 0 ]
[ 1 1 ]
TT
T
X X P f X
X
故 是极小点。
第三节 约束极值问题
★一般模型 m in ( )
( ) 0,1,,
( ),,
( ) 0,1,,
{ | ( ) 0,( ) 0 }
m in ( )
i
j
n
ij
XD
fX
h X i m
NL P s t
g X j l
D X R h X g X
NL P f X
记则（ ）也可以表示为
1.基本概念和性质
⑴起作用约束
0 0 0
00
,X D X X
XX
对于点 在 点等于零的约束称为对 起作用的约束，
在 点不等于零的约束称为对 不起作用的约束。
0
0 ( ) 0,1,,
( ) 0,{ 1,,} ( ) 0( )
X
i
jj
h X i m
g X j J l g X J
X
j
0
在 点 起 作 用 的 约
＝ 的 不 等 式 约 束 。
几 何 意 义,
束 包 括 全 体 等 式 约 束 和满 足位 于 这 些 约 束 的 边 界 上 。
0
0
0 ( ) 0
( ) 0 ( )
X
j
j
gX
gj
X
XJ
0
的 不 等 式 约 束
。
几 何 意 义,
在位的 不 起 作 用 的 约 束 包于 这 些 约 束括的 内 部 。
⑵可行下降方向
0
0 0 0
P
[0,]
XD
X
n方 向 R 在 点 称 为 是 可 行 的是 指 存 在 正 数,使 对 一 切 都 有 + P D ;
0
0 0 0( ) ( ) 0
nP R X D
X P D f X P f X
方 向 在 点 称 为 下 降 的是 指 存 在,有
*
*
N L PX
X
如 果 是 （ ） 的 极 小 点,
则 在 不 存 在 可 行 下 降 方 向 。
⑶可行下降方向的条件
( ) 0
( ) 0 ( ) 0
( ) 0
i
ii
j
hX
h X h X
gX
可 以 化 为 两 个 不 等 式 约 束
,来 表 示,所 以 讨 论 约 束 条 件时 可 只 考 虑由 于 等不 等 式 约 束式 约 束
。
0
0
00
0
( ) 0 ( 1,,)
( ) - ( ) 0
j
PX
g X P j l
f X P f X
PX
由 可 行 下 降 方 向 的 定 义,某 方 向 在 点 若 满 足则 是 的 可 行 下 降 方 向 。
0 0 0
0 0 0
0
( ) ( ) ( ) ( 1,,)
( ) ( ) ( )
T
j j j
T
g X P g X g X P j l
f X P f X f X P
X P D
由泰勒公式其中 是足够小的正数（保证 ）
0
0
( ) 0
( ) 0
T
j
T
g X P
P
f X P
P
不 难 看 出,只 要 便 保 证 是 可 行 下 降 的 。
这 可 作 为 可 行 下 降 的 充 分 条 件 。
00
0
00
( ) ( )
( ) - ( )
j
j
P g X P f X
XP
g X f X
几何意义是,与 夹锐角，同时 与- 也夹锐角。
由此可知，如果在 不存在可行下降方向，则一定不存在同时与 和 夹锐角。
2.最优性条件 （ K-T条件）
0
*
N L P ( ) ( )
N L P
jf X g X
X
考 虑 只 含 有 不 等 式 约 束 的 （ ） 。 设 与 均 为连 续 可 微 函 数,是 （ ） 的 最 有 解 。
**
0
D
( ) 0
XX
fX?
如 果 是 的 内 点,即 约 束 对 是 不 起 作 用 的,则 由 无 约 束极 值 问 题 的 极 值 必 要 条 件,有 ＝ 。
*
1
**
11
*
*
( ) 0
( ) 0 ( )
( ) P
P
X g X
g X X g X
fX
X
如 果 是 某 一 个 约 束 的 边 界 点,
即 对 起 作 用,则 必 有与 - 反 向,否 则 必 有 与 二 者 同 夹锐 角,即 是 的 可 行 下 降 方 向,矛 盾 。
1()gX
*1 ()gX?
*()fX?-
*X
* * * *11( ) ( ) ( ) ( )g X f X f X g X11故 与 同 向,即 存 在 0,使 ＝ 。
*
12
**
12
**
12
* * *
12
( ) 0 ( ) 0
( ) 0 ( ) 0 ( )
( ) ( ) P
( ) ( ) ( )
P
X g X g X
g X g X X f X
g X g X
f X g X g X
如果 位于某两个约束 和 的交点，
即 和 均对 起作用，则必有位于 和 的夹角内部，否则也会有 与
－,和 同夹锐角，即存在可行下降方向,矛盾。
*X
1()gX
2()gX
*()fX?
*1()gX? *
2 ()gX?
12
* * *
1 1 2 2
12
( ) ( ) ( )
,0
f X g X g X
故有 和 使下式成立：
＝＋
*
**
( ) 0
( ) ( )
0
j
jj
jJ
j
X g X j J
f X g X
jJ
依此类推，若 点起作用约束为,,
则有 ＝
，
*
*
( ) 0jjgX
X
其 中 条 件 是 为 了 在 梯 度 组 合 式 中 去 掉 不 起作 用 约 束,称 为 松 紧 条 件 。 这 时 要 求 点 各 起 作 用 约 束 的梯 度 线 性 无 关 。
**
1
*
( ) ( )
( ) 0 ( 1,,)
0 ( 1,,)
l
jj
j
jj
j
f X g X
g X j l
jl
＝
或 表 示 为
＝
定理 (K-T条件 )
**
**
* * * * * *
11
* * * * *
11
*
( ) ( 1,,) ( )
[ ] [ ]
( ) ( ) ( )
( ) 0 1,,
0 1,,
ij
ml
ml
i i j j
ij
jj
j
X N L P X
h X i m g X j J
f X h X g X
g X j l
jl
＝ ＝
设 是 （ ） 的 最 有 解,且 在 点 各 起 作 用 约 束 的 梯 度和,线 性 无 关,则 存 在 向量 和 使 下 式 成 立,
＝ ＋
（ ）
,（ ）
* * * *
11 mlK-T 条 件 中 的,,和,,称 为 广 义 拉 格 朗 日 乘 子 或
K-T 乘 子 。 满 足 K-T 条 件 表 达 式 的 可 行 点 称 为 K-T 点 。 可 以 证 明
K-T 条 件 对 凸 规 划 是 充 要 的 。
例 10：利用 K－ T条件求解下面的非线性规划
2m i n ( ) ( 3 )
.,0 5
f X x
s t x
2
1
2
m i n ( ) ( 3 )
,,( ) 0
( ) 5 0
f X x
s t g X x
g X x
解 原问题可写为
12
12
" ( ) 2 0," ( ) " ( ) 0
( ) ( ) ( )
f X g X g X
f X g X g X
因 为故 解 为 凸 函 数,和 均 为 凹 函 数,
此 问 题 为 凸 规 划 。
为解此方程组，可分几种情况考虑：
12
12
1
2
12
( ) 2 3 ( ) 1,( ) 1
2 3 0
0
( 5 ) 0
,0
f X x g X g X
KT
x
x
x
＝ （ ）,
条 件 表 达 式 为
（ ） － ＋ ＝
**3 ( ) 0x f x由 于 此 问 题 为 凸 规 划,故 是 最 有 解,相 应 最 优 值 。
12 00 且,无 解 ；
①
12 0 3,x K T＝,解 得 满 足 约 束,是 － 点 ；
④
1 2 20 0 5,4,x K T且,解 得 － 不 是 － 点 ；
③
1 2 10 0 0,6,x K T且 ＝,解 得 － 不 是 － 点 ；
②
例 11:考虑非线性规划并验证它为凸规划，用 K－ T条件求解
12
12
12
m a x ( ) l n( 1 )
23
,,
,0
f X x x
xx
st
xx
12
1 1 2
21
22
m i n ( ) l n( 1 )
,,( ) 3 2 0
( ) 0
( ) 0
f X x x
s t g X x x
g X x
g X x
解 原 问 题 可 写 为计算目标和约束函数的海赛阵
12
1
3
1
( ) 1 ( ) [ 2 1 ],( ) [ 1 0],
( 1 )
( ) [ 0 1 ]
-
T
TT
T
f X g X g X
x
gX
KT
，
表达式为：
1 2 3
2
1
1
0 0 0
( 1 )( ) 0,( ) ( ) ( ) 0
0 0
0 0
f g g g
xH X H X H X H X
故此问题是凸规划。
1 1 1 2
13
0 0 3 2 0
00
xx
x
＝,则 无 解,于 是,有 ＝
令 ＝,＝
若
,则 有
12
1
2
0
1
30x
1 － 2 ＋ ＝
－ ＝ 0
（ ）
1 2 1 2 0xx T＝0,＝3,＝ ＝,显然[0 3 ] 是可行点，从而解得 是极小点。
12
1
12
1 1 2
21
32
1 2 3
1
2
( 1 )
1
3 2 0
0
0
,,0
x
xx
x
x
＝ - ＋
＝ - ＋
（ ）
3.二次规划
★一般模型
m i n ( )
1
2
0
,,
0
,
TT
fX X H X C X
A X b
st
X
A m n b m C n
其中 为 阶矩阵； 为 维非负向量； 为 维向量。
0 K - TH?
由 于 二 次 规 划 的 约 束 是 线 性 的,从 而 是 凸 集,故 当 目 标 的 二 次 项系 数 矩 阵 （ 半 正 定 ） 时 为 凸 规 划,可 用 条 件 求 解 。
11
22
( )
( ) 0
( ) 0
f X H X C
g X A g AX b m
g X I g X n
则 梯 度,
与 约 束 （ 个 ） 相 对 应,
与 约 束 （ 个 ） 相 对 应 。
m in ( )
1
2
0
,,
0
TT
fX X H X C X
A X b
st
X
1 1 1
2 2 1
( ) -
( ) -,-
T
m
T
m m n
g
g
X K T Y y y
X K T Y y y K T
记 相 应 于 的 乘 子 为 ＝,相 应 于的 乘 子 为 ＝ 则 由 条 件及 约 束 条 件,有,
12
1
2
12
0
0
0
,,0
T
T
T
TT
H X C A Y IY
Y A X b
YX
A X b
X Y Y
＝
（ ）＝
＝
上 面 的 一 组 式 子 中,若 不 考 虑 两 个 松 紧 条 件,则 其 余 均 为 线 性表 达 式,即,
12
12
0
,,0
T
TT
H X A CY I Y
A X b
X Y Y
＝
思考,能否在此基础上构想基于线性规划求解的方法?
1
0
T
nZ zz如 果 在 上 面 第 一 式 中 增 加 人 工 变 量 ＝ （ 为 使 出 现单 位 阵 ）,并 增 加 使 人 工 变 量 之 和 极 小 化 的 目 标 函 数
（ 为 使 人 工 变 量 最 后 均 为 ）,则 可 构 造 一 个 线 性 规 划,
1
12
12
m in
sg n ( )
,,
,,,,0
sg n ( )
n
T
s
TT
s
s
H X A C
z z z
Y I Y C Z
s t A X X b
X Y Y Z X
C Z Z C
X
＝
其 中 表 示 中 各 分 量 的 符 号 与 中 相 应 分 量 的符 号 相 同,是 为 了 保 证 出 现 单 位 阵 ； 是 松 弛 变 量 。
用 单 纯 形 法 求 解 该 规 划 的 单 纯 形 初 表 为 下 表 。
BX
1Bb? X
sX 1Y 2Y
Z
Z C H? 0 TA I sgn( )CI
sX b
A? I 0 0 0
12
1
2
12
,,
0
0
T
s
T
s
X Y Y
YX
YX
Y X Y X
为使所求得的 还满足松紧条件
＝
＝
应在每次单纯形表的迭代中保证 与 以及 与的相应分量不同时为基变量。
例 12,求解二次规划
22
1 2 1 2
12
12
m in ( )
1
( 2 2 ) 8 1 0
2
6 3 2 0
,,
0,0
fX x x x x
xx
st
xx
1 1 2 2 3
2 0
,[ 3 2],[ 8 10 ],6
0 2
,[ ]
0,K - T
T
T
H A C b
Y y Y y y
H
显然有 故此问题是凸规划。可用 条件求解。
解
12
211
1
322
1
3
2
sgn ( )
2 0 3 8
0 2 2 10
[ 3 2] 6
T
s
H X A Y I Y C Z
yxz
yC
yxz
x
AX X x b
x
12
1 1 2 1
2 1 3 2
1 2 3
1 2 3 1 2 3 1 2
1 3 2 1 3 2
2
2
3
m in
38
2 1 0
,,
26
,,,,,,,0
0 0,0
x
x
x
z z z
y y z
y y z
st
xx
x x x y y y z z
y x y x y x
相应的线性规划为求解时还要满足松紧条件 ＝,＝,＝ 。
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
BC BX
1Bb
1x
1x
1x
1x
2x
2x
3x
3x
1y
1y
1y 2y 3y
1z
1z
1z
2z
2z
2z
2z
求得的结果是：
1 2 3 1 2 3
4 3 3 3 2,,0,,0,0
1 3 1 3 1 3x x x y y y
1
3 1 3 1
*
4 3 3
[ ]
1 3 1 3
T
y
x y x x
X?
在 每 一 次 单 纯 行 表 迭 代 中 都 考 虑 了 松 紧 条 件,如 在 第 一 张表 中,按 通 常 规 则 应 让 进 基,但 考 虑 到 与 它 构 成 松 紧 式的 已 在 基 中,并 且 进 基 也 不 会 使 出 基,故 选 择 进 基,
从 而 所 得 解 满 足 松 紧 条 件,是 原 来 二 次 规 划的 最 优 解 。
4.罚函数基本思想：将约束与目标组合在一起，化为无约束极值问题求解。
★
内点法：从可行域的内部逐步逼近最优解。★
外点法：从可行域的外部逐步逼近最优解。★
外点法的关键是基于（ NLP） 构造一个新的目标函数
P（ X,M）,称为罚函数。
22
11
(,) ( ) [ m in( 0,( ) ) ] ( )
lm
ji
ji
P X M f X M g X M h X
M
M
式 中 是 一 个 充 分 大 的 正 数,称 做 罚 因 子 。
含 的 项 称 为 罚 项 。
当 X是可行点时，罚项为 0
当 X不是可行点时，罚项是很大的整数。
对 P（ X,M） 求极小，可采用无约束优化方法，罚项能保证 X逐步趋近可行域。
一般步骤：
0,,1,0Mk1选 取 初 始 罚 因 子 令 ；①
m in (,),k k kM P X M X对于,求解无约束极值问题 得 ；②
1
| ( ) | ( 1,,)
( ) ( 1,,)
N L P,
1,2
k
ik
ik
k k k
X
h X i m
g X j l
X M M
kk
＋
若 满 足 可 行 性 的 精 度 要 求则 停 止,即 为 （ ） 的 近 似 最 优 解,否 则,取置 ＝ 转 。
③
,P X M
M
用 罚 函 数 法 求 解 一 些 简 单 的 非 线 性 规 划 时,可 先 求 出 （ ）
的 驻 点,然 后 令 。
例 13：求解非线性规划
3
12
1
2
m in ( )
1
( 1 )
3
10
,,
0
fX xx
x
st
x
3 2 2
1 2 1 2
1(,) ( 1 ) [ m i n (0,1 ) ] [ m i n (0,) ]
3P X M x x M x M x
解 构造罚函数
2
11
1
2
2
( 1 ) 2 [ m in( 0,1 ) ] 0
1 2 [ m in( 0,) ] 0
P
x M x
x
P
Mx
x
令
1 1 21 0 1,0 1 0x x x当,不可行；当,由第二式有＝,矛盾，
说明可行域内无驻点。
12
2
1
2
1 0,0,
41
1
2
xx
x M M M
x
M
对于可行域外的点（满足 ）可解得驻点
＝
1
2( 1 ) 2 0
0
02
xM
H
M
在该点，海赛阵说明该驻点是极小点。
T1
2
1M,
0
x
x
令 则,而 1 0 满足约束，是最优解。
例 14：求解非线性规划
2 2 21 2 1 2 1(,) [ m in( 0,) ] [ m in( 0,) ]P X M x x M x x M x
解 构造罚函数
2
1 2 1 1
1
2
12
2
1 2 [ m in( 0,) ] ( 2 ) 2 [ m in( 0,) ] 0
1 2 [ m in( 0,) ] 0
P
M x x x M x
x
P
M x x
x
考察其驻点，令
12
2
12
1
mi n ( )
0
,,
0
fX xx
xx
st
x
12
2
1 2 1 1
2
12
1 0,0,
1 2 ( ) ( 2 ) 2 0
1 2 ( ) 0
xx
M x x x M x
M x x
对于可行域外的点（满足 ）可解得驻点
T1
2
0,
0
xM
x
令 则,而 0 0 是 可 行 点,故 是 最 优 解 。
1
2 2
1
2( 1 )
11
4( 1 ) 2
x
M
x
MM
＝
解得
