运筹学4-4

当 x X o 时，
p 1 Bd k ( x ) d k 或 Bd k ( x ) d k ln[ g i ( x )] i 1 g i ( x ) i 1 其中， d k 为罚参数或罚因子
p
Fd k ( x ) f ( x ) Bd k ( x )
min Fd k ( x ), k 1,2,...
g i ( x ) 0, i 1,..., p n X x R h j ( x ) 0, j 1,..., q
设法适当地加大不可行点处对应的目标 函数值，使不可行点不能成为相应无约 束极小化问题的最优解。
罚函数
c q pc ( x ) c [max( g i ( x ),0)] [h j ( x )] 2 2 j 1 i 1
Fd k ( x ) f ( x ) Bd k ( x )
。否则，令 k:=k+1，转第 2 步。
惩罚函数法
思想：利用问题中的约束函数做出适当的带有 参数的惩罚函数，然后在原来的目标函数上加 上惩罚函数构造出带参数的增广目标函数，把 (MP)问题的求解转换为求解一系列无约束非线 性规划问题。
罚函数法 障碍函数法
罚函数法
min f ( x ) s .t . g i ( x ) 0, i 1,..., p h j ( x ) 0, j 1,..., q
令g( x ) ( g1 ( x ),..., g p ( x )) T
可行域 X 的内部记为 X o { x R n | g( x ) 0}
在可行区域的边界上筑起一道“墙”，当迭代点靠近 边界时，所构造的增广目标函数值陡然增大，于是最 优点就被“挡”在可行区域内部了。
构造障碍函数
实际应用中选取一个递增且趋于无穷的正罚函数参数列罚函数法罚函数法计算步骤在可行区域的边界上筑起一道墙当迭代点靠近边界时所构造的增广目标函数值陡然增大于是最优点就被挡在可行区域内部了
§4.5 约束最优化方法
1. 约束最优化问题的最优化条件
设(MP)问题的可行区域为 X x R n gi ( x) 0, i 1,..., l , h j ( x) 0, j 1,..., m


对 x* X , 令J {1, 2, , m}，即满足 h j ( x* ) 0, jJ
积极约束的下标集：I ( x* ) {i | gi ( x* ) 0, i I }
§4.5 约束最优化方法
Kuhn-Tucker条件（K-T条件）：
定理 4.5.1 设 f : R n R 和 g i : R n R, i I ( x * ) 在点 x * 处可微，
2 p
Fc ( x) f ( x) pc ( x)
min Fc ( x )
罚函数法
实际应用中，选取一个 递增且趋于无穷的正罚 函数参数列
min Fck ( x ) f ( x ) pck ( x )
(1)
2
其中
c pck ( x ) c k [max( g i ( x ),0)] k 2 i 1
障碍函数法步骤
第 1 步 选取初始点 x 0 X o ，罚参数列{d k }( k 1,2,...) ， 给出检验终止条件 0 ，令 k:=1； 第 2 步 做障碍函数 Bd k ( x ) ，构造增广目标函数
x k 1 为初始点求解 第 3 步 选用某种无约束最优化方法，以 min Fd k ( x ), x X o xk xk 得到最优解 。若 已满足某种终止条件，停止迭代，输出 xk
g i , i I \ I ( x * ) 在点 x * 处连续， h j : R n R, j J 在点 x * 处连续
可微，并且各 g i ( x * ), i I ( x * ), h j ( x * ), j J 线性无关。若
x * 是(MP)的局部最优解，则存在两组实数 * , i I ( x * ) 和 * , j J ， j i
ck
x k 1 为初始点， 第 3 步 选用某种无约束最优化方法，以 k xk x min F ( x )
，设得到最优解
xk
。若
已满足某种
终止条件，停止迭代，输出
。否则令 k:=k+1，转第 2 步；
• 例 1. 用罚函数法求解
min x
2
s.t. 1 x 0
障碍函数法
min f ( x ) s.t . g i ( x ) 0, i 1,..., p
注： （1）凡是满足K-T条件的点叫K-T点；
* , * 称为Lagrange乘子; （2）
(3) K-T条件的等价形式：
l m * * * f ( x ) i gi ( x ) *h j ( x* ) 0 j i 1 j 1 * i gi ( x* ) 0, i 1,..., l * i 1,..., l i 0,
例1
例2
用K-T条件解约束规划问题
min f ( x1 , x2 ) ( x1 1) ( x2 2)
2
s.t. g1 ( x) x1 x2 2 0 g 2 ( x) x1 0 g3 ( x) x2 0 h1 ( x) x1 x2 1 0
使得
f ( x * ) * g i ( x * ) * h j ( x * ) 0 i j * jJ i I ( x ) * 0, i I( x* ) i
“向量组 g i ( x * ), i I ( x * ), h j ( x * ), j J 线性无关”—这个 条件称为约束规范条件
Hale Waihona Puke §4.5 约束最优化方法定理 4.5.2 对于(MP)问题，若 f , g i , i I , h j , j J 在点 x * 处连续可微，可行点 x * 满足(MP)的 K-T 条件，且 f , g i , i I ( x * ) 是凸函数，
h j , j J 是线性函数，则 x * 是(MP)的整体最优解。
2
p
[h ( x )] (2)
j 1 j
q
罚函数法计算步骤
第 1 步 选取初始点 x 0 ，罚参数列 {c k }( k 1,2,...) ， 给出检验终止条件的误差 0 ，令 k:=1； 第 2 步 按(2)构造函数 pck ( x ) ，再按(1)构造(MP) 的增广目标函数，即 Fck ( x ) f ( x ) pck ( x ) 求解