Nonmonotone curvilinear line search methods for unconstrained optimization. (English) Zbl 0860.90111
Summary: We present a new algorithmic framework for solving unconstrained minimization problems that incorporates a curvilinear linesearch. The search direction used in our framework is a combination of an approximate Newton direction and a direction of negative curvature. Global convergence to a stationary point where the Hessian matrix is positive semidefinite is exhibited for this class of algorithms by means of a nonmonotone stabilization strategy. An implementation using the Bunch-Parlett decomposition is shown to outperform several other techniques on a large class of test problems.
MSC:
| 90C30 | Nonlinear programming |
Keywords:
global convergence; unconstrained minimization; curvilinear linesearch; approximate Newton direction; nonmonotone stabilization strategyReferences:
| [1] | M. Arioli, T.F. Chan, I.S. Duff, N.I.M. Gould, and J.K. Reid, ”Computing a search direction for large-scale linearly-constrained nonlinear optimization calculations,” Technical Report TR/PA/93/34, CERFACS, 1993. |
| [2] | I. Bongartz, A.R. Conn, N. Gould, and Ph.L. Toint, ”CUTE: Constrained and unconstrained testing environment,” Publications du Départment de Mathématique Report 93/10, Facultés Universitaires De Namur, 1993. To appear in ACM Trans. Math. Soft. · Zbl 0886.65058 |
| [3] | J.R. Bunch and B.N. Parlett, ”Direct methods for solving symmetric indefinite systems of linear equations,” SIAM Journal on Numerical Analysis, vol. 8, pp. 639–655, 1971. · doi:10.1137/0708060 |
| [4] | A.R. Conn, N.I.M. Gould, and Ph.L. Toint, ”LANCELOT: A fortran package for large-scale nonlinear optimization (Release A),” Number 17 in Springer Series in Computational Mathematics, Springer Verlag, Heidelberg, Berlin, 1992. · Zbl 0761.90087 |
| [5] | R.S. Dembo and T. Steihaug, ”Truncated Newton method algorithms for large-scale unconstrained optimization,” Mathematical Programming, vol. 26, pp. 190–212, 1983. · Zbl 0523.90078 · doi:10.1007/BF02592055 |
| [6] | N.Y. Deng, Y. Xiao, and F.J. Zhou, ”Nonmonotonic trust region algorithm,” Journal of Optimization Theory and Applications, vol. 76, pp. 259–285, 1993. · Zbl 0797.90088 · doi:10.1007/BF00939608 |
| [7] | S.P. Dirkse and M.C. Ferris, ”The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems,” Optimization Methods & Software, vol. 5, pp. 123–156, 1995. · doi:10.1080/10556789508805606 |
| [8] | M.C. Ferris and S. Lucidi, ”Nonmonotone stabilization methods for nonlinear equations,” Journal of Optimization Theory and Applications, vol. 81, pp. 53–74, 1994. · Zbl 0803.65070 · doi:10.1007/BF02190313 |
| [9] | A. Forsgren, P.E. Gill, and W. Murray, ”A modified Newton method for unconstrained optimization,” Technical Report SOL 89–12, Department of Operations Research, Stanford University: Stanford, California, 1989. |
| [10] | A. Forsgren, P.E. Gill, and W. Murray, ”Computing modified Newton directions using a partial Cholesky factorization,” Technical Report TRITA-MAT-1993–9, Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden, 1993. · Zbl 0823.49021 |
| [11] | P.E. Gill, W. Murray, D.B. Poncélon, and M.A. Saunders, ”Preconditioners for indefinite systems arising in optimization,” SIAM Journal on Matrix Analysis and Applications, vol. 13, pp. 292–311, 1992. · Zbl 0749.65037 · doi:10.1137/0613022 |
| [12] | P.E. Gill and W. Murray, ”Newton-type methods for unconstrained and linearly constrained optimization,” Mathematical Programming, vol. 7, pp. 311–350, 1974. · Zbl 0297.90082 · doi:10.1007/BF01585529 |
| [13] | L. Grippo, F. Lampariello, and S. Lucidi, ”A nonmonotone line search technique for Newton’s method,” SIAM Journal on Numerical Analysis, vol. 23, pp. 707–716, 1986. · Zbl 0616.65067 · doi:10.1137/0723046 |
| [14] | L. Grippo, F. Lampariello, and S. Lucidi, ”A class of nonmonotone stabilization methods in unconstrained optimization,” Numerische Mathematik, vol. 59, pp. 779–805, 1991. · doi:10.1007/BF01385810 |
| [15] | G.P. McCormick, ”A modification of Armijo’s step-size rule for negative curvature,” Mathematical Programming, vol. 13, pp. 111–115, 1977. · Zbl 0367.90100 · doi:10.1007/BF01584328 |
| [16] | G.P. McCormick, Nonlinear Programming: Theory, Algorithms and Applications, John Wiley & Sons: New York, 1983. · Zbl 0563.90068 |
| [17] | J.J. Moré and D.C. Sorensen, ”On the use of directions of negative curvature in a modified Newton method,” Mathematical Programming, vol. 16, pp. 1–20, 1979. · Zbl 0394.90093 · doi:10.1007/BF01582091 |
| [18] | S.G. Nash, ”Newton-type minimization via Lanczos method,” SIAM Journal on Numerical Analysis, vol. 21, pp. 770–788, 1984. · Zbl 0558.65041 · doi:10.1137/0721052 |
| [19] | J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press: San Diego, California, 1970. · Zbl 0241.65046 |
| [20] | C.C. Paige and M.A. Saunders, ”Solution of sparse indefinite systems of linear equations,” SIAM Journal on Numerical Analysis, vol. 12, pp. 617–629, 1975. · Zbl 0319.65025 · doi:10.1137/0712047 |
| [21] | T. Schlick, ”Modified Cholesky factorization for sparse preconditioners,” SIAM Journal on Scientific Computing, vol. 14, pp. 424–445, 1993. · Zbl 0771.65031 · doi:10.1137/0914026 |
| [22] | R.B. Schnabel and E. Eskow, ”A new modified Cholesky factorization,” SIAM Journal on Scientific and Statistical Computing, vol. 11, pp. 1136–1158, 1990. · Zbl 0716.65023 · doi:10.1137/0911064 |
| [23] | G.A. Shultz, R.B. Schnabel, and R.H. Byrd, ”A family of trust-region-based algorithms for unconstrained minimization,” SIAM Journal on Numerical Analysis, vol. 22, pp. 44–67, 1985. · Zbl 0574.65061 · doi:10.1137/0722003 |
| [24] | Ph.L. Toint, ”Towards an efficient sparsity exploiting Newton method for minimization,” in I.S. Duff (Ed.), Sparse Matrices and Their Uses, Academic Press: London, pp. 57–88, 1981. · Zbl 0463.65045 |
| [25] | Ph.L. Toint, ”An assesment of non-monotone linesearch techniques for unconstrained optimization,” Technical Report 94/14, Department of Mathematics, FUNDP, Namur, Belgium, 1994. |
| [26] | Ph.L. Toint, ”A non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints,” Technical Report 94/24, Department of Mathematics, FUNDP, Namur, Belgium, 1994. |
| [27] | Y. Xiao and F.J. Zhou, ”Nonmonotone trust region methods with curvilinear path in unconstrained minimization,” Computing, vol. 48, pp. 303–317, 1992. · Zbl 0763.65048 · doi:10.1007/BF02238640 |
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.
