Abstract
This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O(nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function
wherex is the vector of primal variables ands is the vector of dual slack variables, and q = n +\(\sqrt n \). The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O(\(\sqrt n \) L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function
where q = n +\(\sqrt n \). We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameterq in the following sense. Suppose thatq = n + n t wheret⩾0. Then the algorithm will solve the linear program in O(n r L) iterations, wherer = max{t, 1 − t}. Thus the value oft that minimizes the complexity bound ist = 1/2, yielding Ye's O(\(\sqrt n \) L) iteration bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K.M. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498.
K.M. Anstreicher, “A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm,” Yale School of Organization and Management (New Haven, CT, 1987).
K.M. Anstreicher and R.A. Bosch, “Long Steps in a O(n 3 L) algorithm for linear programming,” Yale School of Organization and Management (New Haven, CT, 1989).
D.A. Bayer and J.C. Lagarias, “The nonlinear geometry of linear programming, I. Affine and projective scaling trajectories, II. Legendre transform coordinates and central trajectories,”Transactions of the American Mathematical Society (1987), forthcoming.
R. Freund, “Projective transformations for interior point methods, part I: Basic theory and linear programming,” MIT Operations Research Center working paper OR 179-88 (1988).
D. Gay “A variant of Karmarkar's linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90.
C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” Memorandum UCB/ERL M87/10, Electronics Research Laboratory, University of California (Berkeley, CA, 1987).
C.C. Gonzaga, “Polynomial affine logarithms for linear programming,” Report ES-139/88, Universidade Federal do Rio de Janeiro (Rio de Janeiro, Brazil, 1988).
N. Karmarkar, “A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
N. Megiddo, “Pathways to the optimal set in linear programming,” Research Report RJ 5295, IBM Almaden Research Center (San Jose, CA, 1986).
R.C. Monteiro and I. Adler, “An O(n 3 L) primal—dual interior point algorithm for linear programming,” Department of Industrial Engineering and Operations Research, University of California (Berkeley, CA, 1987).
J. Renegar, “A polynomial time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–94.
G. Rinaldi, “The projective method for linear programming with box-type constraints,” Instituto di Analisi dei Sistemi ed Informatica del CNR, Viale Manzoni 30, 00185 (Rome, Italey, 1985).
M.J. Todd and B. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.
M.J. Todd and Y. Ye, “A centered projective algorithm for linear programming,” Technical Report 763, School of ORIE, Cornell University (Ithaca, NY, 1987).
P. Vaidya, “An algorithm for linear programming which requires O(((m+n)n 2+(m+n) 1.5 n)L) arithmetic operations,” AT&T Bell Laboratories (Murray Hill, NJ, 1987).
Y. Ye, “Interior algorithms for linear, quadratic, and linearly constrained convex programming,” Ph.D. Thesis, Department of Engineering Economic Systems, Stanford University (Stanford, CA, 1987).
Y. Ye, “A class of potential functions for linear programming,” Presented at theJoint Summer Research Conference: Mathematical Developments Arising from Linear Programming Algorithms, Bowdoin College (Brunswick, ME, 1988).
Y. Ye, “A class of potential functions for linear programming,” Department of Management Sciences, The University of Iowa (Iowa City, IA, 1988).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Freund, R.M. Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Mathematical Programming 51, 203–222 (1991). https://doi.org/10.1007/BF01586933
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01586933