×

A line search filter algorithm with inexact step computations for equality constrained optimization. (English) Zbl 1244.65091

A new inexact Newton-like algorithm for equality constrained optimization in the framework of a standard line search method is presented. The main feature of this algorithm is to combine inexact step computations with filter techniques proposed by R. Fletcher and S. Leyffer [Math. Program. 91, No. 2 (A), 239–269 (2002; Zbl 1049.90088)]. It can also be regarded as an inexact version of generic sequential quadratic programming methods. The trial step is obtained by truncatedly solving the primal-dual system based on any robust and efficient linear system solver such as a Krylov subspace method. Practical termination tests for the linear system solver are established to ensure global convergence. Preliminary numerical results demonstrate the approach is potentially usefull.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C55 Methods of successive quadratic programming type
90C53 Methods of quasi-Newton type

Citations:

Zbl 1049.90088
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Byrd, R. H.; Curtis, F. E.; Nocedal, J., An inexact SQP method for equality constrained optimization, SIAM J. Optim., 19, 351-369 (2008) · Zbl 1158.49035
[2] Byrd, R. H.; Curtis, F. E.; Nocedal, J., An inexact Newton method for nonconvex equality constrained optimization, Math. Program., 122, 273-299 (2010) · Zbl 1184.90127
[3] Chin, C. M.; Fletcher, R., On the global convergence of an SLP-filter algorithm that takes EQP steps, Math. Program., 96, 161-177 (2003) · Zbl 1023.90060
[4] Curtis, F. E.; Nocedal, J.; Wächter, A., A matrix-free algorithm for equality constrained optimization problems with rank-deficient Jacobians, SIAM J. Optim., 20, 1224-1249 (2009) · Zbl 1195.49035
[5] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[6] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program., 91, 239-269 (2002) · Zbl 1049.90088
[7] Fletcher, R.; Leyffer, S.; Toint, P. L., On the global convergence of a filter-SQP algorithm, SIAM J. Optim., 13, 44-59 (2002) · Zbl 1029.65063
[8] Fletcher, R.; Gould, N.; Leyffer, S.; Toint, P. L.; Wächter, A., Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming, SIAM J. Optim., 13, 635-659 (2003) · Zbl 1038.90076
[9] Gould, N. I.M.; Leyffer, S.; Toint, P. L., A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares, SIAM J. Optim., 15, 17-38 (2004) · Zbl 1075.65075
[10] Gould, N. I.M.; Sainvitu, C.; Toint, P. L., A filter-trust-region method for unconstrained optimization, SIAM J. Optim., 16, 341-357 (2005) · Zbl 1122.90074
[11] Heinkenschloss, M.; Vicente, L. N., Analysis of inexact trust-region SQP algorithms, SIAM J. Optim., 12, 283-302 (2001) · Zbl 1035.90104
[12] Hock, W.; Schittkowski, K., Test Examples for Nonlinear Programming Codes (1981), Springer-Verlag · Zbl 0452.90038
[13] Izmailov, A. F.; Solodov, M. V., A truncated SQP method based on inexact interior-point solutions of subproblems, SIAM J. Optim., 20, 2584-2613 (2010) · Zbl 1211.90233
[14] Lalee, M.; Nocedal, J.; Plantenga, T., On the implementation of an algorithm for large-scale equality constrained optimization, SIAM J. Optim., 8, 682-706 (1998) · Zbl 0913.65055
[15] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer: Springer New York · Zbl 1104.65059
[16] Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equation, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[17] Powell, M. J.D., A fast algorithm for nonlinearly constrained optimization calculations, (Watson, G. A., Numerical Analysis. Numerical Analysis, Proceeding of the Biennial Conference Held at Dundee, 1977. Numerical Analysis. Numerical Analysis, Proceeding of the Biennial Conference Held at Dundee, 1977, Lecture Notes in Mathematics, vol. 630 (1978), Springer-Verlag: Springer-Verlag Berlin), 144-157 · Zbl 0374.65032
[18] C. Shen, S. Leyffer, R. Fletcher, A nonmonotone filter method for nonlinear optimization, Comput. Optim. Appl., published online: 29 October 2011.; C. Shen, S. Leyffer, R. Fletcher, A nonmonotone filter method for nonlinear optimization, Comput. Optim. Appl., published online: 29 October 2011. · Zbl 1259.90140
[19] Ulbrich, S., On the superlinear local convergence of a filter-SQP method, Math. Program., 100, 217-245 (2004) · Zbl 1146.90525
[20] Wächter, A.; Biegler, L. T., Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 16, 1-31 (2005) · Zbl 1114.90128
[21] Wächter, A.; Biegler, L. T., Line search filter methods for nonlinear programming: local convergence, SIAM J. Optim., 16, 32-48 (2005) · Zbl 1115.90056
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.