For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Polynomiality of the Multiplicative Penalty Function Method for Linear Programming and Related Inscribed Ellipsoids
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1991/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)
Full Text: PDF>>
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.