×

zbMATH — the first resource for mathematics

On the convergence of the affine-scaling algorithm. (English) Zbl 0762.90052
An algorithm is described for linear programming which have polynomial- time complexity (also in the presence of degeneracy). Especially, it is shown that, for special stepsize choices, the algorithm generates iterates that converge at least linearly with a convergence ratio of \(1- \beta/\sqrt n\), where \(n\) is the number of variables and \(\beta\in(0,1]\) is a certain stepsize ratio. Moreover, using an adapted form of Barnes’ stepsize choice it is proved that the sequence of iterates converges to a point satisfying a so-called \(\varepsilon\)-complementary slackness condition.
Reviewer: R.Nehse (Ilmenau)

MSC:
90C05 Linear programming
90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”Data structures and programming techniques for the implementation of Karmarkar’s algorithm,”ORSA Journal on Computing 1 (1989) 84–106. · Zbl 0752.90043
[2] 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. · Zbl 0719.90044
[3] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052
[4] D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Englewood Cliffs, NJ, 1989). · Zbl 0743.65107
[5] D.P. Bertsekas and J. Eckstein, ”Dual coordinate step methods for linear network flow problems,”Mathematical Programming 42 (1988) 203–243. · Zbl 0664.90031
[6] T.M. Cavalier and A.L. Soyster, ”Some computational experience and a modification of Karmarkar’s algorithm,” ISME Working Paper 85-105, Pennsylvania State University (University Park, PA, 1985).
[7] V. Chandru and B.S. Kochar, ”A class of algorithms for linear programming,” Research Memorandum No. 85-14, Purdue University (Lafayette, IN, 1985).
[8] V. Chandru and B.S. Kochar, ”Exploring special structures using a variant of Karmarkar’s algorithm,” Research Memorandum No. 86-10, Purdue University (Lafayette, IN, 1986).
[9] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[10] I.I. Dikin, ”On the speed of an iterative process,”Upravlyaemye Sistemi 12 (1974) 54–60. · Zbl 0402.90059
[11] I.I. Dikin, Letter to the Editor,Mathematical Programming 41 (1988) 393–394.
[12] L.R. Ford and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, NJ, 1962). · Zbl 0106.34802
[13] K.R. Frisch, ”The logarithmic potential method of convex programming,” Technical Report. University Institute of Economics (Oslo, Norway, 1955).
[14] C.C. Gonzaga, ”An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior-Point and Related Methods (Springer, New York, 1989). · Zbl 0691.90053
[15] A.J. Hoffman, ”On approximate solutions of systems of linear inequalities,”Journal of Research of the National Bureau of Standards 49 (1952) 263–265.
[16] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[17] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087
[18] K.O. Kortanek and M. Shi, ”Convergence results and numerical experiments on a linear programming hybrid algorithm,”European Journal of Operational Research 32 (1987) 47–61. · Zbl 0631.90038
[19] O.L. Mangasarian and T.-H. Shiau, ”Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems,”SIAM Journal on Control and Optimization 25 (1987) 583–595. · Zbl 0613.90066
[20] R.E. Marsten, M.J. Saltzman, D.F. Shanno and G.S. Pierece, ”Implementation of a dual affine interior point algorithm for linear programming,” Working Paper, Center for the Management of Information, University of Arizona (Tucson, AZ, 1988).
[21] N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms in linear programming,”Mathematics of Operations Research 14 (1989) 97–146. · Zbl 0675.90050
[22] S. Mehrotra and J. Sun, ”A method of analytic centers for quadratically constrained convex quadratic programs,”SIAM Journal on Numerical Analysis 28 (1991) 529–544. · Zbl 0742.65046
[23] C.L. Monma and A.J. Morton, ”Computational experiments with a dual affine variant of Karmarkar’s method for linear programming,”Operations Research Letters 6 (1987) 261–267. · Zbl 0627.90065
[24] R.C. Monteiro and I. Adler, ”Interior path following primal-dual algorithms. Part II: convex quadratic programming,”Mathematical Programming 44 (1989) 43–66. · Zbl 0676.90039
[25] R.D.C. Monteiro, I. Adler and M.G.C. Resende, ”A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension,”Mathematics of Operations Research 15 (1990), 191–214. · Zbl 0714.90060
[26] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[27] C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982). · Zbl 0503.90060
[28] G.B. Passty, ”Ergodic convergence to a zero of the sum of monotone operators in Hilbert space,”Journal of Mathematical Analysis and its Applications 72 (1979) 383–390. · Zbl 0428.47039
[29] J. Renegar, ”A polynomial-time algorithm, based on Newton’s method, for linear programming,”Mathematical Programming 40 (1988) 59–93. · Zbl 0654.90050
[30] S.M. Robinson, ”Bounds for errors in the solution set of a perturbed linear program,”Linear Algebra and its Applications 6 (1973) 69–81. · Zbl 0283.90028
[31] R.T. Rockafellar,Network Flows and Monotropic Optimization (Wiley, New York, 1984). · Zbl 0596.90055
[32] P. Tseng, ”Complexity analysis of a linear complementarity algorithm based on a Lyapunov function,”Mathematical Programming 53 (1992) 297–306. · Zbl 0787.90100
[33] P. Tseng and D.P. Bertsekas, ”Relaxation methods for linear programs,”Mathematics of Operations Research 12 (1987) 569–596. · Zbl 0642.90068
[34] P. Tseng and D.P. Bertsekas, ”Relaxation methods for monotropic programs,”Mathematical Programming 46 (1990) 127–151. · Zbl 0694.90077
[35] T. Tsuchiya, ”Global convergence property of the affine scaling methods for primal degenerate linear programming problems,” to appear in:Mathematics of Operations Research. · Zbl 0762.90053
[36] T. Tsuchiya, ”Global convergence of the affine scaling methods for degenerate linear programming problems,” Technical Report, The Institute of Statistical Mathematics (Tokyo, Japan, 1990).
[37] P.M. Vaidya, ”An algorithm for linear programming which requires O(((m+n)n 2 +(m+n) 1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–201. · Zbl 0708.90047
[38] R.J. Vanderbei, ”Affine-scaling for linear programs with free variables,”Mathematical Programming 43 (1989) 31–44. · Zbl 0825.90681
[39] R.J. Vanderbei and J.C. Lagarias, ”I.I. Dikin’s convergence result for the affine-scaling algorithm,” Technical Report, AT&T Bell Laboratories (Murray Hill, NJ, 1988). · Zbl 0727.90050
[40] R.J. Vanderbei, M.S. Meketon and B.A. Freeman, ”A modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–407. · Zbl 0626.90056
[41] Y. Ye, ”An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258. · Zbl 0734.90057
[42] Y. Ye, ”An extension of Karmarkar’s algorithm and the trust region method for quadratic programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior-Point and Related Methods (Springer, New York, 1989). · Zbl 0678.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.