zbMATH — the first resource for mathematics

An interior algorithm for nonlinear optimization that combines line search and trust region steps. (English) Zbl 1134.90053
Summary: An interior-point method for nonlinear programming is presented. It enjoys the flexibility of switching between a line search method that computes steps by factoring the primal-dual equations and a trust region method that uses a conjugate gradient iteration. Steps computed by direct factorization are always tried first, but if they are deemed ineffective, a trust region iteration that guarantees progress toward stationarity is invoked. To demonstrate its effectiveness, the algorithm is implemented in the KNITRO http://www.ziena.com/knitro.htm software package and is extensively tested on a wide selection of test problems.

90C55 Methods of successive quadratic programming type
90C30 Nonlinear programming
90C51 Interior-point methods
Full Text: DOI
[1] Andersen, E.D., Gondzio, J., Mészáros, C., Xu, X.: Implementation of interior point methods for large scale linear programming. In: T. Terlaky, (ed.), Interior Point Methods in Mathematical Programming, Dordrecht, The Netherlands, 1996. Kluwer Academic Publishers, pp. 189–252 · Zbl 0874.90127
[2] Betts, J., Eldersveld, S.K., Frank, P.D., Lewis, J.G.: An interior-point nonlinear programming algorithm for large scale optimization. Technical report MCT TECH-003, Mathematics and Computing Technology, The Boeing Company, P.O. Box 3707, Seattle WA 98124-2207, 2000
[3] Bongartz, I., Conn, A.R., Gould, N.I.M.,Toint, Ph.L.: CUTE: Constrained and Unconstrained Testing Environment. ACM Transactions on Mathematical Software 21 (1), 123–160 (1995) · Zbl 0886.65058
[4] Bunch, J.R., Parlett, B.N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM Journal on Numerical Analysis 8 (4), 639–655 (1971) · Zbl 0199.49802
[5] Byrd, R.H., Gilbert, J.-Ch., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming 89 (1), 149–185 (2000) · Zbl 1033.90152
[6] Byrd, R.H., Hribar, M.E., Nocedal, J.: An interior point algorithm for large scale nonlinear programming. SIAM J. Optimization 9 (4), 877–900 (1999) · Zbl 0957.65057
[7] Byrd, R.H., Marazzi, M., Nocedal, J.: On the convergence of Newton iterations to non-stationary points. Mathematical Programming, Series A 99, 127–148 (2004) · Zbl 1072.90038
[8] Byrd, R.H., Nocedal, J., Schnabel, R.: Representations of quasi-newton matrices and their use in limited memory methods. Mathematical Programming 49 (3), 285–323 (1991) · Zbl 0719.90071
[9] Conn, A.R., Gould, N.I.M., Toint, Ph.: Trust-region methods. MPS-SIAM Series on Optimization. SIAM publications, Philadelphia, Pennsylvania, USA, 2000 · Zbl 0958.65071
[10] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Mathematical Programming, Series A 91, 201–213 (2002) · Zbl 1049.90004
[11] Dussault, J.-P.: Numerical stability and efficiency of penalty algorithms. SIAM J. Numerical Anal. 32 (1), 296–317 (1995) · Zbl 0816.65039
[12] 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. J. Optimization Theory and Appl. 89 (3), 507–541, June (1996) · Zbl 0851.90115
[13] El-Hallabi, M.: A hybrid algorithm for nonlinear equality constrained optimization problems: global and local convergence theory. Technical Report TR4-99, Mathematics and Computer Science Department, Institut National des Postes et Télécommunications, Rabat, Morocco, 1999
[14] Fletcher, R.: Practical Methods of Optimization. J. Wiley and Sons, Chichester, England, second edition, 1987 · Zbl 0905.65002
[15] Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Mathematical Programming 91, 239–269 (2002) · Zbl 1049.90088
[16] Forsgren, A., Gill, P.E.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM J. Optimization 8 (4), 1132–1152 (1998) · Zbl 0915.90236
[17] Gould, N.I.M., Orban, D., Sartenaer, A., Toint, Ph.L.: Superlinear convergence of primal-dual interior-point algorithms for nonlinear programming. SIAM J. Optimization 11 (4), 974–1002 (2001) · Zbl 1003.65066
[18] Gould, N.I.M., Orban, D., Toint, Ph.L.: CUTEr and sifdec: A Constrained and Unconstrained Testing Environment, revisited. ACM Trans. Math. Softw. 29 (4), 373–394 (2003) · Zbl 1068.90526
[19] 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 (4), 353–372 (2003) · Zbl 1068.90525
[20] Harwell Subroutine Library. A catalogue of subroutines (HSL 2002). AEA Technology, Harwell, Oxfordshire, England, 2002
[21] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, 1999 · Zbl 0930.65067
[22] Potra, F.: Q-superlinear convergence of the iterates in primal-dual interior-point methods. Mathematical Programming B 91 (1), 99–116 (2001) · Zbl 1051.90027
[23] Steihaug, T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numerical Anal. 20 (3), 626–637 (1983) · Zbl 0518.65042
[24] 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 J. Optimization 14 (1), 173–199 (2003) · Zbl 1075.90078
[25] Vanderbei, R.J., Shanno, D.F.: An interior point algorithm for nonconvex nonlinear programming. Comput. Optimization Appl. 13, 231–252 (1999) · Zbl 1040.90564
[26] Wächter, A., Biegler, L.T.: Failure of global convergence for a class of interior point methods for nonlinear programming. Mathematical Programming 88 (3), 565–574 (2000) · Zbl 0963.65063
[27] Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Technical Report RC 23149, IBM T.J. Watson Research Center, Yorktown Heights, NY, March 2004 · Zbl 1134.90542
[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] Yabe, H., Yamashita, H.: Q-superlinear convergence of primal-dual interior point quasi-Newton methods for constrained optimization. J. Oper. Res. Soc. Japan 40 (3), 415–436 (1997) · Zbl 0914.90246
[30] Yamashita, H.: A globally convergent primal-dual interior-point method for constrained optimization. Technical report, Mathematical System Institute, Inc., Tokyo, Japan, May 1992, Revised March 1994
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.