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.
内容記述
Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)
雑誌名
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
On the Polynomiality of the Multiplicative Penalty Function Method for Linear Programming and Related Inscribed Ellipsoids
On the Polynomiality of the Multiplicative Penalty Function Method for Linear Programming and Related Inscribed Ellipsoids 1991.pdf
(189.27KB)
