Date: Tue, 05 Nov 1996 21:04:54 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Fri, 10 Nov 1995 18:14:32 GMT Content-length: 6945
With more than three decades of research, the subject of complementarity problems has become a well-established and fruitful discipline within mathematical programming. Sources of complementarity problems are diverse and include many problems in engineering, economics, and the sciences. Several monographs and surveys have documented the basic theory, algorithms, and applications of complementarity problems and their role in optimization theory.
The meeting started with an overview of the complementarity field at which stage a new web site, CPNET, http://www.cs.wisc.edu/cpnet/ was announced. When completed, this site will eventually contain up-to-date information on upcoming conferences in the area, a list of active researchers and pointers to work on algorithms, applications and software.
Currently, the page contains a list of all the researchers present at the conference, along with papers and software that outline some developments in the area. This includes the growing collection of test problems for MCP, MCPLIB, and the COMPLEMENTARITY TOOLBOX, a suite of programs and routines for use in conjunction with MATLAB. It is hoped that CPNET will allow this collection to grow considerably to include many new algorithms and application problems. There are some pointers to extensions of modeling software that allow real applications to be formulated in standard modeling languages.
There were various themes that developed during the meeting. Several speakers introduced new extensions of the basic framework, and cited applications that needed such extensions. Some new theoretical results were outlined relating to vertical, horizontal and extended linear complementarity problems, along with several ideas to unify these areas. Other speakers considered noncooperative and stochastic game theory and outlined existence results and algorithms for their solution. Variational and bimatrix inequalities also drew the attention of several talks. Merit functions and smoothing techniques were also popular topics.
One extension that received considerable attention was the Mathematical Program with Equilibrium Constraints (MPEC). Several algorithms were given for the solution of these problems, and lots of discussion resulted during application talks relating to reformulating problems into this framework. This appears to be a very fruitful area for future research.
Contact problems are a rich source of complementarity problems. For these problems, complementarity is the result of the contact condition which stipulates that the gap between two objects in contact is either zero or the pressure between them is zero. Classical obstacle problems were extended to include the effects of convection and diffusion. An interesting use of complementarity in contact mechanics arises in robot design and key features of the problem that can be modeled in the new framework include sliding, friction and rigid body properties. Structural mechanics has also used complementarity models in studies of material elasticity and plasticity. Several very informative and interesting talks opened up these areas to the field in general.
Complementarity has been used in economics for a long time. The renowned Walrasian law of supply and demand in general equilibrium theory states that either there is excess supply or the price of the corresponding good is zero. Several extensions of this basic idea were outlined in talks that dealt with oligopolistic equilibria, integrated assessment for problems in energy modeling, relocation effects due to the European Common Market and the National Energy Modeling System (NEMS). The use of similar models for traffic assignment was also outlined. In this area, dynamic models are becoming important and several new ideas for tolling and congestion analysis were presented at the meeting.
Several new algorithmic developments were outlined at the meeting. Some of these involved the traditional simplicial and pivotal based techniques while others used novel reformulations of the complementarity problem both as smooth and nonsmooth systems of nonlinear equations. A very popular approach takes systems of nonsmooth equations and applies a smoothing so that traditional Newton based techniques could be applied. Still other methods were based on quadratic programming and proximal points formulations. New computational extensions were also outlined. Several talks introduced new merit functions that will prove useful in error analysis and future algorithmic design.
In conclusion, the meeting showed that the field of complementarity research is a burgeoning area. There are already many interesting algorithms for solving complementarity problems, along with fairly sophisticated techniques for analysis and computation. The growth in the number of new application areas that use this framework will require even more sophisticated solution techniques. Furthermore, it is clear that even more applications will be developed that use complementarity modeling in some form or another, a significant portion of which was made possible by this meeting.
A refereed proceedings of this meeting will be published in 1996 by SIAM. Further developments in this area will undoubtedly be reported at the next International Conference on Complementarity Problems. Planning is already under way and the conference is tentatively set for July 1998 to be held in Madison, Wisconsin.
Jong-Shi Pang
Department of Mathematical Sciences
The Johns Hopkins University, Baltimore
jsp@vicp.mts.jhu.edu