×

Improving directions of negative curvature in an efficient manner. (English) Zbl 1163.90754

Summary: In order to converge to second-order KKT points, second derivative information has to be taken into account. Therefore, methods for minimization satisfying convergence to second-order KKT points must, at least implicitly, compute a direction of negative curvature of an indefinite matrix. An important issue is to determine the quality of the negative curvature direction. This problem is closely related to the symmetric eigenvalue problem. More specifically we want to develop algorithms that improve directions of negative curvature with relatively little effort, extending the proposals by Boman and Murray. This paper presents some technical improvements with respect to their work. In particular, we study how to compute “good” directions of negative curvature. In this regard, we propose a new method and we present numerical experiments that illustrate its practical efficiency compared to other proposals.

MSC:

90C30 Nonlinear programming

Software:

JDQR; JDQZ
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., & van der Vorst, H. (Eds.). (2000). Templates for the solution of algebraic eigenvalue problems: A practical guide. Philadelphia: SIAM. · Zbl 0965.65058
[2] Boman, E. G. (1999). Infeasibility and negative curvature in optimization. Ph.D. Thesis, Stanford University.
[3] Boman, E. G., & Murray, W. (1998). An iterative approach to computing directions of negative curvature. In: Proceedings of the fifth Copper Mountain conference on iterative methods, University of Colorado.
[4] Bunch, J. R., & Parlett, B. N. (1971). Direct methods for solving symmetric indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 8, 639–655. · Zbl 0222.65038 · doi:10.1137/0708060
[5] Bunch, J. R., Kaufman, L., & Parlett, B. N. (1976). Decomposition of a symmetric matrix. Numerical Mathematics, 27, 95–109. · Zbl 0342.65026 · doi:10.1007/BF01399088
[6] Cheng, S. H., & Higham, N. (1998). A modified Cholesky algorithm based on a symmetric indefinite factorization. SIAM Journal on Matrix Analysis Applications, 19, 1097–1110. · Zbl 0949.65022 · doi:10.1137/S0895479896302898
[7] Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). Trust-region methods. SIAM series on optimization. Philadelphia: SIAM. · Zbl 0958.65071
[8] Davidson, E. R. (1975). The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real symmetric matrices. Journal Computational Physics, 17, 87–94. · Zbl 0293.65022 · doi:10.1016/0021-9991(75)90065-0
[9] Doyle, M. (2003). A barrier algorithm for large nonlinear optimization. Ph.D. Thesis, Stanford University.
[10] Fiacco, A. V., & McCormick, G. P. (1990). Nonlinear programming: sequential unconstrained minimization techniques. Philadelphia: Society for Industrial and Applied Mathematics (originally published by Wiley and Sons, New York, 1968). · Zbl 0193.18805
[11] Fletcher, R., & Freeman, T. L. (1977). A modified Newton method for minimization. Journal of Optimization Theory and Applications, 23, 357–372. · Zbl 0348.65058 · doi:10.1007/BF00933446
[12] Forsgren, A., Gill, P. E., & Murray, W. (1995). Computing modified Newton directions using a partial Cholesky factorization. SIAM Journal on Scientific Computing, 16, 139–150. · Zbl 0823.49021 · doi:10.1137/0916009
[13] Gill, P. E., & Murray, W. (1974). Newton type methods for unconstrained and linearly constrained optimization. Mathematical Programming, 7, 311–350. · Zbl 0297.90082 · doi:10.1007/BF01585529
[14] Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical optimization. New York: Academic Press. · Zbl 0503.90062
[15] Goldfarb, D. (1980). Curvilinear path steplength algorithms for minimization which use directions of negative curvature. Mathematical Programming, 18, 31–40. · Zbl 0428.90068 · doi:10.1007/BF01588294
[16] Golub, G., & van Loan, C. (1996). Matrix computations (3rd ed.). London: The John Hopkins University Press. · Zbl 0865.65009
[17] Gould, N. I. M., Lucidi, S., Roma, M., & Toint, P. L. (2000). Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optimization Methods and Software, 14, 75–98. · Zbl 0988.90039 · doi:10.1080/10556780008805794
[18] Hager, W. W., & Zhang, H. (2005). A new conjugate gradient method with guaranteed descent and efficient line search. SIAM Journal on Optimization, 16, 170–192. · Zbl 1093.90085 · doi:10.1137/030601880
[19] Jacobi, C. G. J. (1846). Ueber ein leichtes Verfahrem, die in der Theorie der Säcularstörungen vorkommenden Gleichungen numerisch aufzulösen. Journal on Reine Angewandte Mathematik, 30, 51–94. · ERAM 030.0852cj · doi:10.1515/crll.1846.30.51
[20] Lucidi, S., Rochetich, F., & Roma, M. (1998). Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization. SIAM Journal on Optimization, 8, 916–939. · Zbl 0912.90259 · doi:10.1137/S1052623495295250
[21] McCormick, G. (1977). A modification of Armijo’s step-size rule for negative curvature. Mathematical Programming, 13, 111–115. · Zbl 0367.90100 · doi:10.1007/BF01584328
[22] Moguerza, J. M., & Prieto, F. J. (2003a). An Augmented-Lagrangian interior-point method using directions of negative curvature. Mathematical Programming, 95, 573–616. · Zbl 1041.90071 · doi:10.1007/s10107-002-0360-8
[23] Moguerza, J. M., & Prieto, F. J. (2003b). Combining search directions using gradient flows. Mathematical Programming, 96, 529–559. · Zbl 1049.90126 · doi:10.1007/s10107-002-0367-1
[24] Moré, J. J., & Sorensen, D. C. (1979). On the use of directions of negative curvature in a modified Newton method. Mathematical Programming, 16, 1–20. · Zbl 0394.90093 · doi:10.1007/BF01582091
[25] Mukai, H., & Polak, E. (1978). A second order algorithm for the general nonlinear programming problem. Journal of Optimization Theory and Applications, 4, 26, 515–532. · Zbl 0373.90067 · doi:10.1007/BF00933150
[26] Neumaier, A. (1997). On satisfying second-order optimality conditions using modified Cholesky factorizations (Tech. report). Universitat Wien, Vienna, Austria.
[27] Olivares, A., Moguerza, J. M., & Prieto, F. J. (2008, accepted). Nonconvex optimization using negative curvature within a modified linesearch. European Journal of Operational Research. · Zbl 1146.90054
[28] Paige, C. C. (1971). The computation of eigenvalues and eigenvectors of very large sparse matrices. Ph.D. Thesis, London University, London, UK.
[29] Pardalos, P. M. (1991). Construction of test problems in quadratic bivalent programming. ACM Transactions Mathematical Software, 17, 74–87. · Zbl 0900.65183 · doi:10.1145/103147.103156
[30] Parlett, B. N. (1980). The symmetric eigenvalue problem. Englewood Cliffs: Prentice-Hall. · Zbl 0431.65017
[31] Ruhe, A. (1974). Iterative eigenvalue algorithms for large symmetric matrices. International Series Numerical Mathematics, 24, 97–115. · Zbl 0296.65016
[32] Saad, Y. (1980). On the rates of convergence of the Lanczos and the block Lanczos methods. SIAM Journal on Numerical Analysis, 17, 687–706. · Zbl 0456.65016 · doi:10.1137/0717059
[33] Saad, Y. (1992). Numerical methods for large eigenvalue problems. Series in algorithms and arch. for adv. sci. comput. Manchester: Manchester University Press.
[34] Saad, Y., & Schultz, M. H. (1985). Conjugate gradient-like algorithms for solving nonsymmetric linear systems. Mathematical Computation, 44, 417–424. · Zbl 0566.65019 · doi:10.1090/S0025-5718-1985-0777273-9
[35] Shultz, G. A., Schnabel, R. B., & Byrd, R. H. (1985). A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties. SIAM Journal on Numerical Analysis, 22(1), 47–67. · Zbl 0574.65061 · doi:10.1137/0722003
[36] Sleijpen, G. L. G., & Van der Vorst, H. A. (1995). The Jacobi-Davidson method for eigenvalue problems as an accelerated inexact Newton scheme (Technical report). Mathematical Institute, Utrecht University.
[37] Sanmatías, S., & Vercher, E. (1998). A generalized conjugate gradient algorithm. Journal of Optimization Theory and Applications, 98, 489–502. · Zbl 0908.90242 · doi:10.1023/A:1022653904717
[38] Sorensen, D. C., & Yang, C. (1995). Accelerating the Lanczos iteration via polynomial spectral transformations (Technical report TR97-29). Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005.
[39] Sun, J., Yang, X., & Chen, X. (2005). Quadratic cost flow and the conjugate gradient method. European Journal of Operational Research, 164, 104–114. · Zbl 1132.90374 · doi:10.1016/j.ejor.2003.04.003
[40] Varga, R. S. (1962). Matrix iterative analysis. Englewood Cliffs: Prentice-Hall. · Zbl 0133.08602
[41] Wilkinson, J. H. (1965). The algebraic eigenvalue problem. Oxford: Clarendon Press. · Zbl 0258.65037
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.