×

zbMATH — the first resource for mathematics

Iterative computation of negative curvature directions in large scale optimization. (English) Zbl 1171.90549
Summary: In this paper we deal with the iterative computation of negative curvature directions of an objective function, within large scale optimization frameworks. In particular, suitable directions of negative curvature of the objective function represent an essential tool, to guarantee convergence to second order critical points. However, an “adequate” negative curvature direction is often required to have a good resemblance to an eigenvector corresponding to the smallest eigenvalue of the Hessian matrix. Thus, its computation may be a very difficult task on large scale problems. Several strategies proposed in literature compute such a direction relying on matrix factorizations, so that they may be inefficient or even impracticable in a large scale setting. On the other hand, the iterative methods proposed either need to store a large matrix, or they need to rerun the recurrence. On this guideline, in this paper we propose the use of an iterative method, based on a planar Conjugate Gradient scheme. Under mild assumptions, we provide theory for using the latter method to compute adequate negative curvature directions, within optimization frameworks. In our proposal any matrix storage is avoided, along with any additional rerun.

MSC:
90C52 Methods of reduced gradient type
60K10 Applications of renewal theory (reliability, demand theory, etc.)
Software:
SifDec; GQTPAR; HSL-VF05; CUTEr; tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bank, R., Chan, T.: A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems. Numer. Algorithms 7, 1–16 (1994) · Zbl 0809.65025
[2] Boman, E., Murray, W.: An iterative approach to computing a direction of negative curvature. Presented at Copper Mountain conference, March 1998. Available at the url: www-sccm.stanford.edu/students/boman/papers.shtml
[3] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS–SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[4] Cullum, J., Willoughby, R.: Lanczos Algorithms for Large Symmetric Eigenvalue Computations. Birkhäuser, Boston (1985) · Zbl 0574.65028
[5] Dixon, L., Ducksbury, P., Singh, P.: A new three-term conjugate gradient method. Technical report 130, Numerical Optimization Centre, Hatfield Polytechnic, Hatfield, Hertfordshire, UK (1985) · Zbl 0556.90077
[6] Facchinei, F., Lucidi, S.: Convergence to second order stationary points in inequality constrained optimization. Math. Oper. Res. 93, 746–766 (1998) · Zbl 0977.90049
[7] Fasano, G.: Use of conjugate directions inside Newton-type algorithms for large scale unconstrained optimization. PhD thesis, Università di Roma ”La Sapienza”, Roma, Italy (2001) · Zbl 1053.90527
[8] Fasano, G.: Lanczos-conjugate gradient method and pseudoinverse computation, on indefinite and singular systems. J. Optim. Theory Appl. DOI 10.1007/s10957-006-91193
[9] Fasano, G.: Planar-conjugate gradient algorithm for large-scale unconstrained optimization, part 1: theory. J. Optim. Theory Appl. 125, 523–541 (2005) · Zbl 1079.90162
[10] Fasano, G.: Planar-conjugate gradient algorithm for large-scale unconstrained optimization, part 2: application. J. Optim. Theory Appl. 125, 543–558 (2005) · Zbl 1079.90163
[11] Fasano, G., Roma, M.: Iterative computation of negative curvature directions in large scale optimization: theory and preliminary numerical results, Technical report 12-05, Dipartimento di Informatica e Sistemistica ”A. Ruberti”, Roma, Italy (2005) · Zbl 1171.90549
[12] Ferris, M., Lucidi, S., Roma, M.: Nonmonotone curvilinear linesearch methods for unconstrained optimization. Comput. Optim. Appl. 6, 117–136 (1996) · Zbl 0860.90111
[13] Golub, G., Van Loan, C.: Matrix Computations, 3rd edn. John Hopkins University Press, Baltimore (1996). · Zbl 0865.65009
[14] Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9, 504–525 (1999) · Zbl 1047.90510
[15] Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optim. Methods Softw. 14, 75–98 (2000) · Zbl 0988.90039
[16] Gould, N.I.M., Orban, D., Toint, P.: \(\mathsf{CUTEr}\) (and \(\mathsf{SifDec}\) ), a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29, 373–394 (2003) · Zbl 1068.90526
[17] Hestenes, M.: Conjugate Direction Methods in Optimization. Springer, New York (1980) · Zbl 0439.49001
[18] Liu, Y., Storey, C.: Efficient generalized conjugate gradient algorithm, part 1. J. Optim. Theory Appl. 69, 129–137 (1991) · Zbl 0724.90067
[19] 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
[20] Lucidi, S., Roma, M.: Numerical experiences with new truncated Newton methods in large scale unconstrained optimization. Comput. Optim. Appl. 7, 71–87 (1997) · Zbl 0893.90154
[21] McCormick, G.: A modification of Armijo’s step-size rule for negative curvature. Math. Program. 13, 111–115 (1977) · Zbl 0367.90100
[22] Miele, A., Cantrell, J.: Study on a memory gradient method for the minimization of functions. J. Optim. Theory Appl. 3, 459–470 (1969) · Zbl 0165.22702
[23] 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
[24] Moré, J., Sorensen, D.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983) · Zbl 0551.65042
[25] Nash, S.: A survey of truncated-Newton methods. J. Comput. Appl. Math. 124, 45–59 (2000) · Zbl 0969.65054
[26] Paige, C., Saunders, M.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12, 617–629 (1975) · Zbl 0319.65025
[27] Parlett, B.: The Symmetric Eigenvalue Problem. Prentice-Hall Series in Computational Mathematics. Prentice-Hall, Englewood Cliffs (1980)
[28] Shultz, G., Schnabel, R., Byrd, R.: A family of trust-region-based algorithms for unconstrained minimization. SIAM J. Numer. Anal. 22, 47–67 (1985) · Zbl 0574.65061
[29] Stoer, J.: Solution of large linear systems of equations by conjugate gradient type methods. In: Bachem A., Grötschel M., Korte B. (eds.) Mathematical Programming. The State of the Art, pp. 540–565. Springer, Berlin/Heidelberg (1983)
[30] Trefethen, L., Bau, D.: Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0874.65013
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.