New variants of the criss-cross method for linearly constrained convex quadratic programming
In this paper, S. Zhang's [Eur. J. Oper. Res. 116 (1999) 607] new and more flexible criss-cross type algorithms (with LIFO and most-often-selected-variable pivot rules) are generalized for linearly constrained convex primaldual quadratic programming problems. These criss-cross type algorithms are different from the one described in Klafszky and Terlaky [Math. Oper. und Stat. Ser. Optim. 24 (1992) 127]. Even though the finiteness proof of these new criss-cross type algorithms is similar to the original one for the algorithm of Klafszky and Terlaky (in the sense that both these proofs are based on the orthogonality theorem), more cases have to be considered due to the flexibility of pivot (LIFO/most-often-selected-variable) rules, which requires a deeper and more careful analysis. When the primaldual problem is a linear programming problem (no quadratic terms in the objective function), the structure of the corresponding linear complementarity problem is simpler (i.e. the matrix of the problem is skew-symmetric). For such problem pairs, our proof of finiteness simplifies to the proof of Ills and Mszros' [Yugoslav J. Oper. Res. 11 (2001) 17] and provides a new finiteness proof for S. Zhang's criss-cross type algorithms.
criss-cross type algorithms linear complementarity problems linearly constrained convex quadratic optimization