Solution of Complementarity Problems via Piecewise Linearization

My master thesis concerns the solution linear complementarity problems (LCP). The Lemke algorithm, the most commonly used algorithm for solving a LCP until this day, was compared with the piecewise Newton method (PLN algorithm). The piecewise Newton method is an algorithm to solve a piecewise linear system on the basis of damped Newton methods. The linear complementarity problem is formulated as a piecewise linear system for the applicability of the PLN algorithm. Then, different application examples will be presented, solved with the PLN algorithm. As a result of the findings (of my master thesis) it can be assumed that – under the condition of coherent orientation – the PLN-algorithm requires fewer iterations to solve a linear complementarity problem than the Lemke algorithm. The coherent orientation for piecewise linear problems corresponds for linear complementarity problems to the P-matrix-property. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)