A superlinearly convergent projection method for constrained systems of nonlinear equations

In this paper, a new projection method for solving a system of nonlinear equations with convex constraints is presented. Compared with the existing projection method for solving the problem, the projection region in this new algorithm is modified which makes an optimal stepsize available at each iteration and hence guarantees that the next iterate is more closer to the solution set. Under mild conditions, we show that the method is globally convergent, and if an error bound assumption holds in addition, it is shown to be superlinearly convergent. Preliminary numerical experiments also show that this method is more efficient and promising than the existing projection method. This work was done when Yiju Wang visited Chongqing Normal University.     

Weak topology and infinite matrix games

This paper approaches infinite matrix games through the weak topology on the players' sets of strategies. A new class of semi-infinite and infinite matrix games is defined, and it is proved that these games always have a value and optimal strategies for each player. Using these games it is proved that some other important classes of infinite matrix game also have values. Received April 1996/Revised version June 1997/Final version September 1997     

Ellipsoid projection method in matrix games

A problem of calculating a solution of a zero-sum matrix game is considered in the paper The problem of search of a solution is reduced to a constrained convex minimization problem for which an ellipsoid projection algorithm is used. The algorithm generates an ?-optimal solution of the game in a polynomial time     

Modified self-adaptive projection method for solving pseudomonotone variational inequalities

In this paper, a self-adaptive projection method with a new search direction for solving pseudomonotone variational inequality (VI) problems is proposed, which can be viewed as an extension of the methods in [B.S. He, X.M. Yuan, J.Z. Zhang, Comparison of two kinds of prediction-correction methods for monotone variational inequalities, Computational Optimization and Applications 27 (2004) 247-267] and [X.H. Yan, D.R. Han, W.Y. Sun, A self-adaptive projection method with improved step-size for solving variational inequalities, Computers & Mathematics with Applications 55 (2008) 819-832]. The descent property of the new search direction is proved, which is useful to guarantee the convergence. Under the relatively relaxed condition that F is continuous and pseudomonotone, the global convergence of the proposed method is proved. Numerical experiments are provided to illustrate the efficiency of the proposed method.     

A modified projection method with a new direction for solving variational inequalities

In this paper, we propose a new projection method for solving variational inequality problems, which can be viewed as an improvement of the method of Li et al. [M. Li, L.Z. Liao, X.M. Yuan, A modified projection method for co-coercive variational inequality, European Journal of Operational Research 189 (2008) 310-323], by adopting a new direction. Under the same assumptions as those in Li et al. (2008), we establish the global convergence of the proposed algorithm. Some preliminary computational results are reported, which illustrated that the new method is more efficient than the method of Li et al. (2008).     

Zero-sum games with incompletely defined payoff

It is shown that a saddle-point solution exists in a two-person, zero-sum game whose payoff is given by a matrix which is not completely defined. On the other hand, we show that such games do not always have a value, so that a saddle-point solution is not necessarily an optimal solution.This work was supported by the Centre d'Etudes Atomiques, Saclay, France.     

Optimality in matrix games with incompletely defined payoff

We study two-person, zero-sum matrix games whose payoffs are not defined for every pair of strategies. A necessary and sufficient condition for these games to possess a value is given, and we show that the value can be approximated by using universally playable strategies.This work was supported by the Centre d'Etudes Nucléaires, Saclay, France.     

Vector linear programming in zero-sum multicriteria matrix games

In this paper, a multiple-objective linear problem is derived from a zero-sum multicriteria matrix game. It is shown that the set of efficient solutions of this problem coincides with the set of Paretooptimal security strategies (POSS) for one of the players in the original game. This approach emphasizes the existing similarities between the scalar and multicriteria matrix games, because in both cases linear programming can be used to solve the problems. It also leads to different scalarizations which are alternative ways to obtain the set of all POSS. The concept of ideal strategy for a player is introduced, and it is established that a pair of Pareto saddle-point strategies exists if both players have ideal strategies. Several examples are included to illustrate the results in the paper.     

A projection method forl p norm location-allocation problems

We present a solution method for location-allocation problems involving thel _p norm, where 1 <p < . The method relaxes the {0, 1} constraints on the allocations, and solves for both the locations and allocations simultaneously. Necessary and sufficient conditions for local minima of the relaxed problem are stated and used to develop an iterative algorithm. This algorithm finds a stationary point on a series of subspaces defined by the current set of activities. The descent direction is a projection onto the current subspace of a direction incorporating second-order information for the locations, and first-order information for the allocations. Under mild conditions, the algorithm finds local minima with {0, 1} allocations and exhibits quadratic convergence. An implementation that exploits the special structure of these problems to dramatically reduce the computational cost of the required numerical linear algebra is described. Numerical results for thirty-six test problems are included.This research was supported in part by Natural Sciences and Engineering Research Council (NSERC) of Canada grants A-5671 and A-8639, and by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.Corresponding author.     

A projection method for a system of nonlinear monotone equations with convex constraints

In this paper, we propose a projection method for solving a system of nonlinear monotone equations with convex constraints. Under standard assumptions, we show the global convergence and the linear convergence rate of the proposed algorithm. Preliminary numerical experiments show that this method is efficient and promising. This work was supported by the Postdoctoral Fellowship of The Hong Kong Polytechnic University, the NSF of Shandong China (Y2003A02).     

Solving variational inequalities by a modified projection method with an effective step-size

In this paper, we propose a new projection method for the solution of variational inequality problems. The method is simple, which uses only function evaluations and projections onto the feasible set. We adopt a new step-size rule and a new search direction in the new method. Under the mild conditions, we prove the proposed method is globally convergent. Preliminary numerical results are reported.     

A necessary and sufficient condition for Pareto-optimal security strategies in multicriteria matrix games

In this paper, a scalar game is derived from a zero-sum multicriteria matrix game, and it is proved that the solution of the new game with strictly positive scalarization is a necessary and sufficient condition for a strategy to be a Pareto-optimal security strategy (POSS) for one of the players in the original game. This is done by proving that a certain set, which is the extension of the set of security level vectors in the criterion function space, is convex and polyhedral. It is also established that only a finite number of scalarizations are necessary to obtain all the POSS for a player. An example is included to illustrate the main steps in the proof.This work was done while the author was a Research Associate in the Department of Electrical Engineering at the Indian Institute of Science and was financially supported by the Council of Scientific and Industrial Research, Delhi, India.The author wishes to express his gratefulness to Professor U. R. Prasad for helpful discussions and to two anonymous referees for suggestions which led to an improved presentation.     

Combat games

We propose a mathematical formulation of a combat game between two opponents with offensive capabilities and offensive objectives. Resolution of the combat involves solving two differential games with state constraints. Depending on the game dynamics and parameters, the combat can terminate in one of four ways: (i) the first player wins, (ii) the second player wins, (iii) a draw (neither wins), or (iv) joint capture. In the first two cases, the optimal strategies of the two players are determined from suitable zero-sum games, whereas in the latter two the relevant games are nonzero-sum. Further, to avoid certain technical difficulties, the concept of a -combat game is introduced.Dedicated to G. LeitmannThe first author wishes to acknowledge the friendship and guidance of George Leitmann, beginning in the author's student days at Berkeley and continuing to the present time. All the authors thank George Leitmann for many recent fruitful discussions on differential games.on sabbatical leave from Technion, Israel Institute of Technology, Haifa, Israel.     

A modified projection method for solving co-coercive variational inequalities

This paper presents a modified projection method for solving variational inequalities, which can be viewed as an improvement of the method of Yan, Han and Sun [X.H. Yan, D.R. Han, W.Y. Sun, A modified projection method with a new direction for solving variational inequalities, Applied Mathematics and Computation 211 (2009) 118-129], by adopting a new prediction step. Under the same assumptions, we establish the global convergence of the proposed algorithm. Some preliminary computational results are reported.     

A globally convergent primal-dual interior-point filter method for nonlinear programming

In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters.The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one resulting from feasibility and centrality, and associated with the normal step; the other resulting from optimality (complementarity and duality), and related with the tangential step.Global convergence to first-order critical points is proved for the new primal-dual interior-point filter algorithm.Mathematics Subject Classification (1991): 65K05, 90C06, 90C29, 90C30Support for this author was provided by CRPC grant CCR–9120008.Support for this author was provided by CRPC grant CCR–9120008.Support for this author was provided by Centro de Matemática da Universidade de Coimbra, by FCT under grant POCTI/35059/MAT/2000, by the European Union under grant IST-2000-26063, and by Fundaç\ ao Calouste Gulbenkian. The author would also like to thank the IBM T.J. Watson Research Center and the Institute for Mathematics and Its Applications for their local support.     

Replication invariance on NTU games

Two concepts of replication (conflictual and non-conflictual) are extended from the class of pure bargaining games to the class of NTU games. The behavior of the Harsanyi, Shapley NTU, Egalitarian and Maschler-Owen solutions of the replica games is compared with that of the Nash and Egalitarian solutions in pure bargaining games. Received June 1995/Final version February 2000     

Globally convergent limited memory bundle method for large-scale nonsmooth optimization

Many practical optimization problems involve nonsmooth (that is, not necessarily differentiable) functions of thousands of variables. In the paper [Haarala, Miettinen, Mäkelä, Optimization Methods and Software, 19, (2004), pp. 673–692] we have described an efficient method for large-scale nonsmooth optimization. In this paper, we introduce a new variant of this method and prove its global convergence for locally Lipschitz continuous objective functions, which are not necessarily differentiable or convex. In addition, we give some encouraging results from numerical experiments.