Augmented Lagrangian methods for variational inequality problems. (English) Zbl 1187.90293
Summary: We introduce augmented Lagrangian methods for solving finite dimensional variational inequality problems whose feasible sets are defined by convex inequalities, generalizing the proximal augmented Lagrangian method for constrained optimization. At each iteration, primal variables are updated by solving an unconstrained variational inequality problem, and then dual variables are updated through a closed formula. A full convergence analysis is provided, allowing for inexact solution of the subproblems.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C47 | Minimax problems in mathematical programming |
| 49J35 | Existence of solutions for minimax problems |
References:
| [1] | A.S. Antipin, Equilibrium programming: proximal methods. Comput. Math. Math. Phys.37 (1997) 1285-1296. · Zbl 0944.90083 |
| [2] | A.S. Antipin, F.P. Vasilev and A.S. Stukalov, A regularized Newton method for solving equilibrium programming problems with an inexactly specified set. Comput. Math. Math. Phys.47 (2007) 19-31. Zbl1210.90175 · Zbl 1210.90175 · doi:10.1134/S0965542507010046 |
| [3] | A. Auslender and M. Teboulle, Lagrangian duality and related multiplier methods for variational inequality problems. SIAM J. Optim.10 (2000) 1097-1115. Zbl0996.49005 · Zbl 0996.49005 · doi:10.1137/S1052623499352656 |
| [4] | D.P. Bertsekas, On penalty and multiplier methods for constrained optimization problems. SIAM J. Control Optim.14 (1976) 216-235. Zbl0324.49029 · Zbl 0324.49029 · doi:10.1137/0314017 |
| [5] | M. Bianchi and R. Pini, Coercivity conditions for equilibrium problems. J. Optim. Theory Appl.124 (2005) 79-92. · Zbl 1064.49004 · doi:10.1007/s10957-004-6466-9 |
| [6] | M. Bianchi and S. Schaible, Generalized monotone bifunctions and equilibrium problems. J. Optim. Theory Appl.90 (1996) 31-43. · Zbl 0903.49006 · doi:10.1007/BF02192244 |
| [7] | E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems. The Mathematics Student63 (1994) 123-145. · Zbl 0888.49007 |
| [8] | H. Brezis, L. Nirenberg and S. Stampacchia, A remark on Ky Fan minimax principle. Bolletino della Unione Matematica Italiana6 (1972) 293-300. · Zbl 0264.49013 |
| [9] | J.D. Buys, Dual algorithms for constrained optimization problems, Ph.D. thesis, University of Leiden, The Netherlands (1972). |
| [10] | F. Facchinei and J.S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2003). · Zbl 1062.90001 |
| [11] | M.C. Ferris and J.S. Pang, Engineering and economic applications of complementarity problems. SIAM Rev.39 (1997) 669-713. Zbl0891.90158 · Zbl 0891.90158 · doi:10.1137/S0036144595285963 |
| [12] | S.D. Flåm and A.S. Antipin, Equilibrium programming using proximal-like algorithms. Math. Prog.78 (1997) 29-41. · Zbl 0890.90150 · doi:10.1007/BF02614504 |
| [13] | F. Flores-Bazán, Existence theorems for generalized noncoercive equilibrium problems: quasiconvex case. SIAM J. Optim.11 (2000) 675-790. Zbl1002.49013 · Zbl 1002.49013 · doi:10.1137/S1052623499364134 |
| [14] | P.T. Harker and J.S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math. Prog.48 (1990) 161-220. Zbl0734.90098 · Zbl 0734.90098 · doi:10.1007/BF01582255 |
| [15] | M.R. Hestenes, Multiplier and gradient methods. J. Optim. Theory Appl.4 (1969) 303-320. · Zbl 0174.20705 · doi:10.1007/BF00927673 |
| [16] | J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. Springer, Berlin (1993). |
| [17] | A.N. Iusem, Augmented Lagrangian methods and proximal point methods for convex optimization. Investigación Operativa8 (1999) 11-49. |
| [18] | A.N. Iusem and R. Gárciga Otero, Inexact versions of proximal point and augmented Lagrangian algorithms in Banach spaces. Numer. Funct. Anal. Optim.22 (2001) 609-640. · Zbl 1018.90067 · doi:10.1081/NFA-100105310 |
| [19] | A.N. Iusem, G. Kassay and W. Sosa, On certain conditions for the existence of solutions of equilibrium problems. Math. Prog.116 (2009) 259-273. · Zbl 1158.90009 · doi:10.1007/s10107-007-0125-5 |
| [20] | A.N. Iusem and M. Nasri, Inexact proximal point methods for equilibrium problems in Banach spaces. Numer. Funct. Anal. Optim.28 (2007) 1279-1308. · Zbl 1144.65041 · doi:10.1080/01630560701766668 |
| [21] | A.N Iusem and W. Sosa, New existence results for equilibrium problems. Nonlinear Anal.52 (2003) 621-635. · Zbl 1017.49008 · doi:10.1016/S0362-546X(02)00154-2 |
| [22] | A.N. Iusem and W. Sosa, Iterative algorithms for equilibrium problems. Optimization52 (2003) 301-316. · Zbl 1176.90640 · doi:10.1080/0233193031000120039 |
| [23] | A.N. Iusem and W. Sosa, On the proximal point method for equilibrium problems in Hilbert spaces in appear Optimization. · Zbl 1206.90212 · doi:10.1080/02331931003603133 |
| [24] | I.V. Konnov, Application of the proximal point method to nonmonotone equilibrium problems. J. Optim. Theory Appl.119 (2003) 317-333. · Zbl 1084.49009 · doi:10.1023/B:JOTA.0000005448.12716.24 |
| [25] | B.W. Kort and D.P. Bertsekas, Combined primal-dual and penalty methods for convex programming. SIAM J. Control Optim.14 (1976) 268-294. · Zbl 0332.90035 · doi:10.1137/0314020 |
| [26] | M.A. Krasnoselskii, Two observations about the method of succesive approximations. Uspekhi Matematicheskikh Nauk10 (1955) 123-127. |
| [27] | G. Mastroeni, Gap functions for equilibrium problems. J. Glob. Optim.27 (2003) 411-426. · Zbl 1061.90112 · doi:10.1023/A:1026050425030 |
| [28] | J. Moreau, Proximité et dualité dans un espace hilbertien. Bulletin de la Societé Mathématique de France93 (1965). Zbl0136.12101 · Zbl 0136.12101 |
| [29] | A. Moudafi, Proximal point methods extended to equilibrium problems. Journal of Natural Geometry15 (1999) 91-100. Zbl0974.65066 · Zbl 0974.65066 |
| [30] | A. Moudafi, Second-order differential proximal methods for equilibrium problems. Journal of Inequalities in Pure and Applied Mathematics4 (2003) Article no. 18. Zbl1175.90413 · Zbl 1175.90413 |
| [31] | A. Moudafi and M. Théra, Proximal and dynamical approaches to equilibrium problems, in Ill-posed Variational Problems and Regularization Techniques, Lect. Notes in Economics and Mathematical Systems477, Springer, Berlin (1999) 187-201. · Zbl 0944.65080 |
| [32] | L.D. Muu and W. Oettli, Convergence of an adaptive penalty scheme for finding constraint equilibria. Nonlinear Anal.18 (1992) 1159-1166. · Zbl 0773.90092 · doi:10.1016/0362-546X(92)90159-C |
| [33] | M. Nasri and W. Sosa, Generalized Nash games and equilibrium problems (submitted). · Zbl 1230.91012 |
| [34] | M.A. Noor, Auxiliary principle technique for equilibrium problems. J. Optim. Theory Appl.122 (2004) 371-386. · Zbl 1092.49010 · doi:10.1023/B:JOTA.0000042526.24671.b2 |
| [35] | M.A. Noor and T.M. Rassias, On nonconvex equilibrium problems. J. Math. Analysis Appl.212 (2005) 289-299. · Zbl 1087.49009 · doi:10.1016/j.jmaa.2005.03.069 |
| [36] | M.J.D. Powell, Method for nonlinear constraints in minimization problems, in Optimization, edited by R. Fletcher, Academic Press, London (1969). · Zbl 0194.47701 |
| [37] | R.T. Rockafellar, A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Prog.5 (1973) 354-373. Zbl0279.90035 · Zbl 0279.90035 · doi:10.1007/BF01580138 |
| [38] | R.T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl.12 (1973) 555-562. · Zbl 0254.90045 · doi:10.1007/BF00934777 |
| [39] | R.T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res.1 (1976) 97-116. Zbl0402.90076 · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 |
| [40] | R.T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim.14 (1976) 877-898. · Zbl 0358.90053 · doi:10.1137/0314056 |
| [41] | M.V. Solodov and B.F. Svaiter, A hybrid projection-proximal point algorithm. Journal of Convex Analysis6 (1999) 59-70. Zbl0961.90128 · Zbl 0961.90128 |
| [42] | M.V. Solodov and B.F. Svaiter, An inexact hybrid extragardient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis7 (1999) 323-345. · Zbl 0959.90038 · doi:10.1023/A:1008777829180 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
