The Study Of New Algorithms For Finding Saddle Points Of Nonconvex Problems With Their Applications

This thesis studies the new algorithms for finding saddle points of nonconvex problems and their applications.The main content consists of four parts.In the first part,we study the local minimax method(LMM)based on new optimization strategies for finding unconstrained saddle points.First,we give a generalized local minimax principle and understand the mathematical nature of the LMM finding unstable saddle points in a stable manner from the perspective of continuous dynamics.Then,we systematically discuss the feasibilities of various step-size search rules and establish a complete global convergence result under the framework of the LMM algorithm using general descent directions.Various efficient optimization strategies can be applied to LMM algorithms.In particular,we propose three new types of LMM algorithms,i.e.,the globally convergent Barzilai-Borwein(BB)type LMM,conjugate gradient type LMM,and L-BFGS type LMM,to improve the computational efficiency of traditional LMM algorithms.Finally,the new LMM algorithms are applied to find multiple solutions for several types of semilinear elliptic boundary value problems,elliptic problems with nonlinear boundary conditions,and Kirchhoff-type quasilinear nonlocal problems,and the numerical performance of different LMM algorithms is compared.Extensive numerical results show that these three new types of LMM algorithms can significantly improve the computational efficiency of traditional LMM algorithms.In the second part,we study the virtual geometry object-type LMM(VGOLMM)based on new optimization strategies for finding unconstrained saddle points.First,based on the analysis of a class of a generalized VGOLMM dynamical system,we propose a framework of the generalized VGOLMM algorithm using general descent directions,and discusses the different step-size search rules and the corresponding global convergence results under this framework.Many efficient optimization strategies can be used to implement this VGOLMM algorithm framework.Due to the simplicity and efficiency of the BB strategy,we propose the VGOLMM algorithm using BB-type step-sizes.Finally,we apply the new VGOLMM algorithm to find multiple solutions for a defocusing nonlinear Schr?dinger equation and a class of Allen-Cahn singularly perturbed Neumann problems.Rich numerical results are obtained and show that the VGOLMM algorithm using the BB-type step-size converges much faster than the original VGOLMM algorithm.In the third part,we study the accurate and efficient new algorithms for computing ground state solutions of Bose-Einstein condensates(BECs).The ground state solution of a BEC is usually defined as the minimizer of the corresponding Gross-Pitaevskii(GP)energy functional under certain constraints.The gradient flow with discrete normalization(GFDN,or the imaginary time evolution method)is one of the most popular techniques for computing the ground states of BECs.Taking the single-component BEC and spin-1 BEC models as examples,through analysis and numerical experiments,we show that several widely used time discretizations based on the GFDN for computing the ground state solution usually results a incorrect ground state solution with an error depending on the time step size.This is an important finding of this article.In order to improve the GFDN,we propose gradient flow with Lagrange multiplier(GFLM)method for computing ground state solutions of BECs,and prove that various typical time discretizations based on the GFLM can accurately match the EulerLagrange equation of the ground state solution.Further,we generalize GFLM to the challenging spin-F BEC model,and study the methods for determining the projection constants.Because the exact projection methods are often more complicated computationally or lack mathematical guarantees for the existence and uniqueness of projection constants,we propose two types of inexact projection strategies,so that the projection constants can be computed explicitly,and estimate their constraint violations.Finally,extensive numerical results for spin-1,spin-2 and spin-3 cases are provided and some interesting phenomena on the ground states are observed.In the last part,we study new algorithms for finding constrained saddle points and apply them to compute excited states of BECs.First,we propose a constrained gentlest ascent dynamics(CGAD)method for finding saddle points with general constrains,and prove that its stable steady state is a constrained saddle point with the corresponding index.A local exponential convergence result for a class of idealized CGAD near the constrained saddle point is established.Then,we apply CGAD to simulate the excited states of BECs.The excited state of a BEC corresponds to the critical point of the GP energy functional under some constraints,whose energy is higher than that of the ground state,so the constrained saddle point of the GP energy functional must be an excited state solution.We apply CGAD to compute the saddle point of the GP energy functional corresponding to the single-component BEC model under unit spherical constraint and design an efficient numerical scheme based on the(semi-implicit)backward-forward Euler time discretization and the Gram-Schmidt orthonormalization process.Finally,we observe some new excited state solutions and interesting physical phenomena based on one-and two-dimensional numerical experiments.