On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性

增广Lagrange方法是求解非线性规划的一种有效方法.从一新的角度证明不等式约束非线性非光滑凸优化问题的增广Lagrange方法的收敛性.用常步长梯度法的收敛性定理证明基于增广Lagrange函数的对偶问题的常步长梯度方法的收敛性,由此得到增广Lagrange方法乘子迭代的全局收敛性.     

随机Bernstein多项式的依分布收敛问题

利用随机的Bernstein多项式研究随机逼近问题具有一定的意义.借助弱收敛的概念,从分布函数的角度,讨论了随机Bernstein多项式依分布收敛问题.同时,与依概率收敛结果相比较,以此说明Bernstein多项式序列依分布收敛适用的范围更广.     

On the convergence of uncertain sequences

Uncertain variables are measurable functions from uncertainty spaces to the set of real numbers. In this paper, a new kind of convergence, convergence uniformly almost surely (convergence uniformly a.s.), is presented. Then, relations between convergence uniformly almost surely and convergence almost surely (convergence a.s.), convergence in measure, convergence in mean, and convergence in distribution are discussed.     

Choquet积分的收敛定理

Murofushi、Sugeno等学者已对关于模糊测度的Choquet积分进行了详细的研究,但关于积分的收敛理论是不够的。本文讨论这一问题,给出Choquet积分的一些收敛定理,包括广义单调收敛定理、Fatou引理等。从中可以看出,Choquet积分与Sugeno模糊积分具有相同的收敛定理。     

Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions

A superlinear convergence bound for rational Arnoldi approximations to functions of matrices is derived. This bound generalizes the well-known superlinear convergence bound for the conjugate gradient method to more general functions with finite singularities and to rational Krylov spaces. A constrained equilibrium problem from potential theory is used to characterize a max-min quotient of a nodal rational function underlying the rational Arnoldi approximation, where an additional external field is required for taking into account the poles of the rational Krylov space. The resulting convergence bound is illustrated at several numerical examples, in particular, the convergence of the extended Krylov method for the matrix square root.     

On the United Theory of the Family of Euler—Haller Type Methods with Cubical Convergence in Banach Spaces

The convergence problem of the family of Euler-Halley methods is considered under the Lipschitz condition with the L-average,and a united convergence theory with its applications is presented.     

广义函数Denjoy积分的收敛性问题

本文讨论广义函数De njoy积分的收敛性问题.首先给出了广义Denjoy可积函数空间中强收敛、弱收敛、弱~*收敛和广义函数Denjoy积分收敛的关系;证明拟一致收敛是广义函数Denjoy积分收敛的一个充分必要条件;最后指出了Denjoy可积广义函数列弱~*收敛与强收敛等价当且仅当原函数等度连续.     

Convergence Properties of the DFP Algorithm for Unconstrained Optimization

In this article, the convergence properties of the DFP algorithm with inexact line searches on uniformly convex functions are investigated. An inexact line search is proposed and the global convergence and superlinear convergence of the DFP algorithm with this line search on uniformly convex functions are proved.     

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.

     

Range convergence monotonicity for vector measures and range monotonicity of the mass

We prove that the range of sequence of vector measures converging widely satisfies a weak lower semicontinuity property, that the convergence of the range implies the strict convergence (convergence of the total variation) and that the strict convergence implies the range convergence for strictly convex norms. In dimension 2 and for Euclidean spaces of any dimensions, we prove that the total variation of a vector measure is monotone with respect to the range.     

Majorants of the Dirichlet kernels and the Dini pointwise tests for generalized Haar systems

In this paper, we obtain five tests (three of which are symmetric) of pointwise convergence of Fourier series with respect to generalized Haar systems; the tests are similar to the Dini convergence tests. It is shown that the Dini convergence tests for Price systems are also valid for generalized Haar systems. It is also shown that the classicalDini convergence test does not apply, in general, even to generalized Haar systems, although the classical symmetric Dini test for generalized Haar systems is valid. Also upper bounds for the Dirichlet kernels for generalized Haar systems are obtained.     

Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability

We give a unified treatment of the convergence of random series and the rate of convergence of the strong law of large numbers in the framework of game-theoretic probability of Shafer and Vovk (2001) [24]. We consider games with the quadratic hedge as well as more general weaker hedges. The latter corresponds to the existence of an absolute moment of order smaller than 2 in the measure-theoretic framework. We prove some precise relations between the convergence of centered random series and the convergence of the series of prices of the hedges. When interpreted in the measure-theoretic framework, these results characterize the convergence of a martingale in terms of the convergence of the series of conditional absolute moments. In order to prove these results we derive some fundamental results on deterministic strategies of Reality, who is a player in a protocol of game-theoretic probability. It is of particular interest, since Reality’s strategies do not have any counterparts in the measure-theoretic framework, ant yet they can be used to prove results which can be interpreted in the measure-theoretic framework.     

A note on the convergence of the secant method for simple and multiple roots

The secant method is one of the most popular methods for root finding. Standard text books in numerical analysis state that the secant method is superlinear: the rate of convergence is set by the gold number. Nevertheless, this property holds only for simple roots. If the multiplicity of the root is larger than one, the convergence of the secant method becomes linear. This communication includes a detailed analysis of the secant method when it is used to approximate multiple roots. Thus, a proof of the linear convergence is shown. Moreover, the values of the corresponding asymptotic convergence factors are determined and are found to be also related with the golden ratio.     

Conformal mapping by the method of alternating projections

Summary The functional analytic principle of alternating projections is used to construct an iterative method for numerical conformal mapping of the unit disc onto regions with smooth boundaries. The result is a simple method which requires in each iterative step only two complex Fourier transforms. Local convergence can be proved using a theorem of Ostrowski. Convergence is linear. The asymptotic convergence factor is equal to the spectral radius of a certain operator. A version with overrelaxation as well as a discretized version are discussed along the same lines. For regions which are close to the unit disc convergence is fast. For some familiar regions the convergence factors can be calculated explicitly. Finally, the method is compared with Theodorsen's.Dedicated to the memory of Peter Henrici     

The combined effect of numerical integration and approximation of the boundary in the finite element method for eigenvalue problems

Summary. The paper deals with the finite element analysis of second order elliptic eigenvalue problems when the approximate domains are not subdomains of the original domain and when at the same time numerical integration is used for computing the involved bilinear forms. The considerations are restricted to piecewise linear approximations. The optimum rate of convergence for approximate eigenvalues is obtained provided that a quadrature formula of first degree of precision is used. In the case of a simple exact eigenvalue the optimum rate of convergence for approximate eigenfunctions in the -norm is proved while in the -norm an almost optimum rate of convergence (i.e. near to is achieved. In both cases a quadrature formula of first degree of precision is used. Quadrature formulas with degree of precision equal to zero are also analyzed and in the case when the exact eigenfunctions belong only to the convergence without the rate of convergence is proved. In the case of a multiple exact eigenvalue the approximate eigenfunctions are compard (in contrast to standard considerations) with linear combinations of exact eigenfunctions with coefficients not depending on the mesh parameter . Received September 18, 1993 / Revised version received September 26, 1994     

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.     

On the Convergence Rate of the Boundary Penalty Method

The convergence rate of the boundary penalty finite element method is discussed for a model Poisson equation with inhomogeneous Dirichlet boundary conditions and a sufficiently smooth solution. It is proved that an optimal convergence rate can be achieved which agrees with the rate obtained recently in the numerical experiments by Utku and Carey.     

A convergence analysis of the iterative aggregation method with one parameter

A method for accelerating linear iterations in a Banach space is studied as a linear iterative method in an augmented space, and sufficient conditions for convergence are derived in the general case and in ordered Banach spaces. An acceleration of convergence takes place if an auxiliary functional is chosen sufficiently close to a dual eigenvector associated with a dominant simple eigenvalue of the iteration operator; in this case, the influence of this eigenvalue on the asymptotic rate of convergence is eliminated. Quantitative estimates and bounds on convergence are given.     

On the Behavior of the Four Order Iteration in Euler's Family Near a Zero

The aim of this paper is to study the local convergence of the four order iteration of Euler's family for solving nonlinear operator equations. We get the optimal radius of the local convergence ball of the method for operators satisfying the weak third order generalized Lipschitz condition with L-average. We also show that the local convergence of the method is determined by a period 2 orbit of the method itself applied to a real function.