第四节非线性规划模型的解
二次插值法
最速下降法
罚函数法非线性规划模型的一般形式：
一、无约束模型,}|)(m in { nRXXf?
二、有约束模型：
)(min Xf
miXgts i,,2,1,0)(,
pjXh j,,2,1,0)(
)()( XfXf
),( XNSX若
,SX?若则 称为 局部最优解，?X 或 局部解 ；
则 称为 整体最优解，?X 或 最优解 或 解一、无约束模型的解
}|)(m in { nRXXf?
沿某直线方向求目标函数的极小值点，称为 一维搜索 。
高维问题 可通过一系列的一维搜索，求出其 近似最优解 。
}|)(min{ Rxxf?一维搜索沿某些方向作一维搜索
)(min Xf
miXgts i,,2,1,0)(,
pjXh j,,2,1,0)(
化为无约束问题讨论顺序：
1,一维搜索 （二次插值法）
],[),( baxxf?单峰函数满足设,321 xxx
)()()( 321 xfxfxf
或 )()()( 321 xfxfxf 1x 2x 3x
)(xf)(xg
x
过三点作抛物线,2210)( xaxaaxg
有 )()( 12121101 xfxaxaaxg )()(
22222102 xfxaxaaxg
)()( 32323103 xfxaxaaxg
,ji xx
0
1
1
1
2
33
2
22
2
11
xx
xx
xx
故方程组有唯一解，且
02?a
即抛物线的开口向上。
令 02)( 21 xaaxg
得极小值点
2
1
2 a
ax
再从 中选出满足前面不等式的三点,xxxx,,,321
重复前面的过程，直到满足终止条件：
2131 ||,|)()(| xxxgxf
则 xx
注,迭代时，若出现 退化情形 2xx?
,2 21 xxx可取 继续迭代。
#
2,最速下降法
X?
f (X)
D= －?f (X)
第 1步 求新点设 f(X) 可微，给定初始点 X1,?>0,
每次沿使 f 下降得最快的 负梯度方向 D=－?f (X)搜索，直到满足终止条件为止。
第 k次迭代令 )( kk XfD 使求 k?
)(m i n)( 0 kkkkk DXfDXf
注意,?k不是步长（因 Dk不是单位向量），
且非负（否则，不是下降得最快的方向）。
得新点 kkkk DXX 1
设已得 Xk
第 2步 验证终止条件
,,)( 11 kk XXXf 则若?
处的最大变化率。在是 11 )()( kk XXfXf
否则，将 Xk+1作为新的出发点，
作为新的迭代方向，进行下一次迭代。
)( 11 kk XfD
有结论,1 kk DD
因为
k
d
DXfd kk
)(?
kk DXf )( 1 kk DD 1
k
k
kk
kk D
DXd
DXfd
)(
)(
0
可见，搜索路线呈 之字形 。
该法的 优点 是：不论维数多高，每次迭代只沿一个方向搜索。
“较 圆,时，则收敛得 较快 ；
“较 扁,时，则收敛得 较慢 。当目标函数等值线
X
实际中,前面阶段可用最速下降法，
后面阶段用旋转方向法。
缺点 是：收敛速度“前快后慢”。
例 求解 2212221 222)(m in xxxxxXf
解 TxxxxXf )224,22()( 1221
,)0,0(3.0 1 TX?初始点，＝?
因,)2,0()( 1 TXf 2)( 1 Xf <?
所以令,)2,0()( 11 TXfD
TDX )2,0(11则有
)2,0()( 11 fDXf48 2
120110 }48{m in)(m in 的现求使 DXf
由,0416f 411＝得?
得新点,1112 DXX T)21,0(? TT )2,0(41)0,0(
第 1步第 2步因,)0,1()( 2 TXf 1)( 2 Xf <?
令 TXfD )0,1()( 22
沿 方向搜索，得2D 212
迭代：
经 5次迭代后得解点,)87,43(6 TX?
,)0,41()( 6 TXf 41)( 6 Xf
TX )
8
7,
4
3(故得近似最优解：
而本题的精确最优解是,T)1,1(
搜索过程见 P.32表 1.11。
例 1.24例 1.23
)6,5(? )1,1(?
罚函数法
)(min Xf
miXgts i,,2,1,0)(,
pjXh j,,2,1,0)(
利用约束函数，引入辅助函数
nRXXMXfMXF ),()(),(?
值迭代。加大时为所求，否则当的求使
M
SMX
MXMXF
nRX
)(
),()},({m i n
思路：
二、有约束模型的解构造非负函数：
,
0,
0,0)(
2
tt
ttu
0)(),(
0)(,0
)]([ 2
XgXg
Xg
Xgu
ii
i
i,))](,0[ min( 2Xg i? nRX?
0)(),(
0)(,0
)]([ 2
XhXh
Xh
Xhv
jj
j
j,)]([ 2Xh j? nRX?
作 罚函数：,)]([)]([)(
11
p
j
j
m
i
i XhvXguX? nRX?
时；当 SX,0
.,0 时当 SX
所有约束都满足至少有一个不满足
0,
0,0)(
2 tt
ttv
作辅助函数：
)()(),( XMXfMXF
m
i
i XgMXf
1
2) ) ](,0[ m i n ({)(,})]([
1
2?
p
j
j Xh nRX?
罚因子 (充分大）
原模型化为无约束模型：
}|),(m in { nRXMXF?
对给定的 M1,求得最优解 X1=X(M1)
当 时，SX?1 1XX )0(
当 时，SX?1
否则，加大罚因子,迭代,…12 MM?
若满足终止条件
)( 11 XM （ X1近似可行）;1XX则可以证明,对于
kMMM 210
XMXM Skk 外从时，解点列当 )}({
因此，该方法也称为 外点法 。
#
例 用罚函数法求解
21)(m i n xxXf
0)(
0)(.
12
2
2
11
xXg
xxXgts
解 构造辅助函数
})],0[ m in ()],0{ [m in (),( 21222121 xxxMxxMXF
2RX?
在图中阴影区域内（ S外的点），用微分法求 F的极小值点。
即
0)(
0)(
12
2
2
11
xXg
xxXg
S
令 02)(41
12
2
11
1
MxxxMxxF
}){(),( 21222121 xxxMxxMXF
0)(21 221
2
xxMxF
)1(
)2(
,2 12 212 Mxx）式解得：由（
,)1(2 11 1 Mx）式得：代入（
MMx 2
1
)1(4
1:
22从而得
＃
注,若不便用微分法求解，则可用无约束模型的搜索法对给定的 Mi（或任意的 M）求 X(Mi),用终止条件终止计算。
T
MMMMX
2
1
)1(4
1,
)1(2
1)(
2
)()0,0( MX T
的解：}|),(m in { 2RXMXF?
变化过程见 P.35
另外：还有混合罚函数法、内点法等。
＃
二次插值法
最速下降法
罚函数法非线性规划模型的一般形式：
一、无约束模型,}|)(m in { nRXXf?
二、有约束模型：
)(min Xf
miXgts i,,2,1,0)(,
pjXh j,,2,1,0)(
)()( XfXf
),( XNSX若
,SX?若则 称为 局部最优解，?X 或 局部解 ；
则 称为 整体最优解，?X 或 最优解 或 解一、无约束模型的解
}|)(m in { nRXXf?
沿某直线方向求目标函数的极小值点，称为 一维搜索 。
高维问题 可通过一系列的一维搜索，求出其 近似最优解 。
}|)(min{ Rxxf?一维搜索沿某些方向作一维搜索
)(min Xf
miXgts i,,2,1,0)(,
pjXh j,,2,1,0)(
化为无约束问题讨论顺序：
1,一维搜索 （二次插值法）
],[),( baxxf?单峰函数满足设,321 xxx
)()()( 321 xfxfxf
或 )()()( 321 xfxfxf 1x 2x 3x
)(xf)(xg
x
过三点作抛物线,2210)( xaxaaxg
有 )()( 12121101 xfxaxaaxg )()(
22222102 xfxaxaaxg
)()( 32323103 xfxaxaaxg
,ji xx
0
1
1
1
2
33
2
22
2
11
xx
xx
xx
故方程组有唯一解，且
02?a
即抛物线的开口向上。
令 02)( 21 xaaxg
得极小值点
2
1
2 a
ax
再从 中选出满足前面不等式的三点,xxxx,,,321
重复前面的过程，直到满足终止条件：
2131 ||,|)()(| xxxgxf
则 xx
注,迭代时，若出现 退化情形 2xx?
,2 21 xxx可取 继续迭代。
#
2,最速下降法
X?
f (X)
D= －?f (X)
第 1步 求新点设 f(X) 可微，给定初始点 X1,?>0,
每次沿使 f 下降得最快的 负梯度方向 D=－?f (X)搜索，直到满足终止条件为止。
第 k次迭代令 )( kk XfD 使求 k?
)(m i n)( 0 kkkkk DXfDXf
注意,?k不是步长（因 Dk不是单位向量），
且非负（否则，不是下降得最快的方向）。
得新点 kkkk DXX 1
设已得 Xk
第 2步 验证终止条件
,,)( 11 kk XXXf 则若?
处的最大变化率。在是 11 )()( kk XXfXf
否则，将 Xk+1作为新的出发点，
作为新的迭代方向，进行下一次迭代。
)( 11 kk XfD
有结论,1 kk DD
因为
k
d
DXfd kk
)(?
kk DXf )( 1 kk DD 1
k
k
kk
kk D
DXd
DXfd
)(
)(
0
可见，搜索路线呈 之字形 。
该法的 优点 是：不论维数多高，每次迭代只沿一个方向搜索。
“较 圆,时，则收敛得 较快 ；
“较 扁,时，则收敛得 较慢 。当目标函数等值线
X
实际中,前面阶段可用最速下降法，
后面阶段用旋转方向法。
缺点 是：收敛速度“前快后慢”。
例 求解 2212221 222)(m in xxxxxXf
解 TxxxxXf )224,22()( 1221
,)0,0(3.0 1 TX?初始点，＝?
因,)2,0()( 1 TXf 2)( 1 Xf <?
所以令,)2,0()( 11 TXfD
TDX )2,0(11则有
)2,0()( 11 fDXf48 2
120110 }48{m in)(m in 的现求使 DXf
由,0416f 411＝得?
得新点,1112 DXX T)21,0(? TT )2,0(41)0,0(
第 1步第 2步因,)0,1()( 2 TXf 1)( 2 Xf <?
令 TXfD )0,1()( 22
沿 方向搜索，得2D 212
迭代：
经 5次迭代后得解点,)87,43(6 TX?
,)0,41()( 6 TXf 41)( 6 Xf
TX )
8
7,
4
3(故得近似最优解：
而本题的精确最优解是,T)1,1(
搜索过程见 P.32表 1.11。
例 1.24例 1.23
)6,5(? )1,1(?
罚函数法
)(min Xf
miXgts i,,2,1,0)(,
pjXh j,,2,1,0)(
利用约束函数，引入辅助函数
nRXXMXfMXF ),()(),(?
值迭代。加大时为所求，否则当的求使
M
SMX
MXMXF
nRX
)(
),()},({m i n
思路：
二、有约束模型的解构造非负函数：
,
0,
0,0)(
2
tt
ttu
0)(),(
0)(,0
)]([ 2
XgXg
Xg
Xgu
ii
i
i,))](,0[ min( 2Xg i? nRX?
0)(),(
0)(,0
)]([ 2
XhXh
Xh
Xhv
jj
j
j,)]([ 2Xh j? nRX?
作 罚函数：,)]([)]([)(
11
p
j
j
m
i
i XhvXguX? nRX?
时；当 SX,0
.,0 时当 SX
所有约束都满足至少有一个不满足
0,
0,0)(
2 tt
ttv
作辅助函数：
)()(),( XMXfMXF
m
i
i XgMXf
1
2) ) ](,0[ m i n ({)(,})]([
1
2?
p
j
j Xh nRX?
罚因子 (充分大）
原模型化为无约束模型：
}|),(m in { nRXMXF?
对给定的 M1,求得最优解 X1=X(M1)
当 时，SX?1 1XX )0(
当 时，SX?1
否则，加大罚因子,迭代,…12 MM?
若满足终止条件
)( 11 XM （ X1近似可行）;1XX则可以证明,对于
kMMM 210
XMXM Skk 外从时，解点列当 )}({
因此，该方法也称为 外点法 。
#
例 用罚函数法求解
21)(m i n xxXf
0)(
0)(.
12
2
2
11
xXg
xxXgts
解 构造辅助函数
})],0[ m in ()],0{ [m in (),( 21222121 xxxMxxMXF
2RX?
在图中阴影区域内（ S外的点），用微分法求 F的极小值点。
即
0)(
0)(
12
2
2
11
xXg
xxXg
S
令 02)(41
12
2
11
1
MxxxMxxF
}){(),( 21222121 xxxMxxMXF
0)(21 221
2
xxMxF
)1(
)2(
,2 12 212 Mxx）式解得：由（
,)1(2 11 1 Mx）式得：代入（
MMx 2
1
)1(4
1:
22从而得
＃
注,若不便用微分法求解，则可用无约束模型的搜索法对给定的 Mi（或任意的 M）求 X(Mi),用终止条件终止计算。
T
MMMMX
2
1
)1(4
1,
)1(2
1)(
2
)()0,0( MX T
的解：}|),(m in { 2RXMXF?
变化过程见 P.35
另外：还有混合罚函数法、内点法等。
＃
