In this paper,accelerated saddle point dynamics is proposed for distributed resource allocation over a multi-agent network,which enables a hyper-exponential convergence rate.Specifically,an inertial fast-slow dynamica...In this paper,accelerated saddle point dynamics is proposed for distributed resource allocation over a multi-agent network,which enables a hyper-exponential convergence rate.Specifically,an inertial fast-slow dynamical system with vanishing damping is introduced,based on which the distributed saddle point algorithm is designed.The dual variables are updated in two time scales,i.e.,the fast manifold and the slow manifold.In the fast manifold,the consensus of the Lagrangian multipliers and the tracking of the constraints are pursued by the consensus protocol.In the slow manifold,the updating of the Lagrangian multipliers is accelerated by inertial terms.Hyper-exponential stability is defined to characterize a faster convergence of our proposed algorithm in comparison with conventional primal-dual algorithms for distributed resource allocation.The simulation of the application in the energy dispatch problem verifies the result,which demonstrates the fast convergence of the proposed saddle point dynamics.展开更多
Langevin simulation of the particles multi-passing over the saddle point is proposed to calculate thermal fission rate. Due to finite friction and the corresponding thermal fluctuation, a backstreaming exists in the p...Langevin simulation of the particles multi-passing over the saddle point is proposed to calculate thermal fission rate. Due to finite friction and the corresponding thermal fluctuation, a backstreaming exists in the process of the particle descent from the saddle to the scission. This leads to that the diffusion behind the saddle point has influence upon the stationary flow across the saddle point. A dynamical correction factor, as a ratio of the flows of multi- and first-overpassing the saddle point, is evaluated analytically. The results show that the fission rate calculated by the particles multi-passing over the saddle point is lower than the one calculated by the particle firstly passing over the saddle point, and the former approaches the results at the scission point.展开更多
We prove probabilistic error estimates for high-index saddle dynamics with or without constraints to account for the inaccurate values of the model,which could be encountered in various scenarios such as model uncerta...We prove probabilistic error estimates for high-index saddle dynamics with or without constraints to account for the inaccurate values of the model,which could be encountered in various scenarios such as model uncertainties or surrogate model algorithms via machine learning methods. The main contribution lies in incorporating the probabilistic error bound of the model values with the conventional error estimate methods for high-index saddle dynamics. The derived results generalize the error analysis of deterministic saddle dynamics and characterize the affect of the inaccuracy of the model on the convergence rate.展开更多
We develop and analyze numerical discretization to the constrained high-index saddle dynamics,the dynamics searching for the high-index saddle points confined on the high-dimensional unit sphere.Compared with the sadd...We develop and analyze numerical discretization to the constrained high-index saddle dynamics,the dynamics searching for the high-index saddle points confined on the high-dimensional unit sphere.Compared with the saddle dynamics without constraints,the constrained high-index saddle dynamics has more complex dynamical forms,and additional operations such as the retraction and vector transport are required due to the constraints,which significantly complicate the numerical scheme and the corresponding numerical analysis.Furthermore,as the existing numerical analysis results usually depend on the index of the saddle points implicitly,the proved numerical accuracy may be reduced if the index is high in many applications,which indicates the lack of robustness with respect to the index.To address these issues,we derive the error estimates for numerical discretization of the constrained high-index saddle dynamics on the high-dimensional sphere and then improve it by providing index-robust error analysis in an averaged norm by adjusting the relaxation parameters.The developed results provide mathematical support for the accuracy of numerical computations.展开更多
The authors prove error estimates for the semi-implicit numerical scheme of sphere-constrained high-index saddle dynamics,which serves as a powerful instrument in finding saddle points and constructing the solution la...The authors prove error estimates for the semi-implicit numerical scheme of sphere-constrained high-index saddle dynamics,which serves as a powerful instrument in finding saddle points and constructing the solution landscapes of constrained systems on the high-dimensional sphere.Due to the semi-implicit treatment and the novel computational procedure,the orthonormality of numerical solutions at each time step could not be fully employed to simplify the derivations,and the computations of the state variable and directional vectors are coupled with the retraction,the vector transport and the orthonormalization procedure,which significantly complicates the analysis.They address these issues to prove error estimates for the proposed semi-implicit scheme and then carry out numerical experiments to substantiate the theoretical findings.展开更多
We introduce a generalized numerical algorithm to construct the solution landscape,which is a pathway map consisting of all the stationary points and their connections.Based on the high-index optimizationbased shrinki...We introduce a generalized numerical algorithm to construct the solution landscape,which is a pathway map consisting of all the stationary points and their connections.Based on the high-index optimizationbased shrinking dimer(Hi OSD)method for gradient systems,a generalized high-index saddle dynamics(GHi SD)is proposed to compute any-index saddles of dynamical systems.Linear stability of the index-k saddle point can be proved for the GHi SD system.A combination of the downward search algorithm and the upward search algorithm is applied to systematically construct the solution landscape,which not only provides a powerful and efficient way to compute multiple solutions without tuning initial guesses,but also reveals the relationships between different solutions.Numerical examples,including a three-dimensional example and the phase field model,demonstrate the novel concept of the solution landscape by showing the connected pathway maps.展开更多
基金supported by the National Natural Science Foundation of China(61773172)supported in part by the Australian Research Council(DP200101197,DE210100274)。
文摘In this paper,accelerated saddle point dynamics is proposed for distributed resource allocation over a multi-agent network,which enables a hyper-exponential convergence rate.Specifically,an inertial fast-slow dynamical system with vanishing damping is introduced,based on which the distributed saddle point algorithm is designed.The dual variables are updated in two time scales,i.e.,the fast manifold and the slow manifold.In the fast manifold,the consensus of the Lagrangian multipliers and the tracking of the constraints are pursued by the consensus protocol.In the slow manifold,the updating of the Lagrangian multipliers is accelerated by inertial terms.Hyper-exponential stability is defined to characterize a faster convergence of our proposed algorithm in comparison with conventional primal-dual algorithms for distributed resource allocation.The simulation of the application in the energy dispatch problem verifies the result,which demonstrates the fast convergence of the proposed saddle point dynamics.
基金The project supported by National Natural Science Foundation of China under Grant Nos.10075007 and 10235020
文摘Langevin simulation of the particles multi-passing over the saddle point is proposed to calculate thermal fission rate. Due to finite friction and the corresponding thermal fluctuation, a backstreaming exists in the process of the particle descent from the saddle to the scission. This leads to that the diffusion behind the saddle point has influence upon the stationary flow across the saddle point. A dynamical correction factor, as a ratio of the flows of multi- and first-overpassing the saddle point, is evaluated analytically. The results show that the fission rate calculated by the particles multi-passing over the saddle point is lower than the one calculated by the particle firstly passing over the saddle point, and the former approaches the results at the scission point.
基金supported by the National Natural Science Foundation of China(Nos.12225102,T2321001,12288101 and 12301555)the National Key R&D Program of China(Nos.2021YFF1200500 and 2023YFA1008903)the Taishan Scholars Program of Shandong Province(No.tsqn202306083).
文摘We prove probabilistic error estimates for high-index saddle dynamics with or without constraints to account for the inaccurate values of the model,which could be encountered in various scenarios such as model uncertainties or surrogate model algorithms via machine learning methods. The main contribution lies in incorporating the probabilistic error bound of the model values with the conventional error estimate methods for high-index saddle dynamics. The derived results generalize the error analysis of deterministic saddle dynamics and characterize the affect of the inaccuracy of the model on the convergence rate.
基金supported by National Natural Science Foundation of China(Grant Nos.12225102,12050002 and 12288101)the National Key Research and Development Program of China(Grant No.2021YFF1200500).
文摘We develop and analyze numerical discretization to the constrained high-index saddle dynamics,the dynamics searching for the high-index saddle points confined on the high-dimensional unit sphere.Compared with the saddle dynamics without constraints,the constrained high-index saddle dynamics has more complex dynamical forms,and additional operations such as the retraction and vector transport are required due to the constraints,which significantly complicate the numerical scheme and the corresponding numerical analysis.Furthermore,as the existing numerical analysis results usually depend on the index of the saddle points implicitly,the proved numerical accuracy may be reduced if the index is high in many applications,which indicates the lack of robustness with respect to the index.To address these issues,we derive the error estimates for numerical discretization of the constrained high-index saddle dynamics on the high-dimensional sphere and then improve it by providing index-robust error analysis in an averaged norm by adjusting the relaxation parameters.The developed results provide mathematical support for the accuracy of numerical computations.
基金supported by the National Natural Science Foundation of China(Nos.12225102,12050002,12288101,12301555)the National Key R&D Program of China(No.2021YFF1200500)the Taishan Scholars Program of Shandong Province。
文摘The authors prove error estimates for the semi-implicit numerical scheme of sphere-constrained high-index saddle dynamics,which serves as a powerful instrument in finding saddle points and constructing the solution landscapes of constrained systems on the high-dimensional sphere.Due to the semi-implicit treatment and the novel computational procedure,the orthonormality of numerical solutions at each time step could not be fully employed to simplify the derivations,and the computations of the state variable and directional vectors are coupled with the retraction,the vector transport and the orthonormalization procedure,which significantly complicates the analysis.They address these issues to prove error estimates for the proposed semi-implicit scheme and then carry out numerical experiments to substantiate the theoretical findings.
基金supported by National Natural Science Foundation of China(Grant No.11861130351)the support from the Elite Program of Computational and Applied Mathematics for Ph D Candidates of Peking University。
文摘We introduce a generalized numerical algorithm to construct the solution landscape,which is a pathway map consisting of all the stationary points and their connections.Based on the high-index optimizationbased shrinking dimer(Hi OSD)method for gradient systems,a generalized high-index saddle dynamics(GHi SD)is proposed to compute any-index saddles of dynamical systems.Linear stability of the index-k saddle point can be proved for the GHi SD system.A combination of the downward search algorithm and the upward search algorithm is applied to systematically construct the solution landscape,which not only provides a powerful and efficient way to compute multiple solutions without tuning initial guesses,but also reveals the relationships between different solutions.Numerical examples,including a three-dimensional example and the phase field model,demonstrate the novel concept of the solution landscape by showing the connected pathway maps.
