×

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.

MSC:

90C55 Methods of successive quadratic programming type
90C30 Nonlinear programming
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[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, ACM Transactions on Mathematical Software, 21, 123 (1) · Zbl 0886.65058 · doi:10.1145/200979.201043
[4] Bunch, SIAM Journal on Numerical Analysis, 8, 639 (4) · Zbl 0199.49802 · doi:10.1137/0708060
[5] Byrd, Mathematical Programming, 89, 149 (1) · doi:10.1007/PL00011391
[6] Byrd, SIAM J. Optimization, 9, 877 (4) · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[7] Byrd, Mathematical Programming, Series A, 99, 127 (2004) · Zbl 1072.90038 · doi:10.1007/s10107-003-0376-8
[8] Byrd, Mathematical Programming, 49, 285 (3) · Zbl 0719.90071 · doi:10.1007/BF01588794
[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, Mathematical Programming, Series A, 91, 201 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[11] Dussault, SIAM J. Numerical Anal., 32, 296 (1) · Zbl 0816.65039 · doi:10.1137/0732012
[12] El-Bakry, J. Optimization Theory and Appl., 89, 507 (3) · Zbl 0851.90115 · doi:10.1007/BF02275347
[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, Mathematical Programming, 91, 239 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[16] Forsgren, SIAM J. Optimization, 8, 1132 (4) · Zbl 0915.90236 · doi:10.1137/S1052623496305560
[17] Gould, SIAM J. Optimization, 11, 974 (4) · Zbl 1003.65066 · doi:10.1137/S1052623400370515
[18] Gould, ACM Trans. Math. Softw., 29, 373 (4) · Zbl 1068.90526 · doi:10.1145/962437.962439
[19] Gould, ACM Trans. Math. Softw., 29, 353 (4) · Zbl 1068.90525 · doi:10.1145/962437.962438
[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, Mathematical Programming B, 91, 99 (1)
[23] Steihaug, SIAM J. Numerical Anal., 20, 626 (3) · Zbl 0518.65042 · doi:10.1137/0720042
[24] Tits, SIAM J. Optimization, 14, 173 (1) · Zbl 1075.90078 · doi:10.1137/S1052623401392123
[25] Vanderbei, Comput. Optimization Appl., 13, 231 (1999) · Zbl 1040.90564 · doi:10.1023/A:1008677427361
[26] Wächter, Mathematical Programming, 88, 565 (3) · doi:10.1007/PL00011386
[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, J. Oper. Res. Soc. Japan, 40, 415 (3)
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.