Search

Nesterov's acceleration in continuous optimization can be understood in a novel way when Nesterov's accelerated gradient (NAG) method is considered as a linear multistep (LM) method for gradient flow. Although the NAG method for strongly convex functions (NAG-sc) has been fully discussed, the NAG method for $L$-smooth convex functions (NAG-c) has not. To fill this gap, we show that the existing NAG-c method can be interpreted as a variable step size LM (VLM) for the gradient flow. Surprisingly, the VLM allows linearly increasing step sizes, which explains the acceleration in the convex case. Here, we introduce a novel technique for analyzing the absolute stability of VLMs. Subsequently, we prove that NAG-c is optimal in a certain natural class of VLMs. Finally, we construct a new broader class of VLMs by optimizing the parameters in the VLM for ill-conditioned problems. According to numerical experiments, the proposed method outperforms the NAG-c method in ill-conditioned cases. These results imply that the numerical analysis perspective of the NAG is a promising working environment, and considering a broader class of VLMs could further reveal novel methods.

Furihata and Matsuo proposed in 2010 an energy-conserving scheme for the Zakharov equations, as an application of the discrete variational derivative method (DVDM). This scheme is distinguished from conventional methods (in particular the one devised by Glassey in 1992) in that the invariants are consistent with respect to time, but it has not been sufficiently studied both theoretically and numerically. In this study, we theoretically prove the solvability under the loosest possible assumptions. We also prove the convergence of this DVDM scheme by improving the argument by Glassey. Furthermore, we perform intensive numerical experiments for comparing the above two schemes. It is found that the DVDM scheme is superior in terms of accuracy, but since it is fully-implicit, the linearly-implicit Glassey scheme is better for practical efficiency. In addition, we proposed a way to choose a solution for the first step that would allow Glassey's scheme to work more efficiently.

We propose a new unified framework for describing and designing gradient-based convex optimization methods from a numerical analysis perspective. There the key is the new concept of weak discrete gradients (weak DGs), which is a generalization of DGs standard in numerical analysis. Via weak DG, we consider abstract optimization methods, and prove unified convergence rate estimates that hold independent of the choice of weak DGs except for some constants in the final estimate. With some choices of weak DGs, we can reproduce many popular existing methods, such as the steepest descent and Nesterov's accelerated gradient method, and also some recent variants from numerical analysis community. By considering new weak DGs, we can easily explore new theoretically-guaranteed optimization methods; we show some examples. We believe this work is the first attempt to fully integrate research branches in optimization and numerical analysis areas, so far independently developed.

This article is a short introduction to numerical methods using the double exponential (DE) transformation, such as tanh-sinh quadrature and DE-Sinc approximation. The DE-based methods for numerical computation have been developed intensively in Japan and the objective of this article is to describe the history in addition to the underlying mathematical ideas., Comment: 10 pages

Some continuous optimization methods can be connected to ordinary differential equations (ODEs) by taking continuous limits, and their convergence rates can be explained by the ODEs. However, since such ODEs can achieve any convergence rate by time scaling, the correspondence is not as straightforward as usually expected, and deriving new methods through ODEs is not quite direct. In this letter, we pay attention to stability restriction in discretizing ODEs and show that acceleration by time scaling basically implies deceleration in discretization; they balance out so that we can define an attainable unique convergence rate which we call an "essential convergence rate".

Recently, various evolutionary partial differential equations (PDEs) with a mixed derivative have been emerged and drawn much attention. Nonetheless, their PDE-theoretical and numerical studies are still in their early stage. In this paper, we aim at the unified framework of numerical methods for such PDEs. However, due to the presence of the mixed derivative, we cannot discuss numerical methods without some appropriate reformulation, which is mathematically challenging itself. Therefore, we first propose a novel procedure for the reformulation of target PDEs into a standard form of evolutionary equations. This contribution may become an important basis not only of numerical analysis, but also of PDE-theory. In order to illustrate this point, we establish the global well-posedness of the sine-Gordon equation. After that, we classify and discuss the spatial discretizations based on the proposed reformulation technique. As a result, we show the average-difference method is suitable for the discretization of the mixed derivative.

We present novel geometric numerical integrators for Hunter--Saxton-like equations by means of new multi-symplectic formulations and known Hamiltonian structures of the problems. We consider the Hunter--Saxton equation, the modified Hunter--Saxton equation, and the two-component Hunter--Saxton equation. Multi-symplectic discretisations based on these new formulations of the problems are exemplified by means of the explicit Euler box scheme, and Hamiltonian-preserving discretisations are exemplified by means of the discrete variational derivative method. We explain and justify the correct treatment of boundary conditions in a unified manner. This is necessary for a proper numerical implementation of these equations and was never explicitly clarified in the literature before, to the best of our knowledge. Finally, numerical experiments demonstrate the favourable behaviour of the proposed numerical integrators.

We consider structure-preserving methods for conservative systems, which rigorously replicate the conservation property yielding better numerical solutions. There, corresponding to the skew-symmetry of the differential operator, that of difference operators is essential to the discrete conservation law. Unfortunately, however, when we employ the standard central difference operator, the simplest one, the numerical solutions often suffer from undesirable spatial oscillations. In this letter, we propose a novel "average-difference method," which is tougher against such oscillations, and combine it with an existing conservative method. Theoretical and numerical analysis in the linear case show the superiority of the proposed method.

The aim of this paper is the derivation of structure preserving schemes for the solution of the EPDiff equation, with particular emphasis on the two dimensional case. We develop three different schemes based on the Discrete Variational Derivative Method (DVDM) on a rectangular domain discretized with a regular, structured, orthogonal grid. We present numerical experiments to support our claims: we investigate the preservation of energy and linear momenta, the reversibility, and the empirical convergence of the schemes. The quality of our schemes is finally tested by simulating the interaction of singular wave fronts., Comment: 41 pages, 41 figures

The numerical integration of the Benjamin and Benjamin--Ono equations are considered. They are non-local partial differential equations involving the Hilbert transform, and due to this, so far quite few structure-preserving integrators have been proposed. In this paper, a new reformulation of the equations is stated, and new structure-preserving discretizations are proposed based on it. Numerical experiments confirm the effectiveness of the proposed integrators.