Search

In this paper, we propose a constraint preserving algorithm for the smallest Z-eigenpair of the compact Laplacian tensor of an even-uniform hypergraph, where Householder transform is employed and a family of modified conjugate directions with sufficient descent is determined. Besides, we prove that there exists a positive step size in the new constraint preserving update scheme such that the Wolfe conditions hold. Based on these properties, we prove the convergence of the new algorithm. Furthermore, we apply our algorithm to the hypergraph partitioning and image segmentation, and numerical results are reported to illustrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) is an efficient solution method for block separable convex programming. To enhance the robustness of the method, the proximal technique is introduced into the minimization subproblems of the ADMM which yields a proximal ADMM method. There are two factors involved in the proximal ADMM method, one is the linearization factor and the other is the relaxation factor. Due to the importance of the two factors in numerical acceleration, this paper considers the relaxation and the optimal choice of the two factors, and presents a relaxed proximal ADMM method for block separable convex programming. The global convergence of the method is established under weaker conditions. Preliminary numerical experiments are made to illustrate the efficiency of designed method. [ABSTRACT FROM AUTHOR]

In this paper, we present a new nonsmooth Newton-type algorithm for solving the generalized complementarity problem based on its reformulation as a system of nonlinear equations using a one-parametric family of complementarity functions. We demonstrate, under suitable hypotheses, that this algorithm converges locally and q-quadratically. In addition, we show numerical experiments that allow us to see the good performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method of using the theory of functional connections (TFC) to approximate the solution of fractional differential equations. For functions with one constraint at one point, several constraints at one point, distinct points, and relative constraints, the theoretical approach of the suggested method is investigated. The choice of the basis function is described, and the issue of using monomials is discussed. For the first time in the literature, the suggested method is used to solve fractional differential initial value problems, boundary value problems, and higher-order problems. Wherever the exact solution exists, the numerical results are compared. The numerical findings for the fractional order scenario are compared with the predictor-corrector method and polynomial least squares method. The error plot for the integer order case with the exact solution is also provided. The proposed approach is also used to solve a corneal shape model. [ABSTRACT FROM AUTHOR]

Convergence and convergence rate analyses of adaptive methods, such as Adaptive Moment Estimation (Adam) and its variants, have been widely studied for nonconvex optimization. The analyses are based on assumptions that the expected or empirical average loss function is Lipschitz smooth (i.e., its gradient is Lipschitz continuous) and the learning rates depend on the Lipschitz constant of the Lipschitz continuous gradient. Meanwhile, numerical evaluations of Adam and its variants have clarified that using small constant learning rates without depending on the Lipschitz constant and hyperparameters ( β 1 and β 2 ) close to one is advantageous for training deep neural networks. Since computing the Lipschitz constant is NP-hard, the Lipschitz smoothness condition would be unrealistic. This paper provides theoretical analyses of Adam without assuming the Lipschitz smoothness condition in order to bridge the gap between theory and practice. The main contribution is to show theoretical evidence that Adam using small learning rates and hyperparameters close to one performs well, whereas the previous theoretical results were all for hyperparameters close to zero. Our analysis also leads to the finding that Adam performs well with large batch sizes. Moreover, we show that Adam performs well when it uses diminishing learning rates and hyperparameters close to one. [ABSTRACT FROM AUTHOR]

Let a network be represented by a simple graph G with n vertices. A common approach to investigate properties of a network is to use the adjacency matrix A = [ a ij ] i , j = 1 n ∈ R n × n associated with the graph G , where a ij > 0 if there is an edge pointing from vertex v i to vertex v j , and a ij = 0 otherwise. Both A and its positive integer powers reveal important properties of the graph. This paper proposes to study properties of a graph G by also using the path length matrix for the graph. The (i j) th entry of the path length matrix is the length of the shortest path from vertex v i to vertex v j ; if there is no path between these vertices, then the value of the entry is ∞ . Powers of the path length matrix are formed by using min-plus matrix multiplication and are important for exhibiting properties of G . We show how several known measures of communication such as closeness centrality, harmonic centrality, and eccentricity are related to the path length matrix, and we introduce new measures of communication, such as the harmonic K-centrality and global K-efficiency, where only (short) paths made up of at most K edges are taken into account. The sensitivity of the global K-efficiency to changes of the entries of the adjacency matrix also is considered. [ABSTRACT FROM AUTHOR]

In this paper, we provide a numerical solution for the nonlinear tempered fractional integrodifferential equation in three dimensions. We use the trapezoidal convolution rule with backward differences (BDF2) for temporal discretization, and develop an alternating direction implicit difference scheme for spatial discretization. A novel fast approximation is applied to tackle the nonlinear term. The stability and convergence analysis of the numerical scheme are analyzed. Furthermore, some numerical experiments are provided to confirm the theoretical results. [ABSTRACT FROM AUTHOR]

Extrapolation, restart and stepsize are very powerful strategies for accelerating the convergence rates of first-order algorithms. In this paper, we propose a modified accelerated proximal gradient algorithm (modAPG), which incorporates the adaptive nonmonotone stepsize strategy, extrapolation and a modified rule of setting the extrapolation parameter to zero at some iterations, for solving a minimization problem composed of a smooth (possibly nonconvex) with Lipschitz continuous gradient and nonsmooth (possibly nonconvex) function. Moreover, the proposed algorithm has a simpler form for this problem with convex setting. We show that any cluster point of the sequence generated by modAPG is a critical point of the problem, and analyze the convergence rates of function values and iterates under the assumption that objective function has the Kurdyka-Łojasiewicz property. Finally, we conduct some preliminary numerical experiments for solving the convex problems, such as image deblurring problem and sparse logistic regression problem; and the nonconvex regularization problem, such as the L 1 2 penalty and the smoothly clipped absolute deviation (SCAD) penalty problem. Numerical experiments demonstrate the promising performance of the proposed method. [ABSTRACT FROM AUTHOR]

In the present paper, a parallel-in-time discretization of linear systems of Volterra equations of type u ¯ (t) = u ¯ 0 + ∫ 0 t K (t - s) u ¯ (s) d s + f ¯ (t) , 0 < t ≤ T , is addressed. Related to the analytical solution, a general enough functional setting is firstly stated. Related to the numerical solution, a parallel numerical scheme based on the Non-Stationary Wave Relaxation (NSWR) method for the time discretization is proposed, and its convergence is studied as well. A CUDA parallel implementation of the method is carried out in order to exploit Graphics Processing Units (GPUs), which are nowadays widely employed for reducing the computational time of several general purpose applications. The performance of these methods is compared to some sequential implementation. It is revealed throughout several experiments of special interest in practical applications the good performance of the parallel approach. [ABSTRACT FROM AUTHOR]

Trigonometric box splines can be considered as the multivariate generalizations of univariate B-splines. This means multivariate trigonometric box splines can be constructed from univariate trigonometric B-splines by suitable adaptive methods. Mainly, this paper is concerned with the construction of a new class of bivariate trigonometric box spline functions with the help of trigonometric B-splines through directional convolution method. These are refinable functions and some of their properties are also investigated. Secondly, a new effective non-stationary subdivision scheme is derived from the two-scale relationship of a particular trigonometric box spline. The non-stationary subdivision scheme is capable of producing such trigonometric box spline surfaces in regular regions. Some important properties along with the interactive modeling capability of this subdivision scheme are described in detail. [ABSTRACT FROM AUTHOR]

This paper aims to estimate the parameters of the time-fractional Black-Scholes (TFBS) partial differential equation with the Caputo fractional derivative by using the real option prices of the S &P 500 index options. First, the numerical solution is obtained by developing a high-order scheme with order ( 3 - α ) for the time discretisation. Some theoretical analyses such as stability and convergence are presented in order to verify the efficiency and accuracy of the proposed scheme. Secondly, we employ a modified hybrid Nelder-Mead simplex search and particle swarm optimization (MH-NMSS-PSO) to identify the fractional order α and implied volatility σ of the TFBS equation, and explore the financial meanings of α under extreme stock market conditions such as the Covid-19 and the 2008 global financial crisis. We analyse the values of α and compare the mean squared errors of both the TFBS model and the BS model. Our empirical results show that α may be regarded as a market fluctuation indicator for classifying financial environments, and the TFBS model is more capable of fitting real option data compared with the BS model, especially for put options during the economic downturn. In addition, we find and discuss an interesting relation between α and σ from both the TFBS model and the BS model in three expressions, which could be an open problem for further research. [ABSTRACT FROM AUTHOR]

In this paper, a fractional optimal control problem with fractional Laplacian and integral state constraint is investigated. The first-order optimality system and regularity of the solutions to optimal control problem are derived. Piecewise linear finite element method combined with variational discretization approach is used to approximate the optimal control problem. A priori error estimates for finite element approximation of the state, adjoint state and control variable are derived. Numerical examples are given to illustrate the theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of structured nonconvex nonsmooth optimization problems, in which the objective function is formed by the sum of a possibly nonsmooth nonconvex function and a differentiable function with Lipschitz continuous gradient, subtracted by a weakly convex function. This general framework allows us to tackle problems involving nonconvex loss functions and problems with specific nonconvex constraints, and it has many applications such as signal recovery, compressed sensing, and optimal power flow distribution. We develop a proximal subgradient algorithm with extrapolation for solving these problems with guaranteed subsequential convergence to a stationary point. The convergence of the whole sequence generated by our algorithm is also established under the widely used Kurdyka–Łojasiewicz property. To illustrate the promising numerical performance of the proposed algorithm, we conduct numerical experiments on two important nonconvex models. These include a compressed sensing problem with a nonconvex regularization and an optimal power flow problem with distributed energy resources. [ABSTRACT FROM AUTHOR]

A modular string averaging procedure (MSA, for short) for a finite number of operators was first introduced by Reich and Zalas in 2016. The MSA concept provides a flexible algorithmic framework for solving various feasibility problems such as common fixed point and convex feasibility problems. In 2001 Bauschke and Combettes introduced the notion of coherence and applied it to proving weak and strong convergence of many iterative methods. In 2019 Barshad, Reich and Zalas proposed a stronger variant of coherence which provides a more convenient sufficient convergence condition for such methods. In this paper we combine the ideas of both modular string averaging and coherence. Focusing on extending the above MSA procedure to an infinite sequence of operators with admissible controls, we establish strong coherence of its output operators. Various applications of these concepts are presented with respect to weak and strong convergence. They also provide important generalizations of known results, where the weak convergence of sequences of operators generated by the MSA procedure with intermittent controls was considered. [ABSTRACT FROM AUTHOR]

In this paper, some local and parallel finite element methods based on two-grid discretizations are provided and studied for the non-stationary Stokes-Darcy model with the Beavers-Joseph interface condition. Two local algorithms, the semi-discrete and fully discrete finite element algorithms, are first introduced and related error estimates are rigorously derived. Based upon the fully discrete local algorithm, two fully discrete parallel algorithms are subsequently developed. The backward Euler scheme is considered for the temporal discretization and finite element method is used for the spatial discretization. The main idea of the parallel algorithms is to solve a decoupled Stokes-Darcy model via a coarse grid on the whole domain, then solve residual equations with a finer grid on overlapped subdomains by some local and parallel procedures at each time step. Some local a priori error is also provided that is crucial to our theoretical analysis. Finally, some numerical results are reported to illustrate the validity of the algorithms. [ABSTRACT FROM AUTHOR]

In the financial market, the change in price of underlying stock following fractal transmission system is modeled by time-fractional Black-Scholes partial differential equations (PDEs). In this paper, we propose a numerical scheme on uniform mesh for solving time-fractional Black-Scholes PDEs governing European options. The fractional time derivative defined in the Caputo sense is discretized by using the classical L1-scheme and the spatial derivatives are discretized by the cubic spline method. The stability and convergence of the proposed method are analyzed and shown to be second order accurate in space with (2 - α) order accuracy in time. Two numerical examples with exact solutions are presented to verify the efficiency and accuracy of the method validating the theoretical results. Finally, three different types of European options governed by time-fractional Black-Scholes PDE are priced using our proposed method as an application. Further, the impact of the order of time-fractional derivative on the option price is shown. [ABSTRACT FROM AUTHOR]

In this paper, we focus on developing a high efficient algorithm for solving d-dimension time-fractional diffusion equation (TFDE). For TFDE, the initial function or source term is usually not smooth, which can lead to the low regularity of exact solution. And such low regularity has a marked impact on the convergence rate of numerical method. In order to improve the convergence rate of the algorithm, we introduce the space-time sparse grid (STSG) method to solve TFDE. In our study, we employ the sine basis and the linear element basis for spatial discretization and temporal discretization, respectively. The sine basis can be divided into several levels, and the linear element basis can lead to the hierarchical basis. Then, the STSG can be constructed through a special tensor product of the spatial multilevel basis and the temporal hierarchical basis. Under certain conditions, the function approximation on standard STSG can achieve the accuracy order O (2 - J J) with O (2 J J) degrees of freedom (DOF) for d = 1 and O (2 Jd) DOF for d > 1 , where J denotes the maximal level of sine coefficients. However, if the solution changes very rapidly at the initial moment, the standard STSG method may reduce accuracy or even fail to converge. To overcome this, we integrate the full grid into the STSG, and obtain the modified STSG. Finally, we obtain the fully discrete scheme of STSG method for solving TFDE. The great advantage of the modified STSG method can be shown in the comparative numerical experiment. [ABSTRACT FROM AUTHOR]

For solving nonlinear monotone equations with convex constraints, Liu and Feng (Numer. Algoritm. 82(1):245–262, 2019) suggested a derivative-free iterative technique. Although they assert that the direction d k satisfies inequality (2.1), however, this is not true, as the derivation of the parameter θ k given by equation (2.7) is not correct. This led to Lemma 2.2, Lemma 3.1 and Theorem 3.1 in Liu and Feng (Numer. Algoritm. 82(1):245–262, 2019) not holding. In addition, Theorem 3.1 is still invalid as the bound for ‖ F (x k + α k ′ d k) ‖ was not established by the authors, instead the authors used the bound for ‖ F (x k + α k d k) ‖ as the bound for ‖ F (x k + α k ′ d k) ‖ . In this paper, We first describe the necessary adjustments and establish the bound for ‖ F (x k + α k ′ d k) ‖ , after which the proposed approach by Liu and Feng continues to converge globally. In addition, we provide some numerical results to support the adjustments. [ABSTRACT FROM AUTHOR]

In this paper, we consider the backward problem for a time fractional diffusion-wave equation in a cylinder. The ill-posedness and a conditional stability of the inverse problem are proved. Based on the generalized quasi-boundary value regularization method, we propose an iterative generalized quasi-boundary value regularization method to deal with the inverse problem, and this iterative method has a higher convergence rate. The convergence rates of the regularized solution under an a priori regularization parameter choice rule and an a posteriori regularization parameter choice rule are obtained. Numerical examples illustrate the effectiveness and stability of our proposed method. [ABSTRACT FROM AUTHOR]

Consider Laplace's equation in a bounded simply-connected domain S, and use the method of fundamental solutions (MFS). The error and stability analysis is made for circular/elliptic pseudo-boundaries in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020), and polynomial convergence rates and exponential growth rates of the condition number (Cond) are obtained. General pseudo-boundaries are suggested for more complicated solution domains in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020, Section 5). Since the ill-conditioning is severe, the success in computation by the MFS mainly depends on stability. This paper is devoted to stability analysis for smooth closed pseudo-boundaries of source nodes. Bounds of the Cond are derived, and exponential growth rates are also obtained. This paper is the first time to explore stability analysis of the MFS for non-circular/non-elliptic pseudo-boundaries. Circulant matrices are often employed for stability analysis of the MFS; but the stability analysis in this paper is explored based on new techniques without using circulant matrices as in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020). To pursue better pseudo-boundaries, the sensitivity index is proposed from growth/convergence rates of stability via accuracy. Better pseudo-boundaries in the MFS can be found by trial computations, to develop the study in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020) for the selection of pseudo-boundaries. For highly smooth and singular solutions, better pseudo-boundaries are different; an analysis of the sensitivity index is explored. Circular/elliptic pseudo-boundaries are optimal for highly smooth solutions, but not for singular solutions. In this paper, amoeba-like domains are chosen in computation. Several useful types of pseudo-boundaries are developed and their algorithms are simple without using nonlinear solutions. For singular solutions, numerical comparisons are made for different pseudo-boundaries via the sensitivity index. [ABSTRACT FROM AUTHOR]

In this paper, we make a theoretical analysis of the convergence rates of Kaczmarz and extended Kaczmarz projection algorithms for some of the most practically used control sequences. We first prove an at least linear convergence rate for the Kaczmarz-Tanabe and its extended version methods (the one in which a complete set of projections using row/column indices is performed in each iteration). Then, we apply the main ideas of this analysis in establishing an at least sublinear, respectively, linear convergence rate for the Kaczmarz algorithm with almost cyclic and the remotest set control strategies, and their extended versions, respectively. These results complete the existing ones related to the random selection procedures. [ABSTRACT FROM AUTHOR]

This paper considers computing partial eigenpairs of differential eigenvalue problems (DEPs) such that eigenvalues are in a certain region on the complex plane. Recently, based on a "solve-then-discretize" paradigm, an operator analogue of the FEAST method has been proposed for DEPs without discretization of the coefficient operators. Compared to conventional "discretize-then-solve" approaches that discretize the operators and solve the resulting matrix problem, the operator analogue of FEAST exhibits much higher accuracy; however, it involves solving a large number of ordinary differential equations (ODEs). In this paper, to reduce the computational costs, we propose operation analogues of Sakurai–Sugiura-type complex moment-based eigensolvers for DEPs using higher-order complex moments and analyze the error bound of the proposed methods. We show that the number of ODEs to be solved can be reduced by a factor of the degree of complex moments without degrading accuracy, which is verified by numerical results. Numerical results demonstrate that the proposed methods are over five times faster compared with the operator analogue of FEAST for several DEPs while maintaining almost the same high accuracy. This study is expected to promote the "solve-then-discretize" paradigm for solving DEPs and contribute to faster and more accurate solutions in real-world applications. [ABSTRACT FROM AUTHOR]

The present paper continues our investigation of an implementation of a least-squares collocation method for higher-index differential-algebraic equations. In earlier papers, we were able to substantiate the choice of basis functions and collocation points for a robust implementation as well as algorithms for the solution of the discrete system. The present paper is devoted to an analytic estimation of condition numbers for different components of an implementation. We present error estimations, which show the sources for the different errors. [ABSTRACT FROM AUTHOR]

This paper is based on the analysis of the backward Euler method for stochastic differential equations. It is motivated by the paper (Hutzenthaler et al. Proc. R. Soc. A 467, 1563–1576, 2011), where authors studied the equations with superlinearly growing coefficients. The main goal of this paper is to reveal sufficient conditions of the strong and weak Lp-divergence of the backward Euler method at finite time, for all p ∈ (0 , ∞) . Theoretical results are supported by examples. [ABSTRACT FROM AUTHOR]

This paper is concerned with the identification of important nodes in node-weighted graphs by applying matrix functions, in particular the matrix exponential. Many tools that use an adjacency matrix for a graph have been developed to study the importance of the nodes in unweighted or edge-weighted networks. However, adjacency matrices for node-weighted graphs have not received much attention. The present paper proposes using a line graph associated with a node-weighted graph to construct an edge-weighted graph that can be analyzed with available methods. Both undirected and directed graphs with positive node weights are considered. We show that when the weight of a node increases, the importance of this node in the graph increases as well, provided that the adjacency matrix is suitably scaled. Applications to real-life problems are presented. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the application of the fading regularization method with the method of fundamental solutions (MFS) to the ill-posed Cauchy-Stokes problem. For both smooth and piecewise smooth two-dimensional geometries, we present a numerical reconstruction of the missing velocity and normal stress tensor on an inaccessible part of the boundary based on knowledge of over-prescribed noisy data acquired on the remaining accessible boundary part. Three numerical examples demonstrate the proposed numerical algorithm's accuracy, convergence, stability, and efficiency, as well as its ability to deblur the data. [ABSTRACT FROM AUTHOR]