Abstract
This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.H. Byrd, R.B. Schnabel and G.A. Shultz, “Approximate solution of the trust region problem by minimization over two-dimensional subspaces,”Mathematical Programming 40 (1988) 247–263.
F.H. Clarke,Optimization and Nonsmooth Analysis, Canadian Math. Soc. Series of Monographs and Advanced Texts (John Wiley, 1983).
J.E. Dennis Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, New Jersey, 1983).
I.S. Duff, J. Nocedal and J.K. Reid, “The use of linear programming for the solution of sparse sets of nonlinear equations,”SIAM Journal on Scientific and Statistical Computing 8 (1987) 99–108.
M. El Hallabi, “A global convergence theory for arbitrary norm trust region methods for nonlinear equations”, Ph.D. Thesis, Rice University, Houston, TX (1987).
M. El Hallabi and R.A. Tapia, “A global convergence theory for arbitrary norm trust region methods for nonlinear equations,” Technical Report 87-25, Department of Mathematical Sciences, Rice University, Houston, TX (1987).
R. Fletcher, “A model algorithm for composite nondifferentiable optimization problem,”Mathematical Programming Studies 17 (1982) 67–76.
R. Fletcher, “AnL 1-penalty method for nonlinear constraints,” in: P. Boggs, R. Byrd and R. Schnabel, eds.,Numerical Optimization (SIAM, Philadelphia, 1984) pp. 26–40.
R. Fletcher,Practical Methods of Optimization (John Wiley, Chichester, 1987).
S.-B.B. Li, “Global convergence of trust region methods for minimizing a nondifferentiable function,” Ph.D. Thesis, Rice University, Houston, TX (1989).
J.J. Moré, “Recent developments in algorithms and software for trust region methods,” in: A. Bachern, M. Grotschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer Verlag, Berlin, 1983) pp. 258–287.
J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970).
M.J.D. Powell, “General algorithms for discrete nonlinear approximation calculations,” Report DAMTP 1983/NA2, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, England (1983).
M.J.D. Powell, “On the global convergence of trust region algorithms for unconstrained minimization,”Mathematical Programming 29 (1984) 297–303.
R.T. Rockafellar,Convex Analysis (Princeton Mathematics Services, Princeton University, Princeton, NJ, 1970).
Y. Yuan, “Global convergence of trust region algorithms for nonsmooth optimization,” Report DAMTP 1983/NA13, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, England (1983).
J. Zhang, N.-H. Kim and L. Lasdon, “An improved successive linear programming algorithm,”Management Science 31 (1985) 1312–1331.
Author information
Authors and Affiliations
Additional information
Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.
Corresponding author.
Rights and permissions
About this article
Cite this article
Dennis, J.E., Li, SB.B. & Tapia, R.A. A unified approach to global convergence of trust region methods for nonsmooth optimization. Mathematical Programming 68, 319–346 (1995). https://doi.org/10.1007/BF01585770
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585770