Optimal Basis and Optimal Tripartition Identification Algorithms for
Quadratic Programming and Linear Complementarity Problems;
from an interior solution to a basis solution and viceversa
Arjan B. Berkelaar, Benjamin Jansen, Kees Roos and Tamas Terlaky
Optimal solutions of interior point algorithms for linear
and quadratic programming and linear complementarity problems
provide maximal complementary solutions. Maximal complementary
solutions can be characterized by optimal (tri)partitions. On
the other hand, the solutions provided by simplex--based pivot
algorithms are given in terms of complementary bases. A basis
identification algorithm is an algorithm which generates a
complementary basis, starting from any complementary solution.
A tripartition identification algorithm is an algorithm which
generates a maximal complementary solution (and its corresponding
tripartition), starting from any complementary solution. In
linear programming such algorithms were respectively proposed
by Megiddo in 1991 and Balinski and Tucker in 1969.
nd quadratic programming and linear complementarity problems
provide maximal complementary solutions. Maximal complementary
solutions can be characterized by optimal (tri)partitions. On
the other hand, the solutions provided by simplex--based pivot
algorithms are given in terms of complementary bases. A basis
identification algorithm is an algorithm which generates a
complementary basis, starting from any complementary solution.
A tripartition identification algorithm is an algorithm which
generates a maximal complementary solution (and its corresponding
tripartition), starting from any complementary solution. In
linear programming such algorithms were respectively proposed
by Megiddo in 1991 and Balinski and Tucker in 1969.
In this paper we will present identification algorithms for
quadratic programming and linear complementarity problems
with sufficient matrices. The presented algorithms are based
on the principal pivot transform and the orthogonality property
of basis tableaus.
Technical Report, March, 1996.
Contact: berkelaa@opres.few.eur.nl