×

zbMATH — the first resource for mathematics

A trust region algorithm for equality constrained optimization. (English) Zbl 0816.90121
An iterative technique for solving equality constrained nonlinear optimization problems is considered. In each step a search direction from an approximate solution is calculated by solving a quadratic programming subproblem which approximates the original problem. In an earlier paper [ibid. 35, No. 3, 265–278 (1986; Zbl 0598.90079)] the authors proposed an algorithm in which the step-length of each iteration is determined by means of a differentiable exact penalty function. The present paper extends the results to the case where convergence is forced by means of trust regions instead of line searches. Basically, in each iteration a trial step (bounded by a positive parameter) in the search direction is subjected to tests before being accepted. Global convergence properties and a local superlinear convergence result are proved.

MSC:
90C30 Nonlinear programming
65K10 Numerical optimization and variational techniques
90-08 Computational methods for problems pertaining to operations research and mathematical programming
49M30 Other numerical methods in calculus of variations (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982). · Zbl 0572.90067
[2] M.C. Biggs, ”On the convergence of some constrained minimization algorithms based on recursive quadratic programming,”Journal of the Institute of Mathematics and its Applications 21 (1978) 67–82. · Zbl 0373.90056
[3] M.C. Biggs, ”A recursive quadratic programming algorithm based on the augmented Lagrangian function,” Technical Report 139, Numerical Optimisation Centre, Hatfield Polytechnic (Hatfield, England, 1983).
[4] P.T. Boggs, J.W. Tolle and P. Wang, ”On the local convergence of quasi-Newton methods for constrained optimization,”SIAM Journal on Control and Optimization 20 (1982) 161–171. · Zbl 0494.65036
[5] R.H. Byrd, R.B. Schnabel and G.A. Shultz, ”A trust region algorithm for nonlinearly constrained optimization,” Technical Report CU-CS-313-85, University of Colorado (Boulder, CO, 1985). · Zbl 0631.65068
[6] M.R. Celis, J.E. Dennis and R.A. Tapia, ”A trust region strategy for nonlinear equality constrained optimization,” in: P.T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numerical Optimization 1984 (SIAM, Philadelphia, 1985) pp. 71–82. · Zbl 0566.65048
[7] R. Fletcher,Practical Methods of Optimization (John Wiley and Sons, Chichester, 1987, 2nd ed.). · Zbl 0905.65002
[8] D.M. Gay, ”Computing optimal locally constrained steps,”SIAM Journal on Scientific and Statistical Computing 2 (1981) 186–197. · Zbl 0467.65027
[9] J.J. Moré, ”Recent developments in algorithms and software for trust region methods,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming, The State of the Art (Springer-Verlag, Berlin, 1983) pp. 258–287.
[10] M.J.D. Powell, ”Convergence properties of a class of minimization algorithms,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming, Vol. 2 (Academic Press, New York, 1975) pp. 1–27. · Zbl 0321.90045
[11] M.J.D. Powell, ”The convergence of variable metric methods for nonlinearly constrained optimization,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming, Vol. 3 (Academic Press, New York, 1978) pp. 27–63. · Zbl 0464.65042
[12] M.J.D. Powell, ”Variable metric methods for constrained optimization,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming, The State of the Art (Springer-Verlag, Berlin, 1983) pp. 288–311.
[13] M.J.D. Powell, ”The performance of two subroutines for constrained optimization on some difficult test problems,” in: P.T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numerical Optimization 1984 (SIAM, Philadelphia, 1985) pp. 160–177.
[14] M.J.D. Powell and Y. Yuan, ”A recursive quadratic programming algorithm for equality constrained optimization,”Mathematical Programming 35 (1986a) 265–278. · Zbl 0598.90079
[15] M.J.D. Powell and Y. Yuan, ”A trust region algorithm for equality constrained optimization,” Report DAMTP 1986/NA2, University of Cambridge, 1986b. · Zbl 0816.90121
[16] K. Schittkowski, ”The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function, Part I: convergence analysis,”Numerische Mathematik 38 (1981) 83–114. · Zbl 0534.65030
[17] K. Schittkowski, ”On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function,”Mathematische Operationsforschung und Statistik, Series Optimization 14 (1983) 197–216. · Zbl 0523.90075
[18] D.C. Sorensen, ”An example concerning quasi-Newton estimates of a sparse Hessian,”SIGNUM Newsletter 16, No. 2 (1981) 8–10.
[19] D.C. Sorensen, ”Trust region methods for unconstrained optimization,” in: M.J.D. Powell, ed.,Nonlinear Optimization 1981 (Academic Press, London, 1982) pp. 29–38.
[20] A. Vardi, ”A trust region algorithm for equality constrained minimization: convergence properties and implementation,”SIAM Journal on Numerical Analysis 22 (1985) 575–591. · Zbl 0581.65045
[21] Y. Yuan, ”Conditions for convergence of trust region algorithms for nonsmooth optimization,”Mathematical Programming 31 (1985) 220–228. · Zbl 0576.90080
[22] Y. Yuan, ”A dual algorithm for minimizing a quadratic function with two quadratic constraints,” Report DAMTP 1988/NA3, University of Cambridge (Cambridge, 1988).
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.