×

zbMATH — the first resource for mathematics

An SQP method for general nonlinear programs using only equality constrained subproblems. (English) Zbl 0930.90082
Summary: We describe a new version of a sequential equality constrained quadratic programming method for general nonlinear programs with mixed equality and inequality constraints. Compared with an older version of the author [Springer Lect. Notes Control Inf. Sci. 30, 123-141 (1981; Zbl 0453.90085)] it is much simpler to implement and allows any kind of changes of the working set in every step. Our method relies on a strong regularity condition. As far as it is applicable the new approach is superior to conventional SQP-methods, as demonstrated by extensive numerical tests.

MSC:
90C55 Methods of successive quadratic programming type
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Bracken, G.P. McCormick, Selected applications of nonlinear programming, Wiley, New York, 1968.
[2] J.W. Burke, An exact penalization viewpoint of constrained optimization, SIAM J. Control Optim. 29 (1991) 968–998. · Zbl 0737.90060 · doi:10.1137/0329054
[3] R.H. Byrd, J. Nocedal, An analysis of reduced Hessian methods for constrained optimization, Math. Programming 49 (1991) 285–323. · Zbl 0719.90071 · doi:10.1007/BF01588794
[4] R.H. Byrd, J. Nocedal, R.B. Schnabel, Representations of quasi-Newton-matrices and their use in limited memory methods, Math. Programming 63 (1994) 129–156. · Zbl 0809.90116 · doi:10.1007/BF01582063
[5] Th.F. Coleman, A.R. Conn, Nonlinear programming via an exact penalty function: Global analysis, Math. Programming 24 (1982) 137–161. · Zbl 0501.90077 · doi:10.1007/BF01585101
[6] Th.F. Coleman, A.R. Conn, Nonlinear programming via an exact penalty function: Asymptotic analysis, Math. Programming 24 (1982) 123–136. · Zbl 0501.90078 · doi:10.1007/BF01585100
[7] Th.F. Coleman, A.R. Conn, On the local convergence of a quasi-Newton-method for the nonlinear programming problem, SIAM J. Numer. Anal. 21 (1984) 755–769. · Zbl 0566.65046 · doi:10.1137/0721051
[8] Th.F. Coleman, P.A. Fenyes, Partitioned quasi-Newton methods for nonlinear equality constrained optimization, Math. Programming 53 (1992) 17–44. · Zbl 0751.90070 · doi:10.1007/BF01585692
[9] A.R. Conn, T. Pietrzykowski, A penalty function method converging directly to a constrained optimum, SIAM J. Numer. Anal. 14 (1977) 348–374. · Zbl 0361.90076 · doi:10.1137/0714022
[10] K. Crusius, Ein global konvergentes Verfahren der projizierten Richtungen mit nicht notwendig zulàssigen Iterationspunkten, Ph.D. Thesis, Mainz University, Mainz, Germany, 1983. · Zbl 0545.65046
[11] R.S. Dembo, A set of geometric programming test problems and their solutions, Math. Programming 10 (1976) 192–213. · Zbl 0349.90066 · doi:10.1007/BF01580667
[12] J.C. Dodu, P. Huard, Utilisation de mises à jour doubles dans les méthodes de quasi-Newton, Comptes Rendus de l’ Academie de Sciences Paris Série I, 313 (1991) 329–334. · Zbl 0733.65042
[13] I.S. Duff, A.M. Erisman, J.K. Reid, Direct method for sparse matrices, Oxford Univ. Press, Oxford, 1986. · Zbl 0604.65011
[14] R. Fletcher, Practical methods of optimization, 2nd ed., Wiley, Chicester, 1987. · Zbl 0905.65002
[15] D. Gabay, Reduced quasi-Newton methods with feasibility improvement for nonlinearly constrained optimization, Math. Programming Stud. 16 (1982) 18–44. · Zbl 0477.90065 · doi:10.1007/BFb0120946
[16] Ph.E. Gill, W. Murray, Numerically stable methods for quadratic programming, Math. Programming 14 (1978) 349–372. · Zbl 0374.90054 · doi:10.1007/BF01588976
[17] Ph.E. Gill, W. Murray, M. Saunders, M.H. Wright, Some theoretical properties of an augmented Lagrangian merit function, in: P.M. Pardalos (Ed.), Advances in Optimization and Parallel Computing, North Holland, Amsterdam, 1992, pp. 101–128. · Zbl 0814.90094
[18] Ph.E. Gill, W. Murray, M. Saunders, M.H. Wright, Sparse matrix methods in optimization, SIAM J. Sci. Comp. 5 (1984) 562–589. · Zbl 0559.65042 · doi:10.1137/0905041
[19] Ph.E. Gill, S.J. Hammarling, W. Murray, M. Saunders, M.H. Wright, Users Guide for NOPSOL (ver. 4.0), Department O R, Stanford University, Report SOL 86-2, 1986.
[20] Ch. Gurwitz, Local convergence of a two-piece update of a projected Hessian matrix, SIAM J. Optim. 4 (1994) 461–485. · Zbl 0834.90118 · doi:10.1137/0804026
[21] Ch. Gurwitz, M. Overton, Sequential quadratic programming methods based on approximating a projected Hessian matrix, SIAM J. Sci. Comp. 10 (1989) 631–653. · Zbl 0686.65033 · doi:10.1137/0910039
[22] D.M. Himmelblau, Applied nonlinear programming, McGraw-Hill, New York, 1972. · Zbl 0241.90051
[23] J. Heinz, P. Spellucci, A successful implementation of the Pantoja-Mayne SQP method, Optim. Meth. Software 4 (1994) 1–28. · doi:10.1080/10556789408805575
[24] W. Hock, K. Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems 187, Springer, Berlin, 1981. · Zbl 0452.90038
[25] D.Q. Mayne, E. Polak, A superlinearly convergent algorithm for constrained optimization problems, Math. Programming Stud. 16 (1982) 45–61. · Zbl 0477.90071 · doi:10.1007/BFb0120947
[26] J.F.A. Pantoja, D.Q. Mayne, Exact penalty function algorithm with simple updating of the penalty parameter, J. Optim. Theory Appl. 69 (1991) 441–467. · Zbl 0724.90065 · doi:10.1007/BF00940684
[27] W. Murray, J.P. Prieto, A sequential quadratic programming algorithm using an incomplete solution of the subproblem, SIAM J. Optim. 5 (1995) 590–640. · Zbl 0840.65052 · doi:10.1137/0805030
[28] J. Nocedal, M. Overton, Projected Hessian updating algorithms for nonlinearly constrained optimization, SIAM J. Numer. Anal. 22 (1985) 821–850. · Zbl 0593.65043 · doi:10.1137/0722050
[29] H.K. Overley, Structured Secant Updates for Nonlinear Constrained Optimization, Ph.D. Thesis, Rice University, Rice, Texas, 1991.
[30] K. Schittkowski, The nonlinear programming method of Wilson, Han and Powell with an augmented Lagrangian type line search function I, II, Numer. Math. 38 (1981) 83–128. · Zbl 0534.65030 · doi:10.1007/BF01395810
[31] K. Schittkowski, More test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems 282, Springer, Berlin, 1987. · Zbl 0658.90060
[32] P. Spellucci, Numerische Verfahren der nichtlinearen Optimierung, Birkhäuser, Basel, 1993. · Zbl 0780.90091
[33] P. Spellucci, donlp2: do nonlinear programming, code obtainable via anonymous ftp from netlib as netlib/opt/donlp2.
[34] P. Spellucci, Han’s method without solving QP, in: A. Auslender, W. Oettli, J. Stoer (Eds.), Optimization and Optimal Control, Lecture Notes in Control and Information Sciences, vol. 30, Springer, Berlin, 1981, pp. 123–141. · Zbl 0453.90085
[35] P. Spellucci, Sequential quadratic programming: Theory, implementation, problems, in: M.J. Beckmann, K.W. Gaede, K. Ritter, H. Schneeweiss (Eds.), Methods of Operations Research, vol. 53, Anton Hain, Meisenheim, 1985, pp. 183–213. · Zbl 0598.90073
[36] P. Spellucci, A new technique for inconsistent QP-problems in the SQP-method, Technical University at Darmstadt, Department of Mathematics, preprint 1561, Darmstadt (1993), to appear in Mathematical Methods of Operations Research, vol. 48 (1998). · Zbl 0964.90062
[37] G.W. Stewart, The effects of rounding error on an algorithm for downdating a Cholesky factorization, J.I.M.A. 23 (1979) 203–213. · Zbl 0405.65019
[38] Y. Xie, Reduced Hessian algorithm for solving large scale equality constrained optimization problems, Ph.D. Thesis, University of Colorado at Boulder, Boulder, Colorado, 1991.
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.