Interior proximal extragradient method for equilibrium problems

The Bregman function-based Proximal Point Algorithm (BPPA) is an efficient tool for solving equilibrium problems and fixed-point problems. Extending rather classical proximal regularization methods, the main additional feature consists in an application of zone coercive regularizations. The latter allows to treat the generated subproblems as unconstrained ones, albeit with a certain precaution in numerical experiments. However, compared to the (classical) Proximal Point Algorithm for equilibrium problems, convergence results require additional assumptions which may be seen as the price to pay for unconstrained subproblems. Unfortunately, they are quite demanding – for instance, as they imply a sort of unique solvability of the given problem. The main purpose of this paper is to develop a modification of the BPPA, involving an additional extragradient step with adaptive (and explicitly given) stepsize. We prove that this extragradient step allows to leave out any of the additional assumptions mentioned above. Hence, though still of interior proximal type, the suggested method is applicable to an essentially larger class of equilibrium problems, especially including non-uniquely solvable ones.     

Modified extragradient algorithms for solving equilibrium problems

ABSTRACT

In this paper, we introduce some new algorithms for solving the equilibrium problem in a Hilbert space which are constructed around the proximal-like mapping and inertial effect. Also, some convergence theorems of the algorithms are established under mild conditions. Finally, several experiments are performed to show the computational efficiency and the advantage of the proposed algorithm over other well-known algorithms.     

An improved LQP-based method for solving nonlinear complementarity problems

The well-known logarithmic-quadratic proximal (LQP)method has motivated a number of efficient numerical algorithms for solving nonlinear complementarity problems (NCPs). In this paper,we aim at improving one of them, i.e., the LQP-based interior prediction-correction method proposed in [He, Liao and Yuan, J. Comp. Math., 2006, 24(1): 33–44], via identifying more appropriate step-sizes in the correction steps. Preliminary numerical results for solving some NCPs arising in traffic equilibrium problems are reported to verify the theoretical assertions.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

On extragradient-viscosity methods for solving equilibrium and fixed point problems in a Hilbert space

Abstract

In this paper, new numerical algorithms are introduced for finding the solution of a variational inequality problem whose constraint set is the common elements of the set of fixed points of a demicontractive mapping and the set of solutions of an equilibrium problem for a monotone mapping in a real Hilbert space. The strong convergence of the iterates generated by these algorithms is obtained by combining a viscosity approximation method with an extragradient method. First, this is done when the basic iteration comes directly from the extragradient method, under a Lipschitz-type condition on the equilibrium function. Then, it is shown that this rather strong condition can be omitted when an Armijo-backtracking linesearch is incorporated into the extragradient iteration. The particular case of variational inequality problems is also examined.     

A path-based double projection method for solving the asymmetric traffic network equilibrium problem

In this paper we propose a new iterative method for solving the asymmetric traffic equilibrium problem when formulated as a variational inequality whose variables are the path flows. The path formulation leads to a decomposable structure of the constraints set and allows us to obtain highly accurate solutions. The proposed method is a column generation scheme based on a variant of the Khobotov’s extragradient method for solving variational inequalities. Computational experiments have been carried out on several networks of a medium-large scale. The results obtained are promising and show the applicability of the method for solving large-scale equilibrium problems. This work has been supported by the National Research Program FIRB/RBNE01WBBBB on Large Scale Nonlinear Optimization.     

New extragradient method for a class of equilibrium problems in Hilbert spaces

The paper proposes a new extragradient algorithm for solving strongly pseudomonotone equilibrium problems which satisfy a Lipschitz-type condition recently introduced by Mastroeni in auxiliary problem principle. The main novelty of the paper is that the algorithm generates the strongly convergent sequences in Hilbert spaces without the prior knowledge of Lipschitz-type constants and any hybrid method. Several numerical experiments on a test problem are also presented to illustrate the convergence of the algorithm.     

A proximal augmented Lagrangian method for equilibrium problems

Considering a recently proposed proximal point method for equilibrium problems, we construct an augmented Lagrangian method for solving the same problem in reflexive Banach spaces with cone constraints generating a strongly convergent sequence to a certain solution of the problem. This is an inexact hybrid method meaning that at a certain iterate, a solution of an unconstrained equilibrium problem is found, allowing a proper error bound, followed by a Bregman projection of the initial iterate onto the intersection of two appropriate halfspaces. Assuming a set of reasonable hypotheses, we provide a full convergence analysis.     

An inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities

The augmented Lagrangian method is attractive in constraint optimizations. When it is applied to a class of constrained variational inequalities, the sub-problem in each iteration is a nonlinear complementarity problem (NCP). By introducing a logarithmic-quadratic proximal term, the sub-NCP becomes a system of nonlinear equations, which we call the LQP system. Solving a system of nonlinear equations is easier than the related NCP, because the solution of the NCP has combinatorial properties. In this paper, we present an inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities, in which the LQP system is solved approximately under a rather relaxed inexactness criterion. The generated sequence is Fejér monotone and the global convergence is proved. Finally, some numerical test results for traffic equilibrium problems are presented to demonstrate the efficiency of the method.      

Extended LQP Method for Monotone Nonlinear Complementarity Problems

To solve nonlinear complementarity problems (NCP), the logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations at each iteration. In this paper, the iterates generated by the original LQP method are extended by explicit formulas and thus an extended LQP method is presented. It is proved theoretically that the lower bound of the progress obtained by the extended LQP method is greater than that by the original LQP method. Preliminary numerical results are provided to verify the theoretical assertions and the effectiveness of both the original and the extended LQP method.     

求解均衡问题的内部束方法

结合logarithmic二次函数和Lemar6chal和Wolfe(1975)提出的束方法,本文提出了一个求解非光滑均衡问题的束方法.一方面,我们算法推广了Nguyen等在文[1]中的束方法,并且保证了算法生成的序列在集合的内部.另一方面,将内部束方法应用到求解均衡问题.     

Hybrid iterative scheme by a relaxed extragradient method for solutions of equilibrium problems and a general system of variational inequalities with application to optimization

In this paper, we introduce a new iterative process for finding the common element of the set of fixed points of a nonexpansive mapping, the set of solutions of an equilibrium problem and the solutions of the variational inequality problem for two inverse-strongly monotone mappings. We introduce a new viscosity relaxed extragradient approximation method which is based on the so-called relaxed extragradient method and the viscosity approximation method. We show that the sequence converges strongly to a common element of the above three sets under some parametric controlling conditions. Moreover, using the above theorem, we can apply to finding solutions of a general system of variational inequality and a zero of a maximal monotone operator in a real Hilbert space. The results of this paper extended, improved and connected with the results of Ceng et al., [L.-C. Ceng, C.-Y. Wang, J.-C. Yao, Strong convergence theorems by a relaxed extragradient method for a general system of variational inequalities, Math. Meth. Oper. Res. 67 (2008), 375–390], Plubtieng and Punpaeng, [S. Plubtieng, R. Punpaeng, A new iterative method for equilibrium problems and fixed point problems of nonexpansive mappings and monotone mappings, Appl. Math. Comput. 197 (2) (2008) 548–558] Su et al., [Y. Su, et al., An iterative method of solution for equilibrium and optimization problems, Nonlinear Anal. 69 (8) (2008) 2709–2719], Li and Song [Liwei Li, W. Song, A hybrid of the extragradient method and proximal point algorithm for inverse strongly monotone operators and maximal monotone operators in Banach spaces, Nonlinear Anal.: Hybrid Syst. 1 (3) (2007), 398-413] and many others.     

A hybrid extragradient method for solving pseudomonotone equilibrium problems using Bregman distance

In this paper, using a hybrid extragradient method, we introduce a new iterative process for approximating a common element of the set of solutions of equilibrium problems involving pseudomonotone bifunctions and the set of common fixed points of a finite family of multi-valued Bregman relatively nonexpansive mappings in the setting of reflexive Banach spaces. For this purpose, we introduce Bregman–Lipschitz-type condition for a pseudomonotone bifunction. It seems that these results for pseudomonotone bifunctions are first in reflexive Banach spaces. This paper concludes with certain applications, where we utilize our results to study the determination of a common point of the solution set of a variational inequality problem and the fixed point set of a finite family of multi-valued relatively nonexpansive mappings. A numerical example to support our main theorem will be exhibited.     

An interior proximal linearized method for DC programming based on Bregman distance or second-order homogeneous kernels

Abstract

We present an interior proximal method for solving constrained nonconvex optimization problems where the objective function is given by the difference of two convex function (DC function). To this end, we consider a linearized proximal method with a proximal distance as regularization. Convergence analysis of particular choices of the proximal distance as second-order homogeneous proximal distances and Bregman distances are considered. Finally, some academic numerical results are presented for a constrained DC problem and generalized Fermat–Weber location problems.     

A viscosity of extragradient approximation method for finding equilibrium problems, variational inequalities and fixed point problems for nonexpansive mappings

In this paper, we investigate the problem for finding the set of solutions for equilibrium problems, the set of solutions of the variational inequalities for k-Lipschitz continuous mappings and fixed point problems for nonexpansive mappings in a Hilbert space. We introduce a new viscosity extragradient approximation method which is based on the so-called viscosity approximation method and extragradient method. We show that the sequence converges strongly to a common element of the above three sets under some parameters controlling conditions. Finally, we utilize our results to study some convergence problems for finding the zeros of maximal monotone operators. Our results are generalization and extension of the results of Kumam [P. Kumam, Strong convergence theorems by an extragradient method for solving variational inequalities and equilibrium problems in a Hilbert space, Turk. J. Math. 33 (2009) 85–98], Wangkeeree [R. Wangkeeree, An extragradient approximation method for equilibrium problems and fixed point problems of a countable family of nonexpansive mappings, Fixed Point Theory and Applications, 2008, Article ID 134148, 17 pages, doi:10.1155/2008/134148], Yao et al. [Y. Yao, Y.C. Liou, R. Chen, A general iterative method for an finite family of nonexpansive mappings, Nonlinear Analysis 69 (5–6) (2008) 1644–1654], Qin et al. [X. Qin, M. Shang, Y. Su, A general iterative method for equilibrium problems and fixed point problems in Hilbert spaces, Nonlinear Analysis (69) (2008) 3897–3909], and many others.     

New subgradient extragradient methods for solving monotone bilevel equilibrium problems

ABSTRACT

In this paper, we propose new subgradient extragradient methods for finding a solution of a strongly monotone equilibrium problem over the solution set of another monotone equilibrium problem which usually is called monotone bilevel equilibrium problem in Hilbert spaces. The first proposed algorithm is based on the subgradient extragradient method presented by Censor et al. [Censor Y, Gibali A, Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. J Optim Theory Appl. 2011;148:318–335]. The strong convergence of the algorithm is established under monotone assumptions of the cost bifunctions with Lipschitz-type continuous conditions recently presented by Mastroeni in the auxiliary problem principle. We also present a modification of the algorithm for solving an equilibrium problem, where the constraint domain is the common solution set of another equilibrium problem and a fixed point problem. Several fundamental experiments are provided to illustrate the numerical behaviour of the algorithms and to compare with others.     

惩罚框架下求解广义Nash均衡问题的分解算法

广义Nash均衡问题(GNEP),是非合作博弈论中一类重要的问题,它在经济学、管理科学和交通规划等领域有着广泛的应用.本文主要提出一种新的惩罚算法来求解一般的广义Nash均衡问题,并根据罚函数的特殊结构,采用交替方向法求解子问题.在一定的条件下,本文证明新算法的全局收敛性.多个数值例子的试验结果表明算法是可行的,并且是有效的.     

A new criterion for the inexact logarithmic-quadratic proximal method and its derived hybrid methods

To solve nonlinear complementarity problems, the inexact logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations (LQP system) approximately at each iteration. Therefore, the efficiencies of inexact-type LQP methods depend greatly on the involved inexact criteria used to solve the LQP systems. This paper relaxes inexact criteria of existing inexact-type LQP methods and thus makes it easier to solve the LQP system approximately. Based on the approximate solutions of the LQP systems, a descent method, and a prediction–correction method are presented. Convergence of the new methods are proved under mild assumptions. Numerical experiments for solving traffic equilibrium problems demonstrate that the new methods are more efficient than some existing methods and thus verify that the new inexact criterion is attractive in practice.     

An extragradient method for relaxed cocoercive variational inequality and equilibrium problems

The purpose of this paper is to investigate the problem of finding the common element of the set of common fixed points of a countable family of nonexpansivemappings, the set of an equilibrium problem and the set of solutions of the variational inequality problem for a relaxed cocoercive and Lipschitz continuous mapping in Hilbert spaces. Then, we show that the sequence converges strongly to a common element of the above three sets under some parameter controlling conditions, which are connected with Yao, Liou, Yao, Takahashi and many others.     

On the proximal point method for equilibrium problems in Hilbert spaces

We analyse a proximal point method for equilibrium problems in Hilbert spaces, improving upon previously known convergence results. We prove global weak convergence of the generated sequence to a solution of the problem, assuming existence of solutions and rather mild monotonicity properties of the bifunction which defines the equilibrium problem, and we establish existence of solutions of the proximal subproblems. We also present a new reformulation of equilibrium problems as variational inequalities ones.