Some remarks on Karmarkar's potential function (Q1109675)

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.