• Abstract

This article presents an image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem. The algorithm works by solving its equivalent problem, and by using convex hull and concave hull approximation of bilinear function, we can construct the affine relaxation problem of the equivalent problem, which can be used to compute the lower bounds during the branch-and-bound search. By subsequently refining the initial image space rectangle and solving a series of affine relaxation problems, the proposed algorithm is convergent to the global optima of the primal problem. For improving the convergence speed, an image space region reducing method is adopted for compressing the investigated image space rectangle. In addition, the global convergence of the algorithm is proved, and its computational complexity is analyzed. Finally, comparing with some existing methods, numerical results indicate that the algorithm has better computational performance.

• General Summary

• Abstract

In this paper, we consider the numerical solution of decoupled mean-field forward backward stochastic differential equations with jumps (MFBSDEJs). By using finite difference approximations and the Gaussian quadrature rule, and the weak order 2.0 Itô-Taylor scheme to solve the forward mean-field SDEs with jumps, we propose a new second order scheme for MFBSDEJs. The proposed scheme allows an easy implementation. Some numerical experiments are carried out to demonstrate the stability, the effectiveness and the second order accuracy of the scheme.

• General Summary

• Abstract

Fractional Klein-Kramers equation can well describe subdiffusion in phase space. In this paper, we develop the fully discrete scheme for time-fractional Klein-Kramers equation based on the backward Euler convolution quadrature and local discontinuous Galerkin methods. Thanks to the obtained sharp regularity estimates in temporal and spatial directions after overcoming the hypocoercivity of the operator, the complete error analyses of the fully discrete scheme are built. It is worth mentioning that the convergence of the provided scheme is independent of the temporal regularity of the exact solution. Finally, numerical results are proposed to verify the correctness of the theoretical results.

• General Summary

• Abstract

Recently, the numerical methods for long-time dynamics of PDEs with weak nonlinearity have received more and more attention. For the nonlinear Schrödinger equation (NLS) with wave operator (NLSW) and weak nonlinearity controlled by a small value $\varepsilon∈ (0, 1],$ an exponential wave integrator Fourier pseudo-spectral (EWIFP) discretization has been developed (Guo et al., 2021) and proved to be uniformly accurate about $\varepsilon$ up to the time at $\mathcal{O}(1/\varepsilon^2).$ However, the EWIFP method is not time symmetric and can not preserve the discrete energy. As we know, the time symmetry and energy-preservation are the important structural features of the true solution and we hope that this structure can be inherited along the numerical solution. In this work, we propose a time symmetric and energy-preserving exponential wave integrator Fourier pseudo-spectral (SEPEWIFP) method for the NLSW with periodic boundary conditions. Through rigorous error analysis, we establish uniform error bounds of the numerical solution at $\mathcal{O}(h^{m_0} + \varepsilon^{2−\beta_{\tau^2}})$ up to the time at $\mathcal{O}(1/\varepsilon^\beta)$ for $\beta ∈ [0, 2],$ where $h$ and $\tau$ are the mesh size and time step, respectively, and $m_0$ depends on the regularity conditions. The tools for error analysis mainly include cut-off technique and the standard energy method. We also extend the results on error bounds, energy-preservation and time symmetry to the oscillatory NLSW with wavelength at $\mathcal{O}(\varepsilon^2)$ in time which is equivalent to the NLSW with weak nonlinearity. Numerical experiments confirm that the theoretical results in this paper are correct. Our method is novel because that to the best of our knowledge there has not been any energy-preserving exponential wave integrator method for the NLSW.

• General Summary

• Abstract

In this paper, we analyze the convergence properties of a stochastic augmented Lagrangian method for solving stochastic convex programming problems with inequality constraints. Approximation models for stochastic convex programming problems are constructed from stochastic observations of real objective and constraint functions. Based on relations between solutions of the primal problem and solutions of the dual problem, it is proved that the convergence of the algorithm from the perspective of the dual problem. Without assumptions on how these random models are generated, when estimates are merely sufficiently accurate to the real objective and constraint functions with high enough, but fixed, probability, the method converges globally to the optimal solution almost surely. In addition, sufficiently accurate random models are given under different noise assumptions. We also report numerical results that show the good performance of the algorithm for different convex programming problems with several random models.

• General Summary

• Abstract

In this paper, we study a posteriori error estimates of the L1 scheme for time discretizations of time fractional parabolic differential equations, whose solutions have generally the initial singularity. To derive optimal order a posteriori error estimates, the quadratic reconstruction for the L1 method and the necessary fractional integral reconstruction for the first-step integration are introduced. By using these continuous, piecewise time reconstructions, the upper and lower error bounds depending only on the discretization parameters and the data of the problems are derived. Various numerical experiments for the one-dimensional linear fractional parabolic equations with smooth or nonsmooth exact solution are used to verify and complement our theoretical results, with the convergence of α order for the nonsmooth case on a uniform mesh. To recover the optimal convergence order $2−α$ on a nonuniform mesh, we further develop a time adaptive algorithm by means of barrier function recently introduced. The numerical implementations are performed on nonsmooth case again and verify that the true error and a posteriori error can achieve the optimal convergence order in adaptive mesh.

• General Summary

• Abstract

A time multipoint nonlocal problem for a Schrödinger equation driven by a cylindrical $Q$-Wiener process is presented. The initial value depends on a finite number of future values. Existence and uniqueness of a solution formulated as a mild solution is obtained. A single-step implicit Euler-Maruyama difference scheme, a Rothe-Maryuama scheme, is suggested as a numerical solution. Convergence rate for the solution of the difference scheme is established. The theoretical statements for the solution of this difference scheme is supported by a numerical example.

• General Summary

• Abstract

This paper is concerned with the inverse problem of scattering of time-harmonic acoustic waves by an inhomogeneous cavity. We shall develop a modified factorization method to reconstruct the shape and location of the interior interface of the inhomogeneous cavity by means of many internal measurements of the near-field data. Numerical examples are carried out to illustrate the practicability of the inversion algorithm.

• General Summary

• Abstract

In this paper, we consider the electromagnetic wave scattering problem from a periodic chiral structure. The scattering problem is simplified to a two-dimensional problem, and is discretized by a finite volume method combined with the perfectly matched layer (PML) technique. A residual-type a posteriori error estimate of the PML finite volume method is analyzed and the upper and lower bounds on the error are established in the $H^1$-norm. The crucial part of the a posteriori error analysis is to derive the error representation formula and use a $L^2$-orthogonality property of the residual which plays a similar role as the Galerkin orthogonality. An adaptive PML finite volume method is proposed to solve the scattering problem. The PML parameters such as the thickness of the layer and the medium property are determined through sharp a posteriori error estimate. Finally, numerical experiments are presented to illustrate the efficiency of the proposed method.

• General Summary

• Abstract

The system of generalized absolute value equations (GAVE) has attracted more and more attention in the optimization community. In this paper, by introducing a smoothing function, we develop a smoothing Newton algorithm with non-monotone line search to solve the GAVE. We show that the non-monotone algorithm is globally and locally quadratically convergent under a weaker assumption than those given in most existing algorithms for solving the GAVE. Numerical results are given to demonstrate the viability and efficiency of the approach.

• General Summary

• Abstract

In this paper, we establish the oracle inequalities of highly corrupted linear observations $b = Ax_0 + f_0 + e ∈ \mathbb{R}^m.$ Here the vector $x_0 ∈ \mathbb{R}^n$ with $n ≫ m$ is a (approximately) sparse signal and $f_0 ∈ \mathbb{R}^m$ is a sparse error vector with nonzero entries that can be possible infinitely large, $e ∼\mathcal{ N} (0, σ^2 I_m)$ represents the Gaussian random noise vector. We extend the oracle inequality $||\hat{x}-x_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}$ for Dantzig selector and Lasso models in [E.J. Candès and T. Tao, Ann. Statist., 35 (2007), 2313–2351] and [T.T. Cai, L. Wang, and G. Xu, IEEE Trans. Inf. Theory, 56 (2010), 3516–3522] to $||\hat{x}-x_0||^2_2+||\hat{f}-f_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}+\sum_j{\rm min}\{|\lambda f_0(j)|^2,\sigma^2\}$ for the extended Dantzig selector and Lasso models. Here $(\hat{x}, \hat{f})$ is the solution of the extended model, and $λ > 0$ is the balance parameter between $||x||_1$ and $||f||_1$ i.e. $||x||_1+\lambda||f||_1.$

• General Summary

• Abstract

The numerical integration of phase-field equations is a delicate task which needs to recover at the discrete level intrinsic properties of the solution such as energy dissipation and maximum principle. Although the theory of energy dissipation for classical phase field models is well established, the corresponding theory for time-fractional phase-field models is still incomplete. In this article, we study certain nonlocal-in-time energies using the first-order stabilized semi-implicit L1 scheme. In particular, we will establish a discrete fractional energy law and a discrete weighted energy law. The extension for a $(2−α)$-order L1 scalar auxiliary variable scheme will be investigated. Moreover, we demonstrate that the energy bound is preserved for the L1 schemes with nonuniform time steps. Several numerical experiments are carried to verify our theoretical analysis.

• General Summary

• Abstract

Image restoration based on total variation has been widely studied owing to its edge-preservation properties. In this study, we consider the total variation infimal convolution (TV-IC) image restoration model for eliminating mixed Poisson-Gaussian noise. Based on the alternating direction method of multipliers (ADMM), we propose a complete splitting proximal bilinear constraint ADMM algorithm to solve the TV-IC model. We prove the convergence of the proposed algorithm under mild conditions. In contrast with other algorithms used for solving the TV-IC model, the proposed algorithm does not involve any inner iterations, and each subproblem has a closed-form solution. Finally, numerical experimental results demonstrate the efficiency and effectiveness of the proposed algorithm.

• General Summary

• Abstract

A fundamental problem in some applications including group testing and communications is to acquire the support of a $K$-sparse signal $x,$ whose nonzero elements are 1, from an underdetermined noisy linear model. This paper first designs an algorithm called binary least squares (BLS) to reconstruct $x$ and analyzes its complexity. Then, we establish two sufficient conditions for the exact reconstruction of $x$’s support with $K$ iterations of BLS based on the mutual coherence and restricted isometry property of the measurement matrix, respectively. Finally, extensive numerical tests are performed to compare the efficiency and effectiveness of BLS with those of batch orthogonal matching pursuit (Batch-OMP) which to our best knowledge is the fastest implementation of OMP, orthogonal least squares (OLS), compressive sampling matching pursuit (CoSaMP), hard thresholding pursuit (HTP), Newton-step-based iterative hard thresholding (NSIHT), Newton-step-based hard thresholding pursuit (NSHTP), binary matching pursuit (BMP) and $ℓ_1$-regularized least squares. Test results show that: (1) BLS can be 10-200 times more efficient than Batch-OMP, OLS, CoSaMP, HTP, NSIHT and NSHTP with higher probability of support reconstruction, and the improvement can be 20%-80%; (2) BLS has more than 25% improvement on the support reconstruction probability than the explicit BMP algorithm with a little higher computational complexity; (3) BLS is around 100 times faster than $ℓ_1$-regularized least squares with lower support reconstruction probability for small $K$ and higher support reconstruction probability for large $K.$ Numerical tests on the generalized space shift keying (GSSK) detection indicate that although BLS is a little slower than BMP, it is more efficient than the other seven tested sparse recovery algorithms, and although it is less effective than $ℓ_1$-regularized least squares, it is more effective than the other seven algorithms.

• General Summary

• Abstract

This paper investigates a semilinear stochastic fractional Rayleigh-Stokes equation featuring a Riemann-Liouville fractional derivative of order $α ∈ (0, 1)$ in time and a fractional time-integral noise. The study begins with an examination of the solution’s existence, uniqueness, and regularity. The spatial discretization is then carried out using a finite element method, and the error estimate is analyzed. A convolution quadrature method generated by the backward Euler method is employed for the time discretization resulting in a fully discrete scheme. The error estimate for the fully discrete solution is considered based on the regularity of the solution, and a strong convergence rate is established. The paper concludes with numerical tests to validate the theoretical findings.

• General Summary

• Abstract

This work focuses on the temporal average of the backward Euler-Maruyama (BEM) method, which is used to approximate the ergodic limit of stochastic ordinary differential equations (SODEs). We give the central limit theorem (CLT) of the temporal average of the BEM method, which characterizes its asymptotics in distribution. When the deviation order is smaller than the optimal strong order, we directly derive the CLT of the temporal average through that of original equations and the uniform strong order of the BEM method. For the case that the deviation order equals to the optimal strong order, the CLT is established via the Poisson equation associated with the generator of original equations. Numerical experiments are performed to illustrate the theoretical results. The main contribution of this work is to generalize the existing CLT of the temporal average of numerical methods to that for SODEs with super-linearly growing drift coefficients.

• General Summary

• Abstract

In this paper, we consider numerical solutions of the fractional diffusion equation with the $α$ order time fractional derivative defined in the Caputo-Hadamard sense. A high order time-stepping scheme is constructed, analyzed, and numerically validated. The contribution of the paper is twofold: 1) regularity of the solution to the underlying equation is investigated, 2) a rigorous stability and convergence analysis for the proposed scheme is performed, which shows that the proposed scheme is $3 + α$ order accurate. Several numerical examples are provided to verify the theoretical statement.

• General Summary

• Abstract

This paper presents three regularized models for the logarithmic Klein-Gordon equation. By using a modified Crank-Nicolson method in time and the Galerkin finite element method (FEM) in space, a fully implicit energy-conservative numerical scheme is constructed for the local energy regularized model that is regarded as the best one among the three regularized models. Then, the cut-off function technique and the time-space error splitting technique are innovatively combined to rigorously analyze the unconditionally optimal and high-accuracy convergence results of the numerical scheme without any coupling condition between the temporal step size and the spatial mesh width. The theoretical framework is uniform for the other two regularized models. Finally, numerical experiments are provided to verify our theoretical results. The analytical techniques in this work are not limited in the FEM, and can be directly extended into other numerical methods. More importantly, this work closes the gap for the unconditional error/stability analysis of the numerical methods for the logarithmic systems in higher dimensional spaces.

• General Summary

• Abstract

We design and analyze an iterative two-grid algorithm for the finite element discretizations of strongly nonlinear elliptic boundary value problems in this paper. We propose an iterative two-grid algorithm, in which a nonlinear problem is first solved on the coarse space, and then a symmetric positive definite problem is solved on the fine space. The main contribution in this paper is to establish a first convergence analysis, which requires dealing with four coupled error estimates, for the iterative two-grid methods. We also present some numerical experiments to confirm the efficiency of the proposed algorithm.

• General Summary

• Abstract

This paper is concerned with the numerical solution of Volterra integro-differential equations with noncompact operators. The focus is on the problems with weakly singular solutions. To handle the initial weak singularity of the solution, a fractional collocation method is applied. A rigorous $hp$-version error analysis of the numerical method under a weighted $H^1$-norm is carried out. The result shows that the method can achieve high order convergence for such equations. Numerical experiments are also presented to confirm the effectiveness of the proposed method.

• General Summary