New variants of the criss-cross method for linear complementarity problems with bisymmetric matrices

In this paper, S. Zhang's new and more flexible criss-cross type pivot rule is generalized for linearly constrained convex/concave primal–dual quadratic programming problem. The obtained criss-cross type algorithm is different from the original criss-cross algorithm defined by Klafszky and Terlaky. The finiteness proof of this new criss-cross algorithm is similar to the original one, in the sense that it is based on the orthogonality theorem. Furthermore, if the primal–dual problem is a linear programming problem (no quadratic terms in the objective function) then the structure of the corresponding linear complementarity problem is simpler and then our proof of finiteness of the algorithm leads to a new proof of S. Zhang's criss-cross type algorithm for linear programming problem.