共查询到20条相似文献,搜索用时 15 毫秒
1.
Minglu Ye 《Optimization》2017,66(7):1119-1134
The generalized Nash equilibrium problem (GNEP) is an n-person noncooperative game in which each player’s strategy set depends on the rivals’ strategy set. In this paper, we presented a half-space projection method for solving the quasi-variational inequality problem which is a formulation of the GNEP. The difference from the known projection methods is due to the next iterate point in this method is obtained by directly projecting a point onto a half-space. Thus, our next iterate point can be represented explicitly. The global convergence is proved under the minimal assumptions. Compared with the known methods, this method can reduce one projection of a vector onto the strategy set per iteration. Numerical results show that this method not only outperforms the known method but is also less dependent on the initial value than the known method. 相似文献
2.
This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set
of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization
reformulation of GNEP using a regularized Nikaido–Isoda function so that solutions of GNEP coincide with global minima of
the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent
optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions
guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance
of our algorithm on some examples. 相似文献
3.
Masao Fukushima 《Computational Management Science》2011,8(3):201-218
The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem, in which each
player’s strategy set may depend on the rival players’ strategies. The GNEP has recently drawn much attention because of its
capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international
pollution control. However, a GNEP usually has multiple or even infinitely many solutions, and it is not a trivial matter
to choose a meaningful solution from those equilibria. The purpose of this paper is two-fold. First we present an incremental
penalty method for the broad class of GNEPs and show that it can find a GNE under suitable conditions. Next, we formally define
the restricted GNE for the GNEPs with shared constraints and propose a controlled penalty method, which includes the incremental
penalty method as a subprocedure, to compute a restricted GNE. Numerical examples are provided to illustrate the proposed
approach. 相似文献
4.
Generalized Nash equilibrium problem (GNEP) is an important model that has many applications in practice. However, a GNEP usually has multiple or even infinitely many Nash equilibrium points and it is not easy to choose a favorable solution from those equilibria. This paper considers a class of GNEP with some kind of separability. We first extend the so-called normalized equilibrium concept to the stationarity sense and then, we propose an approach to solve the normalized stationary points by reformulating the GNEP as a single optimization problem. We further demonstrate the proposed approach on a GNEP model in similar product markets. 相似文献
5.
The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach. 相似文献
6.
In this paper we reformulate the generalized Nash equilibrium problem (GNEP) as a nonsmooth Nash equilibrium problem by means
of a partial penalization of the difficult coupling constraints. We then propose a suitable method for the solution of the
penalized problem and we study classes of GNEPs for which the penalty approach is guaranteed to converge to a solution. In
particular, we are able to prove convergence for an interesting class of GNEPs for which convergence results were previously
unknown. 相似文献
7.
Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the
strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which
form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth)
reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being
an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium,
which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions
of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are
continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint
qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation. 相似文献
8.
9.
Javad Mashreghi 《Numerical Functional Analysis & Optimization》2013,34(9):1053-1071
We develop an inexact proximal point algorithm for solving equilibrium problems in Banach spaces which consists of two principal steps and admits an interesting geometric interpretation. At a certain iterate, first we solve an inexact regularized equilibrium problem with a flexible error criterion to obtain an axillary point. Using this axillary point and the inexact solution of the previous iterate, we construct two appropriate hyperplanes which separate the current iterate from the solution set of the given problem. Then the next iterate is defined as the Bregman projection of the initial point onto the intersection of two halfspaces obtained from the two constructed hyperplanes containing the solution set of the original problem. Assuming standard hypotheses, we present a convergence analysis for our algorithm, establishing that the generated sequence strongly and globally converges to a solution of the problem which is the closest one to the starting point of the algorithm. 相似文献
10.
We define the concept of reproducible map and show that, whenever the constraint map defining the quasivariational inequality (QVI) is reproducible then one can characterize the whole solution set of the QVI as a union of solution sets of some variational inequalities (VI). By exploiting this property, we give sufficient conditions to compute any solution of a generalized Nash equilibrium problem (GNEP) by solving a suitable VI. Finally, we define the class of pseudo-Nash equilibrium problems, which are (not necessarily convex) GNEPs whose solutions can be computed by solving suitable Nash equilibrium problems. 相似文献
11.
12.
In this paper, we study the calmness of a generalized Nash equilibrium problem (GNEP) with non-differentiable data. The approach consists in obtaining some error bound property for the KKT system associated with the generalized Nash equilibrium problem, and returning to the primal problem thanks to the Slater constraint qualification. 相似文献
13.
In this paper, we extend the literature by adapting the Nikaidô–Isoda function as an indicator function termed as regularized indicator Nikaidô–Isoda function, and this is demonstrated to guarantee existence of a solution. Using this function, we present two constrained optimization reformulations of the generalized Nash equilibrium problem (GNEP for short). The first reformulation characterizes all the solutions of GNEP as global minima of the optimization problem. Later this approach is modified to obtain the second optimization reformulation whose global minima characterize the normalized Nash equilibria. Some numerical results are also included to illustrate the behaviour of the optimization reformulations. 相似文献
14.
Javad Mashreghi 《Applicable analysis》2013,92(1):157-172
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. 相似文献
15.
In this paper, we propose a new algorithm for solving a bilevel equilibrium problem in a real Hilbert space. In contrast to most other projection-type algorithms, which require to solve subproblems at each iteration, the subgradient method proposed in this paper requires only to calculate, at each iteration, two subgradients of convex functions and one projection onto a convex set. Hence, our algorithm has a low computational cost. We prove a strong convergence theorem for the proposed algorithm and apply it for solving the equilibrium problem over the fixed point set of a nonexpansive mapping. Some numerical experiments and comparisons are given to illustrate our results. Also, an application to Nash–Cournot equilibrium models of a semioligopolistic market is presented. 相似文献
16.
The generalized Nash equilibrium problem (GNEP) is an extension of the standard Nash game where, in addition to the cost functions,
also the strategy spaces of each player depend on the strategies chosen by all other players. This problem is rather difficult
to solve and there are only a few methods available in the literature. One of the most popular ones is the so-called relaxation
method, which is known to be globally convergent under a set of assumptions. Some of these assumptions, however, are rather
strong or somewhat difficult to understand. Here, we present a modified relaxation method for the solution of a certain class
of GNEPs. The convergence analysis uses completely different arguments based on a certain descent property and avoids some
of the technical conditions for the original relaxation method. Moreover, numerical experiments indicate that the modified
relaxation method performs quite well on a number of different examples taken from the literature. 相似文献
17.
Alexey F. Izmailov Mikhail V. Solodov 《Computational Optimization and Applications》2014,59(1-2):201-218
Error bounds (estimates for the distance to the solution set of a given problem) are key to analyzing convergence rates of computational methods for solving the problem in question, or sometimes even to justifying convergence itself. That said, for the generalized Nash equilibrium problems (GNEP), the theory of error bounds had not been developed in depth comparable to the fields of optimization and variational problems. In this paper, we provide a systematic approach which should be useful for verifying error bounds for both specific instances of GNEPs and for classes of GNEPs. These error bounds for GNEPs are based on more general results for constraints that involve complementarity relations and cover those (few) GNEP error bounds that existed previously, and go beyond. In addition, they readily imply a Lipschitzian stability result for solutions of GNEPs, a subject where again very little had been known. As a specific application of error bounds, we discuss Newtonian methods for solving GNEPs. While we do not propose any significantly new methods in this respect, some new insights into applicability to GNEPs of various approaches and into their convergence properties are presented. 相似文献
18.
Thi Thu Van Nguyen Jean-Jacques Strodiot Van Hien Nguyen 《Journal of Global Optimization》2009,44(2):175-192
In this article we present a new and efficient method for solving equilibrium problems on polyhedra. The method is based on
an interior-quadratic proximal term which replaces the usual quadratic proximal term. This leads to an interior proximal type
algorithm. Each iteration consists in a prediction step followed by a correction step as in the extragradient method. In a
first algorithm each of these steps is obtained by solving an unconstrained minimization problem, while in a second algorithm
the correction step is replaced by an Armijo-backtracking linesearch followed by an hyperplane projection step. We prove that
our algorithms are convergent under mild assumptions: pseudomonotonicity for the two algorithms and a Lipschitz property for
the first one. Finally we present some numerical experiments to illustrate the behavior of the proposed algorithms. 相似文献
19.
Jean Jacques Strodiot Thi Thu Van Nguyen Van Hien Nguyen 《Journal of Global Optimization》2013,56(2):373-397
Generalized Nash equilibrium problems are important examples of quasi-equilibrium problems. The aim of this paper is to study a general class of algorithms for solving such problems. The method is a hybrid extragradient method whose second step consists in finding a descent direction for the distance function to the solution set. This is done thanks to a linesearch. Two descent directions are studied and for each one several steplengths are proposed to obtain the next iterate. A general convergence theorem applicable to each algorithm of the class is presented. It is obtained under weak assumptions: the pseudomonotonicity of the equilibrium function and the continuity of the multivalued mapping defining the constraint set of the quasi-equilibrium problem. Finally some preliminary numerical results are displayed to show the behavior of each algorithm of the class on generalized Nash equilibrium problems. 相似文献
20.
Using a regularized Nikaido-Isoda function, we present a (nonsmooth) constrained optimization reformulation of the player convex generalized Nash equilibrium problem (GNEP). Further we give an unconstrained reformulation of a large subclass of player convex GNEPs which, in particular, includes the jointly convex GNEPs. Both approaches characterize all solutions of a GNEP as minima of optimization problems. The smoothness properties of these optimization problems are discussed in detail, and it is shown that the corresponding objective functions are continuous and piecewise continuously differentiable under mild assumptions. Some numerical results based on the unconstrained optimization reformulation being applied to player convex GNEPs are also included. 相似文献