非线性约束最优化方法 ——乘子法
1.1 研究背景
最优化理论与方法是一门应用性相当广泛的学科，它的最优性主要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性性强等特点，使得相关变量的存储、计算及命题的求解都相当困难，从而导致大规模非线性优化很难实现。因此，寻求高效、可靠的大规模非线性优化算法成为近年来研究的热点。
本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线性等式约束最优化问题方面的一些问题。 1.2非线性约束规划问题的研究方法
非线性约束规划问题的一般形式为
（NPL ） {}{}
m in (),,
s.t. ()0,1,2,...,,
()0,1,2,...,n
i i f x x R c x i E l c x i I l l l m ∈=∈=≤∈=+++
其中，(),()i f x c x 是连续可微的.
在求解线性约束优化问题时，可以利用约束问题本身的性质，
但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题比较复杂、困难。因此，我们将约束问题转化为一系列无约束优化问题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。
传统上我们所提出的非线性约束最优化方法一般都遵循下列三个基本思路之一
1 借助反复的线性逼近把线性方法扩展到非线性优化问题中来
2 采用罚函数把约束非线性问题变换到一系列无约束问题
3 采用可变容差法以便同时容纳可行的和不可行的X 矢量
其中源于思路2 的乘子罚函数法具有适合于等式及不等式约束不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无任何要求等特点。
1.3乘子法
罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到约束问题的极小点，这会使罚函数的Hesse矩阵变得病态，给无约束问题的数值求解带来很大问题，为克服这一缺点，Hestenes和Powell 于1964年各自独立地提出乘子法。所谓乘子法是：由问题的Lagrange 函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它们一直是求解约束优化问题的主要而有效的算法。
考虑如下非线性等式约束优化问题：
（NEP ） min f （x ）
s.t. 0)(=x c i , i=1,2,...,l 设*
x
为问题（NEP ）的最优解，且它的 Lagrange 函数为
)()(),(x c x f x L T
λλ-=
其中T
l x c x c x c x c ))(),...,(),(()(21=，T
l ),...,,(21λλλλ=是与x 相对
应的Lagrange 的乘子向量。在一般正规假设条件（Fritz John 必要
条件）下，),(*
*λx 是),(λx L 的稳定点，即0),(*
*=∇πx L x 。因此，若能找到*
λ，则),(*
λx L 的极小值是*
λ，那么求解问题（NEP ）转化
成求解一个无约束极小化问题。然而),(λx L 的极小值往往不存在。
为了避免出现),(λx L 的极小值不存在的问题，我们构造增广Lagrange 函数
)()(2
1)()(),,(x c x c x c x f x T
T
σλσλϕ+
-=
由于0),(*
*=∇πx L x ，则
0)()()()(),(),,(*
*******=∇=∇+∇=∇x c x c x c x c x L x x x σσλσλϕ
这样*
x
是),,(*
σλϕx 的一个稳定点。
由此可知，当*
λλ=时，适当的选取σ可以使),,(*
σλϕx 的无
约束极小点就是问题（NEP ） 的最优解。 1.4 乘子法的相关定理和引理
引理 设W 是n n ⨯阶矩阵，a 为n 阶向量，若对一切d 满足
0,0T
d a d ≠=，均有0
T
d W d >，则存在*
σ
>，使当*
σ
σ
≥时，矩阵
T
W aa
σ+正定.
证明 考虑集合
{}
1K d d ==，
只需证明，,d K ∀∈当*
σ
σ
≥时，有
()0.T T
d W aa d σ+> （4.20）
事实上，
z ∀≠，则
z d K
z
=
∈，则
()0
T T
z W aa
z σ+>
与()0T
T
d W aa d σ+>等价.
令
{}'0,,T
K d d W d d K =≤∈
若
'K =∅
，则
,
d K ∀∈有
T
d W d >，因此0
σ∀>，有()T
T
T
d W a a d
d W d
σ+≥
>.因此假设
'K ≠∅
，当
/'
d K K ∈时，有
0T
d
W d >，因此0σ∀>，有()0T
T
T
d W aa d d W d σ+≥>.
下面考虑'd K ∈，由于'K 是有界闭集，则函数T
d
W d
与2
()
T
a
d 在'
K
上取到极小值，不妨设(1)(1)()T d W d 与(2)2()T a d 分别为函数的极小值，并且(2)0T a d ≠；否则由定理条件，有(2)
(2)
()0T d
W d
>与(2)
'd
K ∈矛盾.因此
取
(1)
(1)
*
(2)
2
()0,()
T T
d
W d
a d
σ>
>
当*
σ
σ
≥时，有
2
(1)
(1)
(2)
2
()()()()0,T
T
T
T
T T d W aa d d W d a d d W d
a d
σσσ+=+≥+>
因此，,d K ∀∈（4.20）式成立. 定理1 设*
x
是问题（NEP ）的最优解，且满足二阶充分条件，其
相应的Lagrange 乘子为*λ ，则当σ充分大时，*
x 为无约束优
化问题
