Extrapolation methods for fixed‐point multilinear PageRank computations

Nonnegative tensors arise very naturally in many applications that involve large and complex data flows. Due to the relatively small requirement in terms of memory storage and number of operations per step, the (shifted) higher order power method is one of the most commonly used technique for the computation of positive Z‐eigenvectors of this type of tensors. However, unlike the matrix case, the method may fail to converge even for irreducible tensors. Moreover, when it converges, its convergence rate can be very slow. These two drawbacks often make the computation of the eigenvectors demanding or unfeasible for large problems. In this work, we consider a particular class of nonnegative tensors associated with the multilinear PageRank modification of higher order Markov chains. Based on the simplified topological ε‐algorithm in its restarted form, we introduce an extrapolation‐based acceleration of power method type algorithms, namely, the shifted fixed‐point method and the inner‐outer method. The accelerated methods show remarkably better performance, with faster convergence rates and reduced overall computational time. Extensive numerical experiments on synthetic and real‐world datasets demonstrate the advantages of the introduced extrapolation techniques.     

An efficient higher order family of root finders

A one parameter family of iterative methods for the simultaneous approximation of simple complex zeros of a polynomial, based on a cubically convergent Hansen–Patrick's family, is studied. We show that the convergence of the basic family of the fourth order can be increased to five and six using Newton's and Halley's corrections, respectively. Since these corrections use the already calculated values, the computational efficiency of the accelerated methods is significantly increased. Further acceleration is achieved by applying the Gauss–Seidel approach (single-step mode). One of the most important problems in solving nonlinear equations, the construction of initial conditions which provide both the guaranteed and fast convergence, is considered for the proposed accelerated family. These conditions are computationally verifiable; they depend only on the polynomial coefficients, its degree and initial approximations, which is of practical importance. Some modifications of the considered family, providing the computation of multiple zeros of polynomials and simple zeros of a wide class of analytic functions, are also studied. Numerical examples demonstrate the convergence properties of the presented family of root-finding methods.     

遗传-人工蜂群融合算法及其Markov收敛性分析

本文研究了遗传算法易发生"早熟"以及人工蜂群算法在搜索初期寻优速度慢的问题.基于将遗传算法与人工蜂群算法融合以实现二者互补的思想,提出遗传-人工蜂群融合算法(G-ABCA),利用马尔可夫理论对其收敛性进行了理论分析,证明其适应度函数值序列(即优化解满意值序列)是单调且收敛的,并利用四个经典的多峰测试函数对遗传-人工蜂群融合算法、改进的遗传算法以及人工蜂群算法进行了对比实验分析,结果表明:遗传-人工蜂群融合算法不仅收敛,而且其寻优性能显著优于其它两种算法.     

Extension of GKB‐FP algorithm to large‐scale general‐form Tikhonov regularization

In a recent paper an algorithm for large‐scale Tikhonov regularization in standard form called GKB‐FP was proposed and numerically illustrated. In this paper, further insight into the convergence properties of this method is provided, and extensions to general‐form Tikhonov regularization are introduced. In addition, as alternative to Tikhonov regularization, a preconditioned LSQR method coupled with an automatic stopping rule is proposed. Preconditioning seeks to incorporate smoothing properties of the regularization matrix into the computed solution. Numerical results are reported to illustrate the methods on large‐scale problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Acceleration of the EM algorithm using the vector epsilon algorithm

The expectation–maximization (EM) algorithm is a very general and popular iterative computational algorithm to find maximum likelihood estimates from incomplete data and broadly used to statistical analysis with missing data, because of its stability, flexibility and simplicity. However, it is often criticized that the convergence of the EM algorithm is slow. The various algorithms to accelerate the convergence of the EM algorithm have been proposed. The vector ε algorithm of Wynn (Math Comp 16:301–322, 1962) is used to accelerate the convergence of the EM algorithm in Kuroda and Sakakihara (Comput Stat Data Anal 51:1549–1561, 2006). In this paper, we provide the theoretical evaluation of the convergence of the ε-accelerated EM algorithm. The ε-accelerated EM algorithm does not use the information matrix but only uses the sequence of estimates obtained from iterations of the EM algorithm, and thus it keeps the flexibility and simplicity of the EM algorithm.     

Global and superlinear convergence of an algorithm for one-dimensional minimization of convex functions

This paper studies an algorithm for minimizing a convex function based upon a combination of polyhedral and quadratic approximation. The method was given earlier, but without a good specification for updating the algorithm's curvature matrix. Here, for the case of onedimensional minimization, we provide a specification that insures convergence even in cases where the curvature scalar tends to zero or infinity. Under mild additional assumptions, we show that the convergence is superlinear.     

Index to Volume 9 (2000)

The stochastic approximation EM (SAEM) algorithm is a simulation-based alternative to the expectation/maximization (EM) algorithm for situations when the E-step is hard or impossible. One of the appeals of SAEM is that, unlike other Monte Carlo versions of EM, it converges with a fixed (and typically small) simulation size. Another appeal is that, in practice, the only decision that has to be made is the choice of the step size which is a one-time decision and which is usually done before starting the method. The downside of SAEM is that there exist no data-driven and/or model-driven recommendations as to the magnitude of this step size. We argue in this article that a challenging model/data combination coupled with an unlucky step size can lead to very poor algorithmic performance and, in particular, to a premature stop of the method. This article proposes a new heuristic for SAEM's step size selection based on the underlying EM rate of convergence. We also use the much-appreciated EM likelihood-ascent property to derive a new and flexible way of monitoring the progress of the SAEM algorithm. The method is applied to a challenging geostatistical model of online retailing.     

Point estimation of simultaneous methods for solving polynomial equations: A survey (II)

The construction of computationally verifiable initial conditions which provide both the guaranteed and fast convergence of the numerical root-finding algorithm is one of the most important problems in solving nonlinear equations. Smale's “point estimation theory” from 1981 was a great advance in this topic; it treats convergence conditions and the domain of convergence in solving an equation f(z)=0$f(z)=0$ using only the information of f   at the initial point _z0$z_0$. The study of a general problem of the construction of initial conditions of practical interest providing guaranteed convergence is very difficult, even in the case of algebraic polynomials. In the light of Smale's point estimation theory, an efficient approach based on some results concerning localization of polynomial zeros and convergent sequences is applied in this paper to iterative methods for the simultaneous determination of simple zeros of polynomials. We state new, improved initial conditions which provide the guaranteed convergence of frequently used simultaneous methods for solving algebraic equations: Ehrlich–Aberth's method, Ehrlich–Aberth's method with Newton's correction, Börsch-Supan's method with Weierstrass’ correction and Halley-like (or Wang–Zheng) method. The introduced concept offers not only a clear insight into the convergence analysis of sequences generated by the considered methods, but also explicitly gives their order of convergence. The stated initial conditions are of significant practical importance since they are computationally verifiable; they depend only on the coefficients of a given polynomial, its degree n and initial approximations to polynomial zeros.     

A novel method for robust minimisation of univariate functions with quadratic convergence

We describe a novel method for minimisation of univariate functions which exhibits an essentially quadratic convergence and whose convergence interval is only limited by the existence of near maxima. Minimisation is achieved through a fixed-point iterative algorithm, involving only the first and second-order derivatives, that eliminates the effects of near inflexion points on convergence, as usually observed in other minimisation methods based on the quadratic approximation. Comparative numerical studies against the standard quadratic and Brent's methods demonstrate clearly the high robustness, high precision and convergence rate of the new method, even when a finite difference approximation is used in the evaluation of the second-order derivative.     

AN SQP ALGORITHM WITH NONMONOTONE LINE SEARCHFOR GENERAL NONLINEAR CONSTRAINED OPTIMIZATION PROBLEM

1.IntroductionInthispaper,weconsiderthefollowingoptimizationproblem(P):minf(x)(P)e.t.gi(x)~0(j=1,...,m,),gi(x)s0(j==m,+l,...,m),wherex~(xl,'5x.)"EE",f(x),gi(x)(j=1,',m)areallreaLvaluedsmoothfunctions.Inrecentyears)SequentialQuadraticProgramming(SoP)algorithmshavebeenex-tensivelyusedforthesolutionofsuchproblems,andtheyhavebeenwidelyinvestigatedbymanyauthors(see,e.g.[1-5]).AnattractivefeatureoftheSoPmethodisthat,undersomesuitableconditions,asuperlinearconvergencecanbeobtained,providedth…     

A practical two‐term acceleration algorithm for linear systems

In this paper, a practical two‐term acceleration algorithm is proposed, the interval of the parameter which guarantees the convergence of the acceleration algorithm is analyzed in detail. Further, the acceleration ratio of the new acceleration algorithm is obtained in advance. The new acceleration algorithm is less sensitive to the parameter than the Chebyshev semi‐iterative method. Finally, some numerical examples show that the accelerated algorithm is effective. Copyright © 2011 John Wiley & Sons, Ltd.     

An Asynchronous Distributed Expectation Maximization Algorithm for Massive Data: The DEM Algorithm

The family of expectation--maximization (EM) algorithms provides a general approach to fitting flexible models for large and complex data. The expectation (E) step of EM-type algorithms is time-consuming in massive data applications because it requires multiple passes through the full data. We address this problem by proposing an asynchronous and distributed generalization of the EM called the distributed EM (DEM). Using DEM, existing EM-type algorithms are easily extended to massive data settings by exploiting the divide-and-conquer technique and widely available computing power, such as grid computing. The DEM algorithm reserves two groups of computing processes called workers and managers for performing the E step and the maximization step (M step), respectively. The samples are randomly partitioned into a large number of disjoint subsets and are stored on the worker processes. The E step of DEM algorithm is performed in parallel on all the workers, and every worker communicates its results to the managers at the end of local E step. The managers perform the M step after they have received results from a γ-fraction of the workers, where γ is a fixed constant in (0, 1]. The sequence of parameter estimates generated by the DEM algorithm retains the attractive properties of EM: convergence of the sequence of parameter estimates to a local mode and linear global rate of convergence. Across diverse simulations focused on linear mixed-effects models, the DEM algorithm is significantly faster than competing EM-type algorithms while having a similar accuracy. The DEM algorithm maintains its superior empirical performance on a movie ratings database consisting of 10 million ratings. Supplementary material for this article is available online.     

Monte Carlo EM加速算法

EM算法是近年来常用的求后验众数的估计的一种数据增广算法, 但由于求出其E步中积分的显示表达式有时很困难, 甚至不可能, 限制了其应用的广泛性. 而Monte Carlo EM算法很好地解决了这个问题, 将EM算法中E步的积分用Monte Carlo模拟来有效实现, 使其适用性大大增强. 但无论是EM算法, 还是Monte Carlo EM算法, 其收敛速度都是线性的, 被缺损信息的倒数所控制, 当缺损数据的比例很高时, 收敛速度就非常缓慢. 而Newton-Raphson算法在后验众数的附近具有二次收敛速率. 本文提出Monte Carlo EM加速算法, 将Monte Carlo EM算法与Newton-Raphson算法结合, 既使得EM算法中的E步用Monte Carlo模拟得以实现, 又证明了该算法在后验众数附近具有二次收敛速度. 从而使其保留了Monte Carlo EM算法的优点, 并改进了Monte Carlo EM算法的收敛速度. 本文通过数值例子, 将Monte Carlo EM加速算法的结果与EM算法、Monte Carlo EM算法的结果进行比较, 进一步说明了Monte Carlo EM加速算法的优良性.     

Generalized Newton’s method based on graphical derivatives

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations.     

Modelling and numerical approach to a class of metal‐forming problems—Quasi‐steady case

A class of quasi‐steady metal‐forming problems, with rigid‐plastic, incompressible, strain and strain‐rate dependent material model and with unilateral frictionless and nonlinear, nonlocal Coulomb's frictional contact conditions is considered. A coupled variational formulation, constituted of a variational inequality, with nonlinear and nondifferentiable terms, and a strain evolution equation, is derived and under a restriction on the material characteristics and using a variable stiffness parameters method with time retardation, existence, uniqueness and convergence results are obtained and presented. An algorithm, combining this method and the finite element method, is proposed and applied for solving an example strip drawing problem. Copyright © 2011 John Wiley & Sons, Ltd.     

Numerical analysis for the quadratic matrix equations from a modification of fixed‐point type

In this paper, we study the quadratic matrix equations. To improve the application of iterative schemes, we use a transform of the quadratic matrix equation into an equivalent fixed‐point equation. Then, we consider an iterative process of Chebyshev‐type to solve this equation. We prove that this iterative scheme is more efficient than Newton's method. Moreover, we obtain a local convergence result for this iterative scheme. We finish showing, by an application to noisy Wiener‐Hopf problems, that the iterative process considered is computationally more efficient than Newton's method.     

Nonlinear Smoothing and the EM Algorithm for Positive Integral Equations of the First Kind

We study a modification of the EMS algorithm in which each step of the EMS algorithm is preceded by a nonlinear smoothing step of the form , where S is the smoothing operator of the EMS algorithm. In the context of positive integral equations (à la positron emission tomography) the resulting algorithm is related to a convex minimization problem which always admits a unique smooth solution, in contrast to the unmodified maximum likelihood setup. The new algorithm has slightly stronger monotonicity properties than the original EM algorithm. This suggests that the modified EMS algorithm is actually an EM algorithm for the modified problem. The existence of a smooth solution to the modified maximum likelihood problem and the monotonicity together imply the strong convergence of the new algorithm. We also present some simulation results for the integral equation of stereology, which suggests that the new algorithm behaves roughly like the EMS algorithm. Accepted 1 April 1997     

The persistent‐access‐caching algorithm

Caching is widely recognized as an effective mechanism for improving the performance of the World Wide Web. One of the key components in engineering the Web caching systems is designing document placement/replacement algorithms for updating the collection of cached documents. The main design objectives of such a policy are the high cache hit ratio, ease of implementation, low complexity and adaptability to the fluctuations in access patterns. These objectives are essentially satisfied by the widely used heuristic called the least‐recently‐used (LRU) cache replacement rule. However, in the context of the independent reference model, the LRU policy can significantly underperform the optimal least‐frequently‐used (LFU) algorithm that, on the other hand, has higher implementation complexity and lower adaptability to changes in access frequencies. To alleviate this problem, we introduce a new LRU‐based rule, termed the persistent‐access‐caching (PAC), which essentially preserves all of the desirable attributes of the LRU scheme. For this new heuristic, under the independent reference model and generalized Zipf's law request probabilities, we prove that, for large cache sizes, its performance is arbitrarily close to the optimal LFU algorithm. Furthermore, this near‐optimality of the PAC algorithm is achieved at the expense of a negligible additional complexity for large cache sizes when compared to the ordinary LRU policy, since the PAC algorithm makes the replacement decisions based on the references collected during the preceding interval of fixed length. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

A multiscale fourth‐order model for the image inpainting and low‐dimensional sets recovery

We consider a fourth‐order variational model, to solve the image inpainting problem, with the emphasis on the recovery of low‐dimensional sets (edges and corners) and the curvature of the edges. The model permits also to perform simultaneously the restoration (filtering) of the initial image where this one is available. The multiscale character of the model follows from an adaptive selection of the diffusion parameters that allows us to optimize the regularization effects in the neighborhoods of the small features that we aim to preserve. In addition, because the model is based on the high‐order derivatives, it favors naturally the accurate capture of the curvature of the edges, hence to balance the tasks of obtaining long curved edges and the obtention of short edges, tip points, and corners. We analyze the method in the framework of the calculus of variations and the Γ‐convergence to show that it leads to a convergent algorithm. In particular, we obtain a simple discrete numerical method based on a standard mixed‐finite elements with well‐established approximation properties. We compare the method to the Cahn–Hilliard model for the inpainting, and we present several numerical examples to show its performances. Copyright © 2016 John Wiley & Sons, Ltd.     

定数截尾混合指数分布在恒加应力下的MCEM加速算法

应用Monte Carlo EM加速算法给出了混合指数分布在恒加应力水平下,在定数截尾场合的参数估计问题,并通过模拟试验说明利用Monte Carlo EM加速算法来估计混合指数分布比EM算法更有效,收敛速度更快.