×

On diagonally structured problems in unconstrained optimization using an inexact super Halley method. (English) Zbl 1256.65055

For solving the unconstrained minimization problem an iterative method based on the third-order super Halley method is proposed and it is shown how to approximately solve the two systems of linear equations in the inexact super Halley method so that the method retains local and has third-order rate of convergence, thereby making it possible to use iterative methods for solving the linear systems.
This paper introduces an array of arrays (jagged) data structure for storing the second and third derivative of a multivariate function and suitable termination criteria for the (inner) iterative method to achieve a cubic rate of convergence.
Further it is shown that the second derivative is diagonally structured, the third derivative also exhibits a diagonal structure which can be utilized in computing with the third-order derivative. It is proved by examples that the exploitation of an a jagged compressed diagonal storage of the Hessian matrices and for the tensor is more efficient than the row or column oriented approach when one uses an iterative method for solving the systems of linear equations since matrix vector products can be implemented very efficiently for diagonally structured matrices.

MSC:

65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
65H10 Numerical computation of solutions to systems of equations
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gutiérrez, J. M.; Hernández, M. A., A family of Chebyshev-Halley type methods in Banach spaces, Bulletin of the Australian Mathematical Society, 55, 113-130 (1997) · Zbl 0893.47043
[2] Yamamoto, T., Historical developments in convergence analysis for Newton’s and Newton-like methods, Journal of Computational and Applied Mathematics, 124, 1-23 (2000) · Zbl 0965.65079
[3] Yamamoto, T., On the method of tangent hyperbolas on Banach spaces, Journal of Computational and Applied Mathematics, 21, 75-86 (1988) · Zbl 0632.65070
[4] Chen, D.; Argyros, I. K.; Qian, Q., A local convergence theorem for the super-Halley method in a Banach space, Applied Mathematics Letters, 7, 49-52 (1994) · Zbl 0811.65043
[5] Gutiérrez, J. M.; Hernández, M. A., An acceleration of Newton’s method: super-Halley method, Applied Mathematics and Computation, 117, 223-239 (2001) · Zbl 1023.65051
[6] Gundersen, G.; Steihaug, T., On large scale unconstrained optimization problems and higher order methods, Optimization Methods and Software, 25, 337-358 (2010) · Zbl 1202.65074
[7] Schwetlick, H., Numerische Lösung nichtlinearer Gleichungen (1979), R. Oldenbourg Verlag: R. Oldenbourg Verlag München-Wien · Zbl 0402.65028
[8] Zhang, H., On the Halley class of methods for unconstrained optimization problems, Optimization Methods and Software, 25, 753-762 (2010) · Zbl 1203.90154
[9] G. Gundersen, T. Steihaug, Sparsity in higher-order methods for unconstrained optimization, Optimization Methods and Software (2011) in press (doi:10.1080/10556788.2011.597853; G. Gundersen, T. Steihaug, Sparsity in higher-order methods for unconstrained optimization, Optimization Methods and Software (2011) in press (doi:10.1080/10556788.2011.597853 · Zbl 1244.90220
[10] Deng, N.; Zhang, H., Theoretical efficiency of a new inexact method of tangent hyperbolas, Optimization Methods and Software, 19, 247-265 (2004) · Zbl 1141.90540
[11] H. Zhang, Q. Cheng, Y. Xue, N. Deng, An efficient version of an improved method of tangent hyperbolas, in: K. Li, M. Fei, G.W. Irwin, S. Ma (Eds.), Bio-Inspired Computational Intelligence and Applications, International Conference on Life System Modeling and Simulation, LSMS 2007, in: Lecture Notes in Computer Science, vol. 4688, pp. 205-214.; H. Zhang, Q. Cheng, Y. Xue, N. Deng, An efficient version of an improved method of tangent hyperbolas, in: K. Li, M. Fei, G.W. Irwin, S. Ma (Eds.), Bio-Inspired Computational Intelligence and Applications, International Conference on Life System Modeling and Simulation, LSMS 2007, in: Lecture Notes in Computer Science, vol. 4688, pp. 205-214.
[12] Yan, G.; Tian, X., An inexact Halley’s method, Journal of Beijing Institute of Technology, 3, 340-343 (2005) · Zbl 1084.65065
[13] T. Steihaug, S. Suleiman, Rate of convergence of higher order methods, Applied Numerical Mathematics (2011) in press (doi:10.1016/j.apnum.2011.06.016; T. Steihaug, S. Suleiman, Rate of convergence of higher order methods, Applied Numerical Mathematics (2011) in press (doi:10.1016/j.apnum.2011.06.016 · Zbl 1281.65080
[14] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia, PA, USA · Zbl 1002.65042
[15] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins Press: Johns Hopkins Press Baltimore, MD · Zbl 0865.65009
[16] Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM Journal on Numerical Analysis, 19, 400-408 (1982) · Zbl 0478.65030
[17] Dembo, R. S.; Steihaug, T., Truncated-Newton algorithms for large-scale unconstrained optimization, Mathematical Programming, 26, 190-212 (1983) · Zbl 0523.90078
[18] Griewank, A.; Toint, P. L., On the unconstrained optimization of partially separable functions, (Powell, M. D., Nonlinear Optimization, 1981 (1982), Academic Press), 247-265
[19] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J. J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia, PA
[20] Y. Saad, SPARSKIT: A Basic Tool Kit for Sparse Matrix Computations, Technical Report, University of Minnesota, Department of Computer Science and Engineering, Minneapolis, MN, 55455, 1994.; Y. Saad, SPARSKIT: A Basic Tool Kit for Sparse Matrix Computations, Technical Report, University of Minnesota, Department of Computer Science and Engineering, Minneapolis, MN, 55455, 1994.
[21] Melhem, R. G., Parallel solution of linear systems with striped sparse matrices, Parallel Computing, 6, 165-184 (1988) · Zbl 0643.65016
[22] G. Gundersen, T. Steihaug, On computing with general sparse third derivatives in unconstrained optimization, in: NIK’2006: Norsk Informatikkonferanse, 2006, pp. 53-64.; G. Gundersen, T. Steihaug, On computing with general sparse third derivatives in unconstrained optimization, in: NIK’2006: Norsk Informatikkonferanse, 2006, pp. 53-64.
[23] G. Gundersen, Sparsity in Higher-Order Methods for Unconstrained Optimization, Ph.D. Thesis, Department of Informatics, University of Bergen, Norway, Institutt for informatikk, Universitetet i Bergen, Box 7803, N-5020 Bergen, 2008, ISBN 9729961506.; G. Gundersen, Sparsity in Higher-Order Methods for Unconstrained Optimization, Ph.D. Thesis, Department of Informatics, University of Bergen, Norway, Institutt for informatikk, Universitetet i Bergen, Box 7803, N-5020 Bergen, 2008, ISBN 9729961506. · Zbl 1244.90220
[24] Toint, P. L., Some numerical results using a sparse matrix updating formula in unconstrained optimization, Mathematics of Computation, 32, 839-851 (1978) · Zbl 0381.65036
[25] Conn, A. R.; Gould, N. I.M.; Toint, P. L., An introduction to the structure of large scale nonlinear optimization problems and the LANCELOT project, (Glowinski, R.; Lichnewsky, A., Computing Methods in Applied Sciences and Engineering (1990), SIAM: SIAM Philadelphia, PA), 42-51
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.