Augmented Lagrangian methods for variational inequality problems

Alfredo N. Iusem; Mostafa Nasri

RAIRO - Operations Research (2010)

  • Volume: 44, Issue: 1, page 5-25
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Iusem, Alfredo N., and Nasri, Mostafa. "Augmented Lagrangian methods for variational inequality problems." RAIRO - Operations Research 44.1 (2010): 5-25. <http://eudml.org/doc/250859>.

@article{Iusem2010,
abstract = { 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. },
author = {Iusem, Alfredo N., Nasri, Mostafa},
journal = {RAIRO - Operations Research},
keywords = {Augmented Lagrangian method; equilibrium problem; inexact solution; proximal point method; variational inequality problem},
language = {eng},
month = {2},
number = {1},
pages = {5-25},
publisher = {EDP Sciences},
title = {Augmented Lagrangian methods for variational inequality problems},
url = {http://eudml.org/doc/250859},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Iusem, Alfredo N.
AU - Nasri, Mostafa
TI - Augmented Lagrangian methods for variational inequality problems
JO - RAIRO - Operations Research
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 5
EP - 25
AB - 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.
LA - eng
KW - Augmented Lagrangian method; equilibrium problem; inexact solution; proximal point method; variational inequality problem
UR - http://eudml.org/doc/250859
ER -

References

top
  1. A.S. Antipin, Equilibrium programming: proximal methods. Comput. Math. Math. Phys.37 (1997) 1285–1296.  Zbl0944.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
  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
  4. D.P. Bertsekas, On penalty and multiplier methods for constrained optimization problems. SIAM J. Control Optim.14 (1976) 216–235.  Zbl0324.49029
  5. M. Bianchi and R. Pini, Coercivity conditions for equilibrium problems. J. Optim. Theory Appl.124 (2005) 79–92.  Zbl1064.49004
  6. M. Bianchi and S. Schaible, Generalized monotone bifunctions and equilibrium problems. J. Optim. Theory Appl.90 (1996) 31–43.  Zbl0903.49006
  7. E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems. The Mathematics Student63 (1994) 123–145.  Zbl0888.49007
  8. H. Brezis, L. Nirenberg and S. Stampacchia, A remark on Ky Fan minimax principle. Bolletino della Unione Matematica Italiana6 (1972) 293–300.  Zbl0264.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).  
  11. M.C. Ferris and J.S. Pang, Engineering and economic applications of complementarity problems. SIAM Rev.39 (1997) 669–713.  Zbl0891.90158
  12. S.D. Flåm and A.S. Antipin, Equilibrium programming using proximal-like algorithms. Math. Prog.78 (1997) 29–41.  Zbl0890.90150
  13. F. Flores-Bazán, Existence theorems for generalized noncoercive equilibrium problems: quasiconvex case. SIAM J. Optim.11 (2000) 675–790.  
  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
  15. M.R. Hestenes, Multiplier and gradient methods. J. Optim. Theory Appl.4 (1969) 303–320.  Zbl0174.20705
  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.  Zbl1018.90067
  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.  Zbl1158.90009
  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.  Zbl1144.65041
  21. A.N Iusem and W. Sosa, New existence results for equilibrium problems. Nonlinear Anal.52 (2003) 621–635.  Zbl1017.49008
  22. A.N. Iusem and W. Sosa, Iterative algorithms for equilibrium problems. Optimization52 (2003) 301–316.  Zbl1176.90640
  23. A.N. Iusem and W. Sosa, On the proximal point method for equilibrium problems in Hilbert spaces in appear Optimization.  Zbl1206.90212
  24. I.V. Konnov, Application of the proximal point method to nonmonotone equilibrium problems. J. Optim. Theory Appl.119 (2003) 317–333.  Zbl1084.49009
  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.  Zbl0332.90035
  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.  Zbl1061.90112
  28. J. Moreau, Proximité et dualité dans un espace hilbertien. Bulletin de la Societé Mathématique de France93 (1965).  Zbl0136.12101
  29. A. Moudafi, Proximal point methods extended to equilibrium problems. Journal of Natural Geometry15 (1999) 91–100.  Zbl0974.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
  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.  Zbl0944.65080
  32. L.D. Muu and W. Oettli, Convergence of an adaptive penalty scheme for finding constraint equilibria. Nonlinear Anal.18 (1992) 1159–1166.  Zbl0773.90092
  33. M. Nasri and W. Sosa, Generalized Nash games and equilibrium problems (submitted).  Zbl1230.91012
  34. M.A. Noor, Auxiliary principle technique for equilibrium problems. J. Optim. Theory Appl.122 (2004) 371–386.  Zbl1092.49010
  35. M.A. Noor and T.M. Rassias, On nonconvex equilibrium problems. J. Math. Analysis Appl.212 (2005) 289–299.  Zbl1087.49009
  36. M.J.D. Powell, Method for nonlinear constraints in minimization problems, in Optimization, edited by R. Fletcher, Academic Press, London (1969).  Zbl0194.47701
  37. R.T. Rockafellar, A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Prog.5 (1973) 354–373.  Zbl0279.90035
  38. R.T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl.12 (1973) 555–562.  Zbl0254.90045
  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
  40. R.T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim.14 (1976) 877–898.  Zbl0358.90053
  41. M.V. Solodov and B.F. Svaiter, A hybrid projection-proximal point algorithm. Journal of Convex Analysis6 (1999) 59–70.  Zbl0961.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.  Zbl0959.90038

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.