Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

The interior-point revolution in optimization: History, recent developments, and lasting consequences


Author: Margaret H. Wright
Journal: Bull. Amer. Math. Soc. 42 (2005), 39-56
MSC (2000): Primary 49M37, 65K05, 90C30
DOI: https://doi.org/10.1090/S0273-0979-04-01040-7
Published electronically: September 21, 2004
MathSciNet review: 2115066
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Interior methods are a pervasive feature of the optimization landscape today, but it was not always so. Although interior-point techniques, primarily in the form of barrier methods, were widely used during the 1960s for problems with nonlinear constraints, their use for the fundamental problem of linear programming was unthinkable because of the total dominance of the simplex method. During the 1970s, barrier methods were superseded, nearly to the point of oblivion, by newly emerging and seemingly more efficient alternatives such as augmented Lagrangian and sequential quadratic programming methods. By the early 1980s, barrier methods were almost universally regarded as a closed chapter in the history of optimization.

This picture changed dramatically in 1984, when Narendra Karmarkar announced a fast polynomial-time interior method for linear programming; in 1985, a formal connection was established between his method and classical barrier methods. Since then, interior methods have continued to transform both the theory and practice of constrained optimization. We present a condensed, unavoidably incomplete look at classical material and recent research about interior methods.


References [Enhancements On Off] (What's this?)

  • 1. F. Alizadeh, J.-P. Haeberly, and M. L. Overton (1998). Primal-dual interior-point methods for semidefinite programming: convergence rates, stability, and numerical results, SIAM J. Opt. 8, 746-768. MR 1636549 (2000c:90117)
  • 2. R. E. Bixby (2002). Solving real-world linear programs: a decade and more of progress, Operations Research 50, 3-15. MR 1885204
  • 3. S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan (1994). Linear Matrix Inequalities in System and Control Theory, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania. MR 1284712 (95f:93001)
  • 4. R. H. Byrd, J. C. Gilbert, and J. Nocedal (2000). A trust region method based on interior point techniques for nonlinear programming, Math. Prog. 89, 149-185. MR 1795061 (2001j:90120)
  • 5. V. Chvátal (1983). Linear Programming, W. H. Freeman, New York. MR 0717219 (86g:90062)
  • 6. A. R. Conn, N. I. M. Gould, and P. L. Toint (1994). A note on using alternative second-order models for the subproblems arising in barrier function methods for minimization, Num. Math. 68, 17-33. MR 1278446 (95a:90119)
  • 7. A. R. Conn, N. I. M. Gould, and P. L. Toint (2000). A primal-dual trust-region algorithm for minimizing a non-convex function subject to bound and linear equality constraints, Math. Prog. 87, 215-249. MR 1763849 (2001e:90140)
  • 8. A. S. El-Bakry, R. A. Tapia, T. Tsuchiya, and Y. Zhang (1996). On the formulation and theory of the Newton interior-point method for nonlinear programming, J. Opt. Theory Appl. 89, 507-541. MR 1393361 (97c:90104)
  • 9. A. V. Fiacco and G. P. McCormick (1968). Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York. Republished by Society for Industrial and Applied Mathematics, Philadelphia, 1990. MR 1058438 (91d:90089)
  • 10. R. Fletcher (1987). Practical Methods of Optimization (second edition), John Wiley and Sons, Chichester. MR 0955799 (89j:65050)
  • 11. A. Forsgren and P. E. Gill (1998). Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Opt. 8, 1132-1152. MR 1646122 (99k:90121)
  • 12. A. Forsgren, P. E. Gill, and M. H. Wright (2002). Interior methods for nonlinear optimization, SIAM Review 44, 525-597. MR 1980444 (2004c:90098)
  • 13. A. Forsgren, P. E. Gill, and J. R. Shinnerl (1996). Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization, SIAM J. Matrix Anal. Appl. 17, 187-211. MR 1372930 (96m:90084)
  • 14. D. M. Gay, M. L. Overton, and M. H. Wright (1998). A primal-dual interior method for nonconvex nonlinear programming, Advances in Nonlinear Programming (Y. Yuan, ed.), Kluwer Academic, Dordrecht, 31-56. MR 1639869 (99h:90096)
  • 15. P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin and M. H. Wright (1986). On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Prog. 36, 183-209. MR 0866988 (88h:90123)
  • 16. P. E. Gill, W. Murray and M. H. Wright (1981). Practical Optimization, Academic Press, London and New York. MR 0634376 (83d:65195)
  • 17. P. E. Gill, W. Murray and M. H. Wright (1991). Numerical Linear Algebra and Optimization, Volume 1, Addison-Wesley, Redwood City. MR 1074004 (92b:65001)
  • 18. M. X. Goemans and D. P. Williamson (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115-1145. MR 1412228 (97g:90108)
  • 19. D. Goldfarb and M. J. Todd (1989). Linear programming, Optimization (G. L. Nemhauser, A. H. G. Rinnooy Kan and M. J. Todd, eds.), North Holland, Amsterdam and New York, 73-170. MR 1105101
  • 20. C. C. Gonzaga (1992). Path following methods for linear programming, SIAM Review 34, 167-224. MR 1166175 (93j:90050)
  • 21. N. K. Karmarkar (1984). A new polynomial-time algorithm for linear programming, Combinatorica 4, 373-395. MR 0779900 (86i:90072)
  • 22. A. S. Lewis and M. L. Overton (1996). Eigenvalue optimization, Acta Numerica 1996, 149-190. MR 1624599 (99e:90072)
  • 23. F. A. Lootsma (1969). Hessian matrices of penalty functions for solving constrained optimization problems, Philips Res. Repts. 24, 322-330. MR 0305594 (46:4724)
  • 24. D. G. Luenberger (1973). Introduction to Linear and Nonlinear Programming, Addison-Wesley, Menlo Park.
  • 25. W. Murray (1971). Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions, J. Opt. Theory Appl. 7, 189-196. MR 0284212 (44:1441)
  • 26. B. A. Murtagh and M. A. Saunders (1987). MINOS 5.1 User's Guide, Report SOL 83-20R, Department of Operations Research, Stanford University, Stanford, California.
  • 27. Y. Nesterov and A. Nemirovskii (1994). Interior-Point Polynomial Algorithms in Convex Programming, Society for Industrial and Applied Mathematics, Philadelphia. MR 1258086 (94m:90005)
  • 28. J. Nocedal and S. J. Wright (1999). Numerical Optimization, Springer-Verlag, New York. MR 1713114 (2001b:90002)
  • 29. J. M. Ortega and W. C. Rheinboldt (1970). Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, London and New York. MR 0273810 (42:8686)
  • 30. C. Roos, T. Terlaky, and J.-Ph. Vial (1997). Theory and Algorithms for Linear Optimization: An Interior Point Approach, John Wiley & Sons, New York. MR 1450094 (98d:90005)
  • 31. A. Schrijver (1987). Theory of Linear and Integer Programming, John Wiley and Sons, New York. MR 0874114 (88m:90090)
  • 32. D. A. Spielman and S.-H. Teng (2001). Why the simplex method usually takes polynomial time, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, 296-305.
  • 33. M. J. Todd (2001). Semidefinite optimization, Acta Numerica 2001, 515-560. MR 2009698 (2004g:90004)
  • 34. L. Vandenberghe and S. Boyd (1996). Semidefinite programming, SIAM Review 38, 49-95. MR 1379041 (96m:90005)
  • 35. R. J. Vanderbei (1997). Linear Programming: Foundations and Extensions, Kluwer Academic Publishers, Boston. MR 1845638 (2002e:90002)
  • 36. M. H. Wright (1992). Interior methods for constrained optimization, Acta Numerica 1992, 341-407. MR 1165729 (93d:90037)
  • 37. M. H. Wright (1994). Some properties of the Hessian of the logarithmic barrier function, Math. Prog. 67, 265-295. MR 1305569 (95m:90125)
  • 38. M. H. Wright (1995). Why a pure primal Newton barrier step may be infeasible, SIAM J. Opt. 5, 1-12. MR 1315702 (95m:90126)
  • 39. M. H. Wright (1998). Ill-conditioning and computational error in interior methods for nonlinear programming, SIAM J. Opt. 9, 81-111. MR 1660094 (99i:90093)
  • 40. S. J. Wright (1995). Stability of linear equation solvers in interior-point methods, SIAM J. Matrix Anal. Appl. 16, 1287-1307. MR 1351471 (96f:65055)
  • 41. S. J. Wright (1997). Primal-Dual Interior-Point Methods, Society for Industrial and Applied Mathematics, Philadelphia. MR 1422257 (98a:90004)
  • 42. S. J. Wright (1999). Modified Cholesky factorizations in interior-point algorithms for linear programming, SIAM J. Opt. 9, 1159-1191. MR 1724782 (2000k:90076)
  • 43. S. J. Wright (2001). Effects of finite-precision arithmetic on interior-point methods for nonlinear programming, SIAM J. Opt. 12, 36-78. MR 1870586 (2002j:90107)
  • 44. Y. Ye (1997). Interior Point Algorithms, Theory and Analysis, John Wiley & Sons, New York. MR 1481160 (98m:90002)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 49M37, 65K05, 90C30

Retrieve articles in all journals with MSC (2000): 49M37, 65K05, 90C30


Additional Information

Margaret H. Wright
Affiliation: Computer Science Department, Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, New York 10012
Email: mhw@cs.nyu.edu

DOI: https://doi.org/10.1090/S0273-0979-04-01040-7
Received by editor(s): July 9, 2004
Received by editor(s) in revised form: August 17, 2004
Published electronically: September 21, 2004
Additional Notes: Lecture presented at the AMS Special Session on Current Events, Joint Mathematics Meetings, Phoenix, AZ, January 9, 2004
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society