一、惩罚函数法（ SUMT）
约束极值问题的算法
mixgts
xf
i,
问题：
?,10)(..
)(min.1
??
可行点集或可行解集,}0)(|{
..
)(m in
??
?
?
xgxD
Dxts
xf Tm xgxgxgxgts
xf
），，（这里 )()()(0)(..
)(min
1 ???
?
将有约束优化问题转化为一系列无约束优化问题进
行求解。 （ Sequential Unconstrained Minimization
Technique - SUMT）
2、算法思想：
3、算法类型：
? 外点法（外惩法）
? 内点法（内惩法）
4、外点法（外部惩罚函数法）
)x(1?
)x(2?
)x(f
)x(k?
?
?
D *xx
（ 1）几何解释
)x(m i n)x(m i n)x(m i n)x(fm i n kRxRxRxDx nnn ??????? ???? ?21
)( xk?如何构造
）（且
满足：
????
??
kxDxxfx
Dxxfxx
kk
kk
)()()(
)()()(
??
??
则可取：
。）（
）（
满足其中
Dxxp
Dxxp
xp
xpxfx
kk
??
??
??
0)(2;0)(1
)(
,)()()( ??
（ 2）算法分析
? ? ? ? ? ? ?k ? ? ?? 2 1
，事实上，造这样一来，我们只需构 )( xp
0)( ?xg j因为
??
??
??
m
j
j
m
j
j xgxgxp
1
22
1
}0),({m i n)}0),(( m i n {)(
所以可设
）。）和（满足恰前面的条件（显然 21)( xp
也连续。连续，那么）（如果：结论 )(,,2,1)(1 xpmjxg j ??
2
)()()()()}(),({m in 2121
21
xfxfxfxfxfxf ????
事实上，只须注意：
0}0),({min0}0),(min { 2 ???? xgxg jj
的最优解。）：也是问题（）则
。）（，即
有最优解）问题（如果：结论
)(m in(
,,2,10))(()(( 2 );)()(m in,( 1 )2
*
**
*
xfAx
mjxgDx
xxB
Dxk
kjk
kkRx n
?
?
???
?
??
??
?
。所以
。的最优解）是（因为：证明
n
kkk
kRxk
Rxxx
xBx
n
???
?
,)())((
)(m in:)(
*
*
???
??
。所以
）（即又
0))((
,,,2,10))((,)(
*
**
?
???
k
kjk
xp
mjxgDx
?
?? ?
))(())(())((,*** kkkk xpxfxfDx ???? ???? 有所以
))(( * kk x ???
)(xk??
的最优解。是问题所以 )(m a x)(* xfx Dxk ??
)()( xpxf k???
)(xf?
（ 3）算法步骤（外点法）：
。精度
），（可取，初始惩罚因子给定初始点
0:,0
10.1 110
??
??
k
xs t e p
?
??
.)(
)0),((m i n)()()()(m i n
.2
1*
1
2
?
??
?????
k
k
m
j
jkkk
Rx
k
xx
xgxfxpxfx
xs t e p
n
，记为得到极小点为
优化问题为初始点，求解无约束以
?
???
.4;)(m in(
,,,2,1))((,)(3
*
**
s tep
s to pxfAx
mjxgDxs tep
Dxk
kjk
否则转
的最优解，）：就是问题（）则
）（即如果：
?
???
?
??? ?
.2,1:,
14 11
s t e pkk
s t e p kkkk
转因子的放大系数）
为惩罚这里（可取给定：
??
??? ?? ??????
)x(p)x(f)x(m i n
st e p
kk
Rx n
????
?
算法求解可用无约束优化问题的中，在 2( a )
矩阵的条件数越坏）。的
越大，求解困难（无约束优化问题
造成不宜取的过大。否则会一开始在算法中，
H e sse)x(
)x(m i n
k
kk
Rx
k
n
?
??
?
?
( c )
.)(,,2,1
))(()(( b ) **
??
???
??
??
xpmj
xgDx
k
kjk
）或（
用在实际计算中，判断
?
（ 4）应注意的问题
02..
)1()(m i n
( 6 )
2
??
??
xts
xxf
优化问题惩罚函数法）求解如下例：试用外点法（外部
惩罚项：惩罚因子：
惩罚函数：：增广函数
通常称：
)(,
)(,)(
)(
xp
xpx
d
kk
k
??
?
??
?
????
???
2)2(1
2)1(
22
2
xifxx
xifx
k?）（
}0,2{m in1)(
)(
22 ???? xxx
x
kk
k
??
?
）（
如下：构造增广函数解：
??
?
????
???
2)2(212
212)(
xifxx
xifx
dx
xd
k
k
?
?
）（
）（
的最优解。，问题这就是对于固定的
所以
)(m in
1
21
)(*
x
Dxx
kRxk
k
k
k
k
n
??
?
?
?
?
?
?
?
??
解。就是所求原问题的最优
，
*
** 2
1
21lim)(limlim
x
xxx
k
k
kkk
k
k
??
?
???
?????? ?
??
0)2(212
0)(
????
?
xx
dx
xd
k
k
?
?
）（
可得：由
1 2
00 ??
11 ??
102 ??
x
k?
*x
O
)(xf
?
?
?
?
?
?
0
0
)x(h
)x(g
.t.s
)x(fm in
?
?
?
??
??
p,j)x(h
m,i)x(g
.t.s
)x(fm i n
j
i
，
，
?
?
10
10?
?
（ 7）一般模型的外点法
????
????
??
??
l
k
m
j
j
l
k
k
m
j
j
)x(h}),x(g{m i n
))x(h()}),x(g( m i n {)x(p
k
1
2
1
2
2
1
2
1
0
0
的惩罚函数我们不难想到构造如下
?
? 算法步骤相同
算法收敛性：( 8 )
）（）（
）（）（
）（）（
有是由外点法产生的，则若点列结论
kk
kk
k
k
k
k
k
xfxf
xpxp
xx
x
?
?
?
?
?
?
?
1
1
1
1
}{1.
??
求问题的极小点。的任何极限点一定是所列
点法产生的点上的连续函数，则由外都是
）（和）（、设结论
}{
),,1(),,1()(2.
k
n
kj
x
R
lkxhmjxgxf ?? ??
5、内点法（障碍函数法）
内点集边界点集 ????? DintDD
D?
Dint
（ 1）集合结构;}0)(,|{ ??? xgjxD j使得至少存在一个
。},0)(|{in t jxgxD j ???
（ 2）算法思想
内点法（障碍函数法）的迭代点是在可行域
点集内部移动的，对接近可行域边界上的点施加
越来越大的惩罚，对可行域边界上的点施加无限
大的惩罚，这好比边界是一道障碍物，阻碍迭代
点穿越边界。
内点法要求可行点集的内点集合非空，否则
算法无法运行。这样一来内点法只对不等式约束
的优化问题才可能有效。
Dxifxq
Dxifxq
xq
xqxf( x )
kk
?????
??
??
)(2
in t0)(1
:)(
,)()(
）（
）（
满足其中
构造函数 ??
mixgts
xf
i,
考虑如下优化问题：
?,1,0)(..
)(m in
??
0 2 1? ? ? ?k ? ? ??
算法分析)3(
)()()(min
:
xqxfx kk
Rx n
?? ??
?
转化为无约束优化问题
。等或
等或例如：
??
??
??
??
???
??
m
j
j
m
j
j
m
j
m
j
j
xgxq
xg
xq
xg
xq
xg
xq
j
11
1
2
1
)(ln)(
)(
1
ln)(;
)(
1
)(
)(
1
)(
。惩罚项：惩罚因子：
障碍函数：：增广函数
通常称：
)(,
,)(,)(
xq
xqx
kk
k
??
?
。转因子的缩小系数）
为惩罚这里（可取给定
2,1:,
1.4 11
s te pkk
s te p kkkk
??
??? ?? ??????
。否则转的最优解，）：（
就是问题则如果
4;)(m in
,)(.3 11
s teps to pxfA
xxqs tep
Dx
kk
k
?
?? ? ??
（ 3）算法步骤（内点法）：
。精度）（可取
，初始惩罚因子给定初始点
0:,0,1
,0in t.1
1
1
0
???
??
k
Dxs tep
??
?
。，记为得到其最优解
优化问题为初始点，求解无约束以
1*
1
)(
)(
1
)()()()(m i n
.2
?
??
?????
k
k
m
j
j
kkk
Rx
k
xx
xg
xfxqxfx
xs tep
n
?
???
01..
3
1
)(m i n
( 4 )
3
??
?
xts
xxf
下优化问题部惩罚函数法）求解如例子：试用内点法（内
1
1)(
)(
3
?
??
x
xx
x
kk
k
??
? 如下：构造增广函数解：
kxx ???? )1(
可得：由 0)1()( 22 ???? xxdx xd kk ??
。所以因为 kxxx ???? )1(1
)411(
2
1
)411(
2
1
1
k
k
k
x
x
?
?
???
???
?
所以因为负根不满足条件，
因此
1?
2?
3?
x
?
1x2x3x
*x
1)411(
2
1limlim 1* ?????
??
?
?? kk
k
k
xx ?
由此可以得到：
331 x)x(f ?
o 1
?
算法收敛性：( 5 )
。）（）（
有是由内点法产生的，则若点列结论
k
k
k
k
k
xx
x
?? ??? 11
}{1.
求问题的极小点。的任何极限点一定是所
产生的点列连续函数，则由内点法
上的都是）（、设结论
}{
),,1()(2.
k
n
j
x
Rmjxgxf ??
练 习：
1,复习外点法和内点法，掌握外点法
的算法思想和其特点。
2、要求能用外点法去解决实际问题。
3、对于一个简单的实例，能够用外点法
进行手工计算。
约束极值问题的算法
mixgts
xf
i,
问题：
?,10)(..
)(min.1
??
可行点集或可行解集,}0)(|{
..
)(m in
??
?
?
xgxD
Dxts
xf Tm xgxgxgxgts
xf
），，（这里 )()()(0)(..
)(min
1 ???
?
将有约束优化问题转化为一系列无约束优化问题进
行求解。 （ Sequential Unconstrained Minimization
Technique - SUMT）
2、算法思想：
3、算法类型：
? 外点法（外惩法）
? 内点法（内惩法）
4、外点法（外部惩罚函数法）
)x(1?
)x(2?
)x(f
)x(k?
?
?
D *xx
（ 1）几何解释
)x(m i n)x(m i n)x(m i n)x(fm i n kRxRxRxDx nnn ??????? ???? ?21
)( xk?如何构造
）（且
满足：
????
??
kxDxxfx
Dxxfxx
kk
kk
)()()(
)()()(
??
??
则可取：
。）（
）（
满足其中
Dxxp
Dxxp
xp
xpxfx
kk
??
??
??
0)(2;0)(1
)(
,)()()( ??
（ 2）算法分析
? ? ? ? ? ? ?k ? ? ?? 2 1
，事实上，造这样一来，我们只需构 )( xp
0)( ?xg j因为
??
??
??
m
j
j
m
j
j xgxgxp
1
22
1
}0),({m i n)}0),(( m i n {)(
所以可设
）。）和（满足恰前面的条件（显然 21)( xp
也连续。连续，那么）（如果：结论 )(,,2,1)(1 xpmjxg j ??
2
)()()()()}(),({m in 2121
21
xfxfxfxfxfxf ????
事实上，只须注意：
0}0),({min0}0),(min { 2 ???? xgxg jj
的最优解。）：也是问题（）则
。）（，即
有最优解）问题（如果：结论
)(m in(
,,2,10))(()(( 2 );)()(m in,( 1 )2
*
**
*
xfAx
mjxgDx
xxB
Dxk
kjk
kkRx n
?
?
???
?
??
??
?
。所以
。的最优解）是（因为：证明
n
kkk
kRxk
Rxxx
xBx
n
???
?
,)())((
)(m in:)(
*
*
???
??
。所以
）（即又
0))((
,,,2,10))((,)(
*
**
?
???
k
kjk
xp
mjxgDx
?
?? ?
))(())(())((,*** kkkk xpxfxfDx ???? ???? 有所以
))(( * kk x ???
)(xk??
的最优解。是问题所以 )(m a x)(* xfx Dxk ??
)()( xpxf k???
)(xf?
（ 3）算法步骤（外点法）：
。精度
），（可取，初始惩罚因子给定初始点
0:,0
10.1 110
??
??
k
xs t e p
?
??
.)(
)0),((m i n)()()()(m i n
.2
1*
1
2
?
??
?????
k
k
m
j
jkkk
Rx
k
xx
xgxfxpxfx
xs t e p
n
，记为得到极小点为
优化问题为初始点，求解无约束以
?
???
.4;)(m in(
,,,2,1))((,)(3
*
**
s tep
s to pxfAx
mjxgDxs tep
Dxk
kjk
否则转
的最优解，）：就是问题（）则
）（即如果：
?
???
?
??? ?
.2,1:,
14 11
s t e pkk
s t e p kkkk
转因子的放大系数）
为惩罚这里（可取给定：
??
??? ?? ??????
)x(p)x(f)x(m i n
st e p
kk
Rx n
????
?
算法求解可用无约束优化问题的中，在 2( a )
矩阵的条件数越坏）。的
越大，求解困难（无约束优化问题
造成不宜取的过大。否则会一开始在算法中，
H e sse)x(
)x(m i n
k
kk
Rx
k
n
?
??
?
?
( c )
.)(,,2,1
))(()(( b ) **
??
???
??
??
xpmj
xgDx
k
kjk
）或（
用在实际计算中，判断
?
（ 4）应注意的问题
02..
)1()(m i n
( 6 )
2
??
??
xts
xxf
优化问题惩罚函数法）求解如下例：试用外点法（外部
惩罚项：惩罚因子：
惩罚函数：：增广函数
通常称：
)(,
)(,)(
)(
xp
xpx
d
kk
k
??
?
??
?
????
???
2)2(1
2)1(
22
2
xifxx
xifx
k?）（
}0,2{m in1)(
)(
22 ???? xxx
x
kk
k
??
?
）（
如下：构造增广函数解：
??
?
????
???
2)2(212
212)(
xifxx
xifx
dx
xd
k
k
?
?
）（
）（
的最优解。，问题这就是对于固定的
所以
)(m in
1
21
)(*
x
Dxx
kRxk
k
k
k
k
n
??
?
?
?
?
?
?
?
??
解。就是所求原问题的最优
，
*
** 2
1
21lim)(limlim
x
xxx
k
k
kkk
k
k
??
?
???
?????? ?
??
0)2(212
0)(
????
?
xx
dx
xd
k
k
?
?
）（
可得：由
1 2
00 ??
11 ??
102 ??
x
k?
*x
O
)(xf
?
?
?
?
?
?
0
0
)x(h
)x(g
.t.s
)x(fm in
?
?
?
??
??
p,j)x(h
m,i)x(g
.t.s
)x(fm i n
j
i
，
，
?
?
10
10?
?
（ 7）一般模型的外点法
????
????
??
??
l
k
m
j
j
l
k
k
m
j
j
)x(h}),x(g{m i n
))x(h()}),x(g( m i n {)x(p
k
1
2
1
2
2
1
2
1
0
0
的惩罚函数我们不难想到构造如下
?
? 算法步骤相同
算法收敛性：( 8 )
）（）（
）（）（
）（）（
有是由外点法产生的，则若点列结论
kk
kk
k
k
k
k
k
xfxf
xpxp
xx
x
?
?
?
?
?
?
?
1
1
1
1
}{1.
??
求问题的极小点。的任何极限点一定是所列
点法产生的点上的连续函数，则由外都是
）（和）（、设结论
}{
),,1(),,1()(2.
k
n
kj
x
R
lkxhmjxgxf ?? ??
5、内点法（障碍函数法）
内点集边界点集 ????? DintDD
D?
Dint
（ 1）集合结构;}0)(,|{ ??? xgjxD j使得至少存在一个
。},0)(|{in t jxgxD j ???
（ 2）算法思想
内点法（障碍函数法）的迭代点是在可行域
点集内部移动的，对接近可行域边界上的点施加
越来越大的惩罚，对可行域边界上的点施加无限
大的惩罚，这好比边界是一道障碍物，阻碍迭代
点穿越边界。
内点法要求可行点集的内点集合非空，否则
算法无法运行。这样一来内点法只对不等式约束
的优化问题才可能有效。
Dxifxq
Dxifxq
xq
xqxf( x )
kk
?????
??
??
)(2
in t0)(1
:)(
,)()(
）（
）（
满足其中
构造函数 ??
mixgts
xf
i,
考虑如下优化问题：
?,1,0)(..
)(m in
??
0 2 1? ? ? ?k ? ? ??
算法分析)3(
)()()(min
:
xqxfx kk
Rx n
?? ??
?
转化为无约束优化问题
。等或
等或例如：
??
??
??
??
???
??
m
j
j
m
j
j
m
j
m
j
j
xgxq
xg
xq
xg
xq
xg
xq
j
11
1
2
1
)(ln)(
)(
1
ln)(;
)(
1
)(
)(
1
)(
。惩罚项：惩罚因子：
障碍函数：：增广函数
通常称：
)(,
,)(,)(
xq
xqx
kk
k
??
?
。转因子的缩小系数）
为惩罚这里（可取给定
2,1:,
1.4 11
s te pkk
s te p kkkk
??
??? ?? ??????
。否则转的最优解，）：（
就是问题则如果
4;)(m in
,)(.3 11
s teps to pxfA
xxqs tep
Dx
kk
k
?
?? ? ??
（ 3）算法步骤（内点法）：
。精度）（可取
，初始惩罚因子给定初始点
0:,0,1
,0in t.1
1
1
0
???
??
k
Dxs tep
??
?
。，记为得到其最优解
优化问题为初始点，求解无约束以
1*
1
)(
)(
1
)()()()(m i n
.2
?
??
?????
k
k
m
j
j
kkk
Rx
k
xx
xg
xfxqxfx
xs tep
n
?
???
01..
3
1
)(m i n
( 4 )
3
??
?
xts
xxf
下优化问题部惩罚函数法）求解如例子：试用内点法（内
1
1)(
)(
3
?
??
x
xx
x
kk
k
??
? 如下：构造增广函数解：
kxx ???? )1(
可得：由 0)1()( 22 ???? xxdx xd kk ??
。所以因为 kxxx ???? )1(1
)411(
2
1
)411(
2
1
1
k
k
k
x
x
?
?
???
???
?
所以因为负根不满足条件，
因此
1?
2?
3?
x
?
1x2x3x
*x
1)411(
2
1limlim 1* ?????
??
?
?? kk
k
k
xx ?
由此可以得到：
331 x)x(f ?
o 1
?
算法收敛性：( 5 )
。）（）（
有是由内点法产生的，则若点列结论
k
k
k
k
k
xx
x
?? ??? 11
}{1.
求问题的极小点。的任何极限点一定是所
产生的点列连续函数，则由内点法
上的都是）（、设结论
}{
),,1()(2.
k
n
j
x
Rmjxgxf ??
练 习：
1,复习外点法和内点法，掌握外点法
的算法思想和其特点。
2、要求能用外点法去解决实际问题。
3、对于一个简单的实例，能够用外点法
进行手工计算。
