Some remarks on Karmarkar's potential function
type: Item
instance of: scholarly article
title: Some remarks on Karmarkar's potential function
zbMATH Open document ID: 0655.90047
DOI: 10.1007/BF01837971
author: George T. Diderrich
published in: Aequationes Mathematicae
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/137274
review text: 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.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 39B99
zbMATH DE Number: 4070625
zbMATH Keywords: Karmarkar algorithm
zbMATH Keywords: potential function
zbMATH Keywords: projective algorithm
zbMATH Keywords: geometric mean
MaRDI profile type: Publication
cites work: Q5514010
cites work: Q5822835
cites work: A new polynomial-time algorithm for linear programming
cites work: A different convergence proof of the projective method for linear programming
cites work: Q3818127
cites work: On the average number of steps of the simplex method of linear programming
cites work: An experimental approach to karmarkar’s projective method for linear programming
OpenAlex ID: W2092239591
Recommended article: On the convexity of the multiplicative version of Karmarkar's potential function
Recommended article: Q3593002
Recommended article: Q3198031
Recommended article: A Note on Kawashima Functions
Recommended article: Some properties of the Feynman-Kac functional
Recommended article: Remarks on the Carlitz \(\psi\)-functions
description: scientific article; zbMATH DE number 4070625