×

zbMATH — the first resource for mathematics

Global and local convergence of a class of penalty-free-type methods for nonlinear programming. (English) Zbl 1252.90078
Summary: We present a class of trust region algorithms without using a penalty function or a filter for nonlinear inequality constrained optimization and analyze their global and local convergence. In each iteration, the algorithms reduce the value of objective function or the measure of constraints violation according to the relationship between optimality and feasibility. A sequence of steps focused on improving optimality is referred to as an f-loop, while some restoration phase focuses on improving feasibility and is called an h-loop. In an f-loop, the algorithms compute trial step by solving a classic QP subproblem rather than using composite-step strategy. Global convergence is ensured by requiring the constraints violation of each iteration not to exceed an progressively tighter bound on constraints violation. By using a second order correction strategy based on active set identification technique, Marato’s effect is avoided and fast local convergence is shown. The preliminary numerical results are encouraging.

MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. prog. ser. A, 91, 239-269, (2002) · Zbl 1049.90088
[2] Fletcher, R.; Leyffer, S.; Toint, Ph.L., On the global convergence of an filter-SQP algorithm, SIAM J. optim., 13, 44-59, (2002) · Zbl 1029.65063
[3] Fletcher, R.; Gould, N.I.M.; Leyffer, S.; W ächer, A.; Toint, Ph.L., Global convergence of trust region SQP-filter algorithms for general nonlinear programming, SIAM J. optim., 13, 635-659, (2003)
[4] Ulbrich, S., On the superlinear local convergence of a filter-SQP method, Math. prog. ser. B, 100, 217-245, (2004) · Zbl 1146.90525
[5] Chin, C.M.; Fletcher, R., On the global convergence of an SLP-fliter algorithm that takes EQP steps, Math. prog., 96, 161-177, (2003) · Zbl 1023.90060
[6] R. Silva, M. Ulbrich, S. Ulbrich, N. Vicent, A globally convergent primal-dual interior-point filter method for nonlinear programming: New filter optimization measures and computational results, <www.optimization-online.org>, 2008.10.
[7] Ulbrich, M.; Ulbrich, S.; Vicent, N., A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. prog., 100, 379-410, (2004) · Zbl 1070.90110
[8] Wächter, A.; Biegler, L.T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. prog. ser. A, 106, 5-57, (2006) · Zbl 1134.90542
[9] Chin, C.M.; Rashid, A.H.A.; Nor, K.M., Global and local convergence of a filter line search method for nonlinear programming, Optim. meth. soft., 3, 22, 365-390, (2007) · Zbl 1193.90192
[10] 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
[11] 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
[12] Ulbrich, M.; Ulbrich, S., Nonmonotone trust region methods for nonlinear equality constrained optimization without a penalty function, Math. prog., 95, 103-135, (2003) · Zbl 1030.90123
[13] H. Yamashita, H. Yabe, A globally convergent trust-region SQP method without a penalty function for nonlinearly constrained optimization, Technical report, Mathematical Systems, Inc., Sinjuku-ku, Tokyo, Japan, 2003.
[14] Gould, N.I.M.; Toint, Ph.L., Nonlinear programming without a penalty function or a filter, Math. prog., 122, 155-196, (2010) · Zbl 1216.90069
[15] Chen, Z.W., A penalty-free-type nonmonotone trust-region method for nonlinear constrained optimization, Appl. math. comput., 173, 1014-1046, (2006) · Zbl 1093.65058
[16] H. Yamashita, A globally convergent quasi-Newton method for equality constrained optimization that does not use a penalty function, Technical Report, Mathematical Systems Inc., Tokyo, Japan, 1979, Revised in 1982.
[17] S.Q. Qiu, Z.W. Chen, A new penalty-free-type algorithm that based on trust region techniques, submitted to JCAM. · Zbl 1282.90182
[18] Panier, E.R.; Tits, A.L., A superlinear convergent feasible method for the solution of inequality constrained optimization problems, SIAM J. contr. optim., 25, 934-950, (1987) · Zbl 0634.90054
[19] Panier, E.R.; Tits, A.L., On combining feasibility, descent and superlinear convergence in inquality constrained optimization, Math. prog., 59, 261-276, (1993) · Zbl 0794.90068
[20] Facchinei, F.; Lucidi, S., Quadratically and superlinearly convergent algorithm for the solution of inequality constrained minimization problems, Jota, 85, 265-289, (1995) · Zbl 0830.90125
[21] Lucidi, S., New results on a continuously differentiable exact penalty function, SIAM J. optim., 2, 558-574, (1992) · Zbl 0761.90089
[22] Lawrence, G.T.; Tits, A.L., A computationally efficient feasible sequential quadratic programming algorithm, SIAM J. optim., 11, 1092-1118, (2001) · Zbl 1035.90105
[23] Boggs, P.T.; Tolle, J.W., Sequential quadratic programming, Acta numerica, (1995), Cambridge Univ. Press Cambridge, UK, 1-51 · Zbl 0828.65060
[24] Dennis Jr, J.E.; Moré, J.J., Quasi-Newton methods, motivation and theory, SIAM rev., 19, 46-89, (1977) · Zbl 0356.65041
[25] Robinson, S.M., Perturbed kuhn – tucker points and rates of convergence for a class of nonlinear-programming algorithms, Math. prog., 7, 7-16, (1974) · Zbl 0294.90078
[26] Nocedal, J.; Wright, S.J., Numerical optimization, Springer series in operations research, (1999), Springer-Verlag NewYork
[27] Bongartz, I.; Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., CUTE: constrained and unconstrained testing environment, ACM trans. math. software, 21, 123-160, (1995) · Zbl 0886.65058
[28] M.J.D. Powell, A fast algorithms for nonlinearly constrained optimization calculations, in: G.A. Watson (Ed.), Proc. 1977 Dundee Biennial Conference on Numerical Analysis, Springer, Berlin, 1978, 44C157.
[29] Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., LANCELOT: A Fortran package for large-scale nonlinear optimization (release A), (1992), Springer-Verlag Berlin · Zbl 0809.65066
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.