Abstract
Karmarkar's potential function is quasi-convex, but not convex. This note investigates the multiplicative version of the potential function, and shows that it is not necessarily convex in general, but is strictly convex when the corresponding feasible region is bounded. This implies that the multiplicative version of the potential function in Karmarkar's algorithm is convex, since it works on a simplex.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Iri and H. Imai, “A multiplicative penalty function method for linear programming—Another ‘new and fast’ algorithm,”Proceedings of the 6th Mathematical Programming Symposium of Japan (Tokyo, 1985) pp. 97–120.
M. Iri and H. Imai, “A multiplicative barrier function method for linear programming,”Algorithmica 1 (1986) 455–482.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
N. Megiddo, “On the complexity of linear programming,” Research Report RJ 4985 (52162), IBM Almaden Research Center, San Jose (California, 1986).
M.J. Todd and B.P. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Imai, H. On the convexity of the multiplicative version of Karmarkar's potential function. Mathematical Programming 40, 29–32 (1988). https://doi.org/10.1007/BF01580721
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580721