（3）对任意 v R n ，且使得 v T h( x * ) 0 的非零
向量 v ，总有
v T Lx 2 ( x * , * )v 0
那么， x * 是问题（Ⅰ）的严格局部最优点。
即若
x * 是问题的局部最优点
x L( x * , * ) 0
1、拉格朗日函数的极小点
内外混合罚函数法：
I 2 i gi ( x0 ) 0, i 1,2, , m I3 j hj ( x0 ) 0, j 1,2, , l
——内部惩罚函数
可以构造增广目标函数
P( x, r ) f ( x) - r ln gi ( x)
iI1
1 + [ | min(0, gi ( x)) |2 + | min(0, h j ( x)) |2 r iI2 jI3
2 min P ( x , ) f ( x ) + h ( x ) j n xR j 1 l
L( x, ) + P ( x )

M x1 ( x, , ) 2 x1
例1 约束优化问题
s.t.
M x2 ( x, , ) -( + 3) + ( - 2) x2
M ( x , , ) L( x , ) +

2
h( x )T h( x )
引理（收敛相关性质） 设在上面等式约束问题中, x*∈Rn和 *∈Rn满足二阶充分条件(定理2), 则存在 一个数* > 0, 对所有的 ≥ *, x*是增广目标函数 的严格局部极小点; 反之, 若h(x0)=0 ，且 x0对某个 0是增广目标函数的 局部极小点, 则x0 是等式约束问题的局部极小点.
乘子法并不要求 趋于无穷大. 只要 大于某个正 数*, 就能保证无约束问题 min M(x, *, ) 的最优解 为原问题的最优解. 要解决的问题是, 如何确定*? 我们采用迭代的方法求出 *. 求解无约束问题
min M(x,k, )
其解为 xk, 然后修正k为k+1, 再求解
min
f ( x)
h j ( x) 0, j 1, 2, ,l
4、乘子法的理论分析
s.t.
其中h(x)=(h1(x),· · · ,hl(x))T, 目标函数和约束函数二次 连续可微. 设 ∈Rl 为乘子向量, 则上面问题的Lagrange 函数为
L( x, ) f ( x) - T h( x),
2 L( x, ) x12 - 3 x2 - x2 - x2 x1 - ( + 3) x2 - x2
2
2
对于任何 λ , 拉格朗日L(x, λ)关于 x 的极小点不存在.
事实上，对于任何参数 λ , 对任何确定的 x1, 当 x2 → +∞ 时，L( x, ) - .
2、外罚函数参数 构造增广目标函数
2 1
-2
2
2 x2
当 *= -3, ≥ * = 2 时,原问题最优解 (0,0)T 是
增广Lagrange函数的最优解.
M x1 ( x, , ) 2 x1
求解无约束问题
2 1
M x2 ( x, , ) -( + 3) + ( - 2) x2
M ( x , , ) x - ( + 3) x2 +
一. 等式约束问题
二．不等式约束问题 三. 约束优化问题的Matlab求解
约束最优化问题的罚函数思想：
min
s.t.
f ( x)
g i ( x) 0 i 1, 2,, m
h j ( x) 0
j 1, 2,, l
x ( x1 , x2 , , xn )T R n 其可行（容许）解集
2 min f ( x) x12 - 3x2 - x2
x2 0
2 /2 取 P ( x ) x2
解 因为拉格朗日（Lagrange）函数
2 2 L( x, ) x1 - ( + 3) x2 - x2 ,
增广Lagrange函数
M ( x , , ) x - ( + 3) x2 +
若 xk→x*, 则有h(x*) = 0, 即 x* 为可行解.
5、等式约束问题的乘子法 — PH算法
Step1 选定初始点x0, 初始乘子向量1, 初始罚因子1, 放大系数c>1, 控制误差e, 常数q ∈(0,1), 令k=1; Step2 以 xk-1 为初始点求解无约束问题
min M ( x , k , k ) f ( xk ) - h( x ) +
外罚函数法：
回顾
其中
P( x, ) f ( x) + P( x)
P( x) | h j ( x) |2
j 1 l
P( x) 称为罚函数, > 0 称为罚因子.
求解原问题转化为求解一系列的无约束问题 min P(x, k) ( k → + ∞)
min P(x, k) ( k → + ∞) 关于罚函数参数 ：
由于x*是可行点, hj(x*) = 0, 因此应该有 f ( x* ) 0.
这在一般情况下是不成立的.
3、等式约束问题的乘子法
我们将上述两种思路结合起来： 即考虑能否找到
*, *, 使得 x* 是下面的增广Lagrange函数的极小点.
min L ( x, ) n
xR Rl
S x | gi ( x) 0, i 1, 2, , m , h j ( x) 0, j 1, 2, , l,
x ( x1, x2 , , xn )T R n

外罚函数法：
可以构造增广目标函数
其中
m i 1
P( x, ) f ( x) + P( x)
l
-2
2
2 x2
令 0 M 2 x , 1
x1
得
M 0 ( - 2) x2 - ( + 3). x2
+3 T x0 (0, ) . -2
要求 x0 满足约束条件 x2 = 0, 必须取 = -3,
从而 x0 = (0, 0)T = x*, 得到原约束问题的最优解.
x M ( xk , k , ) f ( xk ) - h( xk )(k - h( xk )) 0
希望 xk→x*, k→*, 且 f ( x* ) - h( x* ) * 0
于是采取公式 k+1 = k - h(xk)是比较合理的.
若 {k} 收敛, 则有h(xk) →0.
即
f ( x ) * l * * j h j ( x ) 0 j 1
x L( x * , * ) f ( x * ) - ( * ) T h( x * ) 0
其中 * (1* , 2* , , l * ) T 。
定理2 (二阶充分条件) 设在问题（Ⅰ）中 回顾
（1） f ( x), h1( x), h2 ( x), , h l ( x) 二阶 连续可微； （2）存在 x * R n ， * R l 使得 Lagrange
函数的梯度为零，即
L( x * , * ) f ( x * ) - ( * ) T h( x * ) 0
无约束优化问题的困难：
为使无约束优化的解接近于原约束优化的解，选择的
罚因子 σ 和 r 应该充分大或充分小，但是，这时对应的
无约束优化问题的目标函数接近于“病态”.
这是罚函数法固有的，本质性的弱点。因而提出下面
的乘子法（乘子罚函数法）.
一．等式约束问题的乘子 (罚函数) 法
min
s.t.
f ( x)
《运筹与优化》
邵建峰
第五章 约束最优化方法
信息与计算科学系
邵建峰
邵建峰
本章内容：
5.1 约束最优化问题的最优性条件 5.2 罚函数法 5.3 乘子(罚函数)法
5.4 投影梯度法
5.5 简约梯度法 5.6 约束变尺度法
7.2 乘子(罚函数)法
信息与计算科学系
邵建峰
邵建峰
本节内容：
min M(x,k+1, )
得到两个点列{xk},{k}, 希望 xk→x*, k→*.
如何对 k 进行修正?
L( x, ) f ( x) - T h( x), M ( x , , ) L( x , ) + h( x )T h( x )
2
设已有 k 和 xk, 由 M(x,,) 的定义
x L( x, ) f ( x) - T h( x),
L( x, ) h( x)
2 T 2 2 L ( x , ) f ( x ) x x x h( x)
定理1 (Lagrange) 设
回顾
（1） x * 是问题（Ⅰ）的局部最优点； （2） f ( x), h1( x), h2 ( x), , h l ( x) ： R n R 在 x * 附近 的某邻域内可微； （3） h1( x), h2 ( x), , h l ( x) 线性无关。 则必存在实数 1* , 2* , , l * ，使得
对任意的 x*∈D, 有
L( x* , * ) f ( x* ) - *T h( x* ) f ( x* )
f ( x ) - *T h( x ) L( x, * )
min
s.t.
f ( x)
h j ( x) 0, j 1, 2, , l