Spectral analysis of parallel incomplete factorizations with implicit pseudo‐overlap

Two general parallel incomplete factorization strategies are investigated. The techniques may be interpreted as generalized domain decomposition methods. In contrast to classical domain decomposition methods, adjacent subdomains exchange data during the construction of the incomplete factorization matrix, as well as during each local forward elimination and each local backward elimination involved in the application of the preconditioner. Local renumberings of nodes are combined with suitable global fill‐in strategy in an (successful) attempt to overcome the well‐known trade‐off between high parallelism (locality) and fast convergence (globality). From an algebraic viewpoint, our techniques may be implemented as global renumbering strategies. Theoretical spectral analysis is provided, which displays that the convergence rate weakly depends on the number of subdomains. Numerical results obtained on a 16‐processor SGI Origin 2000 are reported, showing the efficiency of our parallel preconditionings. Copyright © 2001 John Wiley & Sons, Ltd.     

Convergence properties of materially and geometrically non-linear finite-element spatial beam analysis

The way the non-linear constitutive equations in the spatial beam formulations are solved, influences the rate of convergence and the computational cost. Three different approaches are studied: (i) the direct global approach, where the constitutive equations are taken to be the iterative part of the global governing equations, (ii) the local (or indirect global) approach, where the constitutive equations are solved separately in each step of the global iteration, and (iii) the partly reduced approach, which is the combination of (i) and (ii). The approaches are compared with regard to the number of global iterations and the total number of floating point operations. The direct global approach is found to be the best choice.     

Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data

We consider the quickest change-point detection problem in pointwise and minimax settings for general dependent data models. Two new classes of sequential detection procedures associated with the maximal “local” probability of a false alarm within a period of some fixed length are introduced. For these classes of detection procedures, we consider two popular risks: the expected positive part of the delay to detection and the conditional delay to detection. Under very general conditions for the observations, we show that the popular Shiryaev–Roberts procedure is asymptotically optimal, as the local probability of false alarm goes to zero, with respect to both these risks pointwise (uniformly for every possible point of change) and in the minimax sense (with respect to maximal over point of change expected detection delays). The conditions are formulated in terms of the rate of convergence in the strong law of large numbers for the log-likelihood ratios between the “change” and “no-change” hypotheses, specifically as a uniform complete convergence of the normalized log-likelihood ratio to a positive and finite number. We also develop tools and a set of sufficient conditions for verification of the uniform complete convergence for a large class of Markov processes. These tools are based on concentration inequalities for functions of Markov processes and the Meyn–Tweedie geometric ergodic theory. Finally, we check these sufficient conditions for a number of challenging examples (time series) frequently arising in applications, such as autoregression, autoregressive GARCH, etc.     

Erratum to: An abstract model for branching and its application to mixed integer programming

Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic programming subproblem at each iteration. It is shown that the method has superlinear local convergence under assumptions that are no stronger than those required by conventional stabilized SQP methods. The fast local convergence is obtained by allowing a small relaxation of the optimality conditions for the quadratic programming subproblem in the neighborhood of a solution. In the limit, the line search selects the unit step length, which implies that the method does not suffer from the Maratos effect. The analysis indicates that the method has the same strong first- and second-order global convergence properties that have been established for augmented Lagrangian methods, yet is able to transition seamlessly to sSQP with fast local convergence in the neighborhood of a solution. Numerical results on some degenerate problems are reported.     

Nonmonotone Levenberg–Marquardt Algorithms and Their Convergence Analysis

In this paper, two nonmonotone Levenberg–Marquardt algorithms for unconstrained nonlinear least-square problems with zero or small residual are presented. These algorithms allow the sequence of objective function values to be nonmonotone, which accelerates the iteration progress, especially in the case where the objective function is ill-conditioned. Some global convergence properties of the proposed algorithms are proved under mild conditions which exclude the requirement for the positive definiteness of the approximate Hessian T(x). Some stronger global convergence properties and the local superlinear convergence of the first algorithm are also proved. Finally, a set of numerical results is reported which shows that the proposed algorithms are promising and superior to the monotone Levenberg–Marquardt algorithm according to the numbers of gradient and function evaluations.     

General primal-dual penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods are considered, that define a local continuously differentiable primal-dual path. The class of penalty/barrier terms includes most of the usual techniques like logarithmic barriers, SUMT, quadratic loss functions as well as exponential penalties, and the optimization problem which may contain inequality as well as equality constraints. The convergence of the corresponding general primal-dual path-following method is shown for local minima that satisfy strong second-order sufficiency conditions with linear independence constraint qualification (LICQ) and strict complementarity. A basic tool in the analysis of these methods is to estimate the radius of convergence of Newton's method depending on the penalty/barrier-parameter. Without using self-concordance properties convergence bounds are derived by direct estimations of the solutions of the Newton equations. Parameter selection rules are proposed which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem

In this paper, we present an efficient genetic algorithm (GA) for solving the travelling salesman problem (TSP) as a combinatorial optimization problem. In our computational model, we propose a complete subtour exchange crossover that does not break as some good subtours as possible, because the good subtours are worth preserving for descendants. Generally speaking, global search GA is considered to be better approaches than local searches. However, it is necessary to strengthen the ability of local search as well as global ones in order to increase a GA total efficiency. In this study, our GA applies a stochastic hill climbing procedure in the mutation process of the GA. Experimental results showed that the GA leads good convergence as high as 99 percent even for 500 cities TSP.     

混合约束下广义几何规划的一种SQP算法

针对带等式和不等式约束的广义几何规划问题，构造了一种ＳＱＰ算法并证明了该算法的全局收敛性和局部二阶收敛性。     

Local and integral properties of a search algorithm of the stochastic approximation type

An optimum random-search algorithm is considered. The convergence conditions to the greatest increase (local properties) and convergence to the point of extremum (integral properties) of a function by optimizing in the presence of noise, are found. The results are used for finding a global extremum of a multiextremal function.     

A local linear embedding module for evolutionary computation optimization

A Local Linear Embedding (LLE) module enhances the performance of two Evolutionary Computation (EC) algorithms employed as search tools in global optimization problems. The LLE employs the stochastic sampling of the data space inherent in Evolutionary Computation in order to reconstruct an approximate mapping from the data space back into the parameter space. This allows to map the target data vector directly into the parameter space in order to obtain a rough estimate of the global optimum, which is then added to the EC generation. This process is iterated and considerably improves the EC convergence. Thirteen standard test functions and two real-world optimization problems serve to benchmark the performance of the method. In most of our tests, optimization aided by the LLE mapping outperforms standard implementations of a genetic algorithm and a particle swarm optimization. The number and ranges of functions we tested suggest that the proposed algorithm can be considered as a valid alternative to traditional EC tools in more general applications. The performance improvement in the early stage of the convergence also suggests that this hybrid implementation could be successful as an initial global search to select candidates for subsequent local optimization.     

混合变异粒子群优化算法及其应用

为改善粒子群优化算法在解决复杂优化问题时收敛质量不高的不足,提出了一种改进的粒子群优化算法,即混合变异粒子群优化算法(HMPSO).HMPSO算法采用了带有随机因子的惯性权重取值更新策略,降低了标准粒子群优化算法中由于粒子飞行速度过大而错过最优解的概率,从而加速了算法的收敛速度.此外,通过混合变异进化环节的引入,缓解了粒子种群在进化过程中的多样性与收敛性这一矛盾,使得算法的全局探索与局部开发得到有效平衡.利用经典的基准测试函数和平面冗余机械臂逆运动学问题的求解来验证提出算法的有效性,试验结果表明:与其他算法相比,HMPSO算法具有更快的收敛速度、更高的收敛精度、更强的收敛稳定性以及更低的计算成本.     

PSOHS: an efficient two-stage approach for data clustering

Cluster analysis is an important task in data mining and refers to group a set of objects such that the similarities among objects within the same group are maximal while similarities among objects from different groups are minimal. The particle swarm optimization algorithm (PSO) is one of the famous metaheuristic optimization algorithms, which has been successfully applied to solve the clustering problem. However, it has two major shortcomings. The PSO algorithm converges rapidly during the initial stages of the search process, but near global optimum, the convergence speed will become very slow. Moreover, it may get trapped in local optimum if the global best and local best values are equal to the particle’s position over a certain number of iterations. In this paper we hybridized the PSO with a heuristic search algorithm to overcome the shortcomings of the PSO algorithm. In the proposed algorithm, called PSOHS, the particle swarm optimization is used to produce an initial solution to the clustering problem and then a heuristic search algorithm is applied to improve the quality of this solution by searching around it. The superiority of the proposed PSOHS clustering method, as compared to other popular methods for clustering problem is established for seven benchmark and real datasets including Iris, Wine, Crude Oil, Cancer, CMC, Glass and Vowel.     

Modified cuckoo search: A new gradient free optimisation algorithm

A new robust optimisation algorithm, which can be regarded as a modification of the recently developed cuckoo search, is presented. The modification involves the addition of information exchange between the top eggs, or the best solutions. Standard optimisation benchmarking functions are used to test the effects of these modifications and it is demonstrated that, in most cases, the modified cuckoo search performs as well as, or better than, the standard cuckoo search, a particle swarm optimiser, and a differential evolution strategy. In particular the modified cuckoo search shows a high convergence rate to the true global minimum even at high numbers of dimensions.     

一维凸函数牛顿法的全局收敛性及其应用

牛顿法是求解非线性方程F（x)＝0的一种经典方法。在一般假设条件下，牛顿法只具有局部收敛性。本文证明了一维凸函数牛顿法的全局收敛性，并且给出了它在全局优化积分水平集方法中的应用。     

求解旅行商问题的基于类Kruskal的混合粒子群算法

本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题,提出一种基于Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法(SKHPSO)。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段,产生一个较优的初始可行解,作为粒子群中的一员,然后再用改进的混合粒子群算法进行启发式搜索。SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索,而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析,结果表明:SKHPSO可明显提高求解的质量和效率。     

粒子群优化模糊神经网络在语音识别中的应用

针对模糊神经网络训练采用BP算法比较依赖于网络的初始条件,训练时间较长,容易陷入局部极值的缺点,利用粒子群优化算法(PSO)的全局搜索性能,将PSO用于模糊神经网络的训练过程.由于基本PSO算法存在一定的早熟收敛问题,引入一种自适应动态改变惯性因子的PSO算法,使算法具有较强的全局搜索能力.将此算法训练的模糊神经网络应用于语音识别中,结果表明,与BP算法相比,粒子群优化的模糊神经网络具有较高的收敛速度和识别率.     

资料变分同化中的若干理论问题

对变分同化中的若干理论问题进行了研究,具体讨论了一类简单模式在整体和局部观测资料下的变分同化问题．对于整体观测资料下的变分同化问题,利用变分同化方法对预报模式中的初值、参数以及模式进行了修正,从理论上作出了变分同化方法的误差估计及收敛精度的估计,证明了变分同化方法的有效性．对于局部观测资料下的变分同化问题,由于得到的解往往不适定,因而通常的变分同化方法失效．为了克服问题的不适定性所带来的困难,利用变分同化结合正则化方法对预报模式中的初值、参数以及模式进行修正,同样作出了变分同化方法的误差估计及收敛精度估计,证明了变分同化与正则化方法结合的必要性和有效性,并对正则化参数的选择提供了理论判据．最后,举了一个实例说明所提出的方法的有效性．     

Zero Mach number limit in critical spaces for compressible Navier-Stokes equations

We are concerned with the existence and uniqueness of local or global solutions for slightly compressible viscous fluids in the whole space. In [6] and [7], we proved local and global well-posedness results for initial data in critical spaces very close to the one used by H. Fujita and T. Kato for incompressible flows (see [14]). In the present paper, we address the question of convergence to the incompressible model (for ill-prepared initial data) when the Mach number goes to zero. When the initial data are small in a critical space, we get global existence and convergence. For large initial data and a bit of additional regularity, the slightly compressible solution is shown to exist as long as the corresponding incompressible solution does. As a corollary, we get global existence (and uniqueness) for slightly compressible two-dimensional fluids.     

使用非单调线搜索正割方法解约束优化的整体收敛性

基于Powell和Yuan所建议的近似Fetcher罚函数作为函数使用单调线搜索的技术,本文提供了一类正割方法解约束优化。在合理的条件下,证明了所提供的算法的整体收敛性和收敛速率。     

Properties of the solutions of delocalised coagulation and inception problems with outflow boundaries

Well-posedness is established for a family of equations modelling particle populations undergoing delocalised coagulation, advection, inflow and outflow in a externally specified velocity field. Very general particle types are allowed, while the spatial domain is a bounded region of d-dimensional space for which every point lies on exactly one streamline associated with the velocity field. The problem is formulated as a semi-linear ODE in the Banach space of bounded, additive set functions on particle position and type space. A local Lipschitz property is established in total variation norm for the propagators (generalised semi-groups) associated with the problem and used to construct a Picard iteration that establishes local existence and global uniqueness for any initial condition. The unique weak solution is shown further to be a differentiable or at least bounded variation strong solution under smoothness assumptions on the parameters of the coagulation interaction. In the case of one spatial dimension strong differentiability is established even for coagulation parameters with a particular bounded variation structure in space. This one-dimensional extension establishes the convergence of the simulation processes studied in Patterson (Stoch Anal Appl 31:1–30, 2013) to a unique and differentiable limit.