Linear Complementarity

The rich theory of linear complementarity deals with solving linear or quadratic (convex) optimization problems by constructing solutions to the necessary (and sufficient) Karush-Kuhn-Tucker conditions directly. There are many different pivoting techniques to handle the complementarity restrictions among the most prominent are Lemke's algorithm and Cottle's pricinpal pivoting technique. One of the outstanding questions is to clarify the algorithmic complexity for certain classes of LCP-problems, like the instances generated by P-matrices.

The LCP theory encompasses many different mathematical problems (Nash equilibria for bimatrix games, equlibria in transportation flow networks, etc.). Recently we applied the theory to design a fast algorithm for pricing american put options LCP_for_American_Options.

A different approach based on contracting mapping for fixed points is used by M. Wilhelm in Pricing Swing Options .

Our current research of combinatorial methods to solve LCPs is supported by the Swiss National Science Foundation (SNF). We apply combinatorial tools such as unique-sink orientations and oriented matroids for solving LCPs for several matrix classes (K-matrices, hidden Minkowski matrices, P-matrices, sufficient matrices, etc.)

Contacts

• H.-J. Lüthi
• K. Fukuda
• Jan Foniok
• Lorenz Klaus

Collaborators

• Bernd Gärtner

Recent publications

• Columbano S., Fukuda K., Jones C. (2009): "An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices." In: Avis D., Bremner D., Deza A. (eds.): Polyhedral Computation, AMS, Vol. 48:73-102. (URL)
• Foniok J., Fukuda K., Gärtner B., Lüthi H. (2009): "Pivoting in Linear Complementarity: Two Polynomial-Time Cases." Discrete Comput. Geom., 42(2):187-205. (DOI, URL)
• Foniok J., Fukuda K., Klaus L. (2009): "Combinatorial Characterizations of K-matrices." (URL)
• Fukuda K., Moriyama S., Okamoto Y. (2009): "The Holt-Klee condition for oriented matroids." Europ. J. Combinatorics, 30(8):1854-1867. (URL)
• Wilhelm M., Winter C. (2008): "Finite element valuation of swing options." Journal of Computational Finance, 11(3):107-132.
• Borici A., Lüthi H. (2005): "Fast solutions of complementarity formulations in American put pricing." Journal of Computational Finance, 9(1):63-81. (PDF)