Abstract
This paper describes an implementation of an interior-point algorithm for large-scale nonlinear optimization. It is based on the algorithm proposed by Curtis et al. (SIAM J Sci Comput 32:3447–3475, 2010), a method that possesses global convergence guarantees to first-order stationary points with the novel feature that inexact search direction calculations are allowed in order to save computational expense. The implementation follows the proposed algorithm, but includes many practical enhancements, such as functionality to avoid the computation of a normal step during every iteration. The implementation is included in the IPOPT software package paired with an iterative linear system solver and preconditioner provided in PARDISO. Numerical results on a large nonlinear optimization test set and two PDE-constrained optimization problems with control and state constraints are presented to illustrate that the implementation is robust and efficient for large-scale applications.
Similar content being viewed by others
References
Arnautu V., Neittaanmaki P.: Optimal Control from Theory to Computer Programs. Kluwer, Dordrecht (2003)
Balay, S., Brown, J., Buschelman, K., Eijkhout, V., Gropp, W.D., Kaushik, D., Knepley, M.G., McInnes, L.C., Smith, B.F., Zhang, H.: PETSc users manual. Technical Report ANL-95/11—Revision 3.1, Argonne National Laboratory (2010)
Betts J.T.: Practical Methods for Optimal Control Using Nonlinear Programming Advances in Design and Control. SIAM, Philadelphia (2001)
Biegler L.T., Ghattas O., Heinkenschloss M., Keyes D., Bloemen Waanders B.: Real-Time PDE-Constrained Optimization. Computational Science and Engineering. SIAM, Philadelphia (2007)
Biegler, L.T., Ghattas, O., Heinkenschloss, M., Van Bloemen Waanders, B. (eds.): Large-Scale PDE-Constrained Optimization. Lecture Notes in Computational Science and Engineering. Springer, Berlin (2003)
Biros G., Ghattas O.: Parallel Lagrange–Newton–Krylov–Schur methods for PDE-constrained optimization. Part I: the Krylov–Schur solver. SIAM J. Sci. Comput. 27(2), 687–713 (2005)
Biros G., Ghattas O.: Parallel Lagrange���Newton–Krylov–Schur methods for PDE-constrained optimization. Part II: the Lagrange–Newton solver and its application to optimal control of steady viscous flows. SIAM J. Sci. Comput. 27(2), 714–739 (2005)
Byrd R.H., Curtis F.E., Nocedal J.: An inexact SQP method for equality constrained optimization. SIAM J. Optim. 19(1), 351–369 (2008)
Byrd R.H., Curtis F.E., Nocedal J.: An inexact Newton method for nonconvex equality constrained optimization. Math. Program. 122(2), 273–299 (2010)
Curtis, F.E., Huber, J., Schenk, O., Wächter, A.: On the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations. Technical report, Lehigh ISE 12T-006, Optimization Online ID: 2011-04-2992 (2012)
Curtis F.E., Nocedal J.: Flexible penalty functions for nonlinear constrained optimization. IMA J. Numer. Anal. 28(4), 749–769 (2008)
Curtis F.E., Nocedal J., Wächter A.: A matrix-free algorithm for equality constrained optimization problems with rank deficient Jacobians. SIAM J. Optim. 20(3), 1224–1249 (2009)
Curtis F.E., Schenk O., Wächter A.: An interior-point algorithm for nonlinear optimization with inexact step computations. SIAM J. Sci. Comput. 32(6), 3447–3475 (2010)
Dembo R.S., Eisenstat S.C., Steihaug T.: Inexact Newton methods. SIAM J. Numer. Anal. 19(2), 400–408 (1982)
Fourer R., Gay D.M., Kernighan B.W.: AMPL: A Modeling Language for Mathematical Programming. Brooks/Cole, Belmont (2002)
Freund, R.W.: Preconditioning of symmetric, but highly indefinite linear systems. In: Sydow, A. (ed.) 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics, pp. 551–556. Wissenschaft & Technik, Berlin (1997)
Gould N.I.M., Bongartz I., Conn A.R., Toint Ph.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21(1), 123–160 (1995)
Haber E., Ascher U.M.: Preconditioned all-at-once methods for large, sparse parameter estimation problems. Inverse Probl. 17, 1847–1864 (2001)
Heinkenschloss M., Vicente L.N.: Analysis of inexact trust-region SQP algorithms. SIAM J. Optim. 12(2), 283–302 (2002)
Hinze M., Pinnau R., Ulbrich M., Ulbrich S.: Optimization with PDE Constraints, Volume 23 of Mathematical Modeling: Theory and Applications. Springer, Dordrecht (2009)
Jäger H., Sachs E.W.: Global convergence of inexact reduced SQP methods. Optim. Methods Softw. 7(2), 83–110 (1997)
Kirk B.S., Peterson J.W., Stogner R.H., Carey G.F.: libMesh: A C++ library for parallel adaptive mesh refinement/coarsening simulations. Eng. Comput. 22(3–4), 237–254 (2006)
Kirk D.E.: Optimal Control Theory: An Introduction. Prentice-Hall, Englewood Cliffs (1970)
Powell M.J.D: A hybrid method for nonlinear equations. In: Rabinowitz, P. (ed.) Numerical methods for nonlinear algebraic equations, pp. 87–114. Gordon and Breach, London (1970)
Schenk O., Bollhöfer M., Roemer R.A.: On large scale diagonalization techniques for the Anderson model of localization. SIAM J. Sci. Comput. 28(3), 963–983 (2006)
Steihaug T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20(3), 626–637 (1983)
Tröltzsch F.: Optimal control of partial differential equations: theory, methods, and applications, Volume 112. American Mathematical Society, Providence (2010)
Wächter A., Biegler L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
Frank E. Curtis was supported by National Science Foundation grant DMS-1016291.
Rights and permissions
About this article
Cite this article
Curtis, F.E., Huber, J., Schenk, O. et al. A note on the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations. Math. Program. 136, 209–227 (2012). https://doi.org/10.1007/s10107-012-0557-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-012-0557-4
Keywords
- Large-scale optimization
- PDE-constrained optimization
- Interior-point methods
- Nonconvex programming
- Line search
- Trust regions
- Inexact linear system solvers
- Krylov subspace methods