On the Convergence Rate of a Class of Proximal-Based Decomposition Methods for Monotone Variational Inequalities

详细信息    查看全文

• 作者：Xiang-Feng Wang
• 关键词：Variational inequality ; Proximal point algorithm ; Iteration complexity ; Relative error ; Convergence rate ; Error bound ; 65K05 ; 65K15 ; 90C30 ; 90C33
• 刊名：Journal of the Operations Research Society of China
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：3
• 期：3
• 页码：347-362
• 全文大小：449 KB
• 参考文献：1.Chen, C.H., He, B.S., Yuan, X.M.: Matrix completion via an alternating direction method. IMA J. Numer. Anal. 32(1), 227鈥?45 (2012)MathSciNet CrossRef MATH
  2.Wang, X.F., Yuan, X.M.: The linearized alternating direction method of multipliers for Dantzig selector. SIAM J. Sci. Comput. 34(5), A2792鈥揂2811 (2012)MathSciNet CrossRef MATH
  3.Yang, J.F., Zhang, Y.: Alternating direction algorithms for \(l_1\) -problems in compressive sensing. SIAM J. Sci. Comput. 33(1), 250鈥?78 (2011)MathSciNet CrossRef MATH
  4.Yuan, X.M.: Alternating direction method for covariance selection models. J. Sci. Comput. 51(2), 261鈥?73 (2012)MathSciNet CrossRef MATH
  5.Martinet, B.: Regularization d鈥檌nequations variationelles par approximations sucessives. Rev. Francaise Info. Rech. Oper. 4, 154鈥?59 (1970)MathSciNet MATH
  6.Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97鈥?16 (1976)MathSciNet CrossRef MATH
  7.Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877鈥?98 (1976)MathSciNet CrossRef MATH
  8.Chen, G., Teboulle, M.: A proximal-based decomposition method for convex minimization problems. Math. Progr. 64(1), 81鈥?01 (1994)MathSciNet CrossRef MATH
  9.He, B.S., Liao, L.Z., Han, D.R., Yang, H.: A new inexact alternating directions method for monotone variational inequalities. Math. Progr. 92(1), 103鈥?18 (2002)MathSciNet CrossRef MATH
  10.He, B.S., Yuan, X.M.: On the O(1/n) convergence rate of the Douglas鈥揜achford alternating direction method. SIAM J. Numer. Anal. 50(2), 700鈥?09 (2012)
  11.Eckstein, J., Bertsekas, D.P.: On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Progr. 55(1), 293鈥?18 (1992)MathSciNet CrossRef MATH
  12.Fukushima, M.: Application of the alternating direction method of multipliers to seperable convex programming problems. Comput. Optim. Appl. 2, 93鈥?11 (1992)MathSciNet CrossRef
  13.Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17鈥?0 (1976)CrossRef MATH
  14.He, B.S., Yuan, X.M.: The uniform framework of some proximal-based decomposition methods for monotone variational inequalities with separable structure. Pac. J. Optim. 8(4), 817鈥?44 (2012)MathSciNet MATH
  15.Nemirovski, A.: Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229鈥?51 (2004)
  16.Tseng, P.: On accelerated proximal gradient methods for convex鈥揷oncave optimization. Technical Report, University of Washington (2008)
  17.Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence o(\(1/k^2\) ). In: Doklady Akademii nauk SSSR, vol 269, pp. 543鈥?47 (1983)
  18.Facchinei, J., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I. Springer Series in Operations Research. Springer, New York (2003)
  19.Nesterov, Y.: Gradient methods for minimizing composite objective function. Technical Report (2007)
  20.He, B.S., Yuan, X.M.: On nonergodic convergence rate of Douglas鈥揜achford alternating direction method of multipliers. Numer. Math. (2015)
  
• 作者单位：Xiang-Feng Wang (1)
  
  1. Shanghai Key Lab for Trustworthy Computing, Software Engineering Institute, East China Normal University, Shanghai, 200062, China
  
• 刊物主题：Operations Research, Management Science;
• 出版者：Springer Berlin Heidelberg
• ISSN：2194-6698

文摘

A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012, while only global convergence is proved at the same time. In this paper, we give a unified proof on the \(\mathcal{{O}}(1/t)\) iteration complexity, together with the linear convergence rate for this kind of proximal-based decomposition methods. Besides the \(\varepsilon \)-optimal iteration complexity result defined by variational inequality, the non-ergodic relative error of adjacent iteration points is also proved to decrease in the same order. Further, the linear convergence rate of this algorithm framework can be constructed based on some special variational inequality properties, without necessary strong monotone conditions. Keywords Variational inequality Proximal point algorithm Iteration complexity Relative error Convergence rate Error bound