2009-7-27 1
第六章 约束优化方法二,随机方向法三,惩罚函数法四,增广乘子法一,概述一,概述
机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为
求解约束优化问题的方法称为约束优化方法。
根据求解方式的不同，可分为
– 直接解法
– 间接解法
( ) ( )12( ),,,0 1,2,,k k nh x h x x x j l= = =LL
( ) ( )12.,( ),,,0 1,2,,j j ns t g x g x x x j m=? LL
( ) ( )11m i n,,,nf x f x x x= L
2009-7-27 3
直接解法
通常适用于仅含不等式约束的问题
它的基本思路是
所谓可行搜索方向是指，当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。
产生可行搜索方向的方法将由直接解法中的各种算法决定。
1 1,2,k k kk
k
k
x x a d k
a
d
+ = + = L
— — 步 长
— — 可 行 搜 索 方 向
x1
x2
o
x0
x*
2009-7-27 4
直接解法的特点
由于整个求解过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得一个比初始点好的设计点
全局最优解、局部最优解
要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函数有定义
2009-7-27 5
间接解法
基本思路 是原约束优化问题转化成为一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解
1 2 1 2
11
(,,) ( ) [ ( ) ] [ ( ) ]
ml
jk
jk
x f x G g x H h xf m m m m
==
= + +邋
( ),( ),( )jkf x g x h x
12(,,)xf m m对 进 行 无 约 束 极 小 化 计 算通 过 改 变 加 权 因 子 的 大 小,不 断 调 整 设 计 点,使 其 逐 步 逼 近 约 束 最 优 解
2009-7-27 6
间接解法框图开始输入 n,x0,?1,?2
构造?(x,?1,?2 )
求 min?(x,?1,?2 )
满足收敛条件结束
x0=x*
改变?1,?2的值是否
2009-7-27 7
间接解法特点
(1)由于无约束优化方法的研究日趋成熟，已经研究出不少有效的无约束最优化方法和程序，使得间接解法有了可靠的基础。目前，这类算法的计算效率和数值计算的稳定性也都有较大的提高。
(2)可以有效地处理具有等式约束的约束优化问题。
(3)间接解法存在的主要问题是，选取加权因子较为困难。加权因子选取不当，不但影响收敛速度和计算精度，甚至会导致计算失败。
2009-7-27 8
求解约束优化设计问题的方法
直接解法
– 随机方向法,复合形法、可行方向法等
间接解法
– 惩罚函数法和增广乘子法 等
2009-7-27 9
二,随机方向法在可行域内，选择一个初始点 x0
利用随机数的概率特征，产生若干个随机方向从中选择一个能使目标函数值下降的最快的方向作为可行搜索方向，记作 d
初始点 x0出发，沿 d方向以一定的步长进行搜索，
得到新点 x，新点应满足约束条件且 f(x)<f(x0)
令 x0＝ x满足收敛条件结束是否
x1
x2
o
x0
x*
2009-7-27 10
随机方向法的特点
随机方向法的优点是对目标函数的性态无特殊要求，程序设计简单，使用方便。
由于可行搜索方向是从许多随机方向中选择的使目标函数值 下降的最快的方向，加之步长还可以灵活变动，所以此算法的收敛速度比较快。
它是求解小型机械优化问题的一种十分有效的算法。
2009-7-27 11
随机方向法
随机数的产生
初始点的选择
可行搜索方向的产生
搜索步长的确定
2009-7-27 12
随机数的产生
伪随机数
– 产生速度快，计算机内存占用少，有较好的概率统计特性
一种产生伪随机数的模型
– 首先令 r1=235,r2=236,r3=237，取 r=2657863（ r为小于 r1的正奇数）
然后按以下步骤计算
令 r=5r
若 r≥r3，则 r=r－ r3；
若 r≥r2，则 r=r－ r2；
若 r≥r1，则 r=r－ r1
则 q=r/r1 q 即为 (0,1)区间的伪随机数
– 任意区间 (a,b)内的伪随机数计算公式为
( )x a q b a= + -
2009-7-27 13
初始点的选择
可用随机选择的方法来产生，其计算步骤为
– (1)输入设计变量的下限值和上限值，即
– (2)在区间 (0,1)内产生 n个伪随机数 qi (i=1,2,…,n)
– (3)计算随机点 x的各分量
– (4)判别随机点 x是否可行，若随机点 x可行，则取初始点 x0=x；
若随机点不可行，则转步骤 (2)重新计算，直到产生的随机点是可行点为止。
( )1,2,,i i ia x b i n＃ = L
( ) ( )1,2,,i i i i ix a q b a i n= + - = L
2009-7-27 14
可行搜索方向的产生
(1)在 (-1,1)区间内产生伪随机数 rij(i=1,2,…,n; j=1,2,…,k; k≥n),
按下式计算随机单位向量 ej
(2)取一试验步长 a0，按下式计算 k个随机点
(3)检验 k个随机点是否为可行点，除去非可行点，计算余下的可行随机点的函数值，并比较其大小，选出函数值最小的点 xL
(4)比较 xL和 x0两点的目标函数值，
– 若 f(xL)<f(x0)，则取 xL和 x0两点的连线方向作为可行搜索方向；
– 若 f(xL)≥f(x0)，则将步长缩小，转步骤 (1)重新计算，直至 f(xL)<f(x0)为止。
( )
( )
1
2
1
2
1
1
1,2,,j
j
j
n
j
i j
ni
r
r
jk
r
r=
轾犏犏犏犏==
犏轾 犏犏 犏犏 犏臌 臌?
e L
M
0 0jja=+x x e
2009-7-27 15
产生可行搜索方向的条件可概括为，当 xL点满足
则可行搜索方向为
( ) ( )
( ) ( )
( ) ( )
1,2,,
0
0 1,2,,
m in
jL
j
L jk
L
g x j m
f x f x
f x f x
=
ì
=í
<
L
L
0Lxx=-d
2009-7-27 16
搜索步长的确定
可行搜索方向 d确定后，初始点移至 xL点，即
x0=xL，从 x0出发沿 d方向进行搜索
所用步长 a一般用加速步长法来确定
加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算
aat=
—— 步长加速系数，可取?=1.3
a—— 步长，初始步长可取 a=a0
2009-7-27 17
随机方向法的计算步骤
(1)选择一个可行的初始点 x0
(2)产生 k个 n维随机单位向量 ej(j=1,2,…,k)
(3)取试验步长 a0，计算 k个随机点 xj(j=1,2,…,k)
(4)在 k个随机点中找出满足条件的随机点 xL，产生可行搜索方向 d=xL-x0
(5)从初始点 x0出发，沿可行搜索方向 d以步长 a进行迭代计算，直至搜索到一个满足全部约束条件，且目标函数值不再下降的新点 x
(6)若收敛条件得到满足，迭代终止,x*=x。否则令 x0=x转步骤 (2)
( )0 1
0 2
()f x f x
xx
e
e
ì -
í? -
2009-7-27 18
三,惩罚函数法
基本原理
求解该新目标函数的无约束极小值，以期得到原问题的最优解
按一定的法则改变加权因子 r1和 r2的值，构成一系列的无约束优化问题，求得一系列的无约束最优解，并不断逼近原约束问题的最优解。
因此惩罚函数法又称序列无约束极小化方法
m i n
.,0 1,2,,
0 1,2,,
j
k
fx
s t g x j m
h k l
12
11
mm
jk
jj
x f x r G g x r H h x?
加权处理惩罚函数
2009-7-27 19
加权转化项根据其在惩罚函数中的作用，又分别称为 障碍项 和 惩罚项
障碍项 的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可行域
惩罚项 的作用是当迭代点在非可行域或不满足等式约束条件时，
在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。
根据迭代过程是否在可行域内进行，惩罚函数法又可分为 内点惩罚函数法、外点惩罚函数法和混合惩罚函数法 三种。
12
11
mm
jk
jj
x f x r G g x r H h x?
加权转化项
2009-7-27 20
内点惩罚函数法
内点惩罚函数法简称内点法,这种方法将新目标函数定义于 可行域内,序列迭代点在可行域内逐步逼近约束边界上的最优点
内点法只能用来求解具有不等式约束的优化问题
r——惩罚因子，它是由大到小且趋近于 0的数列，即 r0>r1>r2>…→0
由障碍函数的形式可知，当迭代点靠近某一约束边界时，其值趋近于 0，面障碍项的值陡然增加，并趋于无穷大，好像在可行域的边界上 筑起了一“围墙”,使迭代点始终不能越出可行域。
显然，只有当惩罚因子 → 0时，才能求得在约束边界上的最优解。
m i n
.,0 1,2,,j
fx
s t g x j m
11
1 lnmm
j
jjj
x f x r x f x r g xgx
或转化后的惩罚函数形式
2009-7-27 21
内点法
初始点 x0的选择
惩罚因子的初值 r0的选择
惩罚因子的缩减系数 c的选择
收敛条件
2009-7-27 22
(1)初始点 x0的选取
初始点 x0应选择一离约束边界较远的可行点
– 若 x0太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难。
程序设计时，一般都考虑使程序具有人工输入或计算机自动生成可行初始点的两种功能，由使用者选用
计算机自动生成可行初始点通常采用的方法是利用随机数生成设计点
2009-7-27 23
(2)惩罚因子初值 r0的选取
惩罚因子的初值 r0的选取应适当，否则会影响迭代计算的正常进行
– r0太大，将增加迭代的次数；
– r0太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。
1)取 r0=1根据试算的结果，再决定增加或减小
r0的值
2)按经验公式计算 r0值
0
0
1
1m
j j
fx
r
gx?
2009-7-27 24
(3)惩罚因子的缩减系数 c的选取
在构造序列惩罚函数时，惩罚因子 r是一个逐次递减到 0的数列，相邻两次迭代的惩罚因子的关系为
式中的 c称为惩罚因子的缩减系数,c为小于 1
的正数。
一般的看法是,c值的大小在迭代过程中不起决定性作用，通常的取值范围在 0.1～ 0.7之间
1kkr c r
2009-7-27 25
(4)收敛条件
内点法的收敛条件为
11
111
1
2
,,
,
k k k k
kk
kk
x r r x r r
x r r
x r x r
,kkx x r f x f x r
2009-7-27 26
内点法的计算步骤
(1)选取可行的初始点 x0，惩罚因子的初值 r0，
缩减系数 c以及收敛精度?1,?2
(2)构造惩罚函数?(x,r)，选择适当的无约束优化方法，求函数的无约束极值，得 x*(rk)点
(3)有收敛条件判断迭代是否收敛，若满足收敛条件，迭代终止，否则令 rk＋ 1=crk,x0=x*(rk)，
k=k+1，转步骤 (2)
2009-7-27 27
外点惩罚函数法
外点惩罚函数法简称外点法 。这种方法与内点法相反，新目标函数定义在可行域之外，序列迭代点从可行域之外逐渐逼近约束边界上的最优点。
外点法可以用来求解含不等式约束和等式约束的优化问题
m i n
.,0 1,2,,
0 1,2,,
j
k
fx
s t g x j m
h k l
r——惩罚因子，它是由小到大且趋近于?的数列，即 r0<r1<r2<…→?
2
11
m a x 0,ml jk
jk
x f x r g x r h x?
转化后的外点惩罚函数
1
m a x 0,,m j
j
gx
2
1
l
k
k
hx
——分别为对应于不等式约束和等式约束函数的惩罚项
2009-7-27 28
由于外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面
由惩罚项的形式可知，当迭代点 x0不可行时，惩罚项的值大于 0。使得惩罚函数?(x,r)大于原函数值，这可看成是对迭代点不满足约束条件的一种惩罚。
– 当迭代点离约束边界愈远，惩罚项的值愈大，这种惩罚愈重
– 当迭代点不断接近约束边界和等式约束曲面时，惩罚项的值减小，且趋近于 0，惩罚项的作用逐渐消失，迭代点也就趋近于约束边界上的最优点
2
11
m a x 0,
ml
jk
jk
x f x r g x r h x?
2009-7-27 29
外点法
初始点 x0的选择
惩罚因子的初值 r0的选择
惩罚因子的递增系数 c的选择
收敛条件
2009-7-27 30
(1)惩罚因子初值 r0的选取
惩罚因子的初值 r0的选取应适当，否则会影响迭代计算的正常进行，与内点法相反
– r0太小,将增加迭代的次数；
– r0太大,会使惩罚函数的性态变坏，甚至难以收敛到极值点。
1)许多计算表明，取 r0=1常常可以取得满意的效果
2)按经验公式计算 r0值
0
00
0,0 2m a x 1,2,,
j
r j m
m g x f x
2009-7-27 31
(2)惩罚因子的递增系数 c的选取
在构造序列惩罚函数时，惩罚因子 r是一个逐次增加到?的数列，相邻两次迭代的惩罚因子的关系为
式中的 c称为惩罚因子的递增系数,c为大于 1
的正数。
通常取 c＝ 5～ 10，许多计算表明取 c＝ 10常常可以取得满意的结果
1kkr c r
2009-7-27 32
惩罚函数法的特点
惩罚函数法原理简单，算法易行，适用范围广，
并且可以和各种有效的无约束最优化方法结合起来，因此得到了广泛的应用
但是惩罚函数法也存在不少问题，从理论上讲只有当 r→ ∞ （外点法）或 r→0 （内点法）时算法才能收敛，因此序列迭代过程收敛较慢。
另外，当惩罚因子的初值 r0取值不合适时，惩罚函数可能变得病态，使无约束 最优化计算发生困难。
2009-7-27 33
四,增广乘子法
随着近年来，对增广乘子法研究的不断深入，增广乘子法在计算过程中的数值稳定性，计算效率不断提高，都超过了惩罚函数法
目前增广乘子法在理论上得到了总结提高，
在算法上也积累了不少经验，使得这种方法日益完善
增广乘子法以拉格朗日乘子法为基础
2009-7-27 34
拉格朗日乘子法
1
,l pp
p
L f x h x?
x λm in
.,0p
fx
s t h x
,0Lx λ
极值必要条件拉格朗日函数
0 1,2,,
0 1,2,,
i
p
L
in
x
L
pl
联立求解，可得极值点 x*和拉格朗日乘子
2009-7-27 35
用拉格朗日乘子法求问题
22
1 2 1 2 1 2
12
m in 6 0 1 0 4
.,8 0
f x x x x x x x
s t h x x x
构造拉格朗日函数
221 2 1 2 1 2 1 2,6 0 1 0 4 8L x x x x x x x x x
令?L＝ 0
12
1
1 0 2 0L xxx
21
1
4 2 0L xxx
12 80
L xx
1
2
5
3
3
17
x
x
fx
2009-7-27 36
拉格朗日乘子法
缺点
– 对于非凸问题容易失败
– 对于大型的非线性优化问题，需求解高次联立方程组，其数值解法几乎和求解优化问题同样困难
– 还必须分离出方程组的重根
拉格朗日乘子法用来求解一般的约束优化问题并不是一种有效的方法
2009-7-27 37
等式约束的增广乘子法
基本原理
– 将惩罚函数法和拉格朗日乘子法结合起来
m in ( )
.,( ) 0 ( 1,2,,)p
fx
s t h x p l
1
,( ) l pp
p
L x f x h x
2
1
,( ) 2 l p
p
rx r f x h x?
22
1 1 1
,,( ),22l l lp p p p
p p p
rrM x r f x h x h x L x h x
求解非凸问题容易失败求解大型非线性方程组分离方程的重根计算效率低
2009-7-27 38
增广乘子函数
22
1 1 1
,,( ),22l l lp p p p
p p p
rrM x r f x h x h x L x h x
1
,,,0l pp
p
M x r L x r h x h x
约束极值点 x*
第六章 约束优化方法二,随机方向法三,惩罚函数法四,增广乘子法一,概述一,概述
机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为
求解约束优化问题的方法称为约束优化方法。
根据求解方式的不同，可分为
– 直接解法
– 间接解法
( ) ( )12( ),,,0 1,2,,k k nh x h x x x j l= = =LL
( ) ( )12.,( ),,,0 1,2,,j j ns t g x g x x x j m=? LL
( ) ( )11m i n,,,nf x f x x x= L
2009-7-27 3
直接解法
通常适用于仅含不等式约束的问题
它的基本思路是
所谓可行搜索方向是指，当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。
产生可行搜索方向的方法将由直接解法中的各种算法决定。
1 1,2,k k kk
k
k
x x a d k
a
d
+ = + = L
— — 步 长
— — 可 行 搜 索 方 向
x1
x2
o
x0
x*
2009-7-27 4
直接解法的特点
由于整个求解过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得一个比初始点好的设计点
全局最优解、局部最优解
要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函数有定义
2009-7-27 5
间接解法
基本思路 是原约束优化问题转化成为一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解
1 2 1 2
11
(,,) ( ) [ ( ) ] [ ( ) ]
ml
jk
jk
x f x G g x H h xf m m m m
==
= + +邋
( ),( ),( )jkf x g x h x
12(,,)xf m m对 进 行 无 约 束 极 小 化 计 算通 过 改 变 加 权 因 子 的 大 小,不 断 调 整 设 计 点,使 其 逐 步 逼 近 约 束 最 优 解
2009-7-27 6
间接解法框图开始输入 n,x0,?1,?2
构造?(x,?1,?2 )
求 min?(x,?1,?2 )
满足收敛条件结束
x0=x*
改变?1,?2的值是否
2009-7-27 7
间接解法特点
(1)由于无约束优化方法的研究日趋成熟，已经研究出不少有效的无约束最优化方法和程序，使得间接解法有了可靠的基础。目前，这类算法的计算效率和数值计算的稳定性也都有较大的提高。
(2)可以有效地处理具有等式约束的约束优化问题。
(3)间接解法存在的主要问题是，选取加权因子较为困难。加权因子选取不当，不但影响收敛速度和计算精度，甚至会导致计算失败。
2009-7-27 8
求解约束优化设计问题的方法
直接解法
– 随机方向法,复合形法、可行方向法等
间接解法
– 惩罚函数法和增广乘子法 等
2009-7-27 9
二,随机方向法在可行域内，选择一个初始点 x0
利用随机数的概率特征，产生若干个随机方向从中选择一个能使目标函数值下降的最快的方向作为可行搜索方向，记作 d
初始点 x0出发，沿 d方向以一定的步长进行搜索，
得到新点 x，新点应满足约束条件且 f(x)<f(x0)
令 x0＝ x满足收敛条件结束是否
x1
x2
o
x0
x*
2009-7-27 10
随机方向法的特点
随机方向法的优点是对目标函数的性态无特殊要求，程序设计简单，使用方便。
由于可行搜索方向是从许多随机方向中选择的使目标函数值 下降的最快的方向，加之步长还可以灵活变动，所以此算法的收敛速度比较快。
它是求解小型机械优化问题的一种十分有效的算法。
2009-7-27 11
随机方向法
随机数的产生
初始点的选择
可行搜索方向的产生
搜索步长的确定
2009-7-27 12
随机数的产生
伪随机数
– 产生速度快，计算机内存占用少，有较好的概率统计特性
一种产生伪随机数的模型
– 首先令 r1=235,r2=236,r3=237，取 r=2657863（ r为小于 r1的正奇数）
然后按以下步骤计算
令 r=5r
若 r≥r3，则 r=r－ r3；
若 r≥r2，则 r=r－ r2；
若 r≥r1，则 r=r－ r1
则 q=r/r1 q 即为 (0,1)区间的伪随机数
– 任意区间 (a,b)内的伪随机数计算公式为
( )x a q b a= + -
2009-7-27 13
初始点的选择
可用随机选择的方法来产生，其计算步骤为
– (1)输入设计变量的下限值和上限值，即
– (2)在区间 (0,1)内产生 n个伪随机数 qi (i=1,2,…,n)
– (3)计算随机点 x的各分量
– (4)判别随机点 x是否可行，若随机点 x可行，则取初始点 x0=x；
若随机点不可行，则转步骤 (2)重新计算，直到产生的随机点是可行点为止。
( )1,2,,i i ia x b i n＃ = L
( ) ( )1,2,,i i i i ix a q b a i n= + - = L
2009-7-27 14
可行搜索方向的产生
(1)在 (-1,1)区间内产生伪随机数 rij(i=1,2,…,n; j=1,2,…,k; k≥n),
按下式计算随机单位向量 ej
(2)取一试验步长 a0，按下式计算 k个随机点
(3)检验 k个随机点是否为可行点，除去非可行点，计算余下的可行随机点的函数值，并比较其大小，选出函数值最小的点 xL
(4)比较 xL和 x0两点的目标函数值，
– 若 f(xL)<f(x0)，则取 xL和 x0两点的连线方向作为可行搜索方向；
– 若 f(xL)≥f(x0)，则将步长缩小，转步骤 (1)重新计算，直至 f(xL)<f(x0)为止。
( )
( )
1
2
1
2
1
1
1,2,,j
j
j
n
j
i j
ni
r
r
jk
r
r=
轾犏犏犏犏==
犏轾 犏犏 犏犏 犏臌 臌?
e L
M
0 0jja=+x x e
2009-7-27 15
产生可行搜索方向的条件可概括为，当 xL点满足
则可行搜索方向为
( ) ( )
( ) ( )
( ) ( )
1,2,,
0
0 1,2,,
m in
jL
j
L jk
L
g x j m
f x f x
f x f x
=
ì
=í
<
L
L
0Lxx=-d
2009-7-27 16
搜索步长的确定
可行搜索方向 d确定后，初始点移至 xL点，即
x0=xL，从 x0出发沿 d方向进行搜索
所用步长 a一般用加速步长法来确定
加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算
aat=
—— 步长加速系数，可取?=1.3
a—— 步长，初始步长可取 a=a0
2009-7-27 17
随机方向法的计算步骤
(1)选择一个可行的初始点 x0
(2)产生 k个 n维随机单位向量 ej(j=1,2,…,k)
(3)取试验步长 a0，计算 k个随机点 xj(j=1,2,…,k)
(4)在 k个随机点中找出满足条件的随机点 xL，产生可行搜索方向 d=xL-x0
(5)从初始点 x0出发，沿可行搜索方向 d以步长 a进行迭代计算，直至搜索到一个满足全部约束条件，且目标函数值不再下降的新点 x
(6)若收敛条件得到满足，迭代终止,x*=x。否则令 x0=x转步骤 (2)
( )0 1
0 2
()f x f x
xx
e
e
ì -
í? -
2009-7-27 18
三,惩罚函数法
基本原理
求解该新目标函数的无约束极小值，以期得到原问题的最优解
按一定的法则改变加权因子 r1和 r2的值，构成一系列的无约束优化问题，求得一系列的无约束最优解，并不断逼近原约束问题的最优解。
因此惩罚函数法又称序列无约束极小化方法
m i n
.,0 1,2,,
0 1,2,,
j
k
fx
s t g x j m
h k l
12
11
mm
jk
jj
x f x r G g x r H h x?
加权处理惩罚函数
2009-7-27 19
加权转化项根据其在惩罚函数中的作用，又分别称为 障碍项 和 惩罚项
障碍项 的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可行域
惩罚项 的作用是当迭代点在非可行域或不满足等式约束条件时，
在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。
根据迭代过程是否在可行域内进行，惩罚函数法又可分为 内点惩罚函数法、外点惩罚函数法和混合惩罚函数法 三种。
12
11
mm
jk
jj
x f x r G g x r H h x?
加权转化项
2009-7-27 20
内点惩罚函数法
内点惩罚函数法简称内点法,这种方法将新目标函数定义于 可行域内,序列迭代点在可行域内逐步逼近约束边界上的最优点
内点法只能用来求解具有不等式约束的优化问题
r——惩罚因子，它是由大到小且趋近于 0的数列，即 r0>r1>r2>…→0
由障碍函数的形式可知，当迭代点靠近某一约束边界时，其值趋近于 0，面障碍项的值陡然增加，并趋于无穷大，好像在可行域的边界上 筑起了一“围墙”,使迭代点始终不能越出可行域。
显然，只有当惩罚因子 → 0时，才能求得在约束边界上的最优解。
m i n
.,0 1,2,,j
fx
s t g x j m
11
1 lnmm
j
jjj
x f x r x f x r g xgx
或转化后的惩罚函数形式
2009-7-27 21
内点法
初始点 x0的选择
惩罚因子的初值 r0的选择
惩罚因子的缩减系数 c的选择
收敛条件
2009-7-27 22
(1)初始点 x0的选取
初始点 x0应选择一离约束边界较远的可行点
– 若 x0太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难。
程序设计时，一般都考虑使程序具有人工输入或计算机自动生成可行初始点的两种功能，由使用者选用
计算机自动生成可行初始点通常采用的方法是利用随机数生成设计点
2009-7-27 23
(2)惩罚因子初值 r0的选取
惩罚因子的初值 r0的选取应适当，否则会影响迭代计算的正常进行
– r0太大，将增加迭代的次数；
– r0太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。
1)取 r0=1根据试算的结果，再决定增加或减小
r0的值
2)按经验公式计算 r0值
0
0
1
1m
j j
fx
r
gx?
2009-7-27 24
(3)惩罚因子的缩减系数 c的选取
在构造序列惩罚函数时，惩罚因子 r是一个逐次递减到 0的数列，相邻两次迭代的惩罚因子的关系为
式中的 c称为惩罚因子的缩减系数,c为小于 1
的正数。
一般的看法是,c值的大小在迭代过程中不起决定性作用，通常的取值范围在 0.1～ 0.7之间
1kkr c r
2009-7-27 25
(4)收敛条件
内点法的收敛条件为
11
111
1
2
,,
,
k k k k
kk
kk
x r r x r r
x r r
x r x r
,kkx x r f x f x r
2009-7-27 26
内点法的计算步骤
(1)选取可行的初始点 x0，惩罚因子的初值 r0，
缩减系数 c以及收敛精度?1,?2
(2)构造惩罚函数?(x,r)，选择适当的无约束优化方法，求函数的无约束极值，得 x*(rk)点
(3)有收敛条件判断迭代是否收敛，若满足收敛条件，迭代终止，否则令 rk＋ 1=crk,x0=x*(rk)，
k=k+1，转步骤 (2)
2009-7-27 27
外点惩罚函数法
外点惩罚函数法简称外点法 。这种方法与内点法相反，新目标函数定义在可行域之外，序列迭代点从可行域之外逐渐逼近约束边界上的最优点。
外点法可以用来求解含不等式约束和等式约束的优化问题
m i n
.,0 1,2,,
0 1,2,,
j
k
fx
s t g x j m
h k l
r——惩罚因子，它是由小到大且趋近于?的数列，即 r0<r1<r2<…→?
2
11
m a x 0,ml jk
jk
x f x r g x r h x?
转化后的外点惩罚函数
1
m a x 0,,m j
j
gx
2
1
l
k
k
hx
——分别为对应于不等式约束和等式约束函数的惩罚项
2009-7-27 28
由于外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面
由惩罚项的形式可知，当迭代点 x0不可行时，惩罚项的值大于 0。使得惩罚函数?(x,r)大于原函数值，这可看成是对迭代点不满足约束条件的一种惩罚。
– 当迭代点离约束边界愈远，惩罚项的值愈大，这种惩罚愈重
– 当迭代点不断接近约束边界和等式约束曲面时，惩罚项的值减小，且趋近于 0，惩罚项的作用逐渐消失，迭代点也就趋近于约束边界上的最优点
2
11
m a x 0,
ml
jk
jk
x f x r g x r h x?
2009-7-27 29
外点法
初始点 x0的选择
惩罚因子的初值 r0的选择
惩罚因子的递增系数 c的选择
收敛条件
2009-7-27 30
(1)惩罚因子初值 r0的选取
惩罚因子的初值 r0的选取应适当，否则会影响迭代计算的正常进行，与内点法相反
– r0太小,将增加迭代的次数；
– r0太大,会使惩罚函数的性态变坏，甚至难以收敛到极值点。
1)许多计算表明，取 r0=1常常可以取得满意的效果
2)按经验公式计算 r0值
0
00
0,0 2m a x 1,2,,
j
r j m
m g x f x
2009-7-27 31
(2)惩罚因子的递增系数 c的选取
在构造序列惩罚函数时，惩罚因子 r是一个逐次增加到?的数列，相邻两次迭代的惩罚因子的关系为
式中的 c称为惩罚因子的递增系数,c为大于 1
的正数。
通常取 c＝ 5～ 10，许多计算表明取 c＝ 10常常可以取得满意的结果
1kkr c r
2009-7-27 32
惩罚函数法的特点
惩罚函数法原理简单，算法易行，适用范围广，
并且可以和各种有效的无约束最优化方法结合起来，因此得到了广泛的应用
但是惩罚函数法也存在不少问题，从理论上讲只有当 r→ ∞ （外点法）或 r→0 （内点法）时算法才能收敛，因此序列迭代过程收敛较慢。
另外，当惩罚因子的初值 r0取值不合适时，惩罚函数可能变得病态，使无约束 最优化计算发生困难。
2009-7-27 33
四,增广乘子法
随着近年来，对增广乘子法研究的不断深入，增广乘子法在计算过程中的数值稳定性，计算效率不断提高，都超过了惩罚函数法
目前增广乘子法在理论上得到了总结提高，
在算法上也积累了不少经验，使得这种方法日益完善
增广乘子法以拉格朗日乘子法为基础
2009-7-27 34
拉格朗日乘子法
1
,l pp
p
L f x h x?
x λm in
.,0p
fx
s t h x
,0Lx λ
极值必要条件拉格朗日函数
0 1,2,,
0 1,2,,
i
p
L
in
x
L
pl
联立求解，可得极值点 x*和拉格朗日乘子
2009-7-27 35
用拉格朗日乘子法求问题
22
1 2 1 2 1 2
12
m in 6 0 1 0 4
.,8 0
f x x x x x x x
s t h x x x
构造拉格朗日函数
221 2 1 2 1 2 1 2,6 0 1 0 4 8L x x x x x x x x x
令?L＝ 0
12
1
1 0 2 0L xxx
21
1
4 2 0L xxx
12 80
L xx
1
2
5
3
3
17
x
x
fx
2009-7-27 36
拉格朗日乘子法
缺点
– 对于非凸问题容易失败
– 对于大型的非线性优化问题，需求解高次联立方程组，其数值解法几乎和求解优化问题同样困难
– 还必须分离出方程组的重根
拉格朗日乘子法用来求解一般的约束优化问题并不是一种有效的方法
2009-7-27 37
等式约束的增广乘子法
基本原理
– 将惩罚函数法和拉格朗日乘子法结合起来
m in ( )
.,( ) 0 ( 1,2,,)p
fx
s t h x p l
1
,( ) l pp
p
L x f x h x
2
1
,( ) 2 l p
p
rx r f x h x?
22
1 1 1
,,( ),22l l lp p p p
p p p
rrM x r f x h x h x L x h x
求解非凸问题容易失败求解大型非线性方程组分离方程的重根计算效率低
2009-7-27 38
增广乘子函数
22
1 1 1
,,( ),22l l lp p p p
p p p
rrM x r f x h x h x L x h x
1
,,,0l pp
p
M x r L x r h x h x
约束极值点 x*
