A Primal-Dual Variant of the IRI-IMAI Algorithm for Linear Programming

References

• Anstreicher K. M., Terlaky T. Potential reduction algorithms. Interior Point Methods of Mathematical Programming (1996) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 125–158Crossref, Google Scholar
• Gonzaga C. C. Large step path-following methods for linear programming, Part II: Potential-reduction method. SIAM J. Optim.1:280–292Crossref, Google Scholar
• Gonzaga C. C. Path following methods for linear programming. SIAM Rev. (1992) 34:167–227Crossref, Google Scholar
• Iri M., Imai H. A multiplicative barrier function method for linear programming. Algorithmica (1986) 1:455–82Crossref, Google Scholar
• Iri M. A proof of the polynomiality of the Iri-Imai method. J. Complexity (1993) 9:269–290Crossref, Google Scholar
• Karmarkar N. K. A new polynomial time algorithm for linear programming. Combinatorica (1984) 4:373–395Crossref, Google Scholar
• Kojima M., Mizuno S., Yoshise A. An O(√nL) iteration potential reduction algorithm for linear complementarity problems. Math. Programming (1991) 50:331–342Crossref, Google Scholar
• Monteiro R. D. C., Wright S. J. Superlinear primal-dual affine scaling algorithms for LCP. Math. Programming (1995) 69:311–333Crossref, Google Scholar
• Sturm J. F., Zhang S. New complexity results for the Iri-Imai method. Ann. Oper. Res. (1996) 62:539–564Crossref, Google Scholar
• Tanabe K., Iri M., Yajima K. Centered Newton method for mathematical programming. Lecture Notes in Control and Information Sciences (1988) (Springer-Verlag, Berlin, Germany) 197–206Google Scholar
• Todd M. J. Potential-reduction methods in mathematical programming. Math. Programming (1997a) 76:3–45Crossref, Google Scholar
• Todd M. J. On search directions in interior-point methods for semidefinite programming. (1997b) . Technical Report 1205, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NYGoogle Scholar
• Todd M. J., Toh K. C., Tütüncü R. H. On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. (1998) 8:769–796Crossref, Google Scholar
• Todd M. J., Ye Y. A centered projective algorithm for linear programming. Math. Oper. Res. (1990) 15:508–529Link, Google Scholar
• Tsuchiya T. Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems. J. Optim. Theory Appl. (1995) 87:703–726Crossref, Google Scholar
• Tunçel L. Primal-dual symmetry and scale invariance of interior-point methods for convex optimization. Math. Oper. Res. (1998) 23:708–718Link, Google Scholar
• Tütüncü R. H. Quadratic convergence of potential-reduction methods for degenerate problems. (1998) . Research Report No. 98-CNA-009, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Ye Y., Kortanek K. O., Kaliski J., Huang S. Near boundary behavior of primal-dual potential-reduction algorithms for linear programming. Math. Programming (1993) 58:243–255Crossref, Google Scholar
• Ye Y., Todd M. J., Mizuno S. An O(√nL)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. (1994) 19:53–67Link, Google Scholar
• Zhang Y., Tapia R. A., Dennis J. E. On the superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms. SIAM J. Optim. (1992) 2:304–324Crossref, Google Scholar