|Table of Contents|

The Stochastic Descent Algorithm for a Kind ofSemidefinite Variational Inequality Problem(PDF)


Research Field:
Publishing date:


The Stochastic Descent Algorithm for a Kind ofSemidefinite Variational Inequality Problem
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)
semidefinite variational inequality problemcorrection projection and contraction algorithmstochastic descent algorithmprobability convergence
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.


[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.


Last Update: 1900-01-01