Skip to main content

Advertisement

SpringerLink
Log in

An interior-point trust-funnel algorithm for nonlinear optimization

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155–196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, but has the additional capability of being able to solve problems with both equality and inequality constraints. The prominent features of our algorithm are that (i) the subproblems that define each search direction may be solved with matrix-free methods so that derivative matrices need not be formed or factorized so long as matrix-vector products with them can be performed; (ii) the subproblems may be solved approximately in all iterations; (iii) in certain situations, the computed search directions represent inexact sequential quadratic optimization steps, which may be desirable for fast local convergence; (iv) criticality measures for feasibility and optimality aid in determining whether only a subset of computations need to be performed during a given iteration; and (v) no merit function or filter is needed to ensure global convergence.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Argáez, M., Tapia, R.: On the global convergence of a modified augmented Lagrangian linesearch interior-point Newton method for nonlinear programming. J Optim Theory Appl 114, 1–25 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. Byrd, R.H., Curtis, F.E., Nocedal, J.: An inexact SQP method for equality constrained optimization. SIAM J. Optim. 19, 351–369 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  3. Byrd, R.H., Gilbert, J.C., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Math. Program. 89, 149–185 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  4. Byrd, R.H., Hribar, M.E., Nocedal, J.: An interior point algorithm for large-scale nonlinear programming. SIAM J. Optim. 9, 877–900 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  5. Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2000)

  6. Curtis, F.E., Schenk, O., Wächter, A.: An interior-point algorithm for large-scale nonlinear optimization with inexact step computations. SIAM J. Sci. Comput. 32, 3447–3475 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  7. Czyzyk, J., Fourer, R., Mehrotra, S.: Using a massively parallel processor to solve large sparse linear programs by an interior-point method. SIAM J. Sci. Comput. 19, 553–565 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  8. Fletcher, R.: Practical Methods of Optimization. Wiley-Interscience (Wiley), New York (2001)

    MATH  Google Scholar 

  9. Fletcher, R., Gould, N.I.M., Leyffer, S., Toint, Ph.L., Wächter, A.: Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J. Optim. 13, 635–659 (2002). [(electronic) (2003)]

  10. Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Program. 91, 239–269 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Fletcher, R., Leyffer, S., Toint, Ph.L.: On the global convergence of a filter-SQP algorithm. SIAM J. Optim. 13, 44–59 (2002)

  12. Fourer, R., Mehrotra, S.: Performance of an augmented system approach for solving least-squares problems in an interior-point method for linear programming. Math. Program. 19, 26–31 (1991)

    Google Scholar 

  13. Fourer, R., Mehrotra, S.: Solving symmetric indefinite systems in an interior-point method for linear programming. Math. Program. 62, 15–39 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gertz, E.M., Gill, P.E.: A primal-dual trust region algorithm for nonlinear optimization. Math. Program Ser. B 100, 49–94 (2004)

    MATH  MathSciNet  Google Scholar 

  15. Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99–131 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  16. Gill, P.E., Murray, W., Wright, M.H.: Practical Optimization. Academic Press Inc. (Harcourt Brace Jovanovich Publishers), London (1981)

    MATH  Google Scholar 

  17. Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218, 587–601 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  18. Gould, N.I.M., Orban, D., Toint, Ph.L.: GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Softw. 29, 353–372 (2003)

  19. Gould, N.I.M., Robinson, D.P.: A second derivative SQP method: global convergence. SIAM J. Optim. 20, 2023–2048 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  20. Gould, N.I.M., Robinson, D.P.: A second derivative SQP method: local convergence and practical issues. SIAM J. Optim. 20, 2049–2079 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  21. Gould, N.I.M., Robinson, D.P.: A second derivative SQP method with a “trust-region-free” predictor step. IMA J. Numer. Anal. 32, 580–601 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  22. Gould, N.I.M., Robinson, D.P., Thorne, H.S.: On solving trust-region and other regularised subproblems in optimization. Math. Program. Comput. 2, 21–57 (2010)

  23. Gould, N.I.M., Toint, Ph.L.: Nonlinear programming without a penalty function or a filter. Math. Program. 122, 155–196 (2010)

  24. Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  25. Karush, W.: Minima of Functions of Several Variables with Inequalities as Side Conditions. Master’s thesis, Department of Mathematics, University of Chicago, Illinois, USA (1939)

  26. Kuhn, H.W., Tucker, A.W.: Nonlinear programming. In: Neyman, J. (ed.) Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. University of Berkeley Press, California (1951)

    Google Scholar 

  27. Lalee, M., Nocedal, J., Plantenga, T.: On the implementation of an algorithm for large-scale equality constrained optimization. SIAM J. Optim. 8, 682–706 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  28. Mehrotra, S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2, 575–601 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  29. Morales, J.L., Nocedal, J., Wu, Y.: A sequential quadratic programming algorithm with an additional equality constrained phase. IMA J. Numer. Anal. 32, 553–579 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  30. Orban, D., Gould, N.I.M., Robinson, D.P.: Trajectory-following methods for large-scale degenerate convex quadratic programming. Math. Program. Comput. 5, 113–142 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  31. Vanderbei, R.J.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 11, 451–484 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  32. Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. Ser. A 106, 25–57 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  33. Yabe, H., Yamashita, H.: Q-superlinear convergence of primal-dual interior point quasi-Newton methods for constrained optimization. J. Oper. Res. Soc. Jpn. 40, 415–436 (1997)

    MATH  MathSciNet  Google Scholar 

  34. Yamashita, H., Yabe, H.: Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization. Math. Program. 75, 377–397 (1996)

    MATH  MathSciNet  Google Scholar 

  35. Yamashita, H., Yabe, H.: An interior point method with a primal-dual quadratic barrier penalty function for nonlinear optimization. SIAM J. Optim. 14, 479–499 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  36. Yamashita, H., Yabe, H., Tanabe, T.: A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization. Math. Program. Ser. A 102, 111–151 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA

    Frank E. Curtis

  2. Numerical Analysis Group, Rutherford Appleton Laboratory, Chilton, Oxfordshire, UK

    Nicholas I. M. Gould

  3. Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA

    Daniel P. Robinson

  4. Department of Mathematics and NaXys, University of Namur, Namur, Belgium

    Philippe L. Toint

Authors
  1. Frank E. Curtis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicholas I. M. Gould
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel P. Robinson
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Philippe L. Toint
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel P. Robinson.

Additional information

Frank E. Curtis: This author was supported by U.S. Department of Energy Grant DE–SC0010615 and U.S. National Science Foundation Grant DMS–1016291.

Nicholas I. M. Gould: This author was supported by the EPSRC Grant EP/I013067/1.

Daniel P. Robinson: This author was supported by U.S. National Science Foundation Grant DMS–1217153.

Appendix

Appendix

The following is a flow diagram of our trust-funnel method stated as Algorithm 2.

figure d

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Curtis, F.E., Gould, N.I.M., Robinson, D.P. et al. An interior-point trust-funnel algorithm for nonlinear optimization. Math. Program. 161, 73–134 (2017). https://doi.org/10.1007/s10107-016-1003-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1003-9

Keywords

Mathematics Subject Classification

Search

Navigation