New variants of the criss-cross method for linearly constrained convex quadratic programming [An article from: European Journal of Operational Research]

This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2004. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
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 primal-dual 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 primal-dual 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 Illes and Meszaros' [Yugoslav J. Oper. Res. 11 (2001) 17] and provides a new finiteness proof for S. Zhang's criss-cross type algorithms.