LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX C.H.JEFFREYPANG 0 1 Abstract. Forafunctionf :X →R,apointiscriticalifitsderivativesare 0 zero,andacriticalpointisasaddlepointifitisnotalocalextrema. Inthis 2 paper,westudyalgorithmstofindsaddlepointsofgeneralMorseindex. Our n approach is motivated by the multidimensional mountain pass theorem, and a extends our earlier work on methods (based on studying the level sets of f) J tofindsaddlepointsofmountainpasstype. Weprovetheconvergenceofour algorithms in the nonsmooth case, and the local superlinear convergence of 6 anotheralgorithminthesmoothfinitedimensionalcase. ] A N . Contents h t a 1. Introduction 1 m Notation 3 [ 2. Algorithm for critical points 3 3. Convergence properties 5 1 v 4. Optimality conditions 6 5 5. Another convergence property of critical points 12 2 6. Fast local convergence 15 9 7. Proof of superlinear convergence of local algorithm 20 0 8. Conclusion and conjectures 30 . 1 References 31 0 0 1 : v 1. Introduction i X For a function f : X → R, we say that x is a critical point if ∇f(x) = 0, and r a y is a critical value if there is some critical point x such that f(x) = y. A critical point x is a saddle point if it is neither a local minimizer nor a local maximizer. In this paper, we present algorithms based on the multidimensional mountain pass theorem to find saddle points numerically. The main purpose of critical point theory is the study of variational problems. These are problems (P) such that there exists a smooth functional Φ : X → R whose critical points are solutions of (P). Variational problems occur frequently in the study of partial differential equations. Date:January6,2010. 2000 Mathematics Subject Classification. 35B38,58E05,58E30,65N12. Keywordsandphrases. multidimensionalmountainpass,nonsmoothcriticalpoints,superlin- earconvergence,metriccriticalpointtheory. 1 LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 2 At this point, we make a remark about saddle points in the study of min-max problems. Such saddle points occur in problems in game theory and in constrained optimization using the Lagrangian, and have the splitting structure minmaxf(x,y). x∈X y∈Y In min-max problems, this splitting structure is exploited in numerical procedures. See [15] for a survey of algorithms for min-max problems. In the general case, for example in finding weak solutions of partial differential equations, such a splitting structure may only be obtained after the saddle point is located, and thus is not helpful for finding the saddle point. A critical point x is nondegenerate if its Hessian ∇2f(x) is nonsingular and it is degenerate otherwise. TheMorseindex ofacriticalpointisthemaximaldimension of a subspace of X on which the Hessian ∇2f(x) is negative definite. In the finite dimensional case, the Morse index is the number of negative eigenvalues of the Hessian. Local maximizers and minimizers of f :X →R are easily found using optimiza- tion, while saddle points are harder to find. To find saddle points of Morse index 1, one can use algorithms motivated by the mountain pass theorem. Given points a,b∈X , define a mountain pass p∗ ∈Γ(a,b) to be a minimizer of the problem inf sup f(p(t)), p∈Γ(a,b)0≤t≤1 ifitexists. Here,Γ(a,b)isthesetofcontinuouspathsp:[0,1]→X suchthatp(0)= aandp(1)=b. AmbrosettiandRabinowitz’s[1]mountainpasstheoremstatesthat underaddedconditions,thereisacriticalvalueofatleastmax{f(a),f(b)}. Tofind saddlepointsofhigherMorseindex,itisinstructivetolookattheoremsestablishing theexistenceofcriticalpointsofMorseindexhigherthan1. Rabinowitz[14]proved the multidimensional mountain pass theorem which in turn motivated the study of linking methods to find saddle points. We shall recall theoretical material relevant for finding saddle points of higher Morse index in this paper as needed. While the study of numerical methods for the mountain pass problem began in the 70’s or earlier to study problems in computational chemistry, Choi and McKenna [4] were the first to propose a numerical method for the mountain pass problem to solve variational problems. Most numerical methods for finding critical points of mountain pass type rely on discretizing paths in Γ(a,b) and perturbing pathstolowerthemaximumvalueoff onthepath. Thereareafewothermethods offindingsaddlepointsofmountainpasstypethatdonotinvolveperturbingpaths, for example [9, 2]. SaddlepointsofhigherMorseindexareobtainedwithmodificationsofthemoun- tain pass algorithm. Ding, Costa and Chen [6] proposed a numerical method for finding critical points of Morse index 2, and Li and Zhou [13] proposed a method for finding critical points of higher Morse index. In [12], we suggested a numerical method for finding saddle points of mountain pass type. The key observation is that the value (cid:8) (cid:0) (cid:1) (cid:9) sup l≥max f(a),f(b) |a,b lie in different path components of {x|f(x)≤l} isacriticalvalue. Inotherwords, thesupremumofalllevelsl suchthatthereisno pathconnectingaandbinthelevelset{x|f(x)≤l}isacriticalvalue. SeeFigure 1.1 for an illustration of the difference between the two approaches. An extensive LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 3 theoretical analysis and some numerical results of this approach were provided in [12]. In this paper, we extend three of the themes in the level set approach to find saddlepointsofhigherMorseindex,namelytheconvergenceofthebasicalgorithm (Sections 2 and 3), optimality condition of sub-problem (Section 4), and a fast lo- callyconvergentmethodinRn (Sections6and7). Section5presentsanalternative result on convergence to a critical point similar to that of Section 3. We refer the reader to [12] for examples reflecting the limitations of the level set approach for finding saddle points of mountain pass type, which will be relevant for the design of level set methods of finding saddle points of general Morse index. Figure1.1. Thediagramontheleftshowstheclassicalmethodof perturbingpathsforthemountainpassproblem,whilethediagram on the right shows convergence to the critical point by looking at level sets. Notation lev f: This is the level set {x | f(x) ≥ b}, where f : X → R. The interpre- ≥b tations of lev f and lev f are similar. ≤b =b B: The ball of center 0 and radius 1. B(x,r) stands for a ball of center x and radius r. Bn denotes the n-dimensional sphere in Rn. Sn: The n-dimensional sphere in Rn+1. ∂: Subdifferential of a real-valued function, or the relative boundary of a set. If h : Bn → S is a homeomorphism between Bn and S, then the relative boundary of S is h(Sn−1). lin(A): For an affine space A, the lineality space lin(A) is the space {a−a(cid:48) | a,a(cid:48) ∈A}. 2. Algorithm for critical points We look at the critical point existence theorems to give an insight on our algo- rithm for finding critical points of higher Morse index below. Here is the definition of linking sets. We take our definition from [17, Section II.8]. Definition 2.1. (Linking) Let A be a subset of Rn, B a submanifold of Rn with relative boundary ∂B. Then we say that A and ∂B link if (a) A∩∂B =∅, and (b) for any continuous h:Rn →Rn such that h| =id we have h(B)∩A(cid:54)=∅. ∂B LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 4 B B A A Figure 2.1. Linking subsets Figure 2.1 illustrates two examples of linking subsets in R3. In the diagram on theleft,thesetAistheunionoftwopointsinsideandoutsidethesphereB. Inthe diagram on the right, the sets A and B are the interlocking ’rings’. Note however that A and B link does not imply that B and A link, though this will be true with additional conditions. We hope this does not cause confusion. We now recall the Palais-Smale condition. Definition 2.2. (Palais-Smalecondition)LetX beaBanachspaceandf :X →R beC1. Wesaythatasequence{x }∞ ⊂X isaPalais-Smalesequence if{f(x )}∞ i i=1 i i=1 is bounded and ∇f(x ) → 0, and f satisfies the Palais-Smale condition if any i Palais-Smale sequence admits a convergent subsequence. The classical multidimensional pass theorem originally due to Rabinowitz [14] states that under added conditions, if there are linking sets A and B such that max f < min f and the Palais-Smale condition holds, then there is a critical A B value of at least max f for the case when f is smooth. (See Theorem 6.1 for a A statement of the multidimensional mountain pass theorem) Generalizations in the nonsmooth case are also well-known in the literature. See for example [8]. TofindsaddlepointsofMorseindexm,weconsiderfindingasequenceoflinking sets{A }∞ and{B }∞ suchthatdiam(A ),thediameterofthesetA ,decreases i i=1 i i=1 i i tozero,andthesetA isasubsetofanm-dimensionalaffinespace. Thismotivates i the following algorithm. Algorithm 2.3. First algorithm for finding saddle points of Morse index m≥1. (1) Set the iteration count i to 0, and let l be a lower bound of the critical i value and u be an upper bound. i (2) Find x and y , where (S ,x ,y ) is an optimizing triple of i i i i i (2.1) min max |x−y|, S∈Sx,y∈S∩(lev≥21(li+ui)f)∩Ui where U is some open set. Here, S is the set of m-dimensional affine i subspaces of Rn intersecting U . In the inner maximum problem above, i we take the value to be 0 if S ∩(lev f)∩U is empty, making the ≤12(li+ui) i objective function above equal to 0. For simplicity, we shall just assume that minimizers and maximizers of the above problem exist. (3) (Bisection) If the objective of (2.1) is zero, then 1(l +u ) is a lower bound 2 i i of the critical value. Set l = 1(l +u ) and u = u . Otherwise, set i+1 2 i i i+1 i l =l and u = 1(l +u ). i+1 i i+1 2 i i (4) Increase i and go back to step 2. LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 5 The critical step of Algorithm 2.3 lies in step 2. We elaborate on optimal con- ditions that will be a useful approximate for this step in Section 4. One may think of the set A as the relative boundary (to the affine space S ) of S ∩(lev f)∩U . i i i ≥li i A frequent assumption we will make is nondegenericity. Definition 2.4. We say that a critical point is nondegenerate if its Hessian is invertible. Algorithm 2.3 requires m > 0, but when m = 0, nondegenerate critical points of Morse index zero are just strict local minimizers that can be easily found by optimization. We illustrate two special cases of Algorithm 2.3. Example 2.5. (Particular cases of Algorithm 2.3) (a) For the case m = 1, S is the set of lines. The inner maximization problem in (2.1) has its solution on the two endpoints of S ∩(lev f)∩U . This means that (2.1) is equivalent to i ≥21(li+ui) i finding the local closest points between two components of (lev f)∩U , as ≤12(li+ui) i was analyzed in [12]. (b) For the case m=n, S contains the whole of Rn. Hence the outer minimiza- tion problem in (2.1) is superfluous. The level set (lev f)∩U gets smaller ≥12(li+ui) i and smaller as 1(l +u ) approaches the maximum value, till it becomes a single 2 i i point if the maximizer is unique. 3. Convergence properties In this section, we prove the convergence of x , y in Algorithm 2.3 to a critical i i pointwhentheyconvergetoacommonlimit. Werecallsomefactsaboutnonsmooth analysis needed for the rest of the paper. It is more economical to prove our result for nonsmooth critical points because the proofs are not that much harder, and nonsmooth critical points are also of interest in applications. Let X be a Banach space, and f : X → R be a locally Lipschitz function at a given point x. Definition 3.1. (Clarke subdifferential) [5, Section 2.1] Suppose f : X → R is locallyLipschitzatx. TheClarke generalized directional derivative off atxinthe direction v ∈X is defined by f(y+tv)−f(y) f◦(x;v)= limsup , t t(cid:38)0,y→x wherey ∈X andtisapositivescalar. TheClarkesubdifferential off atx,denoted by ∂ f(x), is the subset of the dual space X∗ given by C {ζ ∈X∗ |f◦(x;v)≥(cid:104)ζ,v(cid:105) for all v ∈X}. The point x is a Clarke (nonsmooth) critical point if 0 ∈ ∂ f(x). Here, (cid:104)·,·(cid:105) : C X∗×X →R defined by (cid:104)ζ,v(cid:105):=ζ(v) is the dual relation. For the particular case of C1 functions, ∂ f(x) = {∇f(x)}. Therefore critical C pointsofsmoothfunctionsarealsononsmoothcriticalpoints. Fromthedefinitions above, it is clear that an equivalent definition of a nonsmooth critical point is f◦(x;v) ≥ 0 for all v ∈ X. This property allows us to prove that a point is nonsmooth critical without appealing to the dual space X∗. We now prove our result of convergence to nonsmooth critical points. LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 6 Proposition 3.2. (Convergence to saddle point) Let z¯ ∈ X. Suppose there is a ball B(z¯,r), a sequence of triples {(S ,x ,y )}∞ and a sequence l monotonically i i i i=1 i increasing to f(z¯) such that (x ,y )→(z¯,z¯) and (S ,x ,y ) is an optimizing triple i i i i i of (2.1) in Algorithm 2.3 for l with U =B(z¯,r). Then z¯is a Clarke critical point. i i Proof. Seeking a contradiction, suppose there exists some direction v¯ such that f◦(z¯;v¯)<0. Thismeansthatthereissome(cid:15)¯>0suchthatif|z−z¯|<(cid:15)¯and(cid:15)<(cid:15)¯, then f(z+(cid:15)v¯)−f(z) 1 < f◦(z¯;v¯) (cid:15) 2 1 ⇒f(z+(cid:15)v¯) < f(z)+(cid:15) f◦(z¯;v¯). 2 Suppose i is large enough so that x ,y ∈ B(z¯, (cid:15)¯), and that x ,y ∈ A := S ∩ i i 2 i i i i (lev f) ∩ B(z¯,r) are such that |x − y | = diam(A ). Consider the set A˜ := ≥li i i i (S +(cid:15) v¯)∩(lev f)∩B(z¯,r), where (cid:15) >0 is arbitrarily small. Let x˜ ,y˜ ∈A˜ be i 1 ≥li 1 i i such that |x˜ −y˜|=diam(A˜). From the minimality of the outer minimization, we i i have |x˜ −y˜|≥|x −y |. Note that f(x˜ )=f(y˜)=l . Then i i i i i i i 1 f(x˜ ) < f(x˜ −(cid:15) v¯)+(cid:15) f◦(z¯;v¯) i i 1 12 1 =⇒ f(x˜ −(cid:15) v¯) > f(x˜ )−(cid:15) f◦(z¯;v¯) i 1 i 12 > l . i Thecontinuityoff impliesthatwecanfindsome(cid:15) >0suchthatxˆ :=x˜ −(cid:15) v¯+ 2 i i 1 (cid:15) (x˜ −y˜) lies in A . Similarly, yˆ :=y˜ −(cid:15) v¯ lie in A as well. But 2 i i i i i 1 i |xˆ −yˆ| > |x˜ −y˜| i i i i ≥ |x −y |. i i This contradicts the maximality of |x −y | in A , and thus z¯ must be a critical i i i point. (cid:3) 4. Optimality conditions Wenowreducethemin-maxproblem(2.1)toaconditiononthegradients∇f(x ) i and ∇f(y ) that is easy to verify numerically. This condition will help in the i numerical solution of (2.1). We use methods in sensitivity analysis of optimization problems(asisdonein[3])tostudyhowvaryingthem-dimensionalaffinespaceSin an(m+1)-dimensionalsubspaceaffectstheoptimalvalueintheinnermaximization problemin(2.1). Weconformasmuchaspossibletothenotationin[3]throughout this section. Consider the following parametric optimization problem (P ) in terms of u∈R u asanm+1dimensionalmodelinRm+1 oftheinnermaximizationproblemin(2.1): (P ): v(u):= min F(x,y,u):=−|x−y|2 u s.t. G(x,y,u)∈K, (4.1) x,y ∈Rm+1, LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 7 where G:(Rm+1)2×R→R4 and K ⊂R4 are defined by   −f(x)+b G(x,y,u):= −f(y)+b , K :=R2 ×{0}2.  (0,0,...,0,u,1)x  − (0,0,...,0,u,1)y The problem (P ) reflects the inner maximization problem of (2.1). Due to the u standardpracticeofwritingoptimizationproblemsasminimizationproblems,(4.1) is a minimization problem instead. We hope this does not cause confusion. Let S(u) be the m-dimensional subspace orthogonal to (0,...,0,u,1). The first two components of G(x,y,u) model the constraints f(x) ≥ b and f(y) ≥ b, while the last two components enforce x,y ∈ S(u). Denote an optimal solution to (P ) u tobe(x¯(u),y¯(u)), andlet(x¯,y¯):=(x¯(0),y¯(0)). Wemakethefollowingassumption throughout. Assumption 4.1. (Uniqueness of optimizers) (P ) has a unique solution x¯ = 0 0 and y¯=(0,...,0,1,0) at u=0. We shall investigate how the set of minimizers of (P ) behaves with respect to u u at 0. The derivatives of F and G with respect to x and y, denoted by D F and x,y D G, are x,y D F(x,y,u) = 2(cid:0) (y−x)T (x−y)T (cid:1), x,y  −∇f(x)T   −∇f(y)T  (4.2) and Dx,yG(x,y,u) =  (0,0,...,0,u,1) , (0,0,...,0,u,1) where the blank terms in D G(x,y,u) are all zero. x,y The Lagrangian is the function L:Rm+1×Rm+1×R4×R→R defined by 4 (cid:88) L(x,y,λ,u):=F(x,y,u)+ λ G (x,y,u). i i i=1 We say that λ := (λ ,λ ,λ ,λ ), depending on u, is a Lagrange multiplier if 1 2 3 4 D L(x,y,λ,u) = 0 and λ ∈ N (G(x,y,u)), and the set of all Lagrange mul- x,y K tipliers is denoted by Λ(x,y,u). Here, N (G(x,y,u)) stands for the normal cone K defined by N (cid:0)G(x,y,u)(cid:1):={v ∈R4 |vT[w−G(x,y,u)]≤0 for all w ∈K}. K WeareinterestedinthesetΛ(x¯,y¯,0). Itisclearthatoptimalsolutionsmustsatisfy G(x¯,y¯,0)=0, so λ∈N (0)=R2 ×R2. K + The condition D L(x¯,y¯,λ,0)=0 reduces to x,y (cid:32) 4 (cid:33) (cid:88) D F(x,y,0)+ λ G (x,y,0) | = 0 x,y i i x=x¯,y=y¯ i=1 (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) y¯−x¯ −∇f(x¯) 0 ⇒2 +λ +λ x¯−y¯ 1 0 2 −∇f(y¯) (cid:18)(0,0,...,0,0,1)T(cid:19) (cid:18) 0 (cid:19) +λ +λ = 0. 3 0 4 (0,0,...,0,0,1)T LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 8 Here, G (x¯,y¯,0) is the ith row of G(x¯,y¯,0) for 1 ≤ i ≤ 4. This is exactly the i KKT conditions, and can be rewritten as 2(y¯−x¯)−λ ∇f(x¯)+λ (0,0,...,0,0,1)T = 0, 1 3 (4.3) 2(x¯−y¯)−λ ∇f(y¯)+λ (0,0,...,0,0,1)T = 0. 2 4 It is clear that λ and λ cannot be zero, and so we have 1 2 (cid:18) (cid:19) 2 λ ∇f(x¯)T = 0,0,...,0, , 3 , λ λ 1 1 (cid:18) (cid:19) 2 λ ∇f(y¯)T = 0,0,...,0,− , 4 . λ λ 2 2 Recall that λ ,λ ≥0, so this gives more information about ∇f(x¯) and ∇f(y¯). 1 2 Wenextdiscusstheoptimalityoftheouterminimizationproblemof (2.1),which can be studied by perturbations in the parameter u of (4.1), but we first recall a result on the first order sensitivity of optimal solutions. Definition 4.2. (Robinson’s constraint qualification) (from [3, Definition 2.86]) We say that Robinson’s constraint qualification holds at (x¯,y¯) ∈ Rm+1×Rm+1 if the regularity condition (cid:8) (cid:0) (cid:1) (cid:9) 0∈int G(x¯,y¯,0)+Range D G(x¯,y¯,0) −K x,y is satisfied. Theorem 4.3. (Parametric optimization) (from [3, Theorem 4.26]) For prob- lem(4.1), let (x¯(u),y¯(u)) be as defined earlier. Suppose that (i) Robinson’s constraint qualification holds at (x¯(0),y¯(0)), and (ii) if u →0, then (P ) possesses an optimal solution (x¯(u ),y¯(u )) that has n un n n a limit point (x¯,y¯). Then v(·) is directionally differentiable at u=0 and v(cid:48)(0)=D L(x,y,λ,0). u We proceed to prove our result. Proposition 4.4. (Optimality condition on ∇f(y¯)) Consider the setup so far in this section and suppose Assumption 4.1 holds. If ∇f(y¯) is not a positive multiple of (0,0,...,0,1,0)T at u = 0, then we can perturb u so that (4.1) has an increase in objective. Proof. We first obtain first order sensitivity information from Theorem 4.3. Recall that by definition, Robinson’s constraint qualification holds at (x¯,y¯) if (cid:8) (cid:0) (cid:1) (cid:9) 0∈int G(x¯,y¯,0)+Range D G(x¯,y¯,0) −K . x,y From (4.3), it is clear that ∇f(x¯) and (0,...,0,0,1) are linearly independent, and so are ∇f(y¯) and (0,...,0,0,1). From the formula of D G(x¯,y¯,0) in (4.2), we x,y see immediately that Range(D G(x¯,y¯,0)) = R4, thus the Robinson’s constraint x,y qualification indeed holds. Suppose that lim t = 0. We prove that part (ii) of Theorem 4.3 holds by n→∞ n provingthat(x¯(t ),y¯(t ))cannothaveanyotherlimitpoints. Supposethat(x(cid:48),y(cid:48)) n n is a limit point of {(x¯(t ),y¯(t ))}∞ . It is clear that x(cid:48),y(cid:48) ∈S(0). n n n=1 LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX 9 We can find y → y¯ such that y ∈ S(t ) and f(y ) = b. For example, we can n n n n use the Implicit Function Theorem with the constraints f(y) = b, g(y,u) = 0, where g(y,u) = (0,0,...,0,u,1)Ty. The derivatives with respect to y and y m m+1 are ∂ f(y¯)=− 2 , ∂ f(y¯)= λ4, ∂ym λ2 ∂ym+1 λ2 ∂ g(y¯,0)=0, ∂ g(y¯,0)=1. ∂ym ∂ym+1 Therefore, for y =y =···=y =y =0 and any choice of u close to zero, 1 2 m−2 m−1 there is some y and y such that y ∈S(u) and f(y)=b. m m+1 Clearly |x¯−y | ≤ |x¯(t )−y¯(t )|. Taking limits as n → ∞, we have |x¯−y¯| ≤ n n n |x(cid:48) −y(cid:48)|. Since (x¯,y¯) minimize F, it follows that |x¯−y¯| = |x(cid:48) −y(cid:48)|, and by the uniqueness of solutions to (P ), we can assume that x(cid:48) =x¯ and y(cid:48) =y¯. 0 Theorem4.3impliesthatv(cid:48)(0)=D L(x,y,λ,0). WenowcalculateD L(x,y,λ,0). u u It is clear that D G(x,y,λ,0) = (0,0,0,1)T, and so D L(x,y,λ,0) = λ . Since u u 4 ∇f(y¯) is not a multiple of (0,0,...,0,1,0)T at u = 0, λ (cid:54)= 0, and this gives the 4 conclusion we need. (cid:3) A direct consequence of Proposition 4.4 is the following easily checkable condi- tion. Theorem 4.5. (Gradients are opposite) Let (S ,x ,y ) be an optimizing triple to i i i (2.1) for some l such that S ∩(lev f)∩U is closed, and (x ,y ) is the unique i i ≥li i i i pair of points in S ∩(lev f)∩U satisfying |x −y |=diam(S ∩(lev f)∩U ). i ≥li i i i i ≥li i Then ∇f(x ) and ∇f(y ) are nonzero and point in opposite directions. i i Proof. We can look at an m+1 dimensional subspace which reduces to the setting that we are considering so far in this section. By Proposition 4.4, ∇f(y ) is a i positive multiple of x −y at optimality. Similarly, ∇f(x ) is a positive multiple i i i of y −x at optimality, and the result follows. (cid:3) i i We remark on how to start the algorithm. We look at critical points of Morse index 1 first. In this case, two local minima x¯ , x¯ are needed before the mountain 1 2 pass algorithm can guarantee the existence of a critical point x¯ . For any value 3 above the critical value corresponding to the critical point of Morse index 1, the level set contains a path connecting x¯ and x¯ passing through x¯ . 1 2 3 To find the next critical point of Morse index 2 we remark that under mild conditions, if lev f contains a closed path homeomorphic to S , the boundary of ≤a 1 the disc of dimension 2, then the linking principle guarantees the existence of a critical point through the multidimensional mountain pass theorem. Theorem 6.1 which we quote later gives an idea how this is possible. We refer the reader to [16] and [8, Chapter 19] for more details on linking methods. We now illustrate with an example that without the assumption that (x ,y ) i i is the unique pair of points satisfying |x −y | = diam(S ∩(lev f)∩U ), the i i i ≥li i conclusion in Theorem 4.5 need not hold. Lemma4.6. (Shortestlinesegments)Supposelinesl andl intersectattheorigin 1 2 in R2, and let P be a point on the angle bisector as shown in the diagram on the left of Figure 4.1. The minimum distance of the line segment AB, where A is a point LEVEL SET METHODS FOR FINDING SADDLE POINTS OF GENERAL MORSE INDEX10 L 4 L A 3 P θ B d l l 1 2 α α L 2 L 1 O Figure 4.1. The diagram on the left illustrates the setting of Lemma 4.6, while the diagram on the right illustrates Example 4.7. on l and B is a point on l and AB passes through P, is attained when OAB is 1 2 an isosceles triangle with AB as its base. Proof. Muchofthisishighschooltrigonometryandplanegeometry,butwepresent full details for completeness. Let α be the angle (cid:93)AOP, β be the angle (cid:93)PAO, and d=|OP|. By using the sine rule, we get (cid:18) (cid:19) sinα sinα |AB|=d + . sinθ sin(π−2α−θ) The problem is now reduced to finding the θ that minimizes the value above. Con- tinuing the arithmetic gives: (cid:18) (cid:19) (cid:18) (cid:19) sinα sinα 1 1 d + = dsinα + sinθ sin(π−2α−θ) sinθ sin(2α+θ) (cid:18) (cid:19) sinθ+sin(2α+θ) = dsinα sin(θ)sin(2α+θ) (cid:18) (cid:19) sinθ+sin(2α+θ) = dsinα sin(θ)sin(2α+θ) (cid:18) (cid:19) 2sin(α+θ)cosα = dsinα 1[cos(2α)−cos(2α+2θ)] 2 (cid:18) (cid:19) sin(α+θ) = 2dsin(2α) cos(2α)−cos(2α+2θ) We now differentiate the sin(α+θ) term above, which gives cos(2α)−cos(2α+2θ) (cid:18) (cid:19) d sin(α+θ) dθ cos(2α)−cos(2α+2θ) 1 = [cos(α+θ)[cos(2α)−cos(2α+2θ)]−2sin(2α+2θ)sin(α+θ)] [cos(2α)−cos(2α+2θ)]2