×

Level set methods for finding critical points of mountain pass type. (English) Zbl 1227.65055

Let \(X\) be a topological space and \(f: X\to\mathbb{R}\). \(\Gamma(a, b)\) denotes the set of all continuous paths \(p: [0, 1]\to X\) such that \(p(0)= a\) and \(p(1)= b\). A mountain pass \(p^*\in\Gamma(a, b)\) is defined to be a minimizer of the problem \[ \underset{p\in \Gamma(a, b)}{}{\text{inf}}\;\sup_{0\leq t\leq 1}\, f\circ p(t). \] The mountain pass theorem and its variants provide the primary ways to establish the existence of critical points and to find critical points numerically. A numerical method for finding critical points is described in the present paper. This method is convergent in the nonsmooth case and locally superlinearly convergent in the smooth finite-dimensional case. The algorithm allows to find saddle-points of mountain type. These techniques are applied to describe a strategy for adressing the Wilkinson problem of calculating the distance from a matrix to a closest matrix with repeated eigenvalues. The results are illustrated by some examples with convincing figures. There are applications of mountain passes in computational chemistry and in nonlinear partial differential equation.

MSC:

65K10 Numerical optimization and variational techniques
34K28 Numerical approximation of solutions of functional-differential equations (MSC2010)

Software:

Eigtool; Seigtool
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Sinclair, J. E.; Fletcher, R., A new method of saddle-point location for the calculation of defect migration energies, J. Phys. C: Solid State Phys., 7, 864-870 (1974)
[2] Henkelman, G.; Jóhannesson, G.; Jónsson, H., Methods for finding saddle points and minimum energy paths, (Schwartz, S. D., Progress in Theoretical Chemistry and Physics, vol. 5 (2000), Kluwer)
[3] Ambrosetti, A.; Rabinowitz, P., Dual variational methods in critical point theory and applications, J. Funct. Anal., 14, 349-381 (1973) · Zbl 0273.49063
[4] Youssef Jabri, The Mountain Pass Theorem, Cambridge, 2003.; Youssef Jabri, The Mountain Pass Theorem, Cambridge, 2003. · Zbl 1036.49001
[5] Choi, Y. S.; McKenna, P. J., A mountain pass method for the numerical solution of semilinear elliptic problems, Nonlinear Anal., 20, 417-437 (1993) · Zbl 0779.35032
[6] Aubin, J.-P.; Ekeland, I., Applied Nonlinear Analysis (1984), Wiley, Reprinted by Dover 2007
[7] Ding, Zhonghai; Costa, David; Chen, Goong, A high-linking algorithm for sign-changing solutions of semilinear elliptic equations, Nonlinear Anal., 38, 151-172 (1999) · Zbl 0941.35023
[8] Li, Yongxin; Zhou, Jianxin, A minimax method for finding multiple critical points and its applications to semilinear PDEs, SIAM J. Sci. Comput., 23, 3, 840-865 (2001) · Zbl 1002.35004
[9] Li, Yongxin; Zhou, Jianxin, Convergence results of a local minimax method for finding multiple critical points, SIAM J. Sci. Comput., 24, 3, 865-885 (2002) · Zbl 1040.58003
[10] Yao, Xudong; Zhou, Jianxin, Unified convergence results on a minimax algorithm for finding multiple critical points in Banach spaces, SIAM J. Numer. Anal., 45, 1330-1347 (2007) · Zbl 1143.58006
[11] Moré, J. J.; Munson, T. S., Computing mountain passes and transition states, Math. Program. Ser. B, 100, 151-182 (2004) · Zbl 1063.49021
[12] Barutello, V.; Terracini, S., A bisection algorithm for the numerical mountain pass, NoDEA Nonlinear Differential Equations Appl., 14, 527-539 (2007) · Zbl 1141.46036
[13] Horák, J., Constrained mountain pass algorithm for the numerical solution of semilinear elliptic problems, Numer. Math., 98, 251-276 (2004) · Zbl 1058.65129
[14] Ambrosetti, A., Critical points and nonlinear variational problems, Mém. Soc. Math. Fr. Sér. 2, 49, 1-139 (1992) · Zbl 0766.49006
[15] Degiovanni, M.; Marzocchi, M., A critical point theory for nonsmooth functionals, Ann. Mat. Pura Appl., 167, 73-100 (1994) · Zbl 0828.58006
[16] Katriel, G., Mountain pass theorem and a global homeomorphism theorem, Ann. Inst. H. Poincaré Anal. Non Linéaire, 11, 189-209 (1994) · Zbl 0834.58007
[17] Ioffe, A. D.; Schwartzman, E., Metric critical point theory 1: Morse regularity and homotopic stability of a minimum, J. Math Pures Appl., 75, 125-153 (1996) · Zbl 0852.58018
[18] Chang, Kung-Ching, Variational methods for non-differentiable functionals and their applications to partial differential equations, J. Math. Anal. Appl., 80, 102-129 (1981) · Zbl 0487.49027
[19] Shi, S., Ekeland’s variational principle and the mountain pass lemma, Acta Math. Sinica (NS), 1, 4, 348-355 (1985) · Zbl 0605.58017
[20] Borwein, J. M.; Zhu, Q. J., Techniques of Variational Analysis (2005), Springer · Zbl 1076.49001
[21] Clarke, F. H., Optimization and Nonsmooth Analysis (1983), Wiley: Wiley New York, Republished as vol. 5, Classics in Applied Mathematics, SIAM, 1990 · Zbl 0727.90045
[22] Mordukhovich, B. S., Variational Analysis and Generalized Differentiation I and II (2006), Springer: Springer Berlin
[23] Rockafellar, R. T.; Wets, R. J.-B., Variational Analysis (1998), Springer · Zbl 0888.49001
[24] Yao, Xudong; Zhou, Jianxin, A local minimax characterization of computing multiple nonsmooth saddle critical points, Math. Program. Ser. B, 104, 749-760 (2005) · Zbl 1124.90047
[25] Alam, R.; Bora, S., On sensitivity of eigenvalues and eigendecompositions of matrices, Linear Algebra Appl., 396, 273-301 (2005) · Zbl 1084.15017
[26] Mawhin, J.; Willem, M., Critical Point Theory and Hamiltonian Systems (1989), Springer: Springer Berlin · Zbl 0676.58017
[27] Nirenberg, L., (Variational Methods in Nonlinear Problems. Topics in the Calculus of Variations. Variational Methods in Nonlinear Problems. Topics in the Calculus of Variations, Montecatini Terme, 1987. Variational Methods in Nonlinear Problems. Topics in the Calculus of Variations. Variational Methods in Nonlinear Problems. Topics in the Calculus of Variations, Montecatini Terme, 1987, Lectures Notes in Mathematics, vol. 1365 (1989), Springer), 100-119
[28] Rabinowitz, P. H., (Minimax Methods in Critical Point Theory with Applications to Differential Equations. Minimax Methods in Critical Point Theory with Applications to Differential Equations, CBMS Regional Conference Ser. Math., vol. 65 (1986), AMS) · Zbl 0609.58002
[29] Struwe, M., Variational Methods (2000), Springer
[30] M. Willem, Un Lemme de déformation quantitatif en calcul des variations. A quantitative deformation lemma in the calculus of variations. Institut de Mathématiques pures et appliquées, Applied and Pure Mathematics Institute, Recherche de mathématiques, Mathematics Research, no. 19, Catholic University of Louvain, May 1992 (in French).; M. Willem, Un Lemme de déformation quantitatif en calcul des variations. A quantitative deformation lemma in the calculus of variations. Institut de Mathématiques pures et appliquées, Applied and Pure Mathematics Institute, Recherche de mathématiques, Mathematics Research, no. 19, Catholic University of Louvain, May 1992 (in French). · Zbl 0850.58009
[31] Benedetti, R.; Risler, J.-J., Real Algebraic and Semi-Algebraic Sets (1990), Hermann: Hermann Paris · Zbl 0694.14006
[32] M. Coste, An introduction to semialgebraic geometry, Instituti Editoriali e poligrafici internazionali, Universita di Pisa, 2002. Available electronically at: http://perso.univ-rennes1.fr/michel.coste/; M. Coste, An introduction to semialgebraic geometry, Instituti Editoriali e poligrafici internazionali, Universita di Pisa, 2002. Available electronically at: http://perso.univ-rennes1.fr/michel.coste/
[33] M. Coste, An introduction to \(O\) http://perso.univ-rennes1.fr/michel.coste/; M. Coste, An introduction to \(O\) http://perso.univ-rennes1.fr/michel.coste/
[34] L. van den Dries, Tame Topology and \(o\); L. van den Dries, Tame Topology and \(o\) · Zbl 0953.03045
[35] J.H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford, 1965.; J.H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford, 1965. · Zbl 0258.65037
[36] R. Alam, S. Bora, R. Byers, M.L. Overton, Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components, Linear Algebra Appl. (2010) (in press).; R. Alam, S. Bora, R. Byers, M.L. Overton, Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components, Linear Algebra Appl. (2010) (in press). · Zbl 1228.65062
[37] Burke, J. V.; Lewis, A. S.; Overton, M. L., Spectral conditioning and pseudospectral growth, Numer. Math., 107, 27-37 (2007) · Zbl 1124.15004
[38] Malyshev, A. N., A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues, Numer. Math., 83, 443-454 (1999) · Zbl 0972.15011
[39] Demmel, J. W., On condition numbers and the distance to the nearest ill-conditioned problem, Numer. Math., 51, 251-289 (1987) · Zbl 0597.65036
[40] L.N. Trefethen, M. Embree, Spectra and Pseudospectra, Princeton, NJ, 2005.; L.N. Trefethen, M. Embree, Spectra and Pseudospectra, Princeton, NJ, 2005.
[41] E. Mengi, Private communication, 2009.; E. Mengi, Private communication, 2009.
[42] Mengi, E.; Overton, M., Algorithms for the computation of the pseudospectral radius and the numerical radius of a matrix, IMA J. Numer. Anal., 25, 648-669 (2005) · Zbl 1082.65043
[43] Byers, R., A bisection method for measuring the distance of a stable matrix to the unstable matrices, SIAM J. Sci. Stat. Comput., 9, 875-881 (1988) · Zbl 0658.65044
[44] Boyd, S.; Balakrishnan, V., A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its \(L_\infty \)-norm, Syst. Control Lett., 15, 1-7 (1990) · Zbl 0704.93014
[45] T.G. Wright, EigTooL: a graphical tool for nonsymmetric eigenproblems, 2002; Available online at: http://web.comlab.ox.ac.uk/pseudospectra/eigtool/; T.G. Wright, EigTooL: a graphical tool for nonsymmetric eigenproblems, 2002; Available online at: http://web.comlab.ox.ac.uk/pseudospectra/eigtool/
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.