On the Polynomiality of the Multiplicative Penalty Function Method for Linear Programming and Related Inscribed Ellipsoids

Hiroshi IMAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E74-A   No.4   pp.669-671
Publication Date: 1991/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)
Category: 
Keyword: 


Full Text: PDF>>
Buy this Article



Summary: 
The paper proves the polynomiality of the multiplicative penalty function method for linear programming proposed by Iri and Imai. This is accomplished by considering ellipsoids determined by the Hessian at an interior point and centered at the point, and showing that, for any interior point, there is such an ellipsoid contained in the feasible region in which the penalty function is well approximated by a linear function determined by the gradient at the point.