[1]徐海文,孙黎明.一类半正定变分不等式的随机下降算法[J].南京师范大学学报(自然科学版),2017,40(01):6.[doi:10.3969/j.issn.1001-4616.2017.01.002]
 Xu Haiwen,Sun Liming.The Stochastic Descent Algorithm for a Kind ofSemidefinite Variational Inequality Problem[J].Journal of Nanjing Normal University(Natural Science Edition),2017,40(01):6.[doi:10.3969/j.issn.1001-4616.2017.01.002]
点击复制

一类半正定变分不等式的随机下降算法()
分享到:

《南京师范大学学报》(自然科学版)[ISSN:1001-4616/CN:32-1239/N]

卷:
第40卷
期数:
2017年01期
页码:
6
栏目:
·数学与计算机科学·
出版日期:
2017-03-31

文章信息/Info

Title:
The Stochastic Descent Algorithm for a Kind ofSemidefinite Variational Inequality Problem
文章编号:
1001-4616(2017)01-0006-07
作者:
徐海文1孙黎明2
(1.中国民用航空飞行学院计算机学院,四川 广汉 618307)(2.南京审计大学理学院,江苏 南京211815)
Author(s):
Xu Haiwen1Sun Liming2
(1.College of Computer Science and Technology,Civil Aviation Flight University of China,Guanghan 618307,China)(2.College of Science,Nanjing Audit University,Nanjing 211815,China)
关键词:
半正定变分不等式问题校正投影收缩算法随机下降算法依概率收敛
Keywords:
semidefinite variational inequality problemcorrection projection and contraction algorithmstochastic descent algorithmprobability convergence
分类号:
O221
DOI:
10.3969/j.issn.1001-4616.2017.01.002
文献标志码:
A
摘要:
校正投影收缩算法的下降量证明中多次使用了放大不等式,因此本文利用满足固定均值的随机数适当扩张步长,得到了一类半正定变分不等式问题的随机下降算法. 在适当的假设条件下,利用马尔可夫不等式和依概率收敛的性质,给出了随机下降算法的依概率收敛性证明. 通过一系列的数值试验验证了随机下降算法的有效性,并且表明了合理选择随机数的均值和方差可以提高随机下降算法的计算效率.
Abstract:
The amplification inequality is used for many times in the proof of drop function of correction projection and contraction algorithm,so we propose the stochastic descent algorithm for a class of semidifinite variational inequality problem through the random steplength extension with the random number series satisfying the Gaussian distribution or Uniform distribution and these random number series have a fixed mean. Subsequently,the probability convergence of stochastic descent algorithm is provided by the properties of Markov’s inequality and probability convergence under some suitable conditions. Finally,some numerical experiments show the effectiveness and efficiency of the stochastic descent algorithm,and reasonable selecting mean and variance of random number can improve the efficiency of the algorithm.

参考文献/References:

[1] ALIZADEH F. Interior point methods in semidefinite programming with application to combinatorial optimization[J]. SIAM J Optim,1995(5):13-51.
[2]KOJIMA M,SHINDOH S,HARA S. Interior-point methods for the monotone semidefinite linear complementarity problems in Symmetric Matrices[J]. SIAM J Optim,1997(7):86-125.
[3]SHIDA M,SHINDOH S. Monotone semidefinite complementarity problems[R]. Tokyo:Tokyo Institute of Technology,1996.
[4]GOWDA S M,SONG Y G. On semidefinite complementarity problems[J]. Math Program,2000(88):575-587.
[5]DANTZIG G B,COTTLE R W. Positive(semidefinite)matrices and mathematical programming[J]. Report ORC,1963(13):63-18.
[6]FERRIS M C,PANG J S. Engineering and economic applications of complementarity problems[J]. SIAM Rev,1997(39):669-713.
[7]BOYD S,GHOUI L E,RERON E,et al. Linear matrix inequalities in system and control theory[M]. Siam Stud Appl Math,Philadelphia:SIAM,1994.
[8]HARKER P T,PANG J S. Finite-dimensional variational inequality and nonlinear complementartity problems:a survey of theory,algorithms and applications[J]. Math Program,1990(48):161-220.
[9]FACCHINEI F,PANG J S. Finite-dimensional variational inequalities and complementarity problems,Vol.Ⅰand Ⅱ[M]. Springer Series in Operations Research. New York:Springer Verlag,2003.
[10]MONTEIRO R D C,ZANJACOMO P R. General interior-point maps and existence of weighted paths for nonlinear semidefinite complementarity problems[J]. Math Oper Res,2000,25(3):381-399.
[11]SIM C K,ZHAO G. Asymptotic behavior of Helmberg-Kojima-Monteiro(HKM)paths in interior-point methods for monotone semidefinite linear complementarity problems:general theory[J]. J Optimiz Theory App,2008(137):11-25.
[12]TSENG P. Merit functions for semidefinite complementarity problems[J]. Math Program,1998(83):159-185.
[13]CHEN X,TSENG P. Non-interior continuation methods for solving semidefinite complementarity problems[J]. Math Program,2003,95(3):431-474.
[14]KANZOW C,NAGEL C. Semidefinite programs:new search directions,smoothing-type methods,and numerical results[J]. SIAM J Optim,2002,13(1):1-23.
[15]HE B S,LIAO L Z. Improvements of some projection methods for monotone nonlinear variational inequalities[J]. J Optimiz Theory App,2002,112(1):111-128.
[16]HE B S,XU M H. A general framework of contraction methods for monotone variational inequalities[J]. Pac J Optim,2008,4(2):195-212.
[17]HE B S,TAO M,YUAN X M. Alternating direction method with Gaussian back substitution for separable convex programming[J]. SIAM J Optim,2012(22):313-340.
[18]HAN D R,YUAN X M. A note on the alternating direction method of multipliers[J]. J Optimiz Theory App,2012,155(1):227-238.
[19]CAI X J,HAN D R,Xu L L. An improved first-order primal-dual algorithm with a new correction step[J]. J Glonal Optim,2013,57(4):1 419-1 428.
[20]徐海文,张黔川,杨成,等. 一类半正定变分不等式的CPC算法[J]. 四川师范大学学报(自然科学版),2009,32(4):450-453.
[21]BHATIA R. Matrix Analysis[M]. New York:Springer-Verlag,1997:3-6.
[22]林正炎,陆传荣,苏中根. 概率极限理论基础[M]. 北京:高等教育出版社,2003:16-17.

备注/Memo

备注/Memo:
收稿日期:2016-10-16.
基金项目:国家自然科学基金(U1233105).
通讯联系人:徐海文,博士生,副教授,研究方向: 最优化理论与算法. E-mail:xuhaiwen_dream@163.com
更新日期/Last Update: 1900-01-01