5.3.5 惩罚函数法
间接法: 约束优化问题
无约束优化问题
这种转化必须满足如下两个前提条件： ❖①不破坏原约束问题的约束条件; ❖②最优解必须归结到原约束问题的最优解上去。
参数型 惩罚函数法有两种类型 非参数型
约束优化问题
min F ( X ) X D Rn D : gu ( X ) 0, u 1, 2, ..., p
0
x2
1
r(k) x22
0
------ ① ------ ②
由式①得: x1 1 r(k)
由式②得: x2 r(k)
x1*
lim
r(k) 0
x1
lim
r(k) 0
1
r(k) 1
x2*
lim
r(k) 0
x2
lim
r(k) 0
r(k) 0
X*
1 0
,
F * 8 2.667 3
r(k)
10
无约束优化问题
min ( X , r(k), m(k) ) X D Rn
新目标函数 min ( X , r(k), m(k) ) 惩罚函数
p
q
F (X ) r(k) G gu(X ) m(k) (k) －罚因子，是大于零的一系列可调参数
惩罚项
1
0.1 0.01 0.001 0
X
* k
2.040 1.414 1.147 1.049 1.016
3.162
1
0.316 0.100
0.032
1 0
*k 25.305 9.105 5.094 3.272 2.857 2.667
(补充作业)内点法的解析计算法
❖ 例题:用对数形式的内点法求解:
r(k1) C r(k) , 0 C 1
lim
k
X
* k
X*
10
一、内点法
2. 内点罚函数法的形式及特点 （1）一般形式 （2）特点
①内点法只适用于解不等式约束优化问题。
②初始点X(0)必须在可行域内部选取。
③内点法的突出优点在于每个迭代点都是可行点，当迭代到达 一定阶段时，尽管尚没有到达最优点，但也可以被接受为一个 较好的近似解。
f(x)
x D R1
D : g1( x) x b 0
(x, r(0) ) ( x, r(1) )
r (0) 0.1 ( x, r(k) )
解：首先构造罚函数
( x, r (k) ) F ( x) r (k) 1 ax r (k) 1
g1( x)
xb
r(1) 0.01
o
b
x
x* xk* x1*
罚函数中，既包含了原目标函数F(X)，又包含了约束函数gu(X)和 hv(X)。问题 的关键是恰当地构造函数G[gu(X)]和H[hv(X)]。在对无约束优化问题的求解过程 中，通过不断地调整罚因子，就能使目标函数的最优解逐渐趋近于原约束优化
问题的最优解。
2
5.3.5 惩罚函数法
r(k), m(k) －罚因子，是大于零的一系列可调参数
r (0) , m(0)
r (1) , m(1)
r (2) , m(2)
......
r (k ) , m(k)
( X , r(0), m(0) )
X
* 0
( X , r(1), m(1) )
X1*
( X , r(2), m(2) )
X
* 2
...... ( X, r(k), m(k))
X
* k
X*
X*
③“内点”的含义
“围墙函数法”
o
“障碍函数法”
(x, r(0) ) ( x, r(1) )
r (0) 0.1 ( x, r(k) ) r(1) 0.01
b
x
x* xk* x1*
x0*
9
一、内点法
2. 内点罚函数法的形式及特点
（1）一般形式
min F ( X )
X D Rn
D : gu ( X ) 0, u 1, 2, ..., p
按照该数学模型解出的最优点X*，至少比原设计点X(k)多满足一个
约束条件。重复数次，直到所有的约束条件都得到满足，最终可
取得在可行域内部的初始点x(0)。
12
4. 关于几个参数的选择
(1) 初始罚因子r(0)的选取。
初始罚因子r(0)选择得是否恰当，将对解题的成败和速度产生相当大的影响。
如果r(0)值选得太大，效率低。则在一开始罚函数中的惩罚项的值将远远超出原目标函 数的值，因此，它的第一次无约束极小点将远离原问题的约束最优点。在以后的迭代 中，需要很长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。
3. 初始点X(0)的确定
(1) 自定法 (2) 搜索法
11
初始点x(0)的确定 (1) 自定法 : (2) 搜索法: 先任取一个设计点X(k)； 计算X(k)点的诸约束函数值gu(X(k))，u＝1，2，…，p
若： gu ( X (k) ) 0 u 1, 2,L , s
gu ( X (k) ) 0 u s 1, s 2,L , p
r(k)
x1
x2
2x1 4x2
0 x1 x2 1
r(k)
0
x1 x2 1
------ ① ------ ②
x1 2x2 代入②式得
r(k) 4x2 3x2 1 0
19
(补充作业)内点法的解析计算法
❖ 解(续)
4 x2
r(k) 3x2 1
0
12x22 4x2 r(k) 0
序列无约束极小化方法：SUMT法 （Sequential Unconstrained Minimization Technique）
内点罚函数法(内点法) 罚函数法 外点罚函数法(外点法)
混合罚函数法(混合法)
3
一、内点惩罚函数法
基本思想：将新目标函数定义于可行域内，序列迭代点在可 行域内逐步逼近原目标函数约束边界上的最优点。
hv ( X ) 0, v 1, 2, ..., q
无约束优化问题 min ( X , r(k), m(k) ) X D Rn
1
5.3.5 惩罚函数法
约束优化问题
min F ( X ) X D Rn D : gu ( X ) 0, u 1, 2, ..., p
hv ( X ) 0, v 1, 2, ..., q
根据经验，一般可取初始罚因子r(0)＝1~50。也有资料提出如下建议，按惩罚项的初始值 与目标函数的初始值F(X(0))相近的原则确定r(0)，即取:
F (X (0)) r(0)
p
G gu ( X (0) )
13
u1
4. 关于几个参数的选择
(1) 初始罚因子r(0)的选取。
(2) 递减系数C的选择。一般认为对算法的成败和速度影响不大。
若r(0)取得过小，导致计算的失败。则在一开始惩罚项的作用甚小，在可行域内部的惩 罚函数φ(X，r(0))与原目标函数F(X)很相近，只是在约束边界附近罚函数值才突然增高。 这样，使得其罚函数φ(X，r(k))在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。 一般来说，对于有深沟谷地性态差的函数，不仅搜索所需的时间长，而且很难使迭代 点进入最优点的邻域，以至极易使迭代点落入非可行域而导致计算的失败。即使是用 最稳定的无约束算法，迭代点仍有逸出可行域的危险。
r(k ) Cr (k1) , 0 C 1
lim r(k ) 0
k 4
内点惩罚函数法的思路: 当X由可行域内靠近任一约束边界时,惩罚项值趋于无穷大，所 以它就像围墙一样阻止迭代点越出约束边界。
x2
条件1：不破坏原约束问题的约束条件
5
x1 o
条件2：最优解必须归结到原约束问题的最优解上去
1. 引例
p
q
( X , r(k), m(k) ) F ( X ) r(k) G gu ( X ) m(k) H hv ( X )
u 1
v 1
❖ 设有一维不等式约束优化问题的数学模型
min F ( x) ax
f(x)
x D R1
D : g1( x) x b 0
x*=b, F*=ab
min ( X , r (k) ) X R2
F(X)
r(k)
1 g1( X )
1 g2(X )
1 3
x1
13
x2
r(k)
1 x1 1
1 x2
17
(补充)内点法的解析计算法
解:
(X ,r(k))
1 3
x1
13
x2
r
(
k
)
1 x1 1
1 x2
x1
x1
12
r(k)
x1 12
x0*
8
一、内点法
分析:
①r(k)>0,且迭代点∈D时,总有:
f(x)
(x, r(k)) F (x)
②r(k)是递减序列
r(0) r(1) ...... r(k) r(k) ...... 0
( x, r (0) ) ( x, r (1) )
x0*
x1*
(x, r(k)) xk*
r(k)→0时, (x, r(k) ) F (x)
min(X , r(k) ) min F(X ) r(k) 1/ gu (X )
随着r ( k )的减小, 惩罚作用趋于消失,
lim r(k)
k
1 0 gu (X )
lim( X , r(k) ) F ( X )
k
( X , r(k) )的最优解就逼近原问题的约束最优解