User menu

Long-step strategies in interior-point primal-dual methods

Bibliographic reference Nesterov, Yurii. Long-step strategies in interior-point primal-dual methods.Faculty Research Seminar on Optimization in Theory and Practice (UNIV IOWA, OBERMANN CTR ADV STUDIES, IOWA CITY (Ia), Aug 01-12, 1994). In: Mathematical Programming, Vol. 76, no. 1, p. 47-94 (1997)
Permanent URL http://hdl.handle.net/2078.1/62801
  1. 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 314 (1989) 499–581.
  2. G. de Ghellink and J.-P. Vial, “A polynomial Newton method for linear programming,”Algorithmica 1 (1986) 425–453.
  3. I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics, Doklady 8 (1967) 674–675.
  4. C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Meggido, ed.,Progress in Mathematical Programming: Interior Point and Related Methods (Springer-Verlag, Berlin, 1989) pp. 1–28.
  5. C.C. Gonzaga and R.A. Tapia, “On the quadratic convergence of the simplified Mizuno-Todd-Ye algorithm for Linear Programming,” Research Report TR92-42, Rice University, Houston, TX 77 251 (1992).
  6. B. Jansen, C. Roos, T. Terlaky and J.-P. Vial, “Interior-point methodology for Linear Programming: Duality, sensitivity analysis and computational aspects.” Technical Report No. 1993.12, Geneva University (1993).
  7. N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
  8. M. Kojima, N. Meggido, T. Noma and Y. Yoshise, “A unified approach to interior point algorithms for linear complementarity problems,”Lecture Notes in Computer Science, Vol. 538 (Springer-Verlag, New York, 1991).
  9. 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.
  10. Nesterov Yurii, Nemirovskii Arkadii, Interior-Point Polynomial Algorithms in Convex Programming, ISBN:9780898713190, 10.1137/1.9781611970791
  11. Yu. Nesterov, “Complexity estimates of some cutting plane methods based on analytical barrier,”Mathematical Programming 69 (1995) 149–176.
  12. J. Renegar, “A polynomial time algorithm, based on Newton’s method, for linear programming,”Mathematical Programming 40 (1988) 59–93.
  13. K. Tanabe, “Centered Newton method for mathematical programming,” in: M. Iri and K. Yajima, eds.,System Modeling and Optimization: Proceedings of the 13th IFIP Conference. Tokyo, Japan, Aug./Sept. 1987, Vol. 113 ofLecture Notes in Control and Information Sciences (Springer-Verlag, Berlin, 1988) pp. 197–206.
  14. M.J. Todd and Y. Ye, “A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529.
  15. 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–202.
  16. Y. Ye, “An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.