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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
Operations Research and Fuzziolgy 运筹与模糊学, 2013, 3, 1-6
http://dx.doi.org/10.12677/orf.2013.31001 Published Online February 2013 (http://www.hanspub.org/journal/orf.html)
Subgradient Algorithm for a Form of
Mixed Variational Inequalities
Chao Zheng, Hongyou Yin, Yuanping Wang
College of Sciences, Nanjing University of Aeronautics and Astronautics, Nanjing
Email: xuzhouzhengchao@sina.com, zhengchao_math@163.com
Received: Dec. 9th, 2012; revised: Jan. 7th, 2013; accepted: Jan. 18th, 2013
Abstract: This paper studies a form of mixed variational inequalities problem. When disturbance function is
nonsmooth, the optimal condition of these mixed variational inequalities is proposed. Then subgradient is of-
fered and its convergence is proved.
Keywords: Mixed Variational Inequalities; Nonsmooth; Optimal Condition; Subgradient
一类混合变分不等式的次梯度法
郑 超,殷洪友,王园萍
南京航空航天大学理学院,南京
Email: xuzhouzhengchao@sina.com, zhengchao_math@163.com
收稿日期:2012 年12 月9日;修回日期:2013年1月7日;录用日期:2013年1月18日
摘 要:本文研究了一类混合变分不等式问题.在扰动泛函非光滑的情况下,给出了这类混合变分不等
式的最优性条件,设计了次梯度算法,并证明了该算法的收敛性。
关键词:混合变分不等式;非光滑;最优性条件;次梯度法
1. 引言
“变分不等式”是计算数学与运筹学的一个交叉研究领域,与非线性规划、互补问题、最优化理论、广
义方程、对策论、不动点理论等分支有密切的联系。它作为一类数学模型应用在如力学、工程学、经济学和
运筹学等诸多领域。对于经典的Hartman-Stampacchia 变分不等式的理论与算法方面的研究可见文献[1]和文献
[2]。设 是一个实线性空间,
n
R,, n
x
xxx R,
K
是中的一个闭凸锥,映射
n
R:n
f
KR,:
F
KR
是中的凸泛函,本文考虑广泛应用在弹性塑料学领域的混合变分不等式问题[3]:求
n
R
x
K
,使得






,0,
x
xfxFx FxxK
 

(1)
显然,若F是零泛函,则(1)就是经典 Hartman变分不等式:求
x
K


,使得


,0,
x
xfx xK



混合变分不等式问题比一般的变分不等式问题更加具有代表性,从而研究混合变分不等式问题具有更广
泛的适用范围。对于混合变分不等式问题的研究一般分为理论与算法,前者主要研究解的存在性、唯一性;
后者则主要建立在有效的算法及收敛性分析。文献[4]给出了在 Banach 空间混合变分不等式与 F-互补问题的
等价性,文献[5]提供了混合变分不等式的投影算法,文献[6]假设扰动泛函F非光滑的情况下,给出了投影梯
度算法。
Copyright © 2013 Hanspub 1
郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性
本文在扰动泛函非光滑的情况下,第二章给出了所需的定义和引理,第三章证明了这类混合变分不等式问
题的最优性条件,第四章设计了次梯度算法并对算法的收敛性进行了理论证明。
本文记凸规划问题:求
x
K
,使得









min
xK
PxFxPx Fx


  (2)
2. 预备知识
定义 2.1 设 是非空凸集,若
n
R ,0


 ,则称

是锥。若还有

,则称 是凸锥。 
定义 2.2 设n
K
R是非空开凸集,
f
是
K
上的凸函数,
x
K

,称集合
 

,,
n
f
xvRfyfxvyxyK 
是
f
在
x
处的次微分,称 是

vfx
f
在
x
处的次梯度。
定义 2.3 设n
K
R是非空开凸集且 0
x
K

,记






00
0,
x
vxx xK

 ,则称
 
00
x
x

 是
在点
K0
x
处的可行方向锥。
定义 2.4 设 是锥,则集合
n
R


,0,
n
yR xyx

 称为

的共轭锥。
引理 2.1 设
f
是
K
上的凸函数,则
f
在
K
的每一点都上半连续。
引理 2.2[7] 假设 ,若Pf

x
是(1)的解,且 P

是凸函数,则
x

是(2)的解;反之,若
x
是(2)的解,则
x

也
是(1)的解。
3. 最优性条件
为方便叙述,本节记凸规划问题:





 

min ,min
xK xK

x
f xFxPxFx


  (3)
定理 3.1
x
K
是(3)的最优解当且仅当







,1
min;; 0
gxg
Pxg Fxg


 


 (4)
证:设
x
是(3)的最优解,若(4)不成立,则存在单位向量


0
g
x


,使得







00
00
00
;;lim lim
PxgPxFxgFx
Pxg Fxg







 

 0


由极限的保号性,存在 00

,使得








00
0
0, 0,
PxgPxFxgFx






 

即









00 ,0,Px gFx gPxFx0



 

由于

0
g
x


,因此


0,0,
g
xx xK


 
于是当

充分小时有




01
x
gxxxx xK

 
 
这与
x
是(3)的最优解矛盾。
反之,设(3)成立, ,
x
Kx x

 ,有
Copyright © 2013 Hanspub
2
郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性
 








max ,max,
max ,max,
vPx uFx
vPx uFx
Px Fx
Pxvx xFxux x
xx xx
Pxx xvFxx xu
xx xx


 
 

 

 

 

 

(5)
记0
x
x
g
x
x



,则 01g,且

0
g
x
 ,有(4)和(5)得
 




  





 



 
00 00
00
00
00
00
,1 ,1
00
,1
max ,max,
;;
min ;min;
min ;;
vPx uFx
gxg gxg
gxg
Px Fx
Px xxvgFx xxug
PxxxPxgFxxxFxg
PxxxP x gFxxxFx g
PxFxxxP x gFx g
Px Fx

 

 
 
 
 
  
 
 


 

  



 

即
x
是(3)的最优解。
引理 3.1 设 是闭凸集,且,令
n
CRfr
C 1
min sup,,min,min
fr
gvC
vC
vg dvv




vC
则a)当 时,有
0dd

 ;b)当 时,有
0d


。
证:a) 当时,有0d0C

,从而存在 0
vC

,使 0
min
vC
dv

v,
即 是在 上的投影,于是
0
v0xC2
00
,,vvvv C。
令0
0
0
v
gv
 ,即 00
,,vgvvC

,
从而
00
1
minsup ,sup ,
gvC vC
vgvgv d


.
另一方面, ,
n
gRg 1,有 00 0
sup ,,
vC
vgv gvgvd

。
从而
0.vd


综上所述,有 0
vd

。
b) 当 ,有,从而
0d0C1
min sup,0
gvC
vg


。
如果 0
f
r
C,则 0

,由边界点的凸集分离定理,存在单位向量 0
n
g
R,使得 0
,0,vgv C,从而
0
0sup,vg


 0
,因此 0



C
。
vC
如果 ,则,于是0intC

0S

,
n
gRg1,有

0
max ,supvg ,
vS vC
vg



,
从而
1
min sup,
gvC
vg



。
以下证明

。
如果

,则 ,则存在向量,使
 
0SS

00
v


00vS

,但 0
vC

,根据凸集分离定理,存在单位
Copyright © 2013 Hanspub 3
郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性
向量 0
n
g
R和数 0

,使得 00
,,vvg vC

。
于是 000 0
1
minsup ,sup ,,
gvC vC
vgvgv gv



,即 0
v


,这与 相矛盾,因此

00vS



。 
推论 3.1 在引理 1的条件下,如果 0
00
0
min 0,
vC
v
vvdg
v

,则 00
sup ,
vC
vgv d



。
推论 3.2 在引理 1的条件下, 000dC

。
引理 3.2 设是紧凸集,是闭凸锥,
n
BRn
R


是

的共轭锥,令
,1 1
,minmax,,min sup,
gg g
vB vC
C Bvgvg


 

 
则

。
证:已知 是紧凸集,则B
12
12
sup ,max,max,
vB v
vC
vgvgvg



 。
当 时,有g 2,vg0,从而
2
2
max ,0
v
vg



。
当 时,则存在,使g 2
v
 2,0vg
,
从而

2
22 2
sup ,,,,
v
vg vgvg
 




,于是 1
1
max, ,
sup ,
,
vB
vC
vgg
vg
g




 


,
因此
1,1
min sup,minmax,
ggg
vB
vC
vg vg




 。
推论 3.3 在引理 3.2 的条件下,如果sup ,
vC
vg


 ,则 g

且sup ,max ,
vB
vC
vg vg


。
定理 3.2 设
x
K
是凸规划(3)的最优解当且仅当






0
f
xFx x


。
证:在引理3.2 中取
 


,,BPxFxxCB
 
 

,注意到


,Pxxf x

以及 的光滑性,
则








,1 1
,1
min;;minmax,min sup,
gg g
gxg fx vBfx vC
Pxg Fxgfxvgfxvg


 
 
  

。
是凸规划(3)的最优解的充要条件是







,1
min;; 0
gxg
Pxg Fxg


 


, 根据定理3.1,
x
即0

。根据推论 3.2,有000dC

 。于是
x

是凸规划问题(3)的最优解

0
f
xFx x


。
推论 3.4 设int
x
K
,则
x
是(3)的最优解当且仅当




0fx Fx


。
设0
x
不是(3)的最优解,根据定理 3.2,有






00
0fx Fxx


0
0
,于是存在向量 ,

00
vFx

0
wx

 ,使得

 



00
0000
,
min 0
vFx wx
dxfxv wfxvw

 

0
。
定义 3.1 设0
x
K不是(3)的最优解,若存在单位向量


00
g
x ,使得








0
00 0000
,1
;;min;
gxg
PxgFxgPxg Fxg
 
 
 ;
则称 0
g
是(3)在0
x
处的最速下降方向。
定理 3.3 设0
x
K不是(3)的最优解,向量




000
,vFxw x

 0
满足条件


 




00
0000
,
min 0
vFx wx
dxfxv wfxvw

 

0

Copyright © 2013 Hanspub
4
郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性
则


000
0
000
f
xvw
g
f
xvw

  是(3)在0
x
处的最速下降方向,且





0000
,;dxfxgFxg

 0
证:设
 
00 0
,,Bfx FxxCB

 ,根据引理 3.2,有

 



00
00 0
,1 ,1
min,;min max,
gxgg gfx vB
fx gFxgfxvg



 
由于 0
x
不是最优解,则


00ddx。
根据推论3.1 有


0
00
sup ,
fx vC
fx vgd



。
根据推论3.3 有

00
g
x ,且









0 0
0
000000000 0
sup,max,,max ,,;
fxvBv Fx
fx vC
0
f
xvgfxvg fxgvg fxgFxg
 


 。
因此
 



 


0
0
00000 000
,1
,;sup ,min,
gxg
fx vC
;
f
xgFxgfxvgfxgFxg

 


 ,即 0
g
是(3)的最速下
降方向。

4. 算法及收敛性
算法
Step1 取初始点 ,选取数列
0,xKk0


k

满足 ;
0
0, 0,,
kk k
k
k
 


 

Step2 若



0kk

k
f
xFx x

,则停止;否则,转 Step3;
Step3 计算向量


,
kkk
vFxw x

 

k
,满足


 




,
min 0
kk
kkkk
vFx wx
dxfx vwfx vw

 

k

并且计算


kkk
k
kkk
f
xvw
g
f
xvw

  ;
Step4 令1kkkk
x
xg

 ,,转 Step2。 1kk
引理 4.1 是单调映射。 F

定理 4.1 设
f
是单调映射,

k
x
是由算法4.1 产生的点列,若 k
x
不是凸规划问题的解,则对任意(3)的解
x

,
且

kkk k
g
fxxx

 F,必存在常数 ,使得0
k
T

1,0,
kk k
xxx T


 
x
 ;且若凸规划问题有
最优解,则

k
x
的任一极限点都是凸规划问题的解;若还有扰动泛函
F
是严格凸函数,则混合变分不等式有唯
一的最优解。
证:注意到
 






,0
kkk k
g
fx Fxxfx Fxx

 

,且由 F

 的单调性可知



,0
kk k
gfx fxxx



即



,,
kkk k
gx xfxfxx x

 0

直接计算
222
2
12,
kkkkkkkkk
x
xxgxxx gxx




。
Copyright © 2013 Hanspub 5
郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性
Copyright © 2013 Hanspub
6
若取 2,
kkk
g
xx


,则有 1kk
x
xxx

。
令2,
kkk
Tgxx


,则 ,且0
k
T1kk
x
xxx


,
从而序列

k
x
有界,则必存在聚点,下证

k
x
的任一聚点都是凸规划问题(3)的解。
设

i
k
x
是

k
x
的任一收敛子列,且 limi
k
i
x
x



,从而有






0ii
kk i
k
f
xFx x


于是
 


0
f
xFx x



。
即
x
是凸规划问题(3)的最优解。当扰动 泛函
F
为严格凸函数时,凸规划问题有唯一解,从而混合变分不等
式只有唯一解。

5. 结论
本文通过将混合变分不等式问题转化为凸规划问题,在扰动泛函 F非光滑的情况下,给出了混合变分不等
式的最优性条件,设计了次梯度算法并证明了该算法的收敛性。从算法步骤可以看出,次梯度算法迭代简单,
比较容易实现,在每一迭代点处只要能够计算到目标函数次微分中一个元素就可以。另一方面,次梯度法不需
要线搜索,步长 k

事先给出,只要满足条件
0
0, 0,,
kkk
k
k
 




即可。在这里,条件 是要使点列

0
k
k






k
x
全局收敛所必须的。但是作为最早提出的非光滑优化算法,次
梯度法有许多不足之处,一是收敛速度慢;二是次梯度法甚至不是下降方向。所以是否可以在迭代过程中通过
预测–校正的思想进行调整,从而加快迭代速度也有待深入探索。最后,作者对审稿人提出的修改意见表示感
谢。
参考文献 (References)
[1] P. T. Harker, J. S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and
applications. Mathematica Programming, 1900, 48(2): 161-220.
[2] F. Facchinei, J. S. Pang. Finite-dimensional variational inequalities and complementarity problems. New York: Springer-Verlag, 2003.
[3] W. Han, B. Reddy. On the finite element method for mixed variational inequalities arising in elastoplasticity. SIAM Journal on Numerical
Analysis, 1995, 32(6): 1778-1807.
[4] 殷洪友, 徐成贤, 张忠秀. F-互补问题及其与极小元问题的等价性[J]. 数学学报, 2001, 4: 679-686.
[5] 何诣然. 一个关于混合变分不等式问题的投影算法[J]. 数学物理学报, 2007, 27A(2): 215-220.
[6] 唐国吉, 黄南京. 非Lipschitz 集值混合变分不等式的一个投影次梯度法法[J]. 应用数学和力学, 2011, 32(10): 1254-1263.
[7] 李娟. F-互补问题的算法设计[D]. 南京航空航天大学, 2010.
[8] 韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法[M]. 上海: 上海科学技术出版社, 2006.
[9] 高岩. 非光滑优化[M]. 北京: 科学出版社, 2008.

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