Preprint C72/2008
Proximal Point Methods and Augmented Lagrangian for Equilibrium Problems
Mostafa Nasri
Keywords: Augmented Lagrangian method | Bregman distance | Convex minimization problem | equilibrium problem | inexact solution | Point-to-set operator | proximal point method | Variational inequality problem.
In this work we propose two classes of methods for solving equilibrium problems. The first one consists of two inexact proximal-like algorithms for solving equilibrium problems in reflexive Banach spaces, generalizing two methods, called {\it Inexact Proximal Point+Bregman Projection Method} and {\it Inexact Proximal Point-extragradient Method}, proposed by Iusem and Gárciga for finding zeroes of maximal monotone operators in reflexive Banach spaces, to the context of equilibrium problems. We state our two proximal point algorithms formally and their convergence properties, proving that the sequence generated by each one of them converges to a solution of the equilibrium problem under reasonable assumptions. In order to achieve this goal, we introduce a suitable regularization for equilibrium problem, and then we use this regularization in our two methods, named {\it Inexact Proximal Point+Bregman Projection Method} (Algorithm IPPBP) and {\it Inexact Proximal Point-Extragradient Method} (Algorithm IPPE). These two methods are hybrid methods, which invoke the proximal point method at the beginning of each iteration for obtaining an auxiliary point. In the case of Algorithm IPPBP, this auxiliary point is used for constructing a hyperplane separating the current iterate from the solution set of the problem. The next iterate of Algorithm IPPBP is then obtained by projecting the current iterate onto the separating hyperplane. In the case of Algorithm IPPE, we use again the proximal point method in order to get an auxiliary point, from which an extragradient step is performed. The second class of methods considered here consists of augmented Lagrangian methods for solving finite dimensional equilibrium problems whose feasible sets are defined by convex inequalities, extending the proximal augmented Lagrangian method for constrained optimization. We propose two Lagrangian functions, and consequently two augmented Lagrangian functions for equilibrium problems. Using these functions we develop two augmented Lagrangian methods, called {\it Inexact Augmented Lagrangian-Extragradient Method} (Algorithm IALE) and a variant of Algorithm IALE, called {\it Linearized Inexact Augmented Lagrangian-Extragradient Method} (Algorithm LIALE). At each iteration of these methods, primal variables are updated by solving an unconstrained equilibrium problem, and then dual variables are updated through a closed formula. We provide a full convergence analysis, allowing for inexact solution of the subproblem of Algorithm IALE, applying the convergence theorem for Algorithm IPPE. Along the same line, we propose two additional augmented Lagrangian methods for solving equilibrium problems, to be called {\it Inexact Augmented Lagrangian Projection Method} (Algorithm IALP) and {\it Linearized Inexact Augmented Lagrangian Projection Method} (Algorithm LIALP), whose convergence properties are proved using the convergence results for Algorithm IPPBP. We also show that each equilibrium problem can be reformulated as a variational inequality problem. This approach reduces the augmented Lagrangian methods to implementable methods which substitute each subproblem of the augmented Lagrangian methods by a system of algebraic equations which admits a unique solution.