1,721,003 research outputs found
Computing all solutions of Nash equilibrium problems with discrete strategy sets
Full text linkThe Nash equilibrium problem is a widely used tool for modeling noncooperative games. Many solution methods have been proposed in the literature to compute solutions of Nash equilibrium problems with continuous strategy sets, but, aside from some specific methods for some particular applications, there are no general algorithms to compute solutions of Nash equilibrium problems in which the strategy set of each player is assumed to be discrete. We define a branching method to compute the whole solution set of Nash equilibrium problems with discrete strategy sets. This method is equipped with a procedure that, by fixing variables, effectively prunes the branches of the search tree. Furthermore, we propose a preliminary procedure that by shrinking the feasible set improves the performance of the branching method when tackling a particular class of problems. Moreover, we prove existence of equilibria and we propose an extremely fast Jacobi-Type method which leads to one equilibrium for a new class of Nash equilibrium problems with discrete strategy sets. Our numerical results show that all the proposed algorithms work very well in practice. © 2016 Society for Industrial and Applied Mathematics
Algorithms for generalized potential games with mixed-integer variables
Full text linkWe consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches
Computing equilibria of Cournot oligopoly models with mixed-integer quantities
Full text linkWe consider Cournot oligopoly models in which some variables represent indivisible quantities. These models can be addressed by computing equilibria of Nash equilibrium problems in which the players solve mixed-integer nonlinear problems. In the literature there are no methods to compute equilibria of this type of Nash games. We propose a Jacobi-type method for computing solutions of Nash equilibrium problems with mixed-integer variables. This algorithm is a generalization of a recently proposed method for the solution of discrete so-called “2-groups partitionable” Nash equilibrium problems. We prove that our algorithm converges in a finite number of iterations to approximate equilibria under reasonable conditions. Moreover, we give conditions for the existence of approximate equilibria. Finally, we give numerical results to show the effectiveness of the proposed method
Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality
No full textWe 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. © 2016, Springer-Verlag Berlin Heidelberg
Solution methods for quasi variational inequalities
Full text linkWe propose to solve a general quasi-variational inequality by using its Karush-Kuhn-Tucker conditions. To this end we use a globally convergent algorithm based on a potential reduction approach. We establish global convergence results for many interesting instances of quasi-variational inequalities, vastly broadening the class of problems that can be solved with theoretical guarantees. Our numerical testings are very promising and show the practical viability of the approach
Distributed algorithms for convex problems with linear coupling constraints
Full text linkDistributed and parallel algorithms have been frequently investigated in the recent years, in particular in applications like machine learning. Nonetheless, only a small subclass of the optimization algorithms in the literature can be easily distributed, for the presence, e.g., of coupling constraints that make all the variables dependent from each other with respect to the feasible set. Augmented Lagrangian methods are among the most used techniques to get rid of the coupling constraints issue, namely by moving such constraints to the objective function in a structured, well-studied manner. Unfortunately, standard augmented Lagrangian methods need the solution of a nested problem by needing to (at least inexactly) solve a subproblem at each iteration, therefore leading to potential inefficiency of the algorithm. To fill this gap, we propose an augmented Lagrangian method to solve convex problems with linear coupling constraints that can be distributed and requires a single gradient projection step at every iteration. We give a formal convergence proof to at least ε-approximate solutions of the problem and a detailed analysis of how the parameters of the algorithm influence the value of the approximating parameter ε. Furthermore, we introduce a distributed version of the algorithm allowing to partition the data and perform the distribution of the computation in a parallel fashion
Solving quasi-variational inequalities via their KKT conditions
No full textWe propose to solve a general quasi-variational inequality by using its Karush-Kuhn-Tucker conditions. To this end we use a globally convergent algorithm based on a potential reduction approach. We establish global convergence results for many interesting instances of quasi-variational inequalities, vastly broadening the class of problems that can be solved with theoretical guarantees. Our numerical testings are very promising and show the practical viability of the approach
The Standard Pessimistic Bilevel Problem
Full text linkPessimistic bilevel optimization problems, as optimistic ones, possess a structure
involving three interrelated optimization problems. Moreover, their finite infima are only attained
under strong conditions. We address these difficulties within a framework of moderate assumptions
and a perturbation approach which allow us to approximate such finite infima arbitrarily well by
minimal values of a sequence of solvable single-level problems. To this end, as already done for
optimistic problems, for the first time in the literature we introduce the standard version of the
pessimistic bilevel problem. For its algorithmic treatment, we reformulate it as a standard optimistic
bilevel program with a two follower Nash game in the lower level. The latter lower level game, in turn,
is replaced by its Karush-Kuhn-Tucker conditions, resulting in a single-level mathematical program
with complementarity constraints. We prove that the perturbed pessimistic bilevel problem, its
standard version, the two follower game as well as the mathematical program with complementarity
constraints are equivalent with respect to their global minimal points. We study the more intricate
connections between their local minimal points in detail. As an illustration, we numerically solve a
regulator problem from economics for different values of the perturbation parameters
Parallel Selective Algorithms for Nonconvex Big Data Optimization
Full text linkWe propose a decomposition framework for the
parallel optimization of the sum of a differentiable (possibly
nonconvex) function and a (block) separable nonsmooth, convex
one. The latter term is usually employed to enforce structure in
the solution, typically sparsity. Our framework is very flexible and
includes both fully parallel Jacobi schemes and Gauss–Seidel (i.e.,
sequential) ones, as well as virtually all possibilities “in between”
with only a subset of variables updated at each iteration. Our
theoretical convergence results improve on existing ones, and
numerical results on LASSO, logistic regression, and some nonconvex
quadratic problems show that the new method consistently
outperforms existing algorithms
QVILIB: A LIBRARY OF QUASI-VARIATIONAL INEQUALITY TEST PROBLEMS
No full textQuasi-variational inequalities (QVIs) are a well established and important modelling tool with several applications in different fields. Solution methods exist, but are either especially tailored to very particular classes of problems, or are investigated mainly from a theoretical point of view. However, spurred by several recent applications of QVIs in engineering, the interest in general purpose solution methods is growing. The aim of this paper is to present a collection of test problems from diverse sources which gives a uniform basis on which algorithms for the solution of QVIs can be tested and compared. All the proposed problems are implemented in Matlab and the collection is freely available on request
- …
