A trust region algorithm for equality constrained optimization. (English) Zbl 0816.90121

Powell, M. J. D.; Yuan, Yaxiang

Math. Program., Ser. A 49, No. 2, 189-211 (1990).

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.

Reviewer: D.J.van Wyk (Potchefstroom, South Africa) (M.R.91m:90162)

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)

Keywords:

global convergence properties; equality constrained nonlinear optimization; quadratic programming subproblem; trust regions; local superlinear convergence

Citations:

Zbl 0598.90079

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 · doi:10.1093/imamat/21.1.67
[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 · doi:10.1137/0320014
[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 · doi:10.1137/0902016
[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 · doi:10.1007/BF01580880
[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 · doi:10.1007/BF01395810
[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. · doi:10.1145/1057562.1057564
[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 · doi:10.1137/0722035
[21]	Y. Yuan, ”Conditions for convergence of trust region algorithms for nonsmooth optimization,”Mathematical Programming 31 (1985) 220–228. · Zbl 0576.90080 · doi:10.1007/BF02591750
[22]	Y. Yuan, ”A dual algorithm for minimizing a quadratic function with two quadratic constraints,” Report DAMTP 1988/NA3, University of Cambridge (Cambridge, 1988).