A semismooth equation approach to the solution of nonlinear complementarity problems

In this paper we present a new algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a semismooth equation reformulation of the complementarity problem. We exploit the recent extension of Newton's method to semismooth systems of equations and the fact that the natural merit function associated to the equation reformulation is continuously differentiable to develop an algorithm whose global and quadratic convergence properties can be established under very mild assumptions. Other interesting features of the new algorithm are an extreme simplicity along with a low computational burden per iteration. We include numerical tests which show the viability of the approach.     

A generalized proximal-point method for convex optimization problems in Hilbert spaces

We deal with a generalization of the proximal-point method and the closely related Tikhonov regularization method for convex optimization problems. The prime motivation behind this is the well-known connection between the classical proximal-point and augmented Lagrangian methods, and the emergence of modified augmented Lagrangian methods in recent years. Our discussion includes a formal proof of a corresponding connection between the generalized proximal-point method and the modified augmented Lagrange approach in infinite dimensions. Several examples and counterexamples illustrate the convergence properties of the generalized proximal-point method and indicate that the corresponding assumptions are sharp.     

Generalized Krasnoselskii–Mann-type iterations for nonexpansive mappings in Hilbert spaces

The Krasnoselskii–Mann iteration plays an important role in the approximation of fixed points of nonexpansive operators; it is known to be weakly convergent in the infinite dimensional setting. In this present paper, we provide a new inexact Krasnoselskii–Mann iteration and prove weak convergence under certain accuracy criteria on the error resulting from the inexactness. We also show strong convergence for a modified inexact Krasnoselskii–Mann iteration under suitable assumptions. The convergence results generalize existing ones from the literature. Applications are given to the Douglas–Rachford splitting method, the Fermat–Weber location problem as well as the alternating projection method by John von Neumann.     

Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation

We consider the generalized Nash equilibrium problem (GNEP), where not only the players’ cost functions but also their strategy spaces depend on the rivals’ decision variables. Existence results for GNEPs are typically shown by using a fixed point argument for a certain set-valued function. Here we use a regularization of this set-valued function in order to obtain a single-valued function that is easier to deal with from a numerical point of view. We show that the fixed points of the latter function constitute an important subclass of the generalized equilibria called normalized equilibria. This fixed point formulation is then used to develop a nonsmooth Newton method for computing a normalized equilibrium. The method uses a so-called computable generalized Jacobian that is much easier to compute than Clarke generalized Jacobian or B-subdifferential. We establish local superlinear/quadratic convergence of the method under the constant rank constraint qualification, which is weaker than the frequently used linear independence constraint qualification, and a suitable second-order condition. Some numerical results are presented to illustrate the performance of the method.     

Bounds for the extremal eigenvalues of a class of symmetric tridiagonal matrices with applications

We consider a class of symmetric tridiagonal matrices which may be viewed as perturbations of Toeplitz matrices. The Toeplitz structure is destroyed since two elements on each off-diagonal are perturbed. Based on a careful analysis, we derive sharp bounds for the extremal eigenvalues of this class of matrices in terms of the original data of the given matrix. In this way, we also obtain a lower bound for the smallest singular value of certain matrices. Some numerical results indicate that our bounds are extremely good.     

Improved smoothing-type methods for the solution of linear programs

Summary. We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the primal-dual optimality conditions as a nonlinear and nonsmooth system of equations, and to apply a Newton-type method to a smooth approximation of this nonsmooth system. The method presented here is a predictor-corrector method, and is closely related to some methods recently proposed by Burke and Xu on the one hand, and by the authors on the other hand. However, here we state stronger global and/or local convergence properties. Moreover, we present quite promising numerical results for the whole netlib test problem collection. Received August 9, 2000 / Revised version received September 28, 2000 / Published online June 7, 2001     

Solving quasi-variational inequalities via their KKT conditions

We 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.     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997