Basis- and partition identification for quadratic programming and linear complementarity problems

Basis- and partition identification for quadratic programming and linear complementarity problems

0.00 Avg rating0 Votes
Article ID: iaor20003798
Country: Germany
Volume: 50
Issue: 2
Start Page Number: 261
End Page Number: 282
Publication Date: Jan 1999
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , , ,
Keywords: programming: linear
Abstract:

Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal 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 partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementarity 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 complementary problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus.

Reviews

Required fields are marked *. Your email address will not be published.