×

zbMATH — the first resource for mathematics

A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization. (English) Zbl 1062.90036
Summary: This paper proposes a primal-dual interior point method for solving large scale nonlinearly constrained optimization problems. To solve large scale problems, we use a trust region method that uses second derivatives of functions for minimizing the barrier-penalty function instead of line search strategies. Global convergence of the proposed method is proved under suitable assumptions. By carefully controlling parameters in the algorithm, superlinear convergence of the iteration is also proved. A nonmonotone strategy is adopted to avoid the Maratos effect as in the nonmonotone SQP method by Yamashita and Yabe. The method is implemented and tested with a variety of problems given by Hock and Schittkowski’s book and by CUTE. The results of our numerical experiment show that the given method is efficient for solving large scale nonlinearly constrained optimization problems.

MSC:
90C06 Large-scale problems in mathematical programming
90C51 Interior-point methods
90C55 Methods of successive quadratic programming type
90C30 Nonlinear programming
Software:
CUTE; CUTEr; LANCELOT; TRICE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York, 1982 · Zbl 0572.90067
[2] Bongartz, I., Conn, A.R., Gould, N., Toint, Ph.L.: CUTE:Constrained and Unconstrained Testing Environment. Research Report RC 18860, IBM T.J. Watson Research Center, Yorktown, USA, 1993 · Zbl 0886.65058
[3] Bonnans, J.F., Pola, C.: A trust region interior point algorithm for linearly constrained optimization. Technical Report 1948, INRIA, 1993 · Zbl 0899.90146
[4] Breitfield, M.G., Shanno, D.F.: Preliminary computational experience with modified log-barrier functions for large-scale nonlinear programming. In: Large Scale Optimization, Kluwer academic publishers, Dordrecht, Boston, London, 1994
[5] Bunch, J.R., Kaufman, L., Parlett, B.N.: Decomposition of a symmetric matrix. Numerische Math. 27, 95-110 (1976) · Zbl 0342.65026 · doi:10.1007/BF01399088
[6] 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) · Zbl 1033.90152 · doi:10.1007/PL00011391
[7] Byrd, R.H., Hribar, M.E., Nocedal, J.: An interior point algorithm for large-scale nonlinear programming. SIAM J. Optim. 9, 877-900 (1999) · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[8] Byrd, R.H., Liu, G., Nocedal, J.: On the local behaviour of an interior point method for nonlinear programming. In: Numerical analysis 1997, Griffiths, D.F., Higham, D.J., Watson, G.A., (eds.), Longman, 1998, pp. 37-56 · Zbl 0902.65021
[9] Coleman, T.F., Li, Y.: An interior trust region approach for nonlinear minimization subject to bounds. SIAM J. Optim. 6, 418-445 (1996) · Zbl 0855.65063 · doi:10.1137/0806023
[10] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: LANCELOT a Fortran package for large-scale nonlinear optimization (Release A). Springer Verlag, Heiderberg, Berlin, New York, 1992 · Zbl 0761.90087
[11] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. SIAM, Philadelphia, 2000 · Zbl 0958.65071
[12] Dennis, J.E., Heinkenschloss, M. Jr, Vicente, L.N.: T rust-region interior-point SQP algorithms for a class of nonlinear programming problems. SIAM J. Control Optim. 36, 1750-1794 (1998) · Zbl 0921.90137 · doi:10.1137/S036012995279031
[13] Duff, I.S., Reid, J.K.: The Multifrontal solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 9 (3), 302-325 (1983) · Zbl 0515.65022 · doi:10.1145/356044.356047
[14] 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. Optim. Theor. Appl. 89, 507-541 (1996) · Zbl 0851.90115 · doi:10.1007/BF02275347
[15] Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. SIAM, Philadelphia, 1990 · Zbl 0713.90043
[16] Fletcher, R.: Second order corrections for nondifferentiable optimization. In: Numerical Analysis ? Dundee 1981, G.A.Watson, (ed.), Lecture Notes in Mathematics 912, Springer-Verlag, Berlin, 1982, pp. 85-114
[17] Fletcher, R.: Practical Methods of Optimization. Second Edition, John Wiley & Sons, New York, 1987 · Zbl 0905.65002
[18] Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton?s method. SIAM J. Numerical Anal. 23, 707-716 (1986) · Zbl 0616.65067 · doi:10.1137/0723046
[19] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems 187, Springer-Verlag, Berlin, 1981 · Zbl 0452.90038
[20] Maratos, N.: Exact penalty function algorithms for finite dimensional and control optimization problems. Ph.D.Thesis, Imperial College of Science and Technology, University of London, London, U.K., 1978
[21] Maros, I., Mészáros, Cs.: The role of the augmented system in interior point methods. Technical Report TR/06/95, Brunel University, Department of Mathematics and Statistics, London, 1995
[22] Martinez, H.J., Parada, Z., Tapia, R.A.: On the characterization of Q-superlinear convergence of quasi-Newton interior-point methods for nonlinear programming. Boletin de la Sociedad Matematica Mexicana 1, 137-148 (1995) · Zbl 0853.65061
[23] Mayne, D.Q., Polak, E.: A superlinearly convergent algorithm for constrained optimization problems. Math. Program. Study 16, 45-61 (1982) · Zbl 0477.90071 · doi:10.1007/BFb0120947
[24] Mészáros, Cs.: The ?inexact? minimum local fill-in ordering algorithm. Working paper WP 95-7, Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, 1995
[25] Panier, E.R., Tits, A.L.: Avoiding the Maratos effect by means of a nonmonotone line search I: General constrained problems. SIAM J. Numerical Anal. 28, 1183-1195 (1991) · Zbl 0732.65055 · doi:10.1137/0728063
[26] Rothberg, E., Gupta, A.: Efficient sparse matrix factorization on high-performance workstations-Exploiting the memory hierarchy. ACM Trans. Math. Softw. 17(3), pp313-334 (1991) primal-dual Optimization · Zbl 0900.65066
[27] Yabe, H., Yamashita, H.: Q-superlinear convergence of primal-dual interior point quasi-Newton methods for constrained optimization. J. Oper. Res. Soc. Japan 40, 415-436 (1997) · Zbl 0914.90246
[28] Yamashita, H.: A globally convergent primal-dual interior point method for constrained optimization. Optim. Meth. Softw. 10, 443-469 (1998) · Zbl 0946.90110 · doi:10.1080/10556789808805723
[29] Yamashita, H., Tanabe, T.: A primal-dual interior point trust region method for large scale constrained optimization. Optimization ? Modeling and Algorithms 6, Cooperative Research Report 73, The Institute of Statistical Mathematics, March 1995, pp. 1-25
[30] Yamashita, H., Yabe, H.: A nonmonotone SQP method with global and superlinear convergence properties. Optimization ? Modeling and Algorithms 8, Cooperative Research Report 84, The Institute of Statistical Mathematics, March 1996, pp. 10-29
[31] Yamashita, H., Yabe, H.: Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization. Math. Program. 75, 377-397 (1996) · Zbl 0874.90175
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.