一类混合变分不等式的次梯度法 Subgradient Algorithm for a Form of Mixed Variational Inequalities

doi:10.12677/ORF.2013.31001

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

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]。设是一个实线性空间，

R,, n

xxx R，

是中的一个闭凸锥，映射

R:n

KR，:

KR

是中的凸泛函，本文考虑广泛应用在弹性塑料学领域的混合变分不等式问题[3]：求

，使得













,0,

xfxFx FxxK

 



(1)

显然，若F是零泛函，则(1)就是经典 Hartman变分不等式：求





，使得





,0,

xfx xK







混合变分不等式问题比一般的变分不等式问题更加具有代表性，从而研究混合变分不等式问题具有更广

泛的适用范围。对于混合变分不等式问题的研究一般分为理论与算法，前者主要研究解的存在性、唯一性；

后者则主要建立在有效的算法及收敛性分析。文献[4]给出了在 Banach 空间混合变分不等式与 F-互补问题的

等价性，文献[5]提供了混合变分不等式的投影算法，文献[6]假设扰动泛函F非光滑的情况下，给出了投影梯

度算法。

郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性

本文在扰动泛函非光滑的情况下，第二章给出了所需的定义和引理，第三章证明了这类混合变分不等式问

题的最优性条件，第四章设计了次梯度算法并对算法的收敛性进行了理论证明。

本文记凸规划问题：求

，使得



















min

PxFxPx Fx





  (2)

2. 预备知识

定义 2.1 设是非空凸集，若

R ,0



 ，则称



是锥。若还有



，则称是凸锥。 

定义 2.2 设n

R是非空开凸集，

是

上的凸函数，



，称集合

 



xvRfyfxvyxyK 

是

在

处的次微分，称是



vfx

在

处的次梯度。

定义 2.3 设n

R是非空开凸集且 0



，记













vxx xK



 ，则称

 



 是

在点

处的可行方向锥。

定义 2.4 设是锥，则集合

R





,0,

yR xyx



 称为



的共轭锥。

引理 2.1 设

是

上的凸函数，则

在

的每一点都上半连续。

引理 2.2[7] 假设，若Pf



是(1)的解，且 P



是凸函数，则



是(2)的解；反之，若

是(2)的解，则



也

是(1)的解。

3. 最优性条件

为方便叙述，本节记凸规划问题：











 



min ,min

xK xK



f xFxPxFx





  (3)

定理 3.1

是(3)的最优解当且仅当















min;; 0

gxg

Pxg Fxg





 





 (4)

证：设

是(3)的最优解，若(4)不成立，则存在单位向量









，使得















;;lim lim

PxgPxFxgFx

Pxg Fxg











 



 0





由极限的保号性，存在 00



，使得

















0, 0,

PxgPxFxgFx







 



即



















00 ,0,Px gFx gPxFx0







 



由于







，因此





0,0,

xx xK





 

于是当



充分小时有









gxxxx xK



 

 

这与

是(3)的最优解矛盾。

反之，设(3)成立， ,

Kx x



 ，有

郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性

 



max ,max,

vPx uFx

Px Fx

Pxvx xFxux x

xx xx

Pxx xvFxx xu

xx xx



 

 



 



 



 



 



(5)

记0





，则 01g，且



x

 ，有(4)和(5)得

 



  







 







 

00 00

,1 ,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



 



 

 

 

  

 

 





 



  







 



即

是(3)的最优解。

引理 3.1 设是闭凸集，且，令

CRfr

C 1

min sup,,min,min

gvC

vg dvv









vC

则a)当时，有

0dd



 ；b)当时，有

0d





。

证：a) 当时，有0d0C



，从而存在 0



，使 0

min



v，

即是在上的投影，于是

v0xC2

,,vvvv C。

令0

 ，即 00

,,vgvvC



，

从而

minsup ,sup ,

gvC vC

vgvgv d





.

另一方面， ,

gRg 1，有 00 0

sup ,,

vgv gvgvd



。

从而

0.vd





综上所述，有 0



。

b) 当，有，从而

0d0C1

min sup,0

gvC





。

如果 0

C，则 0



，由边界点的凸集分离定理，存在单位向量 0

R，使得 0

,0,vgv C，从而

0sup,vg





 0

，因此 0







C

。

如果，则，于是0intC





gRg1，有



max ,supvg ,

vS vC





，

从而

min sup,

gvC







。

以下证明



。

如果



，则，则存在向量，使

 

0SS



00





00vS



，但 0



，根据凸集分离定理，存在单位

郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性

向量 0

R和数 0



，使得 00

,,vvg vC



。

于是 000 0

minsup ,sup ,,

gvC vC

vgvgv gv







，即 0





，这与相矛盾，因此



00vS







。 

推论 3.1 在引理 1的条件下，如果 0

min 0,

vvdg



，则 00

sup ,

vgv d







。

推论 3.2 在引理 1的条件下， 000dC



。

引理 3.2 设是紧凸集，是闭凸锥，

BRn

R





是



的共轭锥，令

,1 1

,minmax,,min sup,

gg g

vB vC

C Bvgvg





 



 

则



。

证：已知是紧凸集，则B

sup ,max,max,

vB v

vgvgvg







 。

当时，有g 2,vg0，从而

max ,0







。

当时，则存在，使g 2

v

 2,0vg

，

从而



22 2

sup ,,,,

vg vgvg

 









，于是 1

max, ,

sup ,

vgg







 





，

因此

1,1

min sup,minmax,

ggg

vg vg







 。

推论 3.3 在引理 3.2 的条件下，如果sup ,





 ，则 g



且sup ,max ,

vg vg



。

定理 3.2 设

是凸规划(3)的最优解当且仅当













xFx x





。

证：在引理3.2 中取

 





,,BPxFxxCB

 

 



，注意到



,Pxxf x



以及的光滑性，

则















,1 1

min;;minmax,min sup,

gg g

gxg fx vBfx vC

Pxg Fxgfxvgfxvg





 

 

  



。

是凸规划(3)的最优解的充要条件是















min;; 0

gxg

Pxg Fxg





 





，根据定理3.1，

即0



。根据推论 3.2，有000dC



 。于是



是凸规划问题(3)的最优解



xFx x





。

推论 3.4 设int

，则

是(3)的最优解当且仅当









0fx Fx



。

设0

不是(3)的最优解，根据定理 3.2，有













0fx Fxx





，于是存在向量，



vFx





 ，使得



 







0000

min 0

vFx wx

dxfxv wfxvw



 



。

定义 3.1 设0

K不是(3)的最优解，若存在单位向量





x ，使得

















00 0000

;;min;

gxg

PxgFxgPxg Fxg

 

 

 ;

则称 0

是(3)在0

处的最速下降方向。

定理 3.3 设0

K不是(3)的最优解，向量









000

,vFxw x



 0

满足条件





 









0000

min 0

vFx wx

dxfxv wfxvw



 





郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性

则



000

xvw



  是(3)在0

处的最速下降方向，且











0000

,;dxfxgFxg



 0

证：设

 

00 0

,,Bfx FxxCB



 ，根据引理 3.2，有



 





00 0

,1 ,1

min,;min max,

gxgg gfx vB

fx gFxgfxvg







 

由于 0

不是最优解，则





00ddx。

根据推论3.1 有



sup ,

fx vC

fx vgd







。

根据推论3.3 有



x ，且













0 0

000000000 0

sup,max,,max ,,;

fxvBv Fx

fx vC

xvgfxvg fxgvg fxgFxg

 





 。

因此

 



 





00000 000

,;sup ,min,

gxg

fx vC

;

xgFxgfxvgfxgFxg



 





 ，即 0

是(3)的最速下

降方向。



4. 算法及收敛性

算法

Step1 取初始点，选取数列

0,xKk0







满足；

0, 0,,

kk k

 





 



Step2 若







0kk



xFx x



，则停止；否则，转 Step3；

Step3 计算向量





kkk

vFxw x



 



，满足





 









min 0

kkkk

vFx wx

dxfx vwfx vw



 





并且计算



kkk

xvw



  ；

Step4 令1kkkk



 ，，转 Step2。 1kk

引理 4.1 是单调映射。 F



定理 4.1 设

是单调映射，



是由算法4.1 产生的点列，若 k

不是凸规划问题的解，则对任意(3)的解



，

且



kkk k

fxxx



 F，必存在常数，使得0

T



1,0,

kk k

xxx T





 

 ；且若凸规划问题有

最优解，则



的任一极限点都是凸规划问题的解；若还有扰动泛函

是严格凸函数，则混合变分不等式有唯

一的最优解。

证：注意到

 













kkk k

fx Fxxfx Fxx



 



，且由 F



 的单调性可知







kk k

gfx fxxx







即







kkk k

gx xfxfxx x



 0



直接计算

222

12,

kkkkkkkkk

xxgxxx gxx









。

郑超  带有非自治项的非线性 Schrödinger 方程的基态解的存在性

若取 2,

kkk





，则有 1kk

xxx



。

令2,

kkk

Tgxx





，则，且0

T1kk

xxx



，

从而序列



有界，则必存在聚点，下证



的任一聚点都是凸规划问题(3)的解。

设



是



的任一收敛子列，且 limi







，从而有













0ii

kk i

xFx x





于是

 





xFx x







。

即

是凸规划问题(3)的最优解。当扰动泛函

为严格凸函数时，凸规划问题有唯一解，从而混合变分不等

式只有唯一解。



5. 结论

本文通过将混合变分不等式问题转化为凸规划问题，在扰动泛函 F非光滑的情况下，给出了混合变分不等

式的最优性条件，设计了次梯度算法并证明了该算法的收敛性。从算法步骤可以看出，次梯度算法迭代简单，

比较容易实现，在每一迭代点处只要能够计算到目标函数次微分中一个元素就可以。另一方面，次梯度法不需

要线搜索，步长 k



事先给出，只要满足条件

0, 0,,

kkk

 









即可。在这里，条件是要使点列















全局收敛所必须的。但是作为最早提出的非光滑优化算法，次

梯度法有许多不足之处，一是收敛速度慢；二是次梯度法甚至不是下降方向。所以是否可以在迭代过程中通过

预测–校正的思想进行调整，从而加快迭代速度也有待深入探索。最后，作者对审稿人提出的修改意见表示感

谢。

参考文献 (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.