Parallel Newton methods for the nonlinear complementarity problem

In this paper, we discuss how the basic Newton method for solving the nonlinear complementarity problem can be implemented in a parallel computation environment. We propose some synchronized and asynchronous Newton methods and establish their convergence.This work was based on research supported by the National Science Foundation under grant ECS-8407240 and by a University Research and Development grant from Cray Research Inc. The research was initiated when the authors were with the University of Texas at Dallas.     

Error bounds in mathematical programming

Originated from the practical implementation and numerical considerations of iterative methods for solving mathematical programs, the study of error bounds has grown and proliferated in many interesting areas within mathematical programming. This paper gives a comprehensive, state-of-the-art survey of the extensive theory and rich applications of error bounds for inequality and optimization systems and solution sets of equilibrium problems. This work is based on research supported by the U.S. National Science Foundation under grant CCR-9624018.     

Complementarity formulations and existence of solutions of dynamic multi-rigid-body contact problems with coulomb friction

In this paper, we study the problem of predicting the acceleration of a set of rigid, 3-dimensional bodies in contact with Coulomb friction. The nonlinearity of Coulomb's law leads to a nonlinear complementarity formulation of the system model. This model is used in conjunction with the theory of quasi-variational inequalities to prove for the first time that multi-rigid-body systems with all contacts rolling always has a solution under a feasibility-type condition. The analysis of the more general problem with sliding and rolling contacts presents difficulties that motivate our consideration of a relaxed friction law. The corresponding complementarity formulations of the multi-rigid-body contact problem are derived and existence of solutions of these models is established. The research of this author was based on work supported by the National, Science Foundation under grants DDM-9104078 and CCR-9213739. The research of this author was partially supported by the National Science Foundation under grant IRI-9304734, by the Texas Advanced Research Program grant 999903-078, and by the Texas Advanced Technology Program under grant 999903-095.     

Three modeling paradigms in mathematical programming

Celebrating the sixtieth anniversary since the zeroth International Symposium on Mathematical Programming was held in 1949, this paper discusses several promising paradigms in mathematical programming that have gained momentum in recent years but have yet to reach the main stream of the field. These are: competition, dynamics, and hierarchy. The discussion emphasizes the interplay between these paradigms and their connections with existing subfields including disjunctive, equilibrium, and nonlinear programming, and variational inequalities. We will describe the modeling approaches, mathematical formulations, and recent results of these paradigms, and sketch some open mathematical and computational challenges arising from the resulting optimization and equilibrium problems. Our goal is to elucidate the need for a systematic study of these problems and to inspire new research in the field.     

Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory,algorithms and applications

Over the past decade, the field of finite-dimensional variational inequality and complementarity problems has seen a rapid development in its theory of existence, uniqueness and sensitivity of solution(s), in the theory of algorithms, and in the application of these techniques to transportation planning, regional science, socio-economic analysis, energy modeling, and game theory. This paper provides a state-of-the-art review of these developments as well as a summary of some open research topics in this growing field.The research of this author was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by the AT&T Program in Telecommunications Technology at the University of Pennsylvania.The research of this author was supported by the National Science Foundation under grant ECS-8644098.     

Some n by dn linear complementarity problems

The purpose of this paper is to study some recent applications of the n by dn LCP solvable by a parametric principal pivoting algorithm (PPP algorithm). Often, the LCPs arising from these applications give rise to large systems of linear equations which can be solved fairly efficiently by exploiting their special structures. First, it is shown that by analyzing the n by dn LCP we could study the problem of solving a system of equations and the (nonlinear) complementarity problem when the function involved is separable. Next, we examine conditions under which the PPP algorithm is applicable to a general LCP, and then present examples of LCPs arising from various applications satisfying the conditions; included among them is the n by dn LCP with a certain $\text{P}$-property. Finally we study a special class of n by dn LCPs which do not possess the $\text{P}$-property but to which the PPP algorithm is still applicable; a major application of this class of problems is a certain economic spatial equilibrium model with piecewise linear prices.