Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems

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.     

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

On error bounds and Newton-type methods for generalized Nash equilibrium problems

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.     

Optimization reformulations of the generalized Nash equilibrium problem using regularized indicator Nikaidô–Isoda function

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.     

On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

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.     

Restricted generalized Nash equilibria and controlled penalty algorithm

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.     

Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality

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.     

On solving generalized Nash equilibrium problems via optimization

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.     

Gap Function Approach to the Generalized Nash Equilibrium Problem

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.     

Partial penalization for the solution of generalized Nash equilibrium problems

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.     

Collusive game solutions via optimization

A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementarity problem. We establish the convexity of the optimization problem in the case where each player's strategy set is unidimensional. In the multivariate case, we propose upper and lower bounding procedures for the collusive optimization problem and establish convergence properties of these procedures. Computational results with these procedures for solving some test problems are reported. It is with great honor that we dedicate this paper to Professor Terry Rockafellar on the occasion of his 70th birthday. Our work provides another example showing how Terry's fundamental contributions to convex and variational analysis have impacted the computational solution of applied game problems. This author's research was partially supported by the National Science Foundation under grant ECS-0080577. This author's research was partially supported by the National Science Foundation under grant CCR-0098013.     

A proximal gradient descent method for the extended second-order cone linear complementarity problem

We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method.     

On differentiability properties of player convex generalized Nash equilibrium problems

Abstract

This article studies differentiability properties for a reformulation of a player convex generalized Nash equilibrium problem as a constrained and possibly nonsmooth minimization problem. By using several results from parametric optimization we show that, apart from exceptional cases, all locally minimal points of the reformulation are differentiability points of the objective function. This justifies a numerical approach which basically ignores the possible nondifferentiabilities.     

Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search

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.     

Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets

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.     

Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming

Sample average approximation (SAA) is one of the most popular methods for solving stochastic optimization and equilibrium problems. Research on SAA has been mostly focused on the case when sampling is independent and identically distributed (iid) with exceptions (Dai et al. (2000) [9], Homem-de-Mello (2008) [16]). In this paper we study SAA with general sampling (including iid sampling and non-iid sampling) for solving nonsmooth stochastic optimization problems, stochastic Nash equilibrium problems and stochastic generalized equations. To this end, we first derive the uniform exponential convergence of the sample average of a class of lower semicontinuous random functions and then apply it to a nonsmooth stochastic minimization problem. Exponential convergence of estimators of both optimal solutions and M-stationary points (characterized by Mordukhovich limiting subgradients (Mordukhovich (2006) [23], Rockafellar and Wets (1998) [32])) are established under mild conditions. We also use the unform convergence result to establish the exponential rate of convergence of statistical estimators of a stochastic Nash equilibrium problem and estimators of the solutions to a stochastic generalized equation problem.     

Bilevel optimization applied to strategic pricing in competitive electricity markets

In this paper, we present a bilevel programming formulation for the problem of strategic bidding under uncertainty in a wholesale energy market (WEM), where the economic remuneration of each generator depends on the ability of its own management to submit price and quantity bids. The leader of the bilevel problem consists of one among a group of competing generators and the follower is the electric system operator. The capability of the agent represented by the leader to affect the market price is considered by the model. We propose two solution approaches for this non-convex problem. The first one is a heuristic procedure whose efficiency is confirmed through comparisons with the optimal solutions for some instances of the problem. These optimal solutions are obtained by the second approach proposed, which consists of a mixed integer reformulation of the bilevel model. The heuristic proposed is also compared to standard solvers for nonlinearly constrained optimization problems. The application of the procedures is illustrated in case studies with configurations derived from the Brazilian power system.     

Systems of quasi-variational relations with applications

In this paper, we introduce a system of quasi-variational relations (in short, SQVR) and present several examples which show that it is a very general and unified model of several problems. We establish the existence of solutions of SQVP, in general, and several other problems, in particular. As an application of our results, we derive maximal element theorems and a collectively fixed point theorem for a family of multivalued maps. As further applications, we study Ky Fan type inequality / inclusion problem for vector valued bifunctions which includes constrained Nash equilibrium problem as a special case. We also present a common fixed point theorem for a family of multivalued maps. The results of this paper improve and generalize several known results on (system of) quasi-equilibrium problems, (system of) quasi-variational inclusions, constrained Nash equilibrium problem, collectively fixed point theorem and KKM type theorems for a family of multivalued maps. Our results also contain several results which appeared in recent literature.     

Robustness to uncertain optimization using scalarization techniques and relations to multiobjective optimization

In this paper, we propose two kinds of robustness concepts by virtue of the scalarization techniques (Benson’s method and elastic constraint method) in multiobjective optimization, which can be characterized as special cases of a general non-linear scalarizing approach. Moreover, we introduce both constrained and unconstrained multiobjective optimization problems and discuss their relations to scalar robust optimization problems. Particularly, optimal solutions of scalar robust optimization problems are weakly efficient solutions for the unconstrained multiobjective optimization problem, and these solutions are efficient under uniqueness assumptions. Two examples are employed to illustrate those results. Finally, the connections between robustness concepts and risk measures in investment decision problems are also revealed.     

A neural network for the linear complementarity problem

An artificial neural network is proposed in this paper for solving the linear complementarity problem. The new neural network is based on a reformulation of the linear complementarity problem into the unconstrained minimization problem. Our new neural network can be easily implemented on a circuit. On the theoretical aspect, we analyze the existence of the equilibrium points for our neural network. In addition, we prove that if the equilibrium point exists for the neural network, then any such equilibrium point is both asymptotically and bounded (Lagrange) stable for any initial state. Furthermore, linear programming and certain quadratical programming problems (not necessarily convex) can be also solved by the neural network. Simulation results on several problems including a nonconvex one are also reported.