ICCP99

INTERNATIONAL CONFERENCE ON COMPLEMENTARITY PROBLEMS Contemporary Applications and Algorithms Forum on the future of complementarity

On July 11, Professor Jong-Shi Pang gave a historical perspective of the development of the complementarity field over the past 35 years, starting with the seminal works of Cottle, Lemke, Nash and Scarf. It was noted that complementarity has provided a uniform framework for handling a wide class of mathematical programming problems. This has enabled the field to have fundamental impacts on the theory, algorithms and applications of mathematical programming.

Following this introduction, all the attendees of the conference participated in a forum addressing "the future of complementarity". Prior to the meeting, several researchers had been given the following three questions as a means to initiate the discussion.

1. What are the important areas for future research in complementarity?
2. Which application areas are critical to develop from a complementarity viewpoint?
3. Who should fund complementarity research, how should this be done, and which parts need the most attention?

Research

1. Mathematical Programs with Equilibrium Constraints: (MPEC)
   A key outstanding research area involves mathematical programs with equilibrium constraints. This provides a framework that encompasses the fields of nonlinear programming and complementarity. An important focus of this research is to allow solution of inverse optimization (or inverse pricing) problems, for which many varied applications exist, some of which were outlined at the meeting. Uses of this framework for complementarity problems include searching among the possibly many solutions to a complementarity problem. This involves applications both in game theory, equilibrium analysis and structural engineering. In all cases, the optimization defines a property to prefer one equilibrium over another. Another example arises with ill-posed problems. Approximate solutions with minimum error are frequently of practical importance both in designing algorithms and in understanding applications such as those arising in statistics and machine learning. Ill-posed problem formulations can lead to better methods even in well-posed cases. Key ideas that will deserve further attention are regularization and robust estimation. In particular, it was noted that mathematical programming approaches can exploit the use of polyhedral norms, instead of the traditional use of Euclidean norms due to the ability to treat inequality constraints. Finally, several of the economists mentioned the future need for "equilibrium problems with equilibrium constraints". A separate discussion was held after the forum debating MPEC's more generally. The MPEC discussion page gives more details.
2. Environments and modeling languages
   The development of environments, particularly involving modeling languages, serves as a conduit for algorithm and application interaction. Languages such as AMPL and GAMS shorten the time to take an actual model and produce a stylized version of the model that is amenable to computation and analysis. Within the context of economics, even more specialized extensions like MPSGE have enabled large groups of economists to use complementarity within their work, without having to be experts in algorithmic theory or design. A key research area is to look at other fields, particularly engineering, and determine if similar successes can be achieved here via the use of specialized extensions to modeling systems. In the future, we also need to provide more experimental tools at earlier times in their development, for example in the MATLAB environment. This is a critical mechanism for developing close interactions with applications experts and is imperative for interdisciplinary research and the adoption of complementarity within other disciplines.
3. Numerical data mining and statistics
   Mathematical programming has made key contributions to the very rapidly growing area of data mining. Large scale optimization problems in machine learning, support vector machines and clustering deserve more attention. Statistical applications such as maximum likelihood estimation are used in many practical cases and potential exists for improved performance using mathematical programming tools. The use of constraints and inequalities improve modeling ability and can help regularize problems. Complementarity can play an important role in all these areas.
4. Time-dependent (dynamic) complementarity/VI systems
   Many new applications involve the notion of dynamic changes, either in time or for motion. Principal applications include business cycle models from economics and mechanical body dynamics from engineering. It was mentioned that most of the recent work in the latter area has been carried out in Europe, and involves a mixture of computation, applications and (mathematical) theory.
5. Integer models with complementarity
   Models involving complementarity and integer variables have not appeared extensively in the literature, probably due to a lack of any reasonable algorithm for their solution. The fields of semidefinite linear programming and semidefinite complementarity programming give some hope for future improvements on this front. Also, more interplay between MPEC and combinatorial approaches could lead to potential gains in both disciplines by using algorithmic and theoretical approaches in the other format.
6. Uncertainty in complementarity models
   For practical purposes, many complementarity models involve uncertain data (for example in engineering measurements) and uncertain future outcomes, e.g. economic forecasting models. The field needs to evolve to allow such problems to be treated in an effective manner. Several approaches based on large scale "scenario decompositions" or sample path optimization are under development but these need further investigation.

Education

It was noted that real applications drive theory. We need publicity of genuine applications - not just academic applications (from other fields). More coverage is needed in popular "scientific" outlets such as Scientific American. We need to advertise that OR is a profession by generating more visibility in order that industry will acknowledge our expertise and actively seek our help.

Funding

There is industry support for a variety of important "must solve" applications that seed money could be provided for. Typical problems involve small feasible regions, and hindsight indications of what limited the process.