On the superlinear convergence of a trust region algorithm for nonsmooth optimization. (English) Zbl 0577.90066
It was shown by the author [IMA J. Numer. Anal. 4, 327–335 (1984; Zbl 0555.65037)] that some trust region algorithms for nonsmooth optimization may converge only linearly. In this paper we study a ”second order correction” method proposed by R. Fletcher [Numerical analysis, Lect. Notes Math. 912, 85–114 (1982; Zbl 0476.65048)]. Under some mild conditions it is proved that the method is superlinear convergent.
Reviewer: Yaxiang Yuan
MSC:
| 90C30 | Nonlinear programming |
| 49M37 | Numerical methods based on nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
trust region algorithms; nonsmooth optimization; ”second order correction” method; superlinear convergentReferences:
| [1] | R.H. Bartels, A.R. Conn and J.W. Sinclair, ”Minimization techniques for piecewise differentiable functions: theL 1 solution to an overdetermined linear system”,SIAM Journal of Numerical Analysis 15 (1978) 224–241. · Zbl 0376.65018 · doi:10.1137/0715015 |
| [2] | R. Fletcher, ”A Fortran subroutine for general quadratic programming”, A.E.R.E. Report 6370, Harwell, England (1970). |
| [3] | R. Fletcher, ”A model algorithm for composite NDO problem”,Mathematical Programming Studies 17 (1982) 67–76. · Zbl 0478.90063 |
| [4] | R. Fletcher,Practical methods of optimization Vol. 2, Constrained optimization (John Wiley, New York, 1981). · Zbl 0474.65043 |
| [5] | R. Fletcher, ”Second order correction for nondifferentiable optimization”, in: G.A. Watson, ed.,Numerical analysis (Springer-Verlag, Berlin, 1982) pp. 85–114. |
| [6] | D. Goldfarb and A. Idnani, ”A numerically stable dual method for solving strictly convex quadratic programs”,Mathematical Programming 27 (1983) 1–33. · Zbl 0537.90081 · doi:10.1007/BF02591962 |
| [7] | P.E. Gill and W. Murray,Numerical methods for constrained optimization (Academic Press, London, 1974). · Zbl 0297.90082 |
| [8] | P.E. Gill and W. Murray, ”Numerically stable methods for quadratic programming”,Mathematical Programming 14 (1978) 349–372. · Zbl 0374.90054 · doi:10.1007/BF01588976 |
| [9] | P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”Linearly constrained optimization”, in: M.J.D. Powell, ed.,Nonlinear optimization 1981 (Academic Press, London, 1982). · Zbl 0571.90073 |
| [10] | W. Murray and M.L. Overton, ”A projected Lagrangian algorithm for nonlinear minmax optimization”,SIAM Journal on Scientific and Statistical Computing 1 (1980) 345–370. · Zbl 0461.65052 · doi:10.1137/0901025 |
| [11] | W. Murray and M.L. Overton, ”A projected Lagrangian algorithm for nonlinearL 1 optimization”,SIAM Journal on Scientific and Statistical Computing 2 (1981) 207–224. · Zbl 0468.65036 · doi:10.1137/0902018 |
| [12] | J. Nocedal and M. Overton, ”Projected Hessian updating algorithms for nonlinear constrained optimization”, Report 59, Computer Science Department, New York University (November, 1983). · Zbl 0593.65043 |
| [13] | M.J.D. Powell, ”A new algorithm for unconstrained optimization”, in: J.B. Rosen, O.L. Mangasarian and K. Ritter, eds.,Nonlinear programming (Academic Press, New York, 1970). · Zbl 0228.90043 |
| [14] | 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 2 (Academic Press, New York, 1975). · Zbl 0321.90045 |
| [15] | Y. Yuan, ”Some properties of trust region algorithms for nonsmooth optimization”, Report DAMTP 1983/NA4, University of Cambridge. |
| [16] | Y. Yuan, ”An example of only linear convergence of trust region algorithms for nonsmooth optimization”,IMA Journal of Numerical Analysis 4 (1984) 327–335. · Zbl 0555.65037 · doi:10.1093/imanum/4.3.327 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
