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

Wright, Margaret

doi:10.1090/S0273-0979-04-01040-7

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
Posted: 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.

1. Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton, Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results, SIAM J. Optim. 8 (1998), no. 3, 746–768 (electronic). MR 1636549 (2000c:90117), http://dx.doi.org/10.1137/S1052623496304700
2. Robert E. Bixby, Solving real-world linear programs: a decade and more of progress, Oper. Res. 50 (2002), no. 1, 3–15. 50th anniversary issue of Operations Research. MR 1885204, http://dx.doi.org/10.1287/opre.50.1.3.17780
3. Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan, Linear matrix inequalities in system and control theory, SIAM Studies in Applied Mathematics, vol. 15, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1284712 (95f:93001)
4. Richard H. Byrd, Jean Charles Gilbert, and Jorge Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program. 89 (2000), no. 1, Ser. A, 149–185. MR 1795061 (2001j:90120), http://dx.doi.org/10.1007/PL00011391
5. Vašek Chvátal, Linear programming, A Series of Books in the Mathematical Sciences, W. H. Freeman and Company, New York, 1983. MR 717219 (86g:90062)
6. A. R. Conn, Nick Gould, and Ph. L. Toint, A note on using alternative second-order models for the subproblems arising in barrier function methods for minimization, Numer. Math. 68 (1994), no. 1, 17–33. MR 1278446 (95a:90119), http://dx.doi.org/10.1007/s002110050046
7. Andrew R. Conn, Nicholas I. M. Gould, Dominique Orban, and Philippe L. Toint, A primal-dual trust-region algorithm for non-convex nonlinear programming, Math. Program. 87 (2000), no. 2, Ser. B, 215–249. Studies in algorithmic optimization. MR 1763849 (2001e:90140), http://dx.doi.org/10.1007/s101070050112
8. A. S. El-Bakry, R. A. Tapia, T. Tsuchiya, and Y. Zhang, On the formulation and theory of the Newton interior-point method for nonlinear programming, J. Optim. Theory Appl. 89 (1996), no. 3, 507–541. MR 1393361 (97c:90104), http://dx.doi.org/10.1007/BF02275347
9. Anthony V. Fiacco and Garth P. McCormick, Nonlinear programming, 2nd ed., Classics in Applied Mathematics, vol. 4, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. Sequential unconstrained minimization techniques. MR 1058438 (91d:90089)
10. R. Fletcher, Practical methods of optimization, 2nd ed., A Wiley-Interscience Publication, John Wiley & Sons Ltd., Chichester, 1987. MR 955799 (89j:65050)
11. Anders Forsgren and Philip E. Gill, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim. 8 (1998), no. 4, 1132–1152. MR 1646122 (99k:90121), http://dx.doi.org/10.1137/S1052623496305560
12. Anders Forsgren, Philip E. Gill, and Margaret H. Wright, Interior methods for nonlinear optimization, SIAM Rev. 44 (2002), no. 4, 525–597 (2003). MR 1980444 (2004c:90098), http://dx.doi.org/10.1137/S0036144502414942
13. Anders Forsgren, Philip E. Gill, and Joseph R. Shinnerl, Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization, SIAM J. Matrix Anal. Appl. 17 (1996), no. 1, 187–211. MR 1372930 (96m:90084), http://dx.doi.org/10.1137/S0895479894270658
14. David M. Gay, Michael L. Overton, and Margaret H. Wright, A primal-dual interior method for nonconvex nonlinear programming, Advances in nonlinear programming (Beijing, 1996) Appl. Optim., vol. 14, Kluwer Acad. Publ., Dordrecht, 1998, pp. 31–56. MR 1639869 (99h:90096), http://dx.doi.org/10.1007/978-1-4613-3335-7_2
15. Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, and Margaret H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Math. Programming 36 (1986), no. 2, 183–209. MR 866988 (88h:90123), http://dx.doi.org/10.1007/BF02592025
16. Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical optimization, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1981. MR 634376 (83d:65195)
17. Philip E. Gill, Walter Murray, and Margaret H. Wright, Numerical linear algebra and optimization. Vol. 1, Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, 1991. MR 1074004 (92b:65001)
18. Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228 (97g:90108), http://dx.doi.org/10.1145/227683.227684
19. Donald Goldfarb and Michael J. Todd, Linear programming, Optimization, Handbooks Oper. Res. Management Sci., vol. 1, North-Holland, Amsterdam, 1989, pp. 73–170. MR 1105101, http://dx.doi.org/10.1016/S0927-0507(89)01003-0
20. Clovis C. Gonzaga, Path-following methods for linear programming, SIAM Rev. 34 (1992), no. 2, 167–224. MR 1166175 (93j:90050), http://dx.doi.org/10.1137/1034048
21. N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), no. 4, 373–395. MR 779900 (86i:90072), http://dx.doi.org/10.1007/BF02579150
22. Adrian S. Lewis and Michael L. Overton, Eigenvalue optimization, Acta numerica, 1996, Acta Numer., vol. 5, Cambridge Univ. Press, Cambridge, 1996, pp. 149–190. MR 1624599 (99e:90072), http://dx.doi.org/10.1017/S0962492900002646
23. F. A. Lootsma, Hessian matrices of penalty functions for solving constrained-optimization problems, Philips Res. Rep. 24 (1969), 322–330. MR 0305594 (46 #4724)
24. D. G. Luenberger (1973). Introduction to Linear and Nonlinear Programming, Addison-Wesley, Menlo Park.
25. W. Murray, Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions, J. Optimization Theory Appl. 7 (1971), 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. Yurii Nesterov and Arkadii Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1258086 (94m:90005)
28. Jorge Nocedal and Stephen J. Wright, Numerical optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999. MR 1713114 (2001b:90002)
29. J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 0273810 (42 #8686)
30. C. Roos, T. Terlaky, and J.-Ph. Vial, Theory and algorithms for linear optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Ltd., Chichester, 1997. An interior point approach. MR 1450094 (98d:90005)
31. Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114 (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, Semidefinite optimization, Acta Numer. 10 (2001), 515–560. MR 2009698 (2004g:90004), http://dx.doi.org/10.1017/S0962492901000071
34. Lieven Vandenberghe and Stephen Boyd, Semidefinite programming, SIAM Rev. 38 (1996), no. 1, 49–95. MR 1379041 (96m:90005), http://dx.doi.org/10.1137/1038003
35. Robert J. Vanderbei, Linear programming, 2nd ed., International Series in Operations Research & Management Science, 37, Kluwer Academic Publishers, Boston, MA, 2001. Foundations and extensions. MR 1845638 (2002e:90002)
36. Margaret H. Wright, Interior methods for constrained optimization, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 341–407. MR 1165729 (93d:90037)
37. Margaret H. Wright, Some properties of the Hessian of the logarithmic barrier function, Math. Programming 67 (1994), no. 2, Ser. A, 265–295. MR 1305569 (95m:90125), http://dx.doi.org/10.1007/BF01582224
38. Margaret H. Wright, Why a pure primal Newton barrier step may be infeasible?, SIAM J. Optim. 5 (1995), no. 1, 1–12. MR 1315702 (95m:90126), http://dx.doi.org/10.1137/0805001
39. Margaret H. Wright, Ill-conditioning and computational error in interior methods for nonlinear programming, SIAM J. Optim. 9 (1999), no. 1, 84–111 (electronic). MR 1660094 (99i:90093), http://dx.doi.org/10.1137/S1052623497322279
40. Stephen J. Wright, Stability of linear equations solvers in interior-point methods, SIAM J. Matrix Anal. Appl. 16 (1995), no. 4, 1287–1307. MR 1351471 (96f:65055), http://dx.doi.org/10.1137/S0895479893260498
41. Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1422257 (98a:90004)
42. Stephen J. Wright, Modified Cholesky factorizations in interior-point algorithms for linear programming, SIAM J. Optim. 9 (1999), no. 4, 1159–1191 (electronic). Dedicated to John E. Dennis, Jr., on his 60th birthday. MR 1724782 (2000k:90076), http://dx.doi.org/10.1137/S1052623496304712
43. Stephen J. Wright, Effects of finite-precision arithmetic on interior-point methods for nonlinear programming, SIAM J. Optim. 12 (2001), no. 1, 36–78 (electronic). MR 1870586 (2002j:90107), http://dx.doi.org/10.1137/S1052623498347438
44. Yinyu Ye, Interior point algorithms, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1997. Theory and analysis; A Wiley-Interscience Publication. MR 1481160 (98m:90002)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|