Perturbation approach to generalized Nash equilibrium problems with shared constraints

This paper aims to consider an application of conjugate duality in convex optimization to the generalized Nash equilibrium problems with shared constraints and nonsmooth cost functions. Sufficient optimality conditions for the problems regarding to players are rewritten as inclusion problems and the maximal monotonicity of set-valued mappings generated by the subdifferentials of functions from data of GNEP is proved. Moreover, some assertions dealing with solutions to GNEP are obtained and applications of splitting algorithms to the oligopolistic market equilibrium models are presented.     

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.     

一类带概率互补约束的随机优化问题的最优性条件

主要讨论了一类带概率互补约束的随机优化问题的最优性条件.首先利用一类非线性互补(NCP)函数将概率互补约束转化成为一个通常的概率约束.然后,利用概率约束的相关理论结果,将其等价地转化成一个带不等式约束的优化问题.最后给出了这类问题的弱驻点和最优解的最优性条件.     

Mathematical programs with multiobjective generalized Nash equilibrium problems in the constraints

This paper considers a class of mathematical programs that include multiobjective generalized Nash equilibrium problems in the constraints. Little research can be found in the literature although it has some interesting applications. We present a single level reformulation for this kind of problems and show their equivalence in terms of global and local minimizers. We find that the reformulation is a special case of the so-called mathematical program with equilibrium constraints which is extensively studied in the literature.     

A best-response approach for equilibrium selection in two-player generalized Nash equilibrium problems

ABSTRACT

In this paper, we propose a best-response approach to select an equilibrium in a two-player generalized Nash equilibrium problem. In our model we solve, at each of a finite number of time steps, two independent optimization problems. We prove that convergence of our Jacobi-type method, for the number of time steps going to infinity, implies the selection of the same equilibrium as in a recently introduced continuous equilibrium selection theory. Thus the presented approach is a different motivation for the existing equilibrium selection theory, and it can also be seen as a numerical method. We show convergence of our numerical scheme for some special cases of generalized Nash equilibrium problems with linear constraints and linear or quadratic cost functions.     

On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables

ABSTRACT

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it.     

Smoothing Newton algorithm for symmetric cone complementarity problems based on a one-parametric class of smoothing functions

In this paper, we introduce a one-parametric class of smoothing functions in the context of symmetric cones which contains two symmetric perturbed smoothing functions as special cases, and show that it is coercive under suitable assumptions. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve the complementarity problems over symmetric cones, and it is proved that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for randomly generated second-order cone programs and several practical second-order cone programs from the DIMACS library are reported.     

求解广义非线性互补问题的光滑化拟牛顿法

利用光滑对称扰动Fischer-Burmeister函数将广义非线性互补问题转化为非线性方程组,提出新的光滑化拟牛顿法求解该方程组.然后证明该算法是全局收敛的,且在一定条件下证明该算法具有局部超线性(二次)收敛性.最后用数值实验验证了该算法的有效性.     

Smoothing algorithms for complementarity problems over symmetric cones

There recently has been much interest in studying optimization problems over symmetric cones. In this paper, we first investigate a smoothing function in the context of symmetric cones and show that it is coercive under suitable assumptions. We then extend two generic frameworks of smoothing algorithms to solve the complementarity problems over symmetric cones, and prove the proposed algorithms are globally convergent under suitable assumptions. We also give a specific smoothing Newton algorithm which is globally and locally quadratically convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for second-order cone complementarity problems are reported.     

Smoothing methods for convex inequalities and linear complementarity problems

A smooth approximationp (x, ) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e^–x ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CCR-9322479.     

On a class of least-element complementarity problems

The present paper studies the linear complementarity problem of finding vectorsx andy inR ₊ ⁿ such thatc + Dx + y 0,b – x 0 andx ^T (c + Dx + y) = y ^T (b – x) = 0 whereD is aZ-matrix andb > 0. Complementarity problems of this nature arise, for example, from the minimization of certain quadratic functions subject to upper and lower bounds on the variables. Two least-element characterizations of solutions to the above linear complementarity problem are established first. Next, a new and direct method to solve this class of problems, which depends on the idea of least-element solution is presented. Finally, applications and computational experience with its implementation are discussed.Research partially supported by the National Science Foundation Grant MCS 71-03341 A04 and the Air Force Office of Scientific Research Contract F 44620 14 C 0079.     

Continuity for vector optimization problems with equilibrium constraints

The concept of vector optimization problems with equilibrium constraints (VOPEC) is introduced. By using the continuity results of the approximate solution set to the equilibrium problem, we obtain the same results of the marginal map and the approximate value in VOPEC (e) for vector-valued mapping.     

Maximal element with applications to Nash equilibrium problems in Hadamard manifolds

ABSTRACT

The purpose of this paper is to study the existence of maximal elements with applications to Nash equilibrium problems for generalized games in Hadamard manifolds. By employing a KKM lemma, we establish a new maximal element theorem in Hadamard manifolds. As applications, some existence results of Nash equilibria for generalized games are derived. The results in this paper unify, improve and extend some known results from the literature.     

Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power markets

This paper is dedicated to solving a nonsmooth second-order cone complementarity problem, in which the mapping is assumed to be locally Lipschitz continuous, but not necessarily to be continuously differentiable everywhere. With the help of the vector-valued Fischer-Burmeister function associated with second-order cones, the nonsmooth second-order cone complementarity problem can be equivalently transformed into a system of nonsmooth equations. To deal with this reformulated nonsmooth system, we present an approximation function by smoothing the inner mapping and the outer Fischer-Burmeister function simultaneously. Different from traditional smoothing methods, the smoothing parameter introduced is treated as an independent variable. We give some conditions under which the Jacobian of the smoothing approximation function is guaranteed to be nonsingular. Based on these results, we propose a smoothing Newton method for solving the nonsmooth second-order cone complementarity problem and show that the proposed method achieves globally superlinear or quadratic convergence under suitable assumptions. Finally, we apply the smoothing Newton method to a network Nash-Cournot game in oligopolistic electric power markets and report some numerical results to demonstrate its effectiveness.

     

Multiobjective optimization problems with equilibrium constraints

The paper is devoted to new applications of advanced tools of modern variational analysis and generalized differentiation to the study of broad classes of multiobjective optimization problems subject to equilibrium constraints in both finite-dimensional and infinite-dimensional settings. Performance criteria in multiobjective/vector optimization are defined by general preference relationships satisfying natural requirements, while equilibrium constraints are described by parameterized generalized equations/variational conditions in the sense of Robinson. Such problems are intrinsically nonsmooth and are handled in this paper via appropriate normal/coderivative/subdifferential constructions that exhibit full calculi. Most of the results obtained are new even in finite dimensions, while the case of infinite-dimensional spaces is significantly more involved requiring in addition certain “sequential normal compactness” properties of sets and mappings that are preserved under a broad spectrum of operations.     

An algorithm for a class of nonlinear complementarity problems with non-Lipschitzian functions

In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective.     

A new class of complementarity functions for symmetric cone complementarity problems

A popular approach to solving the complementarity problem is to reformulate it as an equivalent equation system via a complementarity function. In this paper, we propose a new class of functions, which contains the penalized natural residual function and the penalized Fischer–Burmeister function for symmetric cone complementarity problems. We show that this class of functions is indeed a class of complementarity functions. We finally prove that the merit function of this new class of complementarity functions is coercive.     

A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints

A class of smoothing sample average approximation (SAA) methods is proposed for solving the stochastic mathematical program with complementarity constraints (SMPCC) considered by Birbil et al. [S.I. Birbil, G. Gürkan, O. Listes, Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res. 31 (2006) 739–760]. The almost sure convergence of optimal solutions of the smoothed SAA problem to that of the true problem is established by the notion of epi-convergence in variational analysis. It is demonstrated that, under suitable conditions, any accumulation point of Karash–Kuhn–Tucker points of the smoothed SAA problem is almost surely a kind of stationary point of SMPCC as the sample size tends to infinity. Moreover, under a strong second-order sufficient condition for SMPCC, the exponential convergence rate of the sequence of Karash–Kuhn–Tucker points of the smoothed SAA problem is investigated through an application of Robinson?s stability theory. Some preliminary numerical results are reported to show the efficiency of proposed method.     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.