Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-28T02:08:04.333Z Has data issue: false hasContentIssue false
  • English
  • Français

Interior-point methods for optimization

Published online by Cambridge University Press:  25 April 2008

Arkadi S. Nemirovski  and
Michael J. Todd
Arkadi S. Nemirovski
Affiliation:
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA E-mail: [email protected]
Michael J. Todd
Affiliation:
School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This article describes the current state of the art of interior-point methods (IPMs) for convex, conic, and general nonlinear optimization. We discuss the theory, outline the algorithms, and comment on the applicability of this class of methods, which have revolutionized the field over the last twenty years.

Type
Research Article
Information
Acta Numerica , Volume 17 , May 2008 , pp. 191 - 234
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alizadeh, F. (1995), ‘Interior point methods in semidefinite programming with applications to combinatorial optimization’, SIAM J. Optim. 5, 13–51.CrossRefGoogle Scholar
Alizadeh, F., Haeberly, J.-P. A. and Overton, M. L. (1998), ‘Primal–dual interiorpoint methods for semidefinite programming: Convergence rates, stability and numerical results’, SIAM J. Optim. 8, 746–768.CrossRefGoogle Scholar
Andersen, E. D. and Ye, Y. (1999), ‘On a homogeneous algorithm for monotone complementarity system’, Math. Program. 84, 375–399.CrossRefGoogle Scholar
Bauschke, H. H., Güler, O., Lewis, A. S. and Sendov, H. S. (2001), ‘Hyperbolic polynomials and convex analysis’, Canad. J. Math. 53, 470–488.Google Scholar
Ben-Tal, A. and Nemirovski, A. S. (2001), Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM, Philadelphia.Google Scholar
Bixby, R. E. (2002), ‘Solving real-world linear programs: A decade and more of progress’, Oper. Res. 50, 3–15.CrossRefGoogle Scholar
Bomze, I. M. (1988), ‘On standard quadratic optimization problems’, J. Global Optim. 13, 369–387.CrossRefGoogle Scholar
Bomze, I. M. and de Klerk, E. (2002), ‘Solving standard quadratic optimization problems via semidefinite and copositive programming’, J. Global Optim. 24, 163–185.CrossRefGoogle Scholar
Bomze, I. M., Dür, M., de Klerk, E., Roos, C., Quist, A. J. and Terlaky, T. (2000), ‘On copositive programming and standard quadratic optimization problems’, J. Global Optim. 18, 301–320.CrossRefGoogle Scholar
Boyd, S. and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.CrossRefGoogle Scholar
Boyd, S., El Ghaoui, L., Feron, E. and Balakrishnan, V. (1994), Linear Matrix Inequalities in System and Control Theory, Vol. 15 of Studies in Applied Mathematics, SIAM.CrossRefGoogle Scholar
Byrd, R. H., Nocedal, J. and Waltz, R. A. (2006), KNITRO: An integrated package for nonlinear optimization. In Large-Scale Nonlinear Optimization (di Pillo, G. and Roma, M., eds), Springer, New York, pp. 35–59.CrossRefGoogle Scholar
Carroll, C. W. (1961), ‘The created response surface technique for optimizing nonlinear, restrained systems’, Oper. Res. 9, 169–185.CrossRefGoogle Scholar
Chai, J. S. and Toh, K. C. (2007), ‘Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming’, Comput. Optim. Appl. 36, 221–247.CrossRefGoogle Scholar
Chen, L. and Goldfarb, D. (2006), ‘Interior-point l 2-penalty methods for nonlinear programming with strong convergence properties’, Math. Program. 108, 1–36.Google Scholar
Courant, R. (1943), ‘Variational methods for the solution of problems of equilibrium and vibrations’, Bull. Amer. Math. Soc. 49, 1–23.Google Scholar
Faraut, J. and Koranyi, A. (1994), Analysis on Symmetric Cones, Clarendon Press, Oxford.CrossRefGoogle Scholar
Faybusovich, L. (1997), ‘Linear systems in Jordan algebras and primal–dual interiorpoint algorithms’, J. Comput. Appl. Math. 86, 149–175.Google Scholar
Fiacco, A. V. and McCormick, G. P. (1968), Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley.Google Scholar
Forsgren, A., Gill, P. E. and Wright, M. H. (2002), ‘Interior methods for nonlinear optimization’, SIAM Review 44, 525–597.Google Scholar
Freund, R. W., Jarre, F. and Schaible, S. (1996), ‘On self-concordant barrier functions for conic hulls and fractional programming’, Math. Program. 74, 237–246.CrossRefGoogle Scholar
Frisch, K. R. (1955), The logarithmic potential method of convex programming. Memorandum of 05 13, University Institute of Economics, Oslo, Norway.Google Scholar
Gay, D. M., Overton, M. L. and Wright, M. H. (1998), A primal–dual interior method for nonconvex nonlinear programming. In Advances in Nonlinear Programming (Yuan, Y., ed.), Kluwer, pp. 31–56.CrossRefGoogle Scholar
Gill, P. E., Murray, W., Saunders, M. A., Tomlin, J. A. and Wright, M. H. (1986), ‘On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method’, Math. Program. 36, 183–209.Google Scholar
Goemans, M. X. (1997), ‘Semidefinite programming in combinatorial optimization’, Math. Program. 79, 143–161.Google Scholar
Gonzaga, C. C. (1989), An algorithm for solving linear programming problems in O(n 3L) operations. In Progress in Mathematical Programming: Interior Point and Related Methods (Megiddo, N., ed.), Springer, New York, pp. 1–28.Google Scholar
Gould, N. I. M., Orban, D. and Toint, P. L. (2005), Numerical methods for large-scale nonlinear optimization. In Acta Numerica, Vol. 14, Cambridge University Press, pp. 299–361.Google Scholar
Guéeret, C., Prins, C. and Sevaux, M. (2002), Applications of Optimization with XpressMP, Dash Optimization. Translated and revised by Heipcke, Susanne.Google Scholar
Güler, O. (1996), ‘Barrier functions in interior-point methods’, Math. Oper. Res. 21, 860–885.Google Scholar
Güler, O. (1997), ‘Hyperbolic polynomials and interior-point methods for convex programming’, Math. Oper. Res. 22, 350–377.Google Scholar
Helmberg, C., Rendl, F., Vanderbei, R. and Wolkowicz, H. (1996), ‘An interior-point method for semidefinite programming’, SIAM J. Optim. 6, 342–361.Google Scholar
Karmarkar, N. (1984), ‘A new polynomial-time algorithm for linear programming’, Combinatorica 4, 373–395.CrossRefGoogle Scholar
de Klerk, E., Roos, C. and Terlaky, T. (1997), ‘Initialization in semidefinite programming via a self-dual skew-symmetric embedding’, Oper. Res. Letters 20, 213–221.Google Scholar
Kojima, M., Mizuno, S. and Yoshise, A. (1989), ‘A polynomial–time algorithm for a class of linear complementarity problems’, Math. Program. 44, 1–26.Google Scholar
Kojima, M., Shindoh, S. and Hara, S. (1997), ‘Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices’, SIAM J. Optim. 7, 86–125.CrossRefGoogle Scholar
Lasserre, J. B. (2001), ‘Global optimization with polynomials and the problem of moments’, SIAM J. Optim. 11, 796–817.CrossRefGoogle Scholar
Lewis, A. S. and Overton, M. L. (1996), Eigenvalue optimization. In Acta Numerica, Vol. 5, Cambridge University Press, pp. 149–160.Google Scholar
Lobo, M. S., Vandenberghe, L., Boyd, S. and Lebret, H. (1998), ‘Applications of second-order cone programming’, Linear Algebra Appl. 284, 193–228.CrossRefGoogle Scholar
Luo, Z.-Q., Sturm, J. F. and Zhang, S. (2000), ‘Conic convex programming and self-dual embedding’, Optim. Methods Software 14, 169–218.CrossRefGoogle Scholar
Megiddo, N. (1989), Pathways to the optimal set in linear programming. In Progress in Mathematical Programming: Interior Point and Related Methods (Megiddo, N., ed.), Springer, New York, pp. 131–158.CrossRefGoogle Scholar
Mizuno, S. (1994), ‘Polynomiality of infeasible-interior-point algorithms for linear programming’, Math. Program. 67, 109–119.CrossRefGoogle Scholar
Monteiro, R. D. C. (1997), ‘Primal–dual path-following algorithms for semidefinite programming’, SIAM J. Optim. 7, 663–678.CrossRefGoogle Scholar
Monteiro, R. D. C. and Adler, I. (1989), ‘Interior path following primal–dual algorithms I: Linear programming’, Math. Program. 44, 27–41.CrossRefGoogle Scholar
Nash, S. G. (1998), ‘SUMT (revisited)’, Oper. Res. 46, 763–775.CrossRefGoogle Scholar
Nemirovski, A. (2004), Interior Point Polynomial Time Methods in Convex Programming. Lecture Notes: www2.isye.gatech.edu/~nemirovs/Lect_IPM.pdf.Google Scholar
Nemirovski, A. and Tunçel, L. (2005), ‘“Cone-free” primal–dual path-following and potential-reduction polynomial time interior-point methods’, Math. Program. 102, 261–295.CrossRefGoogle Scholar
Nesterov, Y. (1997), ‘Long-step strategies in interior-point primal–dual methods’, Math. Program. 76, 47–94.CrossRefGoogle Scholar
Nesterov, Y. (2003), Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, Dordrecht.Google Scholar
Nesterov, Y. and Nemirovski, A. (1994), Interior Point Polynomial Time Methods in Convex Programming, SIAM, Philadelphia.Google Scholar
Nesterov, Y. E. and Todd, M. J. (1997), ‘Self-scaled barriers and interior-point methods for convex programming’, Math. Oper. Res. 22, 1–42.CrossRefGoogle Scholar
Nesterov, Y. E. and Todd, M. J. (1998), ‘Primal–dual interior-point methods for self-scaled cones’, SIAM J. Optim. 8, 324–364.CrossRefGoogle Scholar
Nesterov, Y., Todd, M. J. and Ye, Y. (1999), ‘Infeasible-start primal–dual methods and infeasibility detectors for nonlinear programming problems’, Math. Program. 84, 227–267.CrossRefGoogle Scholar
Nocedal, J. and Wright, S. J. (2006), Numerical Optimization, Springer, New York.Google Scholar
Parrilo, P. A. (2003), ‘Semidefinite programming relaxations for semialgebraic problems’, Math. Program. 96, 293–320.CrossRefGoogle Scholar
Parrilo, P. A. and Sturmfels, B. (2003), Minimizing polynomials. In Algorithmic and Quantitative Real Algebraic Geometry, Vol. 60 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 83–99.CrossRefGoogle Scholar
Potra, F. A. and Sheng, R. (1998), ‘On homogeneous interior-point algorithms for semidefinite programming’, Optim. Methods Software 9, 161–184.Google Scholar
Renegar, J. (1988), ‘A polynomial-time algorithm, based on Newton's method, for linear programming’, Math. Program. 40, 59–93.CrossRefGoogle Scholar
Renegar, J. (2001), A Mathematical View of Interior-Point Methods in Convex Optimization, SIAM, Philadelphia.CrossRefGoogle Scholar
Renegar, J. (2006), ‘Hyperbolic programs, and their derivative relaxations’, Found. Comput. Math. 6, 59–79.CrossRefGoogle Scholar
Roos, C., Terlaky, T. and Vial, J.-P. (1997), Theory and Algorithms for Linear Optimization: An Interior Point Approach, Wiley.Google Scholar
Schmieta, S. H. and Alizadeh, F. (2001), ‘Associative and Jordan algebras, and polynomial-time interior-point algorithms for symmetric cones’, Math. Oper. Res. 26, 543–564.CrossRefGoogle Scholar
Tanabe, K. (1988), Centered Newton method for mathematical programming. In System Modeling and Optimization, Springer, New York, pp. 197–206.Google Scholar
Todd, M. J. (2001), Semidefinite optimization. In Acta Numerica, Vol. 10, Cambridge University Press, pp. 515–560.Google Scholar
Todd, M. J. and Ye, Y. (1990), ‘A centered projective algorithm for linear programming’, Math. Oper. Res. 15, 508–529.CrossRefGoogle Scholar
Todd, M. J., Toh, K.-C. and Tütüncü, R. H. (1998), ‘On the Nesterov–Todd direction in semidefinite programming’, SIAM J. Optim. 8, 769–796.CrossRefGoogle Scholar
Toh, K. C. (2007), ‘An inexact primal–dual path-following algorithm for convex quadratic SDP’, Math. Program. 112, 221–254.CrossRefGoogle Scholar
Tunçcel, L. (1998), ‘Primal–dual symmetry and scale-invariance of interior-point algorithms for convex programming’, Math. Oper. Res. 23, 708–718.CrossRefGoogle Scholar
Vanderbei, R. J. (2007), Linear Programming: Foundations and Extensions, Springer, New York.Google Scholar
Vanderbei, R. J. and Shanno, D. F. (1999), ‘An interior-point algorithm for nonconvex nonlinear programming’, Comput. Optim. Appl. 13, 231–252.CrossRefGoogle Scholar
Waltz, R. A., Morales, J. L., Nocedal, J. and Orban, D. (2006), ‘An interior algorithm for nonlinear optimization that combines line search and trust region steps’, Math. Program. 107, 391–408.Google Scholar
Wächter, A. and Biegler, L. T. (2006), ‘On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming’, Math. Program. 106, 25–57.Google Scholar
Wolkowicz, H., Saigal, R. and Vanderberghe, L., eds (2000), Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer, Boston.Google Scholar
Wright, M. H. (1992), Interior methods for constrained optimization. In Acta Numerica, Vol. 1, Cambridge University Press, pp. 341–407.Google Scholar
Wright, S. J. (1997), Primal–Dual Interior-Point Methods, SIAM, Philadelphia.CrossRefGoogle Scholar
Xu, X., Hung, P. F. and Ye, Y. (1996), ‘A simplified homogeneous self-dual linear programming algorithm and its implementation’, Ann. Oper. Res. 62, 151–171.Google Scholar
Ye, Y. (1991), ‘An O(n 3L) potential reduction algorithm for linear programming’, Math. Program. 50, 239–258.CrossRefGoogle Scholar
Ye, Y. (1997), Interior Point Algorithms: Theory and Analysis, Wiley.CrossRefGoogle Scholar
Ye, Y., Todd, M. J. and Mizuno, S. (1994), ‘An O()-iteration homogeneous and self-dual linear programming algorithm’, Math. Oper. Res. 19, 53–67.CrossRefGoogle Scholar
Zhang, Y. (1994), ‘On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem’, SIAM J. Optim. 4, 208–227.Google Scholar