A new proof for the Criss-Cross method for quadratic programming

In a working paper Chang has introduced a simple method for the linear complementarity problem involving a nonnegative definite matrix, based on principal pivoting and the least-index rule of Bland. This method has two important special cases, namely the Criss-Cross methods for linear programming and for convex quadratic programming, invented later independently by Terlaky and Klafsky. The proof of Chang is very complicated. Terlaky and Klafszky provided much simpler proofs for the Criss-Cross method. The paper proposes another simple proof for the Criss-Cross method for quadratic programming. It appears from an example by Roos that the number of pivots required by the Criss-Cross method may grow exponentially with the number of the constraints of the problem. The paper uses two additional examples, due essentially to Fathi and Murty, to analyse the worst-case behaviour of the method.