6th International Conference on Complementarity Problems (ICCP2014) Berlin

Short Courses

Michael Ferris, Short Course: Theory and Computations for Multiple Optimization Problems with Equilibrium Constraints (MOPEC)
We present a mechanism for describing and solving collections of optimization problems that are linked by equilibrium conditions. The general framework of MOPEC (multiple optimization problems with equilibrium constraints) captures many example applications that involve independent decisions coupled by shared resources. Included in this class are classical models such as the PIES model, general equilibria with incomplete market models, and agent based formulations arising from Nash Games. We describe this mechanism in the context of energy planning, environmental and land-use problems, for example for capacity expansion, hydro operation, and water rights pricing. We show how to incorporate stochastic information into these systems and give examples of their use and their possible extensions to hierarchical modeling. We outline several algorithms and investigate their computational efficiency. We demonstrate how MOPECs can be implemented in modeling systems such as GAMS or AMPL.
Todd S. Munson, Short Course: Model-Method Iteration: Solving Good Problems and Detecting Bad Ones
Often, a single model can be presented to a numerical method in many different ways. Some equivalent formulations are easily solvable by some methods, while others may be nearly impossible to solve. Determining a good problem formulation can be expressed as an iterative process where we construct a model, attempt to solve the model, refine the model or change the method upon failure, and repeat. The way in which the failures manifest can provide important guidance during the refinement step, but the information presented is often ignored because it is not understood. In this tutorial, I will use case studies to illustrate good modeling practices and show the diagnostic tools and information available in some numerical methods. After identifying potential reasons for failures, I will discuss actions that can be taken to address some of them. This tutorial is geared toward practitioners needing to solve mixed complementarity problems and requires some exposure to theory and linear algebra.

Technical Presentations

Todd S. Munson, Revisiting Preprocessing for Generalized Nash Games
In this talk, we will revisit the use of preprocessing in the context of generalized Nash games. The basic technique for linear complementarity problems is to discover skew symmetric structure, reduce the problem to a polyhedral variational inequality, modify the geometric structure, and then return to the original space with the problem changed. For generalized Nash games, we show how to uncover the Nash game structure, reduce the individual components to a polyhedral variational inequality parameterized by the other player’s decisions, and discuss the modifications that can be made.
Michael Ferris , The Convergence of Stationary Iterations with Indefinite Splitting
The relationship of diagonal dominance ideas to the convergence of stationary iterations is well known. There are a multitude of situations in which such considerations can be used to guarantee convergence when the splitting matrix (the preconditioner) is positive definite. In this paper we prove sufficient conditions for convergence of a stationary iteration based on a splitting with an indefinite preconditioner. Examples covered by this theory coming from Complementarity, Optimization and Economics are described.
Mihai Anitescu, Iterative Methods for Complementarity Problems in Many-Body Contact Dynamics Simulation
Many-body dynamics problems are expected to handle millions of unknowns when, for instance, investigating the three-dimensional flow of granular material. Solving such problems by a differential variational inequality approach results in very large scale and challenging complementarity problems. We describe the setup and performance of several iterative methods that are based on an optimization interpretation of the resulting complementarity or cone complementarity problem. These include: the gradient projected minimum residual method and the preconditioned spectral projected gradient with fallback method that are applied to temporal discretizations of differential variational formulations of large-scale many-body dynamics problems. We compare their performance with the one of more elementary methods, such as projected Jacobi and Gauss-Seidel that were recently used to solve very large scale instances of such problems.