A primal-dual interior point method whose running time depends only on the constraint matrix.

*(English)*Zbl 0868.90081Summary: We propose a primal-dual “layered-step” interior point (LIP) algorithm for linear programming with data given by real numbers. This algorithm follows the central path, either with short stops or with a new type of step called a “layered least squares” (LLS) step. The algorithm returns an exact optimum after a finite number of steps – in particular, after \(O(n^{3.5}c(A))\) iterations, where \(c(A)\) is a function of the coefficient matrix. The LLS steps can be thought of as accelerating a classical path-following interior point method. One consequence of the new method is a new characterization of the central path: we show that it composed of at most \(n^2\) alternating straight and curved segments. If the LIP algorithm is applied to integer data, we get as another corollary a new proof of a well-known theorem by Tardos that linear programming can be solved in strongly polynomial time provided that \(A\) contains small-integer entries.

##### MSC:

90C51 | Interior-point methods |

##### Keywords:

layered least squares; interior point method; characterization of the central path; strongly polynomial time
PDF
BibTeX
Cite

\textit{S. A. Vavasis} and \textit{Y. Ye}, Math. Program. 74, No. 1 (A), 79--120 (1996; Zbl 0868.90081)

Full Text:
DOI

##### References:

[1] | R. K. Ahuja, T. L. Magnanti and J. B. Orlin,Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, New Jersey, 1993). · Zbl 1201.90001 |

[2] | D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories,Transactions of the AMS 314 (1989) 499–526. · Zbl 0671.90045 |

[3] | D. A. Bayer and J. C. Lagaria, The nonlinear geometry of linear programming, II. Legendre transform coordinates and central trajectories,Transactions of the AMS 314 (1989) 527–581. · Zbl 0671.90046 |

[4] | D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry,Transactions of the AMS 320 (1990) 193–225. · Zbl 0699.90070 |

[5] | A. Ben-Tal and M. Teboulle, A geometric property of the least squares solutions of linear equations,Linear Algebra and Its Applications 139 (1990) 165–170. · Zbl 0704.15005 |

[6] | T. Coleman, Large-scale numerical optimization: introduction and overview, in: A. Kent and J. G. Williams, eds.,Encyclopedia of Computer Science and Technology 28 (Marcel Dekker, New York, 1993) 167–195. |

[7] | J. Edmonds, Systems of distinct representatives and linear algebra,Journal of Research of the National Bureau of Standards 71B (1967) 241–245. · Zbl 0178.03002 |

[8] | A. Forsgren, On linear least-squares problems with diagnonally dominant weight matrices, Technical Report TRITA-MAT-1995-OS2, Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden. · Zbl 0885.65046 |

[9] | G. H. Golub and C. F. V. Loan,Matrix Computations, 2nd edn. (Johns Hopkins University Press, Baltimore, 1989) · Zbl 0733.65016 |

[10] | C. C. Gonzaga, Path-following methods for linear programming,SIAM Review 34 (1992) 167–224. · Zbl 0763.90063 |

[11] | J. A. Kaliski and Y. Ye, A short-cut potential reduction algorithm for linear programming,Management Science 39 (1993) 757–773. · Zbl 0783.90073 |

[12] | N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 |

[13] | L. Khachiyan, On the complexity of approximating extremal determinants in matrices, Preprint (1994). · Zbl 0819.65085 |

[14] | L. G. Khachiyan. A polynomial algorithm in linear programming,Doklady Akademii Nauk SSSR 244 (1979) 1093–1086 (translated inSoviet Math. Dokl. 20 (1979) 191–194). · Zbl 0414.90086 |

[15] | 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 |

[16] | I. J. Lustig, R. E. Marsten and D. F. Shanno, Computational experience with a primal-dual interior point method for linear programming,Linear Algebra and Its Applications 152 (1991) 191–222. · Zbl 0731.65049 |

[17] | L. McLinden, An analogue of Moreau’s proximation theorem, with applications to the nonlinear complementarity problem.Pacific Journal of Mathematics 88 (1980) 101–161. · Zbl 0434.90096 |

[18] | N. Megiddo, Pathways to the optimal set in linear programming, in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior Point and Related Method (Springer, New York, 1989) 131–158. · Zbl 0687.90056 |

[19] | 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 |

[20] | S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming,Mathematics of Operations Research 18 (1993) 964–981. · Zbl 0810.90091 |

[21] | S. Mizuno, M.J. Todd and Y. Ye, A surface of analytic centers and infeasible interior-point algorithms for linear programming,Mathematics of Operations Research 20 (1995) 135–162. · Zbl 0834.90088 |

[22] | R. C. Monteiro and I. Adler, Interior path following primal-dual algorithm. Part I: linear programming,Mathematical Programming 44 (1989) 27–41. · Zbl 0676.90038 |

[23] | Y. Nesterov and A. Nemirovskii,Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM Studies in Applied Mathematics 13 (SIAM, Philadelphia, 1994). · Zbl 0824.90112 |

[24] | D. P. O’Leary, On bounds for scaled projections and pseudoinverses,Linear Algebra and Its Applications 132 (1990) 115–117. · Zbl 0701.15003 |

[25] | J. B. Orlin, A faster strongly polynomial minimum cost flow algorithm, in:Proceedings 20th ACM Symposium on the Theory of Computing (1988) 277–388. |

[26] | C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice Hall, Englewood Cliff, NJ, 1982). · Zbl 0503.90060 |

[27] | J. Renegar, A polynomial-time algorithm based on Newton’s method for linear programming.Mathematical Programming 40 (1988) 59–94. · Zbl 0654.90050 |

[28] | J. Renegar, Linear Programming, Complexity Theory, and Elementary Functional Analysis, unpublished manuscript, Department of Operations Research and Industrial Engineering, Cornell University (1993). |

[29] | M. G. C. Resende and G. Veiga, An efficient implementation of a network interior point method, Technical report, Mathematical Sciences Research Center, AT & T Bell Laboratories, Murray Hill, NJ 07974-0636, USA (1992). Revised March 1992, revised version 2.0 August 1992 (to appear inDIMACS Series in Discrete Mathematics and Theoretical Computer Science). · Zbl 0787.90028 |

[30] | G. Sonnevend, An ’analytic center’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in: A. Prekopa, J. Szelezsan and B. Strazicky, eds.,System Modelling and Optimization: Proceedings of the 12th IFIP Conference, Budapest, Hungary (1985). Lecture Notes in Control and Information Sciences. 84 (Springer Verlag, Berlin, Germany, 1986) 866–876. |

[31] | G. Sonnevend, J. Stoer and G. Zhao. On the complexity of following the central path of linear programs by linear extrapolation II,Mathematical Programming 52 (1991) 527–553. · Zbl 0742.90056 |

[32] | G. W. Stewart, On scaled projections and pseudoinverses,Linear Algebra and Its Applications 112 (1989) 189–193. · Zbl 0658.15003 |

[33] | E. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs,Operations Research 34 (1986) 250–256. · Zbl 0626.90053 |

[34] | M. J. Todd, A Dantzig-Wolfe-like variant of Karmarkar’s interior-point linear programming algorithm,Operations Research 38 (1990) 1006–1018. · Zbl 0724.90037 |

[35] | K. Tone, An active-set strategy in an interior point method for linear programming,Mathematical Programming 59 (1993) 345–360. · Zbl 0804.90093 |

[36] | L. Tuncel, A pseudo-polynomial complexity analysis for interior-point algorithms. Technical Report CORR 93-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada (1993). |

[37] | S. A. Vavasis,Nonlinear Optimization: Complexity Issues (Oxford University Press, New York, 1991). |

[38] | S. A. Vavasis, Stable finite elements for problems with wild coefficients, Technical Report 93-1364, Department of Computer Science, Cornell University, Ithaca, NY (1993) (to appear inSIAM Journal on Numerical Analysis). · Zbl 0858.65112 |

[39] | S. A. Vavasis, Stable numerical algorithms for equilibrium systems,SIAM Journal on Matrix Analysis and Applications 15 (1994) 1108–1131. · Zbl 0806.65020 |

[40] | S. A. Vavasis and Y. Ye, Condition numbers for polyhedra with real number data,Operations Research Letters 17 (1995) 209–214. · Zbl 0858.90097 |

[41] | M. H. Wright, Numerical methods for nonlinearly constrained optimization, Ph. D. Thesis, Stanford University (1976). |

[42] | M. H. Wright, Interior methods for constrained optimization, in: A. Iserles, ed.,Acta Numerica 1992 (Cambridge University Press, Cambridge, 1992) 341–407. · Zbl 0766.65053 |

[43] | Y. Ye, On the finite convergence of interior-point algorithms for linear programming,Mathematical Programming 57 (1992) 325–336. · Zbl 0794.90036 |

[44] | 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.