Convergence of an algorithm for constructing snakes

We investigate an algorithm for constructing snakes (extremal polynomials introduced by S. Karlin) suggested by Dzyadyk. It is proved that, in the general case, this algorithm is linearly convergent. In the case where the basis functions of the Chebyshev system belong to the classC ², this algorithm is quadratically convergent.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 7, pp. 825–832, July, 1994.     

Convergence of theQR algorithm

TheQR algorithm ofJ. G. F. Francis is used in computing matrix eigenvalues. The convergence proof given here is an analogue ofRutishauser's proof of the convergence of theLR algorithm, but our proof covers the case of disorder of the eigenvalues.The work presented in this paper was supported by the AEC Computing and Applied Mathematics Center, Courant Institute of Mathematical Sciences, New York University, under contract AT(30-1)-1480 with the U.S.Atomic Energy Commission.     

Convergence of multidimensional cascade algorithm

A necessary and sufficient condition on the spectrum of the restricted transition operator is given for the convergence in of the multidimensional cascade algorithm for any starting function whose shifts form a partition of unity. Received September 12, 1995 / Revised version received August 2, 1996     

Convergence of an annealing algorithm

The annealing algorithm is a stochastic optimization method which has attracted attention because of its success with certain difficult problems, including NP-hard combinatorial problems such as the travelling salesman, Steiner trees and others. There is an appealing physical analogy for its operation, but a more formal model seems desirable. In this paper we present such a model and prove that the algorithm converges with probability arbitrarily close to 1. We also show that there are cases where convergence takes exponentially long—that is, it is no better than a deterministic method. We study how the convergence rate is affected by the form of the problem. Finally we describe a version of the algorithm that terminates in polynomial time and allows a good deal of practical confidence in the solution.     

Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

Convergence analysis for a multiplicatively relaxed EM algorithm

The expectation maximization (EM) algorithm is an iterative procedure used to determine maximum likelihood estimators in situations of incomplete data. In the case of independent Poisson variables it converges to a solution of a problem of the form min ∑[〈aⁱ,x〉 ? b_i log 〈aⁱ, x〉] such that x ?0. Thus, it can be used to solve systems of the form Ax = b, x?0 (with A stochastic and b positive.) It converges to a feasible solution if it exists and to an approximate one otherwise (the one that minimizes d (b, Ax), where d is the Kullback–Leibler information divergence). We study the convergence of the multiplicatively relaxed version proposed by Tanaka for use in positron emission tomography. We prove global convergence in the underrelaxed and unrelaxed cases. In the overrelaxed case we present a local convergence theorem together with two partial global results: the sequence generated by the algorithm is bounded and, if it converges, its limit point is a solution of the aforementioned problem.     

Convergence theorems of a hybrid algorithm for equilibrium problems

In this paper, we introduce a hybrid iterative scheme for finding a common element of the set of common fixed points of two hemi-relatively non-expansive mappings and the set of solutions of an equilibrium problem by the CQ hybrid method in Banach spaces. Our results improve and extend the corresponding results announced by Cheng and Tian [Y. Cheng, M. Tian, Strong convergence theorem by monotone hybrid algorithm for equilibrium problems, hemi-relatively nonexpansive mappings and maximal monotone operators, Fixed Point Theory Appl. 2008 (2008) 12 pages, doi:10.1155/2008/617248], Takahashi and Zembayashi [W. Takahashi, K. Zembayashi, Strong convergence theorem by a new hybrid method for equilibrium problems and relatively non-expansive mappings, Fixed Point Theory Appl. (2008) doi:10.1155/2008/528476] and some others.     

Convergence properties of Beale-Powell restart algorithm

The Beale-Powell restart algorithm is highly useful for large-scale unconstrained optimization. An example is taken to show that the algorithm may fail to converge. The global convergence of a slightly modified algorithm is proved. Project partially supported by the National Natural Science Foundation of China.     

A new linogram algorithm for computerized tomography

We propose a new linogram algorithm for the high quality Fourierreconstruction of digital N x N images from their Radon transform.The algorithm is based on univariate fast Fourier transformsfor nonequispaced data in the time domain and in the frequencydomain. The algorithm requires only O(N² logN) arithmetic operationsand preserves the good reconstruction quality of the filteredbackprojection.     

Convergence analysis of a Halpern type algorithm for accretive operators

In this paper, we study the convergence of a Halpern type proximal point algorithm for accretive operators in Banach spaces. Our results fill the gap in the work of Zhang and Song (2012) [1] and, consequently, all the results there can be corrected accordingly.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

Convergence of an iterative algorithm for solving Hamilton-Jacobi type equations

Solutions of the optimal control and -control problems for nonlinear affine systems can be found by solving Hamilton-Jacobi equations. However, these first order nonlinear partial differential equations can, in general, not be solved analytically. This paper studies the rate of convergence of an iterative algorithm which solves these equations numerically for points near the origin. It is shown that the procedure converges to the stabilizing solution exponentially with respect to the iteration variable. Illustrative examples are presented which confirm the theoretical rate of convergence.

     

Convergence of LR algorithm for a one-point spectrum tridiagonal matrix

We prove convergence for the basic LR algorithm on a real unreduced tridiagonal matrix with a one-point spectrum—the Jordan form is one big Jordan block. First we develop properties of eigenvector matrices. We also show how to deal with the singular case.     

Convergence rates of a global optimization algorithm

Second order conditions for the (pseudo-) convexity of a function restricted to an affine subspace are obtained by extending those already known for functions on ⁿ . These results are then used to analyse the (pseudo-) convexity of potential functions of the type introduced by Karmarkar.This research was completed while the first author was on sabbatical leave at the Département d'Informatiques et de Recherche Opérationelle, Université de Montréal, and supported by NSERC (grant Q015807). This research was also supported by NSERC (grants A8312 and A5408) and la Coopération franco-québécoise (project 20-02-13).     

Convergence analysis of the general Gauss-Newton algorithm

Summary The convergence of the Gauss-Newton algorithm for solving discrete nonlinear approximation problems is analyzed for general norms and families of functions. Aquantitative global convergence theorem and several theorems on the rate of local convergence are derived. A general stepsize control procedure and two regularization principles are incorporated. Examples indicate the limits of the convergence theorems.     

Convergence of a nonlinear wavelet algorithm for the solution of PDEs

We prove convergence of an adaptive wavelet algorithm for the solution of elliptic PDEs, which combines Richardson type iterations with nonlinear projection steps.     

Convergence analysis of a subsampled Levenberg-Marquardt algorithm

In this work, a subsampled Levenberg-Marquardt algorithm is proposed for solving nonconvex finite-sum optimization problem. At each iteration, based on subsampled function value, gradient and simplified Hessian, a linear system is inexactly solved and the regularized parameter is updated as trust-region algorithms. Provided the sample size increases asymptotically, we prove that the generated sequence converges to a stationary point almost surely.     

Convergence of a cyclic ellipsoid algorithm for systems of linear equalities

A variable metric optimization method for non differentiable functions due to Shor, Yudin and Nemirovskii, and Khacian, is applied to a full rank system of linear equalities, under a cyclic implementation. At each step of the iteration, the variable metric matrix is used to construct an ellipsoid around the current iterate; this ellipsoid contains the solution. The variable metric matrix is updated in such a way that this inclusion property always hold, and that the volume of the ellipsoid shrinks as a geometric progression, whose rate depends only on the dimension of the space.For the problem of linear equalities, with cyclic implementation, it is shown that every axis of the ellipsoid shrinks more or less as a geometric progression (with the same rate for every axis) and thus that the distance between the iterates and the solution converges to zero as a geometric series whose rate depends only on the dimension of the space. The variable metric matrix is shown to build up information about the inverse of the matrix defining the system of equalities.A somewhat different implementation of the method is shown to converge in a number of steps equal at most to the dimension of the space.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada, under Grant A4152 and the S.S.H.R.C. of Canada.