Facial Reduction Algorithms for Conic Optimization Problems

In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems.     

Convergence of the Nelder-Mead method

We develop a matrix form of the Nelder-Mead simplex method and show that its convergence is related to the convergence of infinite matrix products. We then characterize the spectra of the involved matrices necessary for the study of convergence. Using these results, we discuss several examples of possible convergence or failure modes. Then, we prove a general convergence theorem for the simplex sequences generated by the method. The key assumption of the convergence theorem is proved in low-dimensional spaces up to 8 dimensions.

     

Classes of abelian groups related to sequential convergence

We study classes of abelian groups related to sequential com¬pactness and its generalizations (completeness, coarseness and sequential pre-compactness) in convergence groups. In particular, we describe the algebraic structure of the abelian groups on which every coarse convergence is complete and we prove that: i) every abelian group admits a sequentially precompact convergence; ii) every algebraically compact abelian group admits a sequen¬tially compact convergence.     

Rates of Ideal Convergence for Approximation Operators

In this paper, we study a general Korovkin-type approximation theory by using the notion of ideal convergence which includes many convergence methods, such as, the usual convergence, statistical convergence, A-statistical convergence, etc. We mainly compute the rate of ideal convergence of sequences of positive linear operators.     

Analyzing the convergence factor of residual inverse iteration

We will establish here a formula for the convergence factor of the method called residual inverse iteration, which is a method for nonlinear eigenvalue problems and a generalization of the well-known inverse iteration. The formula for the convergence factor is explicit and involves quantities associated with the eigenvalue to which the iteration converges, in particular the eigenvalue and eigenvector. Residual inverse iteration allows for some freedom in the choice of a vector w _k and we can use the formula for the convergence factor to analyze how it depends on the choice of w _k . We also use the formula to illustrate the convergence when the shift is close to the eigenvalue. Finally, we explain the slow convergence for double eigenvalues by showing that under generic conditions, the convergence factor is one, unless the eigenvalue is semisimple. If the eigenvalue is semisimple, it turns out that we can expect convergence similar to the simple case.     

A randomized tensor singular value decomposition based on the t‐product

The tensor SVD (t‐SVD) for third‐order tensors, previously proposed in the literature, has been applied successfully in many fields, such as computed tomography, facial recognition, and video completion. In this paper, we propose a method that extends a well‐known randomized matrix method to the t‐SVD. This method can produce a factorization with similar properties to the t‐SVD, but it is more computationally efficient on very large data sets. We present details of the algorithms and theoretical results and provide numerical results that show the promise of our approach for compressing and analyzing image‐based data sets. We also present an improved analysis of the randomized and simultaneous iteration for matrices, which may be of independent interest to the scientific community. We also use these new results to address the convergence properties of the new and randomized tensor method as well.     

Convergence theorems for adapted sequences of random sets

We consider random sets with values in a separable Banach space. We study set-valued amarts, L¹-amarts, uniform amarts and submartingales. For all these classes of random sets, we prove convergence theorems in all main modes of set convergence (weak, Wijsman, Mosco, and Hausdorff). We also prove new convergence theorems for vector-valued subpramarts and pramarts.     

Jacobi Spectral Methods for Volterra-Urysohn Integral Equations of Second Kind with Weakly Singular Kernels

Abstract

In this article, we discuss Jacobi spectral Galerkin and iterated Jacobi spectral Galerkin methods for Volterra-Urysohn integral equations with weakly singular kernels and obtain the convergence results in both the infinity and weighted L²-norm. We show that the order of convergence in iterated Jacobi spectral Galerkin method improves over Jacobi spectral Galerkin method. We obtain the convergence results in two cases when the exact solution is sufficiently smooth and non-smooth. For finding the improved convergence results, we also discuss Jacobi spectral multi-Galerkin and iterated Jacobi spectral multi-Galerkin method and obtain the convergence results in weighted L²-norm. In fact, we prove that the iterated Jacobi spectral multi-Galerkin method improves over iterated Jacobi spectral Galerkin method. We provide numerical results to verify the theoretical results.     

Numerical Solutions of Stochastic Differential Delay Equations with Jumps

Abstract

In this article, we investigate the strong convergence of the Euler–Maruyama method and stochastic theta method for stochastic differential delay equations with jumps. Under a global Lipschitz condition, we not only prove the strong convergence, but also obtain the rate of convergence. We show strong convergence under a local Lipschitz condition and a linear growth condition. Moreover, it is the first time that we obtain the rate of the strong convergence under a local Lipschitz condition and a linear growth condition, i.e., if the local Lipschitz constants for balls of radius R are supposed to grow not faster than log R.     

Transport Equation with Nonlocal Velocity in Wasserstein Spaces: Convergence of Numerical Schemes

Motivated by pedestrian modelling, we study evolution of measures in the Wasserstein space. In particular, we consider the Cauchy problem for a transport equation, where the velocity field depends on the measure itself. We deal with numerical schemes for this problem and prove convergence of a Lagrangian scheme to the solution, when the discretization parameters approach zero. We also prove convergence of an Eulerian scheme, under more strict hypotheses. Both schemes are discretizations of the push-forward formula defined by the transport equation. As a by-product, we obtain existence and uniqueness of the solution. All the results of convergence are proved with respect to the Wasserstein distance. We also show that L ¹ spaces are not natural for such equations, since we lose uniqueness of the solution.     

Convergence analysis of projected fixed‐point iteration on a low‐rank matrix manifold

In this paper, we analyze the convergence of a projected fixed‐point iteration on a Riemannian manifold of matrices with fixed rank. As a retraction method, we use the projector splitting scheme. We prove that the convergence rate of the projector splitting scheme is bounded by the convergence rate of standard fixed‐point iteration without rank constraints multiplied by the function of initial approximation. We also provide counterexample to the case when conditions of the theorem do not hold. Finally, we support our theoretical results with numerical experiments.     

Convergence of Normal Form Transformations: The Role of Symmetries

We discuss the convergence problem for coordinate transformations which take a given vector field into Poincaré–Dulac normal form. We show that the presence of linear or nonlinear Lie point symmetries can guarantee convergence of these normalizing transformations in a number of scenarios. As an application, we consider a class of bifurcation problems.     

Convergence of Polynomial Level Sets

In this paper we give a characterization of pointwise and uniform convergence of sequences of homogeneous polynomials on a Banach space by means of the convergence of their level sets. Results are obtained both in the real and the complex cases, as well as some generalizations to the nonhomogeneous case and to holomorphic functions in the complex case. Kuratowski convergence of closed sets is used in order to characterize pointwise convergence. We require uniform convergence of the distance function to get uniform convergence of the sequence of polynomials.

     

Double convergence and products of Fréchet spaces

The paper is devoted to convergence of double sequences and its application to products. In a convergence space we recognize three types of double convergences and points, respectively. We give examples and describe their structure and properties. We investigate the relationship between the topological and convergence closure product of two Fréchet spaces. In particular, we give a necessary and sufficient condition for the topological product of two compact Hausdorff Fréchet spaces to be a Fréchet space.     

Local convergence of quasi-Newton methods under metric regularity

We consider quasi-Newton methods for generalized equations in Banach spaces under metric regularity and give a sufficient condition for q-linear convergence. Then we show that the well-known Broyden update satisfies this sufficient condition in Hilbert spaces. We also establish various modes of q-superlinear convergence of the Broyden update under strong metric subregularity, metric regularity and strong metric regularity. In particular, we show that the Broyden update applied to a generalized equation in Hilbert spaces satisfies the Dennis–Moré condition for q-superlinear convergence. Simple numerical examples illustrate the results.     

The quasi-metric of complexity convergence

For any weightable quasi-metric space (X, d) having a maximum with respect to the associated order ≤ _d , the notion of the quasi-metric of complexity convergence on the the function space (equivalently, the space of sequences) X^ω , is introduced and studied. We observe that its induced quasi-uniformity is finer than the quasi-uniformity of pointwise convergence and weaker than the quasi-uniformity of uniform convergence. We show that it coincides with the quasi-uniformity of pointwise convergence if and only if the quasi-metric space (X, d) is bounded and it coincides with the quasi-uniformity of uniform convergence if and only if X is a singleton. We also investigate completeness of the quasi-metric of complexity convergence. Finally, we obtain versions of the celebrated Grothendieck theorem in this context.     

Optimization of the Hermitian and Skew-Hermitian Splitting Iteration for Saddle-Point Problems

We study the asymptotic rate of convergence of the alternating Hermitian/skew-Hermitian iteration for solving saddle-point problems arising in the discretization of elliptic partial differential equations. By a careful analysis of the iterative scheme at the continuous level we determine optimal convergence parameters for the model problem of the Poisson equation written in div-grad form. We show that the optimized convergence rate for small mesh parameter h is asymptotically 1–O(h ^1/2). Furthermore we show that when the splitting is used as a preconditioner for a Krylov method, a different optimization leading to two clusters in the spectrum gives an optimal, h-independent, convergence rate. The theoretical analysis is supported by numerical experiments.This revised version was published online in October 2005 with corrections to the Cover Date.     

Weak and Strong Convergence Theorems of G-Monotone Nonexpansive Mapping in Banach Spaces with a Graph

In this article, we introduce a faster iteration for finding a fixed point of G-monotone nonexpansive mapping in a uniformly convex Banach space with a directed graph. We establish weak and strong convergence theorems of fixed point for G-monotone nonexpansive mapping with a more convenient G-convex interval instead of the previous fixed point dominated conditions in convergence analysis. Moreover, we provide two numerical examples to illustrate the convergence behavior and advantages of the proposed method.     

General Methods for Monitoring Convergence of Iterative Simulations

Abstract

We generalize the method proposed by Gelman and Rubin (1992a) for monitoring the convergence of iterative simulations by comparing between and within variances of multiple chains, in order to obtain a family of tests for convergence. We review methods of inference from simulations in order to develop convergence-monitoring summaries that are relevant for the purposes for which the simulations are used. We recommend applying a battery of tests for mixing based on the comparison of inferences from individual sequences and from the mixture of sequences. Finally, we discuss multivariate analogues, for assessing convergence of several parameters simultaneously.     

Semilocal convergence of a k-step iterative process and its application for solving a special kind of conservative problems

In this paper, we analyze the semilocal convergence of k-steps Newton’s method with frozen first derivative in Banach spaces. The method reaches order of convergence k + 1. By imposing only the assumption that the Fréchet derivative satisfies the Lipschitz continuity, we define appropriate recurrence relations for obtaining the domains of convergence and uniqueness. We also define the accessibility regions for this iterative process in order to guarantee the semilocal convergence and perform a complete study of their efficiency. Our final aim is to apply these theoretical results to solve a special kind of conservative systems.