In this paper,by designing a normalized nonmonotone search strategy with the BarzilaiBorwein-type step-size,a novel local minimax method(LMM),which is a globally convergent iterative method,is proposed and analyzed to...In this paper,by designing a normalized nonmonotone search strategy with the BarzilaiBorwein-type step-size,a novel local minimax method(LMM),which is a globally convergent iterative method,is proposed and analyzed to find multiple(unstable)saddle points of nonconvex functionals in Hilbert spaces.Compared to traditional LMMs with monotone search strategies,this approach,which does not require strict decrease of the objective functional value at each iterative step,is observed to converge faster with less computations.Firstly,based on a normalized iterative scheme coupled with a local peak selection that pulls the iterative point back onto the solution submanifold,by generalizing the Zhang-Hager(ZH)search strategy in the optimization theory to the LMM framework,a kind of normalized ZH-type nonmonotone step-size search strategy is introduced,and then a novel nonmonotone LMM is constructed.Its feasibility and global convergence results are rigorously carried out under the relaxation of the monotonicity for the functional at the iterative sequences.Secondly,in order to speed up the convergence of the nonmonotone LMM,a globally convergent Barzilai-Borwein-type LMM(GBBLMM)is presented by explicitly constructing the Barzilai-Borwein-type step-size as a trial step-size of the normalized ZH-type nonmonotone step-size search strategy in each iteration.Finally,the GBBLMM algorithm is implemented to find multiple unstable solutions of two classes of semilinear elliptic boundary value problems with variational structures:one is the semilinear elliptic equations with the homogeneous Dirichlet boundary condition and another is the linear elliptic equations with semilinear Neumann boundary conditions.Extensive numerical results indicate that our approach is very effective and speeds up the LMMs significantly.展开更多
The local minimax method(LMM)proposed by Li and Zhou(2001,2002)is an efficient method to solve nonlinear elliptic partial differential equations(PDEs)with certain variational structures for multiple solutions.The stee...The local minimax method(LMM)proposed by Li and Zhou(2001,2002)is an efficient method to solve nonlinear elliptic partial differential equations(PDEs)with certain variational structures for multiple solutions.The steepest descent direction and the Armijo-type step-size search rules are adopted in Li and Zhou(2002)and play a significant role in the performance and convergence analysis of traditional LMMs.In this paper,a new algorithm framework of the LMMs is established based on general descent directions and two normalized(strong)Wolfe-Powell-type step-size search rules.The corresponding algorithm framework,named the normalized Wolfe-Powell-type LMM(NWP-LMM),is introduced with its feasibility and global convergence rigorously justified for general descent directions.As a special case,the global convergence of the NWP-LMM combined with the preconditioned steepest descent(PSD)directions is also verified.Consequently,it extends the framework of traditional LMMs.In addition,conjugate-gradient-type(CG-type)descent directions are utilized to speed up the NWP-LMM.Finally,extensive numerical results for several semilinear elliptic PDEs are reported to profile their multiple unstable solutions and compared with different algorithms in the LMM’s family to indicate the effectiveness and robustness of our algorithms.In practice,the NWP-LMM combined with the CG-type direction performs much better than its known LMM companions.展开更多
Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one...Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortio展开更多
The minimax optimization model introduced in this paper is an important model which has received some attention over the past years. In this paper, the application of minimax model on how to select the distribution ce...The minimax optimization model introduced in this paper is an important model which has received some attention over the past years. In this paper, the application of minimax model on how to select the distribution center location is first introduced. Then a new algorithm with nonmonotone line search to solve the non-decomposable minimax optimization is proposed. We prove that the new algorithm is global Convergent. Numerical results show the proposed algorithm is effective.展开更多
In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting....In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.展开更多
基金supported by the NSFC(Grant Nos.12171148,11771138)the NSFC(Grant Nos.12101252,11971007)+2 种基金the NSFC(Grant No.11901185)the National Key R&D Program of China(Grant No.2021YFA1001300)by the Fundamental Research Funds for the Central Universities(Grant No.531118010207).
文摘In this paper,by designing a normalized nonmonotone search strategy with the BarzilaiBorwein-type step-size,a novel local minimax method(LMM),which is a globally convergent iterative method,is proposed and analyzed to find multiple(unstable)saddle points of nonconvex functionals in Hilbert spaces.Compared to traditional LMMs with monotone search strategies,this approach,which does not require strict decrease of the objective functional value at each iterative step,is observed to converge faster with less computations.Firstly,based on a normalized iterative scheme coupled with a local peak selection that pulls the iterative point back onto the solution submanifold,by generalizing the Zhang-Hager(ZH)search strategy in the optimization theory to the LMM framework,a kind of normalized ZH-type nonmonotone step-size search strategy is introduced,and then a novel nonmonotone LMM is constructed.Its feasibility and global convergence results are rigorously carried out under the relaxation of the monotonicity for the functional at the iterative sequences.Secondly,in order to speed up the convergence of the nonmonotone LMM,a globally convergent Barzilai-Borwein-type LMM(GBBLMM)is presented by explicitly constructing the Barzilai-Borwein-type step-size as a trial step-size of the normalized ZH-type nonmonotone step-size search strategy in each iteration.Finally,the GBBLMM algorithm is implemented to find multiple unstable solutions of two classes of semilinear elliptic boundary value problems with variational structures:one is the semilinear elliptic equations with the homogeneous Dirichlet boundary condition and another is the linear elliptic equations with semilinear Neumann boundary conditions.Extensive numerical results indicate that our approach is very effective and speeds up the LMMs significantly.
基金supported by National Natural Science Foundation of China(Grant Nos.12171148 and 11771138)the Construct Program of the Key Discipline in Hunan Province.Wei Liu was supported by National Natural Science Foundation of China(Grant Nos.12101252 and 11971007)+2 种基金supported by National Natural Science Foundation of China(Grant No.11901185)National Key Research and Development Program of China(Grant No.2021YFA1001300)the Fundamental Research Funds for the Central Universities(Grant No.531118010207).
文摘The local minimax method(LMM)proposed by Li and Zhou(2001,2002)is an efficient method to solve nonlinear elliptic partial differential equations(PDEs)with certain variational structures for multiple solutions.The steepest descent direction and the Armijo-type step-size search rules are adopted in Li and Zhou(2002)and play a significant role in the performance and convergence analysis of traditional LMMs.In this paper,a new algorithm framework of the LMMs is established based on general descent directions and two normalized(strong)Wolfe-Powell-type step-size search rules.The corresponding algorithm framework,named the normalized Wolfe-Powell-type LMM(NWP-LMM),is introduced with its feasibility and global convergence rigorously justified for general descent directions.As a special case,the global convergence of the NWP-LMM combined with the preconditioned steepest descent(PSD)directions is also verified.Consequently,it extends the framework of traditional LMMs.In addition,conjugate-gradient-type(CG-type)descent directions are utilized to speed up the NWP-LMM.Finally,extensive numerical results for several semilinear elliptic PDEs are reported to profile their multiple unstable solutions and compared with different algorithms in the LMM’s family to indicate the effectiveness and robustness of our algorithms.In practice,the NWP-LMM combined with the CG-type direction performs much better than its known LMM companions.
文摘Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortio
基金Supported by the Fundamental Research Funds for the Central Universities(2014JBM044)
文摘The minimax optimization model introduced in this paper is an important model which has received some attention over the past years. In this paper, the application of minimax model on how to select the distribution center location is first introduced. Then a new algorithm with nonmonotone line search to solve the non-decomposable minimax optimization is proposed. We prove that the new algorithm is global Convergent. Numerical results show the proposed algorithm is effective.
文摘In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.
