×

zbMATH — the first resource for mathematics

A class of approximate inverse preconditioners based on Krylov-subspace methods for large-scale nonconvex optimization. (English) Zbl 07236495
MSC:
90C26 Nonconvex programming, global optimization
90C06 Large-scale problems in mathematical programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Al-baali, Extra updates for the BFGS method, Optim. Methods Softw., 13 (2000), pp. 157-179. · Zbl 0957.90115
[2] M. Al-Baali, A. Caliciotti, G. Fasano, and M. Roma, Exploiting damped techniques for nonlinear conjugate gradient methods, Math. Methods Oper. Res., 86 (2017), pp. 501-522. · Zbl 1390.90388
[3] J. Baglama, D. Calvetti, G. Golub, and L. Reichel, Adaptively preconditioned GMRES algorithms, SIAM J. Sci. Comput., 20 (1998), pp. 243-269. · Zbl 0954.65026
[4] S. Bellavia, J. Gondzio, and B. Morini, A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems, SIAM J. Sci. Comput., 35 (2013), pp. A192-A211. · Zbl 1264.65036
[5] M. Benzi, Preconditioning techniques for large linear systems: A survey, J. Comput. Phys., 182 (2002), pp. 418-477. · Zbl 1015.65018
[6] M. Benzi, J. Cullum, and M. Tu̇ma, Robust approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 22 (2000), pp. 1318-1332. · Zbl 0985.65035
[7] L. Bergamaschi, V. De Simone, D. di Serafino, and A. Martinez, BFGS-like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming, Numer. Linear Algebra Appl., 25 (2018), pp. 1-19. · Zbl 06986987
[8] D. Bernstein, Matrix Mathematics, 2nd ed., Princeton University Press, Princeton, NJ, 2009. · Zbl 1183.15001
[9] D. Bertaccini and F. Durastante, Limited memory block preconditioners for fast solution of fractional partial differential equations, J. Sci. Comput., 77 (2018), pp. 950-970. · Zbl 1404.65014
[10] D. Bertaccini and S. Filippone, Sparse approximate inverse preconditioners on high performance GPU platforms, Comput. Math. Appl., 71 (2016), pp. 693-711. · Zbl 1359.65041
[11] L. Bottou, F. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Rev., 60 (2018), pp. 223-311. · Zbl 1397.65085
[12] J. Bunch, Partial pivoting strategies for symmetric matrices, SIAM J. Numer. Anal., 11 (1974), pp. 521-528. · Zbl 0253.65024
[13] J. Bunch and L. Kaufman, Some stable methods for calculating inertia and solving symmetric linear equations, Math. Comput., 31 (1977), pp. 163-179. · Zbl 0355.65023
[14] J. Bunch and R. Marcia, A pivoting strategy for symmetric tridiagonal matrices, Numer. Linear Algebra Appl., 12 (2005), pp. 911-922. · Zbl 1164.65331
[15] J. Bunch and R. Marcia, A simplified pivoting strategy for symmetric tridiagonal systems, Numer. Linear Algebra Appl., 13 (2006), pp. 865-867. · Zbl 1174.65348
[16] R. Byrd, R. Schnabel, and G. Shultz, Parallel quasi-Newton methods for unconstrained optimization, Math. Program., 42 (1988), pp. 273-306. · Zbl 0665.90085
[17] A. Caliciotti, G. Fasano, S. G. Nash, and M. Roma, An adaptive truncation criterion, for linesearch-based truncated Newton methods in large scale nonconvex optimization, Oper. Res. Lett., 46 (2018), pp. 7-12. · Zbl 07064413
[18] A. Caliciotti, G. Fasano, S. G. Nash, and M. Roma, Data and performance profiles applying an adaptive truncation criterion, within linesearch-based truncated Newton methods, in large scale nonconvex optimization, Data in Brief, 17 (2018), pp. 246-255. · Zbl 07064413
[19] R. Chandra, Conjugate Gradient Methods for Partial Differential Equations, Ph.D thesis, Yale University, New Haven, CT, 1978.
[20] S.-C. Choi, Iterative Methods for Singular Linear Equations and Least-Squares Problems, Ph.D thesis, Stanford University, Stanford, CA, 2006.
[21] S.-C. Choi, C. Paige, and M. Saunders, MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput., 33 (2011), pp. 1810-1836. · Zbl 1230.65050
[22] A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust-Region Methods, MOS-SIAM Ser. Optim., SIAM, Philadelphia, PA, 2000.
[23] V. De Simone and D. di Serafino, A matrix-free approach to build band preconditioners for large-scale bound-constrained optimization, J. Comput. Appl. Math., 268 (2014), pp. 82-92. · Zbl 1293.65042
[24] E. D. Dolan and J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201-213. · Zbl 1049.90004
[25] I. Duff, R. Grimes, and J. Lewis, Sparse matrix test problems, ACM Trans. Math. Software, 15 (1989), pp. 1-14. · Zbl 0667.65040
[26] J. Duintjer Tebbens and M. Tu̇ma, Efficient preconditioning of sequences of nonsymmetric linear systems, SIAM J. Sci. Comput., 29(5) (2007), pp. 1918-1941. · Zbl 1155.65036
[27] J. Duintjer Tebbens and M. Tu̇ma, Preconditioner updates for solving sequences of linear systems in matrix-free environment, Numer. Linear Algebra Appl., 17 (2010), pp. 997-1019. · Zbl 1240.65092
[28] G. Fasano, A CG-type method for the solution of Newton’s equation within optimization frameworks, Optim. Methods Softw., 19 (2004), pp. 267-290. · Zbl 1141.90541
[29] G. Fasano, Planar-conjugate gradient algorithm for large-scale unconstrained optimization, Part 1: Theory, J. Optim. Theory Appl., 125 (2005), pp. 523-541. · Zbl 1079.90162
[30] G. Fasano, Planar-conjugate gradient algorithm for large-scale unconstrained optimization, Part 2: Application, J. Optim. Theory Appl., 125 (2005), pp. 543-558. · Zbl 1079.90163
[31] G. Fasano and M. Roma, A Class of Preconditioners for Large Indefinite Linear Systems, as By-Product of Krylov Subspace Methods: Part I, Technical Report 4/2011, Dipartimento di Management, Università Ca’ Foscari, Venezia, 2011.
[32] G. Fasano and M. Roma, A Class of Preconditioners for Large Indefinite Linear Systems, as By-Product of Krylov Subspace Methods: Part II, Technical Report 5/2011, Dipartimento di Management, Università Ca’ Foscari, Venezia, 2011.
[33] G. Fasano and M. Roma, Preconditioning Newton-Krylov methods in nonconvex large scale optimization, Comput. Optim. Appl., 56 (2013), pp. 253-290. · Zbl 1314.90063
[34] G. Fasano and M. Roma, A novel class of approximate inverse preconditioners for large positive definite linear systems in optimization, Comput. Optim. Appl., 65 (2016), pp. 399-429. · Zbl 1369.90166
[35] P. E. Gill, W. Murray, D. B. Ponceleon, and M. A. Saunders, Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 292-311. · Zbl 0749.65037
[36] L. Giraud, S. Gratton, and E. Martin, incremental spectral preconditioners for sequences of linear systems, Appl. Numer. Math., 57 (2007), pp. 1164-1180. · Zbl 1123.65031
[37] G. Golub and C. Van Loan, Matrix Computations, 4th ed., The John Hopkins Press, Baltimore, MD, 2013. · Zbl 1268.65037
[38] N. I. M. Gould, D. Orban, and P. L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads, Comput. Optim. Appl., 60 (2015), pp. 545-557. · Zbl 1325.90004
[39] S. Gratton, S. Mercier, N. Tardieu, and X. Vasseur, Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics, Numer. Linear Algebra Appl., 23 (2016), pp. 865-887. · Zbl 1413.65041
[40] S. Gratton, A. Sartenaer, and J. Tshimanga, On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides, SIAM J. Optim., 21 (2011), pp. 912-935. · Zbl 1273.65044
[41] A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, Philadelphia, PA, 1997. · Zbl 0883.65022
[42] N. Higham, Stability of block \(LDL^T\) factorization of a symmetric tridiagonal matrix, Numer. Linear Algebra Appl., 287 (1999), pp. 181-189. · Zbl 0941.65030
[43] N. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, PA, 2002. · Zbl 1011.65010
[44] R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1999.
[45] C.-Y. Hsia, W.-L. Chiang, and C.-J. Lin, Preconditioned conjugate gradient methods in truncated Newton frameworks for large-scale linear classification, in Proceedings of Machine Learning Research, J. Zhu and I. Takeuchi, eds., Asian Conference on Machine Learning, 2018, pp. 1-15.
[46] The HSL Mathematical Software Library, http://www.hsl.rl.ac.uk/.
[47] L. Lukšan and J. Vlček, Efficient tridiagonal preconditioner for the matrix-free truncated Newton method, Appl. Math. Comput., 235 (2014), pp. 394-407. · Zbl 1334.65113
[48] R. Marcia, On solving sparse symmetric linear systems whose definiteness is unknown, Appl. Numer. Math., 58 (2008), pp. 449-458. · Zbl 1350.65040
[49] S. Mercier, S. Gratton, N. Tardieu, and X. Vasseur, A new preconditioner update startegy for the solution of sequences of linear systems in structural mechanics: Application to saddle point problems in elasticity, Comput. Mech., 60 (2017), pp. 969-982. · Zbl 1398.65047
[50] J. Morales and J. Nocedal, Automatic preconditioning by limited memory quasi-Newton updating, SIAM J. Optim., 10 (2000), pp. 1079-1096. · Zbl 1020.65019
[51] J. L. Morales and J. Nocedal, Algorithm preqn: Fortran 77 subroutine for preconditioning the conjugate gradient method, ACM Trans. Math. Software, 27 (2001), pp. 83-91. · Zbl 1070.65538
[52] S. Nash, Preconditioning of truncated-Newton methods, SIAM J. Sci. Stat. Comp., 6 (1985), pp. 599-616. · Zbl 0592.65038
[53] S. Nash, A survey of truncated-Newton methods, J. Comput. Appl. Math., 124 (2000), pp. 45-59. · Zbl 0969.65054
[54] J. Nocedal, Updating Quasi-Newton matrices with limited storage, Math. Comput., 35 (1980), pp. 773-782. · Zbl 0464.65037
[55] J. Nocedal and S. Wright, Numerical Optimization, 2nd ed., Springer-Verlag, New York, 2006. · Zbl 1104.65059
[56] C.C. Paige and M.A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617-629. · Zbl 0319.65025
[57] M. Roma, A dynamic scaling based preconditioning for truncated Newton methods in large scale unconstrained optimization, Optim. Methods Softw., 20 (2005), pp. 693-713. · Zbl 1127.90408
[58] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, PA, 2003. · Zbl 1031.65046
[59] Y. Saad and M. H. Schultz, A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comp., 7 (1986), pp. 856-869. · Zbl 0599.65018
[60] M. A. Saunders, Solution of sparse rectangular systems using LSQR and CRAIG, BIT, 35 (1995), pp. 588-604. · Zbl 0844.65029
[61] J. Sifuentes, M. Ebree, and R. Morgan, GMRES convergence for perturbed coefficient matrices, with application to approximate deflation preconditioning, SIAM J. Matrix Anal. Appl., 34(3) (2013), pp. 1066-1088. · Zbl 1314.65051
[62] J. Stoer, Solution of large linear systems of equations by conjugate gradient type methods, in Mathematical Programming. The State of the Art, A. Bachem, M.Grötschel, and B. Korte, eds., Springer-Verlag, Berlin, 1983, pp. 540-565.
[63] L. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, PA, 1997. · Zbl 0874.65013
[64] H. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, UK, 2003. · Zbl 1023.65027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.