Abstract
In this paper we give a new convergence analysis of a projective scaling algorithm. We consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed fraction λ≤2/3 of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, we will show (i) polynomiality of the algorithm with complexities of O(nL) and O(n 2 L) iterations for λ<2/3 and λ=2/3, respectively; (ii) global covnergence of the algorithm when the optimal face is unbounded; (iii) convergence of the primal iterates to a relative interior point of the optimal face; (iv) convergence of the dual estimates to the analytic center of the dual optimal face; and (v) convergence of the reduction rate of the objective function value to 1−λ.
Similar content being viewed by others
References
I. Adler and R.D.C. Monteiro, “Limiting behavior of the affine scaling continuous trajectories for linear programming problems,”Mathematical Programming 50 (1991) 29–51.
K.M. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498.
K.M. Anstreicher, “The worst-case step in Karmarkar's algorithm,”Mathematics of Operations Research 14 (1989) 294–302.
K.M. Anstreicher, “On the performance of Karmarkar's algorithm over a sequence of iterations,”SIAM Journal on Optimization 1 (1991) 22–29.
E.R. Barnes “A variation on Karmarkar's algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182.
D.A. Bayer and J.C. Lagarias, “The nonlinear geometry of linear programming: I. Affine and projective trajectories,”Transactions of the American Mathematical Society 314 (1989) 499–526.
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675.
I.I. Dikin, “The convergence of dual variables,” Technical Report., Siberian Energy Institute, Irkutsk (1991).
D.M. Gay, “A variant of Karmarkar's linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90.
C.C. Gonzaga “Conical projection algorithms for linear programming,”Mathematical Programming 43 (1989) 151–173.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
C. McDiarmid, “On the improvement per iteration in Karmarkar's algorithm for linear programming,”Mathematical Programming 46 (1990) 299–320.
R.D.C. Monteiro, T. Tsuchiya and Y. Wang, “A simplified global convergence proof of the affine scaling algorithm,”Annals of Operations Research 7 (1993) 443–482.
Yu.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming,” Technical Report, School of OR/IE. Cornell University Ithaca, NY (1995).
R. Saigal, A simple proof of primal affine scaling method,” Technical Report, University of Michigan, Ann Arbor MI (1992).
M.J. Todd, “Potential reduction methods in mathematical programming,” Technical Report, School of OR/IE, Cornell University, Ithaca, NY (1995).
M.J. Todd and B.P. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.
T. Tsuchiya and M. Muramatsu, “Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems,”SIAM Journal on Optimization 5 (1995) 525–551.
R.J. Vanderbei and J.C. Lagarias, “I.I. Dikin's convergence result for the affine-scaling algorithm,”Contemporary Mathematics 114 (1990) 109–119.
R.J. Vanderbei, M.S. Meketon and B.A. Freedman, “A modification of Karmarkar's linear programing algorithm,”Algorithmica 1 (1986) 395–407.
Y. Ye and M. Kojima, “Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Muramatsu, M., Tsuchiya, T. Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm. Mathematical Programming 72, 291–305 (1996). https://doi.org/10.1007/BF02592094
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02592094