共查询到20条相似文献,搜索用时 46 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
Koichi Nabetani Paul Tseng Masao Fukushima 《Computational Optimization and Applications》2011,48(3):423-452
We consider the generalized Nash equilibrium problem (GNEP), in which each player’s strategy set may depend on the rivals’
strategies through shared constraints. A practical approach to solving this problem that has received increasing attention
lately entails solving a related variational inequality (VI). From the viewpoint of game theory, it is important to find as
many GNEs as possible, if not all of them. We propose two types of parametrized VIs related to the GNEP, one price-directed
and the other resource-directed. We show that these parametrized VIs inherit the monotonicity properties of the original VI
and, under mild constraint qualifications, their solutions yield all GNEs. We propose strategies to sample in the parameter
spaces and show, through numerical experiments on benchmark examples, that the GNEs found by the parametrized VI approaches
are widely distributed over the GNE set. 相似文献
5.
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. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
D. Dorsch H. T. Jongen V. Shikhman 《Journal of Optimization Theory and Applications》2013,159(3):606-634
In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions. 相似文献
9.
We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized
gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable,
but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary
point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints
are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the
minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability
of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under
some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization
problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality
constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints
by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach. 相似文献
10.
11.
12.
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. 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
We consider the generalized Nash equilibrium problem (GNEP), where not only the players’ cost functions but also their strategy spaces depend on the rivals’ decision variables. Existence results for GNEPs are typically shown by using a fixed point argument for a certain set-valued function. Here we use a regularization of this set-valued function in order to obtain a single-valued function that is easier to deal with from a numerical point of view. We show that the fixed points of the latter function constitute an important subclass of the generalized equilibria called normalized equilibria. This fixed point formulation is then used to develop a nonsmooth Newton method for computing a normalized equilibrium. The method uses a so-called computable generalized Jacobian that is much easier to compute than Clarke generalized Jacobian or B-subdifferential. We establish local superlinear/quadratic convergence of the method under the constant rank constraint qualification, which is weaker than the frequently used linear independence constraint qualification, and a suitable second-order condition. Some numerical results are presented to illustrate the performance of the method. 相似文献
16.
The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010). 相似文献
17.
Ryoichi Nishimura Shunsuke Hayashi Masao Fukushima 《Journal of Global Optimization》2012,53(1):107-120
Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an
incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the
past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization
policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic,
and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius
norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity
problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give
some numerical example to illustrate the behavior of robust Nash equilibria. 相似文献
18.
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. 相似文献
19.
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. 相似文献
20.
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. 相似文献