Summary
The main objective of this paper is to clarify the role of the potential function in the projective algorithm and to determine all other admissible potential functions from some reasonable axioms. In particular, it is shown that there is only one “natural” choice of potential function, namely the ratio of the objective function and the geometric mean as a scaling function. In addition, it is shown that the geometric mean has the smallest distortion over possible asymmetrical scaling functions. This result is obtained through the development of a functional equation characterizing possible scaling functions and applying a key lemma utilized by Blair, Padberg and Schrijver in simplifying Karmarkar's analysis of the projective algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aczél, J. [1966],Lectures on functional equations and their applications. Chapters 3 and 5, Academic Press, New York, London.
Anstreicher, K. [1985],Analysis of a modified Karmarkar algorithm. Yale University, Preprint, School of Organization and Management. AlsoA monotonic projective algorithm for fractional linear programming, Algorithmica1 (1986), 483–498.
Bellman, R. andBeckenbach, E. F. [1961],Inequalities. Springer, Berlin.
Blair, C. [1985],The iterative step in the linear programming algorithm of N. Karmarkar. University of Illinois, Department of Business Administration, Faculty Working Paper No. 1114, February. Also appearing in Algorithmica1, (1986), 537–539.
Borwein, J., Styan, G. andWolkowicz, H. [1982],Some inequalities involving statistical expressions (solution of a problem of H. Foster). SIAM Rev.24, 340–342.
Busemann, H. andKelly, P. J. [1953],Projective geometry and projective metrics. Academic Press, New York.
Karmarkar, N. [1984],A new polynomial-time alogorithm for linear programming. Combinatorica4, 373–395
Levy, H. [1961],Projective and related geometries. MacMillan Company, New York.
Lustig, I. J. [1985],A practical approach to Karmarkar's algorithm. Stanford University, Department of Operations Research, Technical Report Sol 85–5, June.
Padberg, M. [1986],A different convergence proof of the projective method of linear programming. Oper. Res. Lett.4, 253–257.
Schrijver, A. [1986],Theory of linear and integer programming. Wiley-Interscience, New York.
Smale, S. [1983],On the average number of steps of the simplex method of linear programming. Math. Programming27, 241–263.
Tomlin, J. A. [1985],An experimental approach to Karmarkar's projective method for linear programming. Ketron, Inc., Mountain View, California.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Diderrich, G.T. Some remarks on Karmarkar's potential function. Aeq. Math. 36, 57–75 (1988). https://doi.org/10.1007/BF01837971
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01837971