A new proof for the criss-cross method for quadratic programming

Abstract

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 Klafszky. The proof of Chang is very complicated. Terlaky and Klafszky provide much simpler proofs for the Criss-Cross method. We propose 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. We use two additional examples, due essentially to Fathi and Murty, to analyse the worst-case behaviour of the method.

Keywords:

• Quadratic Programming
• Linear Programming
• Principal Pivoting
• Pivotal Operation
• Bland's Rule
• Terlaky's Criss-Cross Method for Linear Programming