Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

In Pang and Fukushima (Comput Manage Sci 2:21–56, 2005), a sequential penalty approach was presented for a quasi-variational inequality (QVI) with particular application to the generalized Nash game. To test the computational performance of the penalty method, numerical results were reported with an example from a multi-leader-follower game in an electric power market. However, due to an inverted sign in the penalty term in the example and some missing terms in the derivatives of the firms’ Lagrangian functions, the reported numerical results in Pang and Fukushima (Comput Manage Sci 2:21–56, 2005) are incorrect. Since the numerical examples of this kind are scarce in the literature and this particular example may be useful in the future research, we report the corrected results. The online version of the original article can be found under doi:.     

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.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

Asymmetric variational inequality problems over product sets: Applications and iterative methods

In this paper, we (i) describe how several equilibrium problems can be uniformly modelled by a finite-dimensional asymmetric variational inequality defined over a Cartesian product of sets, and (ii) investigate the local and global convergence of various iterative methods for solving such a variational inequality problem. Because of the special Cartesian product structure, these iterative methods decompose the original variational inequality problem into a sequence of simpler variational inequality subproblems in lower dimensions. The resulting decomposition schemes often have a natural interpretation as some adjustment processes. This research was based on work supported by the National Science Foundation under grant ECS 811–4571.     

On cone orderings and the linear complementarity problem

This paper first generalizes a characterization of polyhedral sets having least elements, which is obtained by Cottle and Veinott [6], to the situation in which Euclidean space is partially ordered by some general cone ordering (rather than the usual ordering). We then use this generalization to establish the following characterization of the class $\text{C}$ of matrices ($\text{C}$ arises as a generalization of the class of Z-matrices; see [4], [13], [14]): M∈$\text{C}$ if and only if for every vector q for which the linear complementarity problem (q,M) is feasible, the problem (q,M) has a solution which is the least element of the feasible set of (q,M) with respect to a cone ordering induced by some simplicial cone. This latter result generalizes the characterizations of K-and Z-matrices obtained by Cottle and Veinott [6] and Tamir [21], respectively.     

Piecewise affine parameterized value-function based bilevel non-cooperative games

Mathematical Programming - Generalizing certain network interdiction games communicated to us by Andrew Liu and his collaborators, this paper studies a bilevel, non-cooperative game wherein the...     

Spatial oligopolistic equilibria with arbitrage,shared resources,and price function conjectures

This paper considers equilibria among multiple firms that are competing non-cooperatively against each other to sell electric power and buy resources needed to produce that power. Examples of such resources include fuels, power plant sites, and emissions allowances. The electric power market is a spatial market on a network in which flows are constrained by Kirchhoffs current and voltage laws. Arbitragers in the power market erase spatial price differences that are non-cost based. Power producers can compete in power markets à la Cournot (game in quantities), or in a generalization of the Cournot game (termed the conjectured supply function game) in which they anticipate that rivals will respond to price changes. In input markets, producers either compete à la Bertrand (price-taking behavior) or they can conjecture that price will increase with consumption of the resource. The simultaneous competition in power and input markets presents opportunities for strategic price behavior that cannot be analyzed using models of power markets alone. Depending on whether the producers treat the arbitrager endogenously or exogenously, we derive two mixed nonlinear complementarity formulations of the oligopolistic problem. We establish the existence and uniqueness of solutions as well as connections among the solutions to the model formulations. A numerical example is provided for illustrative purposes.Support was provided by the National Science Foundation under grant ECS-0080577.This authors research was partially supported by the National Science Foundation under grants ECS-0080577 and CCR-0098013.The authors thank Chris Day, Fieke Riekers, and Adrian Wals for their collaboration. They are particularly indebted to Grant Roch for writing AMPL and MATLAB codes for solving the numerical example reported in the paper.