×

A nonmonotone filter method for nonlinear optimization. (English) Zbl 1259.90140

Summary: We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global \(g\)-filter for global convergence, and a local nonmonotone \(l\)-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method.

MSC:

90C30 Nonlinear programming
90C55 Methods of successive quadratic programming type
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Audet, C., Dennis, J., Jr.: A pattern search filter method for nonlinear programming without derivatives. SIAM J. Optim. 14(4), 980–1010 (2004) · Zbl 1073.90066
[2] Benson, H., Vanderbei, R.: Cute models in AMPL (1998). http://orfe.princeton.edu/rvdb/ampl/nlmodels/cute/
[3] Bongartz, I., Conn, A.R., Gould, N.I.M., Toint, P.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 123–160 (1995) · Zbl 0886.65058
[4] Chamberlain, R.M., Powell, M.J.D., Lemarechal, C., Petersen, H.C.: The watchdog technique for forcing convergence in algorithms for constrained optimization. Math. Program. Stud. 16, 1–17 (1982) · Zbl 0477.90072
[5] Chin, C.M., Fletcher, R.: On the global convergence of an SLP-filter algorithm that takes EQP steps. Math. Program. 96(1), 161–177 (2003) · Zbl 1023.90060
[6] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[7] Dolan, E.D., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002) · Zbl 1049.90004
[8] Facchinei, F., Lucidi, S.: Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. J. Optim. Theory Appl. 85, 265–289 (1995) · Zbl 0830.90125
[9] Fletcher, R.: Stable reduced Hessian updates for indefinite quadratic programming. Math. Program. 87(2), 251–264 (2000) · Zbl 0964.65065
[10] Fletcher, R., Leyffer, S.: User manual for filterSQP. Numerical Analysis Report NA/181, University of Dundee (1998) · Zbl 0912.90225
[11] Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Program. 91, 239–270 (2002) · Zbl 1049.90088
[12] Fletcher, R., Leyffer, S.: Filter-type algorithms for solving systems of algebraic equations and inequalities. In: di Pillo, G., Murli, A. (eds.) High Performance Algorithms and Software for Nonlinear Optimization, pp. 259–278. Kluwer Academic, Dordrecht (2003) · Zbl 1112.90372
[13] Fletcher, R., Gould, N.I.M., Leyffer, S., Toint, P.L., Wächter, A.: Global convergence of trust-region SQP-filter algorithms for general nonlinear programming. SIAM J. Optim. 13(3), 635–659 (2002) · Zbl 1038.90076
[14] Fletcher, R., Leyffer, S., Toint, P.L.: On the global convergence of a filter-SQP algorithm. SIAM J. Optim. 13(1), 44–59 (2002) · Zbl 1029.65063
[15] Fletcher, R., Leyffer, S., Toint, P.L.: A brief history of filter methods. SIAG/OPT Views-and-News 18(1), 2–12 (2007)
[16] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modelling Language for Mathematical Programming, 2nd edn. Books/Cole Thomson Learning, New York (2003)
[17] Gonzaga, C.C., Karas, E.W., Vanti, M.: A globally convergent filter method for nonlinear programming. SIAM J. Optim. 14(3), 646–669 (2003) · Zbl 1079.90129
[18] Gould, N.I.M., Toint, P.L.: Global convergence of a non-monotone trust-region SQP-filter algorithm for nonlinear programming. Numerical Analysis Report RAL-TR-2003-003, Rutherford Appleton Laboratory, UK (2003). Available online at www.numerical.rl.ac.uk/reports/reports.shtml · Zbl 1063.90052
[19] Kanzow, C., Qi, H.-D.: A QP-free constrained Newton-type method for variational inequality problems. Math. Program. 85, 81–106 (1999) · Zbl 0958.65078
[20] Karas, E.W., Ribeiro, A., Sagastizábal, C., Solodov, M.: A bundle-filter method for nonsmooth convex constrained optimization. Math. Program. 116, 297–320 (2009) · Zbl 1165.90024
[21] Maratos, N.: Exact penalty function algorithms for finite dimensional and control optimization problems. Ph.D. thesis, Univ. of London (1978)
[22] Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983) · Zbl 0551.65042
[23] Qi, H.D., Qi, L.Q.: A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization. SIAM J. Optim. 11(1), 113–132 (2000) · Zbl 0999.90038
[24] Ribeiro, A., Karas, E.W., Gonzaga, C.C.: Global convergence of filter methods for nonlinear programming. SIAM J. Optim. 19, 1231–1249 (2008) · Zbl 1169.49034
[25] Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5, 43–62 (1980) · Zbl 0437.90094
[26] Ulbrich, S.: On the superlinear local convergence of a filter-SQP method. Math. Program. 100(1), 217–245 (2004) · Zbl 1146.90525
[27] Wächter, A., Biegler, L.: Line search filter methods for nonlinear programming: local convergence. SIAM J. Optim. 16(1), 32–48 (2005) · Zbl 1115.90056
[28] Wächter, A., Biegler, L.: Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16(1), 1–31 (2005) · Zbl 1114.90128
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.