一般约束非线性规划问题的光滑牛顿法

冯迎春, 郑 列

(湖北工业大学 理学院, 武汉 430068)

FENG Ying-chun, ZHENG Lie

( School of Science , Hubei University of Technology ,Wuhan 430068 , China)

一般约束非线性规划问题的光滑牛顿法

冯迎春, 郑 列

(湖北工业大学 理学院, 武汉 430068)

用改进的光滑NCP函数替代了文 [1,2]中的弱互补函数, 提出了一种新的光滑牛顿法, 从而实现了一般约束优化问题的KKT条件到非线性方程组之间的完全等价转化, 且将文[3]中提出的求解无约束最优化问题的修正BFGS 方法加以改进, 应用于求解一般的约束最优化问题, 避免了计算Hesse矩阵工作量较大的问题, 并在一定的条件下证明了该算法的全局收敛性.

NCP函数; 牛顿法; KKT条件

A Smooth Newton Method for General Constrained Nonlinear Optimization Problem

FENG Ying-chun, ZHENG Lie

( School of Science , Hubei University of Technology ,Wuhan 430068 , China)

Abstract:In this paper, an improved smooth NCP function replaces the weak complementary functions in the literature [1,2] and a new smooth Newton method is proposed, therefore the KKT conditions of the constraint optimization is transformed into an equivalent nonlinear equations. the Modified BFGS Algorithm proposed in literature [3] is applied to solve the general constrained optimization problem, the main advantages of this method lies that its iterative matrix is positive definite, while avoiding the calculation of the workload of Hesse matrix, and it is proved that the algorithm is global convergence under certain conditions.

Key words:NCP function; Newton method; KKT conditions

引言

考虑一般约束非线性规划问题(简称为GNP问题)

其中g( x)=(g1( x),…,gl( x ))T:→Rl,h( x)=(hl+1(x),…,hl+m(x ))T:→和f:→均为连续可微函数, E={1,2,…,l},I={l+1,l+2,…,l+m}.

1 算法及理论基础

为了把约束规划问题转化为无约束规划问题, 引入广义Lagrange函数

下面考虑基于改进的光滑NCP函数和广义Lagrange函数的光滑牛顿法, 其算法如下:

Step1 给定初值: x1∈Rn, λ1∈Rl, μ1∈Rm为给定正数, 参数η, γ∈(0,1), ε≥0, θ∈[0,1], 初始对称正定矩阵B1, k:=1.

Step3 取αk为{1,η ,η2,…}中满足不等式φ(zk+αkδk)≤φ(zk)+γαkH(zk)δk的最大值.

Step4 令zk+1=zk+αkδk.

Step5计算Bk+1, k:=k+1, 转Step2.

在算法中, 我们采用BFGS公式来计算Bk+1, 其修正公式为:

2 收敛性分析

若u=0, 由式(6)及假设2)可知v=0,w=0. 若u≠0, 由于Bk为正定矩阵及式(6), 所以

由(7)、(10)及(11)可知uTB u恒为0, 故与上式相矛盾, 从而假设u≠0不成立, 因此(u, v, w)=0. 所以ω为

kk可逆阵.

[1] 桂胜华, 张 倩, 邢 丽. 弱互补函数的拉格朗日—拟牛顿法[J]. 上海第二工业大学学报, 2005, 12(5): 21～27

[2] 桂胜华, 周 岩. 拉格朗日—拟牛顿法解约束非线性规划问题[J]. 同济大学学报, 2007, 4(4): 556～561

[3] 焦宝聪. 一类改进BFGS算法及其收敛性分析[J]. 数学的实践与认识, 1999, 29 (2): 143～149

[4] 王秀国, 邱菀华. 一种解决不等式约束优化的光滑牛顿法[J]. 运筹与管理, 2004, 10(5): 62～66

[5] 孙守霞, 刘 伟. 解非线性不等式约束优化问题的非精确光滑牛顿法[J]. 鲁东大学学报, 2007, 23(1): 19～22

[6] 陈宝林. 最优化理论与算法[M]. 北京: 清华大学出版社, 2005

[7] 袁亚湘. 非线性优化计算方法[M]. 北京: 科学出版社, 2008

O221.2

A

1672-5298(2010)01-0020-04

2009-09-26

冯迎春(1983- ), 女, 湖南长沙人, 湖北工业大学理学院硕士研究生. 主要研究方向: 最优化理论