On the asymptotic convergence of sequences of analytic functions

We consider sequences {f _n } of analytic self mappings of a domain and the associated sequence {Θ _n } of inner compositions given by . The case of interest in this paper concerns sequences {f _n } that converge assymptotically to a function f, in the sense that for any sequence of integers {n _k } with n ₁ < n ₂ < ... one has that locally uniformly in Ω. Most of the discussion concerns the case where the asymptotic limit f is the identity function in Ω. Received: 16 December 2006     

On the convergence of the affine-scaling algorithm

The affine-scaling algorithm, first proposed by Dikin, is presently enjoying great popularity as a potentially effective means of solving linear programs. An outstanding question about this algorithm concerns its convergence in the presence of degeneracy. In this paper, we give new convergence results for this algorithm that do not require any non-degeneracy assumption on the problem. In particular, we show that if the stepsize choice of either Dikin or Barnes or Vanderbei, et al. is used, then the algorithm generates iterates that converge at least linearly with a convergence ratio of , wheren is the number of variables and (0,1] is a certain stepsize ratio. For one particular stepsize choice which is an extension of that of Barnes, we show that the cost of the limit point is within O(/(1–)) of the optimal cost and, for sufficiently small (roughly, proportional to how close the cost of the nonoptimal vertices are to the optimal cost), is exactly optimal. We prove the latter result by using an unusual proof technique, that of analyzing the ergodic convergence of the corresponding dual vectors. For the special case of network flow problems with integer data, we show that it suffices to take = 1/(6mC), wherem is the number of constraints andC is the sum of the cost coefficients, to attain exact optimality.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), by the National Science Foundation, grant NSF-ECS-8519058, and by the Science and Engineering Research Board of McMaster University.     

On the asymptotic equivalence ofL pmetrics for convergence to normality

Summary This paper is concerned with the rate of convergence to zero of theL _pmetrics _np1p, constructed out of differences between distribution functions, for departure from normality for normed sums of independent and identically distributed random variables with zero mean and unit variance. It is shown that the _np are, under broad conditions, asymptotically equivalent in the strong sense that, for 1p, p, _np/_np is universally bounded away from zero and infinity asn.     

On the convergence of the Weiszfeld algorithm

In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper. Received: January 1999 / Accepted: December 2001?Published online April 12, 2002 RID="*" ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia RID="**" ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06 RID="*" RID="**"     

On rates of convergence and asymptotic normality in the multiknapsack problem

In Meanti et al. (1990) an almost sure asymptotic characterization has been derived for the optimal solution value as function of the knapsack capacities, when the profit and requirement coefficients of items to be selected from are random variables. In this paper we establish a rate of convergence for this process using results from the theory of empirical processes.     

On the convergence property of the DFP algorithm

The DFP algorithm of unconstrained optimization possesses excellent properties of convergence for convex functions. However, a convergence theory of the DFP algorithm without the convexity assumption has not yet been established. This paper gives the following result: If the objective function is suitably smooth, and if the DFP algorithm produces a convergent point sequence, then the limit point of the sequence is a critical point of the objective function. Also, some open questions are mentioned.Supported by the National Science Foundation of China.     

On the convergence of the generalized Weiszfeld algorithm

In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper shows that many of these algorithms indeed converge.     

On the convergence of theQR algorithm with multishifts

A unified treatment of the cases of quadratic and cubic convergence of the QR algorithm with multishifts is provided. The approach used is similar to that of Elsner and Watkins but does not use the notion of the distance between subspaces. Bibliography:10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 275–283. Translated by E. E. Tyrtyshnikov.     

On the asymptotic convergence factor of the total step method in interval computation

For a special class of n×n interval matrices A we derive a necessary and sufficient condition for the asymptotic convergence factor α of the total step method x^(m+1)=Ax^(m)+b to be less than the spectral radius ϱ(|A|) of the absolute value |A| of A.     

On the convergence rate of the simulated annealing algorithm

The convergence rate of the simulated annealing algorithm is examined. It is shown that, if the objective function is nonsingular, then the number of its evaluations required to obtain the desired accuracy ɛ in the solution can be a slowly (namely, logarithmically) growing function as ɛ approaches zero.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

On the convergence of row-modification algorithm for matrix projections

This paper proposes an algorithm for matrix minimum-distance projection, with respect to a metric induced from an inner product that is the sum of inner products of column vectors, onto the collection of all matrices with their rows restricted in closed convex sets. This algorithm produces a sequence of matrices by modifying a matrix row by row, over and over again. It is shown that the sequence is convergent, and it converges to the desired projection. The implementation of the algorithm for multivariate isotonic regressions and numerical examples are also presented in the paper.     

On the convergence of a new trust region algorithm

Summary. In this paper we present a new trust region algorithm for general nonlinear constrained optimization problems. The algorithm is based on the exact penalty function. Under very mild conditions, global convergence results for the algorithm are given. Local convergence properties are also studied. It is shown that the penalty parameter generated by the algorithm will be eventually not less than the norm of the Lagrange multipliers at the accumulation point. It is proved that the method is equivalent to the sequential quadratic programming method for all large , hence superlinearly convergent results of the SQP method can be applied. Numerical results are also reported. Received March 21, 1993     

On the asymptotic convergence to mixed equilibria in 2×2 asymmetric games

We analyse the stability properties of mixed equilibria in 2×2 asymmetric games under evolutionary dynamics. With the standard replicator dynamics these equilibria are stable but not asymptotically stable. We modified the replicator dynamics by introducing players of two types: myopies — like in the standard replicator dynamics — and best responders. The behaviour of the latter is described by a continuos time version of the best reply dynamics. Asymptotic convergence under theModified Replicator Dynamics is proved by identifying a strictly decreasing Ljapunov function. We argue that the finding has important implications to justify the use of economic models with mixed strategy equilibria.     

A convergence theorem for asymptotic contractions

We show that to each asymptotic contraction T with a bounded orbit in a complete metric space X, there corresponds a unique point x _* such that all the iterates of T converge to x _*, uniformly on any bounded subset of X. If, in addition, some power of T is continuous at x _*, then x _* is a fixed point of T. Dedicated to Professor Felix E. Browder with admiration and respect     

On the convergence of an algorithm for discreteL p approximation

Summary The convergence properties of an algorithm for discreteL _p approximation (1p<2) that has been considered by several authors are studied. In particular, it is shown that for 1<p<2 the method converges (with a suitably close starting value) to the best approximation at a geometric rate with asymptotic convergence constant 2-p. A similar result holds forp=1 if the best approximation is unique. However, in this case the convergence constant depends on the function to be approximated.