设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投搞
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
Operations Research and Fuzziolgy 运筹与模糊学, 2012, 2, 19-24
http://dx.doi.org/10.12677/orf.2012.22003 Published Online May 2012 (http://www.hanspub.org/journal/orf)
A Class of Modified Generalized Quasi-Newton
Algorithms for Solving Complementarity Problem
Wei Wang, Zongwei Jia, Yongchuang Han
School of Mathematics, Liaoning Normal University, Dalian
Email: wei_0713@sina.com, jiazongwei88@163.com
Received: Jan. 6th, 2012; revised: Jan. 14th, 2012; accepted: Feb. 13th, 2012
Abstract: Since the complementarity problem is proposed, people have done series of research, propose a lot of
efficient algorithms, more used methods are projection method, interior-point method, smooth (nonsmooth)
Newton method, etc. In thi s paper, complementarity problem i s convert into unconstrained optim i z at ion by using
Fischer-Burmeister function, then unconstrained optimization is solved by modified generalized quasi-Newton
algorithm. the improved algori thm has good num erical results verified by numerical experim ents.
Keywords: Complementarity Problem; Unconstrained Optimization Problem; Generalized Quasi-Newton
Algorithms
一类修正的广义拟牛顿法解互补问题
王 炜,贾宗伟,韩永闯
辽宁师范大学数学学院,大连
Email: wei_0713@sina.com, jiazongwei88@163.com
收稿日期:2012 年1月6日;修回日期:2012 年1月14日;录用日期:2012 年2月13 日
摘 要:互补问题自被提出至今,人们对它进行了一系列研究,提出了许多有效算法,比较常用的有
投影法、内点法、光滑(非光滑)牛顿法等。本文利用 Fischer-Burmeister 函数将互补问题转化为无约束
优化问题,再利用修正的广义拟牛顿算法求解。改进后的算法经数值实验验证有良好的数值效果。
关键词:互补问题;无约束优化问题;广义拟牛顿算法
1. 引言
互补问题在工程和经济领域中的应用非常广泛,如力学中的弹塑性分析问题、接触问题、蠕变问题、土力
学问题、润滑力学问题等都可以转化为如下的互补问题来求解[1-4]:对于


:nn
F
xR R,求一点 n
x
R使得




0, 0,0
T
xF xxF x

.
互补问题的研究过程中,涌现出了许多求解算法。光滑牛顿法简单优越,但是即使一个线性互补问题,转化后
的方程往往是线性的,且非线性程度较高,导致理论和计算的复杂化;投影类算法法每次迭代运算量少,存储
量少,保稀疏性,但其收敛速率被认为是最多线性的;无约束优化法较为成熟,因此本文算法只需选取适当的
势函数将互补问题转化为无约束优化问题,再对其求解。Mangasarian 和Soldow 给出一个可微的势函数,并且
证明了解势函数与解互补问题的等价性,为以后的研究工作做了理论基础[5]。对于无约束优化问题,BYRD R. H.
做了非拟牛顿算法的研究[6,7],随后陈兰平提出一种基于 Broyden 族的非拟牛顿算法,并证明了非拟牛顿凸族的
收敛性[8]。陈兰平提出的拟牛顿方程只有目标函数梯度信息[8],本文对其做了改进,使它不仅包含目标函数梯度
Copyright © 2012 Hanspub 19
王炜 等  一类修正的广义拟牛顿法解互补问题
信息,还包含目标函数的信息,具有更广泛的形式。数值实验中,不仅验证了改进的算法的可行性,并且讨论
了算法计算速度较快时参数的取值。
在第 2章,讲述了互补问题转化成无约束问题的具体过程,并给出了修正的拟牛顿迭代公式;在第 3章,
给出了本文修正广义拟牛顿算法的步骤;在第 4章,对算法全局收敛性和超线性收敛性进行了论述证明;在第
5章,数值实验表明,本文的算法是有效的。
2. 预备知识

:nn
F
xR R,求一点 n
x
R使得




0, 0,0
T
xF xxF x

. (1)
当

F
x为线性函数时,称(1)为线性互补问题,记为


,LCP M q;否则,称(1)为非线性互补问题,记为


NCP F。
本文的方法是利用互补函数把互补问 题转化为无约束最 优化问题[9],再用广义拟牛顿法求解,转化过程如下:

12
,,, T
n
xx x
 

,,,T
,12 n

x
F
xFxFx Fx,取适当的互补函数令

,ab

,令






11
,
,
nn
xFx
xM
x
Fx









,
 
2
1
2
f
x

x,其中 为向量 2-范数。
互补函数 要满足:;推广之,可得到以下成立

,ab



,00, 0,0aba bab

 
*
x
是


NCP F的解 *
x
是


x

的解。
于是,互补问题最终转化为无约束优化问题


x,其中
  




11
2
,
1,
2,
nn
xFx
fxx xM
x
Fx










。本文
f
min
所用的互补函数是 Fischer-Burmeister 函数

22
,ababa b


。
对于无约束最优化问题

min, n
f
xx R,拟牛顿方程为 1kk k
y



B,其 中


f
x是二阶连续可微的, 1k

B
为
Hessian 阵 的一个近似,

21
k
fx










11
,, ,,
kkkk kkkkkkkk

s
xxgfxygx gxgfxffx

 ,
搜索方向 ,
kk
dgHk
1
kk


H
B。
本文采用的广义拟牛顿迭代公式如下:

1
TT
T
kkk kkk
kk k
T
k
kkk
yyss VV
Qt
yy

 
HH
HH Hk
. (2)
其中

12
Tkkk
kkkk TT
kkk kk
sy
Vyy ys yy




H
HH
,


k
Qt是T
kk
y
s和 的凸组合,
k
R
 


1,0,
T
kkk k
Qt tystRt 1,


11
2kkT T
kkk
Rffgsg



kk
s.
当 时,(2)式即为 Broyden族校正公式;当1t


0, 1t,(2)式是非拟的拟牛顿校正公式。
3. 修正的广义拟牛顿算法
给定初始点 0n
x
R,初始矩阵 。
1
000
,
nn nn
RR

BHB

选择充分小的 0

, ,令
 
0,1 ,0,1

 0k

。
Copyright © 2012 Hanspub
20
王炜 等  一类修正的广义拟牛顿法解互补问题
1) 确定下降方向 。
kk
dgHk
2) 取步长 k
m
k


,其中, 是满足下式的最小非负整数,
k
m





,0,1,0,1
mmT
kkk kk
fxd fgd

 
.
3) 求1
,
kkk kk
x
xx d

 。
4) 若k
g

,则停止;否则,转 5)。
5) 利用校正公式

1
1
0
0
T
kk
TT
kTT
kkk kkk
kk kkkk
T
k
kkk
ys
yyssVVy s
Qt
yy



k


 


, 若
,若
H
HHH
HH H
.
计算 1k
H
,令 ,转 1)。
1kk
4. 全局收敛性和超线性收敛性
假设 1 1)


f
x在 上二阶连续可微;2)
n
R


f
x在水平集内是一致凸函数。
假设 2 1)

f
x在 上二阶连续可微;2)
n
R


f
x在局部极小值点*
x
的Hessian 矩阵

*
x
G正定;3) 存在 *
x
点的一个邻域

*,Nx


,使得

x
G在该邻域内 Lipschitz 连续。
引理 1 设k
H
正定,则校正公式 2)使1k

Η
保持正定。
证明:将k
H
分解为 ,对,令,则有下面三个不等式成立
T
kk
LLHk0T
k
,
n
zRz ,
T
kkkk
aLzbLs

2
0
T
Tkk
TT
kkk k
kkk
TT
kkk kk
ab
yy
zzaa
yy bb




HH
HH
,
  

2
11
()
T
Tk
TT T
kk
kk kkk k
kk
zs
ss
ztystRz tystR
Qt Qt



0





 0
T
ys 
z
(限定 ),
kk

20
TT T
kk k
zVVz zV

,
且三个等号不能同时成立,故 大于零。即
1
T
k
z

H1k

H
为正定矩阵。
定理 1 设

是由修正的校正公式产生的非奇异矩阵序列,在假设 1条件下,迭代序列


k
B

k
x
收敛到


f
x的
极小值点。
证明:记,
TT
kkk k
kk
TT
kk kk
ys yy
mM
s
ys

,引理 5.71[10],存在与 k无关的正常数 ,使得。 ,mM ,
kk
mmM M
对修正的校正公式



12
T
T
kkkT
kkk k
kk k
TT
kkkkk
Qtyy
ss VV
ss ys

 
BB
BB Bk
,
两边求迹得


22
2
12
kkkk
kk
TT
kkkkk
sQy
tr trV
ss ys

 
B
BB
Bk
。
为求 1k
B
的行列式,我们先给出一个有关秩-2校正矩阵行列式的计算式和求矩阵逆公式:

det 1
TT
I
uvu v
,

11
11
1
1
T
T
T
A
uv A
Auv AvAu





.
推广之:

12341234142 3
det1 1
TT TTTT
I
uu uuuuuuuuuu ,






1
122
detdetdet det
TT
TT
kkkk kkk
kkkkkk k
kk k
TT
TT
kkkkkk
kk kk
QtyyQt yy
ss ss
I
ss ss
ys ys




 



B
BB B
BB B
BB





.
Copyright © 2012 Hanspub 21
王炜 等  一类修正的广义拟牛顿法解互补问题
记


1
123
2
,,,
kkk
TT
k
kk k
TT
kkkkk
Qt y
s
uusu u
ss ys

 
B
B
B4
y
,
12 1
T
Tkkk
T
kkk
ss
uu ss
 
B
B,





1
23 2
T
kkkkk k
T
T
Tkk
kk
Qtsy Qt
uu ys
ys


BB , 14
T
Tkk
T
kkk
ys
uu
s
s
 B.
因此



1
2
det
T
T
kkkk k
kk k
TT
T
kkkkkk
kk
Qt yyQt
ss
I
s
sss
 
ys







B
B
BB
,


1
detdet k
kk
T
kkk
Qt
s
s
BB
B
。
令cos ,
TT
kkkkkk
kk
T
kkk kk
s
ss
q
ss
s
s
s


BB
B
,
 






1
det detdetdet
TT
kk k
kk kkk
kk kk
TTTT
k
kkkkkkkkkkkk
Qt QtQt
ys ssm
q
ss ysssss ys
BB BB
BB
T
,
  

22
2
22
22
2
2
()
22
cos cos
T
kkk
Tkkk
kkkk
TTT T
kk kkk kkkkk
TTT
kkk
kkkkkkkkkkkk
k
TT TTT
kkk
kkkkkkkkk kkk
ys
ys
Vss
ys ys ssss
ys
ssss ysMMqq
q
mm
ysssysyss s








 
B
B
B
BB
B
BB
B
,
其中 2cos
TT
kkkkkkkk
T
kk
kk kk
ys ys
M
q
m
ys ms


BB 。



122
2
cos
cos cos
kk
kkkk
kk k
T
kkk
kkkk
MQt
qMMq
tr trq
mm
y

k
q




 


BB .
对对称正定矩阵 B,定义函数
 




In dettr


B
BB,则


0

B。
设12
,,,
n





为B的n个特征根,则
 


1
In detIn0
ii
i
tr


n



BB B

。
函数在 上非正。

1Inhtt t

0,









 

 
111
22
2
In det
2
In
cos
cos cos
2
In111cos
kk k
kk k
kkkkkk
kk
T T
kkk k
kkkkkk
kkkk kk
k k
TT
k
kk kkk
tr
MQ tQ t
qMMqqm
q
mm q
ys ys
Qtm MQtqM
q
m
ys ys






 



 





  


BB B
B
B

 
 
 
22
2
In
cos
In1
1cos2coscos
111In
1cos
kk
k
kk
kkkk
kTT
kk kk
kkkkkkk
k k
kk
Mq q
m
Qtm MQt
ys ys
mMM m
qq
m


 












 




 


 




B
.
假设 。则,有
2
0
limcos 0
k
k

11
0,kkk

21
cos 1
2
k




。
令


2
2
1cos
1cos
k
k
k
T





。则 2
2
1,InIn2 Incos
2cos
kk
k
TT k


。
Copyright © 2012 Hanspub
22
王炜 等  一类修正的广义拟牛顿法解互补问题







 



1
2
In1111 In
In11In1In
In11In2Incos
kkkk
kk kk k
TT
kk kk
kkkk
kkk k
TT
kk kk
kkkk
k k
TT
kk kk
Qtm MQtqT q
ys ys
Qtm MQtqT q
ys ys
Qtm MQt
ys ys
 












 


BB
B
B


2
.
由假设知:对上述的 有
12 1
,0,kk kkk




22
In cosIn11In2
1
kkkk
kTT
kkkk
Qtm MQt
ys ys



 



.
代入上不等式,有







  
1
2
In11In2
1In11In2
kkkk
kk TT
kk kk
kkkk
kTT
kk kk
Qtm MQt
ys ys
Qtm MQt
kk ys ys
 



 





 




BB
B
.
不等式右端趋近于负无穷,矛盾,假设不成立。
这样便存在

k
x
的无穷子列

0
k
N
x和00

,使得对 00
,cos k
kN



。在 假设1条件下,定理 2.3.1成立
[10],利用 Zoutendijk 条件可以推出数列

0
kN
g0。由于


f
x在水平集上是一致凸函数,稳定点与最小值点
是一致的,也是唯一的。这样便可推出点列


k
x
收敛到目标函数的唯一极小值点。
定理 2 在假设 2下,若迭代点列

k
x
收敛到最优解*
x
,步长有界且


k
x
满足 *
1k
k
xx



,则


k
x
超线
性收敛到 *
x
。
证明:类似于文献[6,11,12]中Broyden族算法超线性收敛的证明,可得结论成立。因证明过长在此略。
5. 数值实验
本节在数学软件 matlab 7.0环境下对互补问题进行数值实验,下面是一个经典的非线性互补算例。

22
112234
22
11234
22
112 234
22
1234
32 236
2102
3229
3233
xxxxxx
xxxxx
Fx xxxxx x
xxxx
2
9






 














.
实验中都取 0.4

,0.5

,,表 1中取
5
10


0.55, 0.5t


。
Table 1. Effectiveness of the algorithm
表1. 算法有效性
初始点 最优点 迭代次数 最优值
(2,1,1,1)T (1.2247,0.0000,0.0000,0.5000)T 30 2.8568e–011
(1,4,5,1)T (1.0000,0.0000,3.0000,0.0000)T 24 2.0025e–013
(4,1,1,6)T (1.2247,0.0000,0.0000,0.5000)T 34 1.2085e–012
(100,0.5,0.1,10 )T (1.2247,0.0000,0.0000,0.5000)T 32 3.1677e–012
(10,0.5,10,1)T (1.0000,0.0000,3.0000,0.0000)T 26 6.5622e–013
此互补问题有两组解

62,0,0,1 2T和,所 取 的5个初始点能够求得这两组解,表 1可验证本文

1, 0,3, 0T

Copyright © 2012 Hanspub 23
王炜 等  一类修正的广义拟牛顿法解互补问题
Copyright © 2012 Hanspub
24

算法的有效性和全局收敛性。
表2取初始点 ,格中上一行是最优值,下一行是迭代次数。格中*表示求得解
,不加*表示求得解

。

1, 4, 5,1T

00,0.50001.2247,0.0000,0.00 T1.0000,0.0000,3.0000,0.0000 T
Table 2. Exploration of the calculation speed
表2. 计算速度探索
ρ
t 0.3 0.45 0.5 0.6 0.75 0.9
0.3 6.9099e–014
41 6.9754e–011
46 1.3940e–012
46 7.4963e–013
36 2.1207e–012
31 0.0630
125
0.45 4.0898e–012
52 1.2922e–011
37 8.9246e–013
32 8.8529e–015
33 4.0264e–013
24 1.1747e–012
201
0.5 3.7457e–012
59 3.3100e–014
38 6.5403e–012
31 4.2646e–012
25 8.5990e–013
24 1.4983e–013
138
0.6 1.6075e–012
53 1.2108e–013
39 2.8874e–012
33 2.1244e–013
29 3.8813e–013
26 1.3273e–012
112*
0.75 1.1007e–012
42 2.9526e–013
32 1.0549e–012
31 2.6751e–013
26 8.2304e–014
24 4.4525e–012
81*
0.9 1.6216e–013
37 4.7631e–013
29 1.0725e–011
25 1.6679e–013
25 1.3665e–013
26 4.0754e–012
51*
1 2.5390e–012
30 1.1277e–013
30 3.0698e–013
27 1.4660e–014
24 6.6347e–013
26 8.9073e–016
61
由表 2可知,变化t和

的值,算法的计算速度也会不同。当 0.9, 0.3t


时,最优值是 0.0630,明显不
是恰当的最优值,因此线搜索中

的取值也会影响收敛速度的大小。t的值固定,

在0.6~0.75之间时,计算
速度相对是较快的;

的值固定,t在0.75~1之间时,计算速度相对较快。
通过实验数据分析表明,改进算法具有有效性和全局收敛性,并且具有良好的数值效果和较快的收敛速度,
将参数

和t分别限定在某个范围时,收敛速度达到最快。
6. 结论
本文利用互补函数将互补问题转化为无约束优化问题,再利用修正的广义拟牛顿算法求解。改进后的算法
经数值实验验证有良好的数值效果。本文算法的校正公式中参数

取值时和 Broyden 族校正公式类似,某些取
值可能比 BFGS算法的数值效果更好,还有待深入探索。
参考文献 (References)
[1] G. Maier. A matrix structural theory of piecewise linear elastopl as tic it y with interacting yield planes. Meccanica, 1970, 5(1): 54-66.
[2] 陈万吉, 陈国庆. 接触问题的互补变分原理及非线性互补模型[J]. 计算结构力学及其应用, 1996, 13(2): 138-146.
[3] F. Tin-Loi, S. H. Xia. Nonholonmic elastoplastic ana1ysis involving unilateral frictionless contact as a mixed complementarity problem. Com-
puter Methods in Applied Mechanics and Engineering, 2001, 190(35-36): 4551-4568.
[4] 何素艳, 李建字, 张洪武等. 工程力学中的互补问题: 模型[J]. 计算力学学报, 2004, 21(2): 185-190.
[5] O. L. Mangasarian, M. V. Soldow. Nonlinear complementarity as unconstrained and constrained minimization. Mathematical Programming,
1993, 62(1-3): 277-297.
[6] R. H. Byrd, J. Nocedal and Y. Yuan. Global convergence of a class of quasi-Newton methods on convex problems. SIAM Journal of Numeri-
cal Analysis, 1987, 24(5): 1171-1189.
[7] R. H. Byrd, J. Nocedal. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on
Numerical Analysis, 1989, 26(3): 727-739.
[8] 陈兰平, 焦宝聪. 一类非拟 Neston算法及其收敛性[J]. 应用数学与计算数学学报, 1997, 11(2): 9-17.
[9] C. Kanzow. Nonlinear complementarity as unconstrained optimization. Journal of Optimization Theory and Applications, 1996, 88(1): 139-
155.
[10] 王宜举, 修乃华. 非线性规划理论与算法[M]. 西安: 陕西科学技术出版社, 2008.
[11] D. Sun, L. Qi. On NCP-functions. Computational Optimization and Applications, 1999, 13(1-3): 201-220.
[12] J. Y. Han, D. F. Sun. Newton and quasi-Newton method for normal maps with polyhedral sets. Journal of Optimization Theory and Applica-
tions, 1997, 94(3): 659.

版权所有:汉斯出版社 (Hans Publishers) Copyright © 2012 Hans Publishers Inc. All rights reserved.