×

zbMATH — the first resource for mathematics

Iterative Grossone-based computation of negative curvature directions in large-scale optimization. (English) Zbl 1450.90009
Summary: We consider an iterative computation of negative curvature directions, in large-scale unconstrained optimization frameworks, needed for ensuring the convergence toward stationary points which satisfy second-order necessary optimality conditions. We show that to the latter purpose, we can fruitfully couple the conjugate gradient (CG) method with a recently introduced approach involving the use of the numeral called Grossone. In particular, recalling that in principle the CG method is well posed only when solving positive definite linear systems, our proposal exploits the use of grossone to enhance the performance of the CG, allowing the computation of negative curvature directions in the indefinite case, too. Our overall method could be used to significantly generalize the theory in state-of-the-art literature. Moreover, it straightforwardly allows the solution of Newton’s equation in optimization frameworks, even in nonconvex problems. We remark that our iterative procedure to compute a negative curvature direction does not require the storage of any matrix, simply needing to store a couple of vectors. This definitely represents an advance with respect to current results in the literature.

MSC:
90C06 Large-scale problems in mathematical programming
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
Software:
CUTEst; HSL; tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ferris, M.; Lucidi, S.; Roma, M., Nonmonotone curvilinear line search methods for unconstrained optimization, Comput. Optim. Appl., 6, 117-136 (1996) · Zbl 0860.90111
[2] Goldfarb, D., Curvilinear path steplength algorithms for minimization which use directions of negative curvature, Math. Program., 18, 1, 31-40 (1980) · Zbl 0428.90068
[3] Gould, NIM; Lucidi, S.; Roma, M.; Toint, PL, Exploiting negative curvature directions in linesearch methods for unconstrained optimization, Optim. Methods Softw., 14, 75-98 (2000) · Zbl 0988.90039
[4] Goldfarb, D.; Mu, C.; Wright, J.; Zhou, C., Using negative curvature in solving nonlinear programs, Comput. Optim. Appl., 68, 3, 479-502 (2017) · Zbl 1393.90114
[5] Lucidi, S.; Rochetich, F.; Roma, M., Curvilinear stabilization techniques for truncated Newton methods in large-scale unconstrained optimization, SIAM J. Optim., 8, 916-939 (1998) · Zbl 0912.90259
[6] McCormick, GP, A modification of Armijo’s step-size rule for negative curvature, Math. Program., 13, 1, 111-115 (1977) · Zbl 0367.90100
[7] Moré, J.; Sorensen, D., On the use of directions of negative curvature in a modified Newton method, Math. Program., 16, 1-20 (1979) · Zbl 0394.90093
[8] Curtis, F.; Robinson, D., Exploiting negative curvature in deterministic and stochastic optimization, Math. Program., 176, 69-94 (2019) · Zbl 1417.49036
[9] Fasano, G.; Roma, M., Iterative computation of negative curvature directions in large scale optimization, Comput. Optim. Appl., 38, 1, 81-104 (2007) · Zbl 1171.90549
[10] Fasano, G.; Lucidi, S., A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization, Optim. Lett., 3, 4, 521-535 (2009) · Zbl 1180.90192
[11] Hestenes, MR; Stiefel, EL, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[12] De Leone, R.; Fasano, G.; Sergeyev, YD, Planar methods and grossone for the conjugate gradient breakdown in nonlinear programming, Comput. Optim. Appl., 71, 73-93 (2018) · Zbl 06946577
[13] Sergeyev, YD, Numerical infinities and infinitesimals: methodology, applications, and repercussions on two Hilbert problems, EMS Surv. Math. Sci., 4, 2, 219-320 (2017) · Zbl 1390.03048
[14] Fasano, G., Conjugate gradient (CG)-type method for the solution of Newton’s equation within optimization frameworks, Optim. Methods Softw., 19, 3-4, 267-290 (2004) · Zbl 1141.90541
[15] Lolli, G., Metamathematical investigations on the theory of grossone, Appl. Math. Comput., 255, 3-14 (2015) · Zbl 1338.03118
[16] Margenstern, M., Using Grossone to count the number of elements of infinite sets and the connection with bijections, p-Adic Numbers Ultrametric Anal. Appl., 3, 3, 196-204 (2011) · Zbl 1259.03064
[17] Montagna, F.; Simi, G.; Sorbi, A., Taking the Pirahã seriously, Commun. Nonlinear Sci. Numer. Simul., 21, 1-3, 52-69 (2015) · Zbl 1401.03110
[18] Sergeyev, Y.D.: Computer system for storing infinite, infinitesimal, and finite quantities and executing arithmetical operations with them. USA patent 7,860,914 (2010)
[19] Cococcioni, M.; Cudazzo, A.; Pappalardo, M.; Sergeyev, YD, Solving the lexicographic multi-objective mixed-integer linear programming problem using branch-and-bound and Grossone methodology, Commun. Nonlinear Sci. Numer. Simul., 84, 105177 (2020)
[20] Cococcioni, M.; Pappalardo, M.; Sergeyev, YD, Lexicographic multi-objective linear programming using grossone methodology: theory and algorithm, Appl. Math. Comput., 318, 298-311 (2018) · Zbl 1426.90226
[21] De Cosmis, S.; Leone, RD, The use of grossone in mathematical programming and operations research, Appl. Math. Comput., 218, 16, 8029-8038 (2012) · Zbl 1273.90117
[22] De Leone, R., Nonlinear programming and grossone: quadratic programming and the role of constraint qualifications, Appl. Math. Comput., 318, 290-297 (2018) · Zbl 1426.90235
[23] Gaudioso, M.; Giallombardo, G.; Mukhametzhanov, MS, Numerical infinitesimals in a variable metric method for convex nonsmooth optimization, Appl. Math. Comput., 318, 312-320 (2018) · Zbl 1426.90197
[24] Sergeyev, YD; Kvasov, DE; Mukhametzhanov, MS, On strong homogeneity of a class of global optimization algorithms working with infinite and infinitesimal scales, Commun. Nonlinear Sci. Numer. Simul., 59, 319-330 (2018)
[25] Caldarola, F., The Sierpinski curve viewed by numerical computations with infinities and infinitesimals, Appl. Math. Comput., 318, 321-328 (2018) · Zbl 1426.28016
[26] Sergeyev, YD, Numerical point of view on Calculus for functions assuming finite, infinite, and infinitesimal values over finite, infinite, and infinitesimal domains, Nonlinear Anal. Ser. A Theory Methods Appl., 71, 12, e1688-e1707 (2009) · Zbl 1238.28013
[27] Sergeyev, Y.D.: Numerical infinities applied for studying Riemann series theorem and Ramanujan summation. In: AIP Conference Proceedings of ICNAAM 2017, vol. 1978, p. 020004. AIP Publishing, New York (2018). 10.1063/1.5043649
[28] Zhigljavsky, A., Computing sums of conditionally convergent and divergent series using the concept of grossone, Appl. Math. Comput., 218, 16, 8064-8076 (2012) · Zbl 1254.03123
[29] Caldarola, F., The exact measures of the Sierpinski d-dimensional tetrahedron in connection with a diophantine nonlinear system, Commun. Nonlinear Sci. Numer. Simul., 63, 228-238 (2018)
[30] D’Alotto, L., A classification of two-dimensional cellular automata using infinite computations, Indian J. Math., 55, 143-158 (2013) · Zbl 1371.37017
[31] Sergeyev, YD, Evaluating the exact infinitesimal values of area of Sierpinski’s carpet and volume of Menger’s sponge, Chaos Solitons Fractals, 42, 5, 3042-3046 (2009)
[32] Falcone, A., Garro, A., Mukhametzhanov, M.S., Sergeyev, Y.D.: A simulink-based infinity computer simulator and some applications. Lecture Notes in Computer Science 11974 LNCS, pp. 362-369 (2020). 10.1007/978-3-030-40616-5_31
[33] Iudin, DI; Sergeyev, YD; Hayakawa, M., Infinity computations in cellular automaton forest-fire model, Commun. Nonlinear Sci. Numer. Simul., 20, 3, 861-870 (2015)
[34] Margenstern, M., Fibonacci words, hyperbolic tilings and grossone, Commun. Nonlinear Sci. Numer. Simul., 21, 1-3, 3-11 (2015) · Zbl 1329.37012
[35] Sergeyev, YD, Counting systems and the First Hilbert problem, Nonlinear Anal. Ser. A Theory Methods Appl., 72, 3-4, 1701-1708 (2010) · Zbl 1191.03038
[36] Sergeyev, YD; Garro, A., Single-tape and multi-tape Turing machines through the lens of the Grossone methodology, J. Supercomput., 65, 2, 645-663 (2013)
[37] Fiaschi, L.; Cococcioni, M., Numerical asymptotic results in game theory using Sergeyev’s Infinity Computing, Int. J. Unconv. Comput., 14, 1, 1-25 (2018)
[38] Rizza, D., A study of mathematical determination through Bertrand’s Paradox, Philosophia Mathematica, 26, 3, 375-395 (2018) · Zbl 1423.60008
[39] Rizza, D., Numerical methods for infinite decision-making processes, Int. J. Unconv. Comput., 14, 2, 139-158 (2019)
[40] Amodio, P.; Iavernaro, F.; Mazzia, F.; Mukhametzhanov, M.; Sergeyev, YD, A generalized Taylor method of order three for the solution of initial value problems in standard and infinity floating-point arithmetic, Math. Comput. Simul., 141, 24-39 (2017)
[41] Sergeyev, YD, Higher order numerical differentiation on the Infinity Computer, Optim. Lett., 5, 4, 575-585 (2011) · Zbl 1230.65028
[42] Iavernaro, F.; Mazzia, F.; Mukhametzhanov, MS; Sergeyev, YD, Conjugate-symplecticity properties of Euler-Maclaurin methods and their implementation on the Infinity Computer, Appl. Numer. Math., 155, 58-72 (2020) · Zbl 1440.65273
[43] Sergeyev, YD; Mukhametzhanov, MS; Mazzia, F.; Iavernaro, F.; Amodio, P., Numerical methods for solving initial value problems on the Infinity Computer, Int. J. Unconv. Comput., 12, 1, 3-23 (2016)
[44] Sergeyev, YD, Independence of the grossone-based infinity methodology from non-standard analysis and comments upon logical fallacies in some texts asserting the opposite, Found. Sci., 24, 1, 153-170 (2019) · Zbl 1428.03076
[45] Golub, GH; Loan, CFV, Matrix Computations (2013), Baltimore: The Johns Hopkins University Press, Baltimore
[46] Paige, C.; Saunders, M., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-29 (1975) · Zbl 0319.65025
[47] HSL_MI02 Symmetric possibly-indefinite system: SYMMBK method. Harwell Mathematical Software Library http://www.hsl.rl.ac.uk (2013)
[48] Fasano, G., Planar-conjugate gradient algorithm for large scale unconstrained optimization, part 1: theory, J. Optim. Theory Appl., 125, 3, 523-541 (2005) · Zbl 1079.90162
[49] Fasano, G., Planar-conjugate gradient algorithm for large scale unconstrained optimization, part 2: application, J. Optim. Theory Appl., 125, 3, 543-558 (2005) · Zbl 1079.90163
[50] Fasano, G., Lanczos-conjugate gradient method and pseudoinverse computation, on indefinite and singular systems, J. Optim. Theory Appl., 132, 2, 267-285 (2007) · Zbl 1151.65023
[51] Nash, SG, A survey of truncated-Newton methods, J. Comput. Appl. Math., 124, 45-59 (2000) · Zbl 0969.65054
[52] Fasano, G.; Di Pillo, G.; Murli, A., Planar-CG methods and matrix tridiagonalization in large scale unconstrained optimization, High Performance Algorithms and Software for Nonlinear Optimization, 243-263 (2003), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1065.90073
[53] Fasano, G.; Pesenti, R., Conjugate direction methods and polarity for quadratic hypersurfaces, J. Optim. Theory Appl., 175, 764-794 (2017) · Zbl 1387.90240
[54] Gould, NIM; Orban, D.; Toint, PL, CUTEst: a constrained and unconstrained testing environment with safe threads, Comput. Optim. Appl., 60, 545-557 (2015) · Zbl 1325.90004
[55] Dolan, ED; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[56] Žilinskas, A.; Gillard, J.; Scammell, M.; Zhigljavsky, A., Multistart with early termination of descents, J. Global Optim. (2019)
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.