On the Convergence and O(1/N) Complexity of a Class of Nonlinear Proximal Point Algorithms for Monotonic Variational Inequalities

Jian Wu, Gaohang Yu


This paper presents a class of proximal point algorithms using a nonlinear proximal term for monotonic variational inequality problems. This work extents proximal point algorithms using Bregman distance for minimization problems, and differs with J. Eckstein's approximate iterations in Bregman-function-based proximal algorithms (1998). We study the convergence of the proposed algorithms  and obtain a $O(1/N)$ computing complexity/convergence rate of the algorithms. Further more, connections to some existed popular methods were given, which shows that our algorithm can include these methods within a general form.


A. Auslender, M. Teboulle, Lagrangian duality and related multiplier methods for variational inequality problems, SIAM Journal of Optimization 10(4), 1097-1115(2000)

J. Burke, J. Qian, On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating, Mathematical Programming. 88(1), 157-181 (2000)

Y. Censor and S. Zenios, Proximal Minimization Algorithm with D-Functions, Journal of Optimization Theory and Applications, 73(3), (1992).

Eckstein, J.: Approximate iterations in Bregman-function-based proximal algorithms. Mathematical Programming, Ser. A 83(1), 113-123(1998)

M. Ferris,J. Pang, Engineering and economic applications of complementarity problems. SIAM Rev. 39(4), 669-713 (1997)

He, B.S.: Inexact implicit methods for monotone general variational inequalities. Mathematical Programming, Ser. A 86(1), 199-217 (1999)

B. He, X. Fu and Z. Jiang, PPA using a linear proximal term, Journal of Optimization Theory and Applications, 141:209-239, 2009.

B. Martinet, Regularisation d’in’equations variationelles par approximations succesives, Rev. Francaise d’Inform. Recherche Operation, 4, 154-159 (1970).

R. Rockafellar, Monotone operators and the PPA, SIAM Journal on Control and Optimization, 14, 877-898 (1976).

M. Teboulle, Convergence of proximal-like algorithms. Journal of Optimization Theory and Applications, 7, 1069-1083(1997)

Full Text: PDF

DOI: 10.19139/soic.v2i2.73


  • There are currently no refbacks.