×

zbMATH — the first resource for mathematics

Superlinear convergence of the affine scaling algorithm. (English) Zbl 0870.90083
Summary: We show that a variant of the long-step affine scaling algorithm (with variable stepsizes) is two-step superlinearly convergent when applied to general linear programming (LP) problems. Superlinear convergence of the sequence of dual estimates is also established. For homogeneous LP problems having the origin as the unique optimal solution, we also show that \({2\over 3}\) is a sharp upper bound on the (fixed) stepsize that provably guarantees that the sequence of primal iterates converge to the optimal solution along a unique direction of approach. Since the point to which the sequence of dual estimates converge depend on the direction of approach of the sequence of primal iterates, this result gives a plausible (but not accurate) theoretical explanation for why \({2\over 3}\) is a sharp upper bound on the (fixed) stepsize that guarantees the convergence of the dual estimates.

MSC:
90C05 Linear programming
Software:
DIMACS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N.K. 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, N.K. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming,”Mathematical Programming 44 (1989) 297–335. (Errata inMathematical Programming 50 (1991) 415.) · Zbl 0682.90061
[3] 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
[4] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052
[5] Y.-C. Cheng, D.J. Houck, J.-M. Liu, M.S. Meketon, L. Slutsman, R.J. Vanderbei and P. Wang, ”The AT& T KORBX System”,AT&T Technical Journal 68 (3) (1989) 7–19.
[6] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Doklady Akademii Nauk SSSR 174 (1967) 747–748. (Translated in:Soviet Mathematics Doklady 8 (1967) 674–675.) · Zbl 0189.19504
[7] I.I. Dikin, ”On the convergence of an iterative process,”Upravlyaemye Sistemi 12 (1974) 54–60 (In Russian). · Zbl 0402.90059
[8] I.I. Dikin, ”The convergence of dual variables,” Technical Report Siberian Energy Institute (Irkutsk, Russia, December 1991).
[9] I.I. Dikin, ”Determination of the interior point of one system of linear inequalities,”Kibernetica and System Analysis 1 (1992). · Zbl 0875.90326
[10] I.I. Dikin and V.I. Zorkaltsev,Iterative Solutions of Mathematical Programming Problems (Nauka, Novosibirsk, USSR, 1980).
[11] R. Fletcher,Practical Methods of Optimization, 2nd edition (Wiley, New York, 1987). · Zbl 0905.65002
[12] C.C. Gonzaga, ”Convergence of the large step, primal affine-scaling algorithm for primal nondegenerate linear programs,” Technical Report, ES-230/90, Dept. of Systems Engineering and Computer Science, COPPE Federal University of Rio de Janeiro (Rio de Janeiro, Brazil, Sept. 1990).
[13] L.A. Hall and R.J. Vanderbei, ”Two-thirds is sharp for affine scaling,”Operations Research Letters 13 (1993) 197–201. · Zbl 0794.90033
[14] A.J. Hoffman, ”On approximate solutions of systems of linear inequalities,”Journal of Research of the National Bureau of Standards 49 (1952) 263–265.
[15] N.K. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[16] N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms in linear programming,”Mathematics of Operations Research 14 (1989) 97–114. · Zbl 0675.90050
[17] S. Mehrotra, ”Quadratic convergence in a primal-dual method,”Mathematics of Operations Research 18 (1993) 741–751. · Zbl 0794.90034
[18] C.L. Monma and A.J. Morton, ”Computational experience with the dual affine variant of Karmarkar’s method for linear programming,”Operations Research Letters 6 (1987) 261–267. · Zbl 0627.90065
[19] R.D.C. Monteiro and T. Tsuchiya and Y. Wang, ”A simplified global convergence proof of the affine scaling algorithm,”Annals of Operations Research 47 (1993) 443–482. · Zbl 0804.90091
[20] M. Muramatsu and T. Tsuchiya, ”Convergence analysis of the projective scaling algorithm, based on a long-step homogeneous affine scaling algorithm,”Mathematical Programming 72, (1996) 291–305. · Zbl 0853.90084
[21] M.G.C. Resende and G. Veiga, ”An efficient implementation of a network interior point method.” in: D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, Vol. 12 (American Mathematical Society, 1993) pp. 299–348. · Zbl 0787.90028
[22] L. Sinha and B. Freedman and N. Karmarkar and A. Putcha and K. Ramakrishnan, ”Overseas network planning,”Proc. Third Internat. Network Planning Sysmposium–Networks’86, (IEEE Communications Society, held on June 1–6, 1986, Tarpon Springs, FL, 1986) 121–124.
[23] M. Todd, ”A low complexity interior-point algorithm for linear programming,”SIAM Journal on Optimization 2 (1992) 198–209. · Zbl 0811.90070
[24] M. Todd and J.-P. Vial, ”Todd’s complexity interior-point algorithm is a predictor-corrector path-following algorithm,”Operations Research Letters 11 (1992) 199–207. · Zbl 0768.90055
[25] P. Tseng and Z.Q. Luo, ”On the convergence of the affine-scaling algorithm,”Mathematical Programming 56 (1992) 301–319. · Zbl 0762.90052
[26] T. Tsuchiya, ”Global convergence of the affine-scaling methods for degenerate linear programming problems,”Mathematical Programming 52 (1991) 377–404. · Zbl 0749.90051
[27] T. Tsuchiya, ”Quadratic convergence of Iri and Imai’s method for degenerate linear programming problems,”Journal of Optimization Theory and Applications 87 (3) (1995) 703–726. · Zbl 0840.90101
[28] T. Tsuchiya, ”Global convergence property of the affine scaling method for primal degenerate linear programming problems,”Mathematics of Operations Research 17 (3) (1992) 527–557. · Zbl 0762.90053
[29] T. Tsuchiya and M. Muramatsu, ”Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems,”SIAM Journal on Optimization 5 (3) (1995) 525–551. · Zbl 0838.90081
[30] R.J. Vanderbei and J.C. Lagarias, ”I.I. Dikin’s convergence result for the affine-scaling algorithm,”Contemporary Mathematics 114 (1990) 109–119. · Zbl 0727.90050
[31] R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”A modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (4) (1986) 395–407. · Zbl 0626.90056
[32] C. Witzgall, P.T. Boggs and P.D. Domich, ”On the convergence behavior of trajectories for linear programming,”Contemporary Mathematics 114 (1990) 109–119. · Zbl 0725.90060
[33] Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, ”A quadratically convergent \(O(\sqrt n L)\) -iteration algorithm for linear programming,”Mathematical Programming 59 (1993) 151–162. · Zbl 0778.90037
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.