×

zbMATH — the first resource for mathematics

On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. (English) Zbl 1134.90542
Summary: We present a primal-dual interior-point algorithm with a filter line-search method for nonlinear programming. Local and global convergence properties of this method were analyzed in previous work. Here we provide a comprehensive description of the algorithm, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix. Heuristics are also considered that allow faster performance. This method has been implemented in the IPOPT code, which we demonstrate in a detailed numerical study based on 954 problems from the CUTEr test set. An evaluation is made of several line-search options, and a comparison is provided with two state-of-the-art interior-point codes for nonlinear programming.

MSC:
90C51 Interior-point methods
90C06 Large-scale problems in mathematical programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benson, H. Y., Shanno, D. F., Vanderbei, R. J.: Interior-point methods for nonconvex nonlinear programming: Filter methods and merit functions. Computational Optimization and Applications, 23 (2), 257–272 (2002) · Zbl 1022.90017 · doi:10.1023/A:1020533003783
[2] Byrd, R. H., Gilbert, J. Ch., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming, 89, 149–185 (2000) · Zbl 1033.90152 · doi:10.1007/PL00011391
[3] Byrd, R. H., Hribar, M. E., Nocedal, J.: An interior point algorithm for large-scale nonlinear programming. SIAM Journal on Optimization, 9 (4), 877–900 (1999) · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[4] Byrd, R. H., Liu, G., Nocedal, J.: On the local behavior of an interior point method for nonlinear programming. In: Griffiths, D. F., Higham, D. J. (eds), Numerical Analysis 1997, pages 37–56. Addison–Wesley Longman, Reading, MA, USA, 1997 · Zbl 0902.65021
[5] Chamberlain, R. M., Lemarechal, C., Pedersen, H. C., Powell, M. J. D.: The watchdog technique for forcing convergence in algorithms for constrained optimization. Mathematical Programming Study, 16, 1–17 (1982) · Zbl 0477.90072 · doi:10.1007/BFb0120945
[6] Conn, A. R., Gould, N. I. M., Toint, Ph. L.: LANCELOT: a Fortran package for large-scale nonlinear optimization (Release A). Number 17 in Springer Series in Computational Mathematics. Springer Verlag, Heidelberg, Berlin, New York, 1992 · Zbl 0761.90087
[7] Conn, A. R., Gould, N. I. M., Toint, Ph. L.: Trust-Region Methods. SIAM, Philadelphia, PA, USA, 2000 · Zbl 0958.65071
[8] Conn, A. R., Gould, N.I.M., Orban, D., Toint, Ph. L.: A primal-dual trust-region algorithm for non-convex nonlinear programming. Mathematical Programming, 87 (2), 215–249 (2000) · Zbl 0970.90116 · doi:10.1007/s101070050112
[9] Dolan, E. D., Moré, J. J.: Benchmarking optimization software with performance profiles. Mathematical Programming, 91 (2), 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[10] El-Bakry, A. S., Tapia, R. A., Tsuchiya, T., Zhang, Y.: On the formulation and theory of the Newton interior-point method for nonlinear programming. Journal of Optimization Theory and Application, 89 (3), 507–541 (1996) · Zbl 0851.90115 · doi:10.1007/BF02275347
[11] Fiacco, A. V., McCormick, G. P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley, New York, USA, 1968 Reprinted by SIAM Publications, 1990. · Zbl 0193.18805
[12] Fletcher, R.: Practical Methods of Optimization. John Wiley and Sons, New York, USA, second edition, 1987 · Zbl 0905.65002
[13] Fletcher, R., Gould, N. I. M., Leyffer, S., Toint, Ph. L., Wächter, A.: Global convergence of a trust-region SQP-filter algorithms for general nonlinear programming. SIAM Journal on Optimization, 13 (3), 635–659 (2002) · Zbl 1038.90076 · doi:10.1137/S1052623499357258
[14] Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Mathematical Programming, 91 (2), 239–269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[15] Fletcher, R., Leyffer, S., Toint, Ph. L.: On the global convergence of a filter-SQP algorithm. SIAM Journal on Optimization, 13 (1), 44–59 (2002) · Zbl 1029.65063 · doi:10.1137/S105262340038081X
[16] Forsgren, A., Gill, P. E., Wright, M. H.: Interior methods for nonlinear optimization. SIAM Review, 44 (4), 525–597 (2002) · Zbl 1028.90060 · doi:10.1137/S0036144502414942
[17] Gould, N. I. M., Orban, D., Sartenaer, A., Toint, Ph. L.: Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM Journal on Optimization, 11 (4), 974–1002 (2001) · Zbl 1003.65066 · doi:10.1137/S1052623400370515
[18] Gould, N. I. M., Orban, D., Toint, Ph. L.: CUTEr (and SifDec), a constrained and unconstrained testing environment, revisited. Technical Report TR/PA/01/04, CERFACS, Toulouse, France, 2001 · Zbl 1068.90526
[19] Harwell Subroutine Library, AEA Technology, Harwell, Oxfordshire, England. A catalogue of subroutines (HSL 2000), 2002
[20] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York, NY, USA, 1999 · Zbl 0930.65067
[21] Tits, A. L., Wächter, A., Bakhtiari, S., Urban, T. J., Lawrence, C. T.: A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties. SIAM Journal on Optimization, 14 (1), 173–199 (2003) · Zbl 1075.90078 · doi:10.1137/S1052623401392123
[22] Ulbrich, M., Ulbrich, S., Vicente, L. N.: A globally convergent primal-dual interior-point filter method for nonlinear programming. Mathematical Programming, 100 (2), 379–410 (2004) · Zbl 1070.90110 · doi:10.1007/s10107-003-0477-4
[23] Vanderbei, R. J., Shanno, D. F.: An interior-point algorithm for nonconvex nonlinear programming. Computational Optimization and Applications, 13, 231–252 (1999) · Zbl 1040.90564 · doi:10.1023/A:1008677427361
[24] Wächter, A.: An Interior Point Algorithm for Large-Scale Nonlinear Optimization with Applications in Process Engineering. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, January 2002
[25] Wächter, A., Biegler, L. T.: Failure of global convergence for a class of interior point methods for nonlinear programming. Mathematical Programming, 88 (2), 565–574 (2000) · Zbl 0963.65063 · doi:10.1007/PL00011386
[26] Wächter, A., Biegler, L. T.: Line search filter methods for nonlinear programming: Motivation and global convergence. Technical Report RC 23036, IBM T.J. Watson Research Center, Yorktown Heights, USA, 2001; revised 2004. To appear in SIAM Journal on Optimization. · Zbl 1114.90128
[27] Waltz, R. A., Morales, J. L., Nocedal, J., Orban, D.: An interior algorithm for nonlinear optimization that combines line search and trust region steps. Technical Report OTC 6/2003, Optimization Technology Center, Northwestern University, Evanston, IL, USA. To appear in Mathematical Programming A · Zbl 1134.90053
[28] Waltz, R. A., Nocedal, J.: KNITRO user’s manual. Technical Report OTC 2003/05, Optimization Technology Center, Northwestern University, Evanston, IL, USA, April 2003
[29] Yamashita, H.: A globally convergent primal-dual interior-point method for constrained optimization. Optimization Methods and Software, 10, 443–469 (1998) · Zbl 0946.90110 · doi:10.1080/10556789808805723
[30] Yamashita, H., Yabe, H., Tanabe, T.: A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization. Technical report, Mathematical System Institute, Inc., Tokyo, Japan, July 1997. Revised July 1998 · Zbl 1062.90036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.