COMPASS

COMPASS is a globally convergent algorithm for solving the Mixed Complementarity Problem (MCP) implemented in MATLAB version R2011a. The mathematical theory behind it is based on the PATH solver, the standard solver for complementarity problems. COMPASS is published under the GNU General Public License and hence is free software.

The MCP in the box constrained formulation (objective function and boundaries) and the Jacobian of the objective function must be provided in a file based interface by the user.

The program was written by Stefan Schmelzer (University of Vienna) as part of his diploma thesis. Please inform the author at schmelzer@ihs.ac.at if you make serious use of this code.

COMPASS is an implementation of a stabilized Newton method. The MCP is reformulated as the problem of finding a zero of a generally nonsmooth function (normal map, or normal equation), a general first order approximation of which is computed at the current iterate. Finding a zero of this approximation turns out to be a linear MCP, which is solved with the help of a pivot technique, similar to the one described by Lemke. This pivot algorithm yields a piecewise linear path connecting the current point and the zero of the approximation.

Whether the endpoint of this path is accepted as the next iterate, depends on the non-monotone stabilization (NMS) - scheme, which employs a watchdog technique: the algorithm is embedded in a general descent framework, which uses a smooth merit function, and, depending on it, non-monotone descent criteria. These criteria are not checked in every step, which reduces the number of function and gradient evaluations. If the solution to the linear MCP is checked and not accepted, the generated path is searched for an acceptable point. If no satisfying point can be found, a projected gradient step is used.

The algorithm terminates successfully when the zero of the merit function has been found; this point corresponds to the zero of the normal map, as well as to a solution of the MCP.

The gzipped tar file COMPASS_v1.0.tar.gz (653KB) contains the MATLAB source code, a driver program showing its use, test examples for Version 1.0 (2012), and the diploma thesis

This thesis describes the mathematical backgrounds of the solver, the implementation, a convergence result, as well as some application and test examples. Please quote this thesis when using COMPASS in scientific work.