On the convergence of a factorized distribution algorithm with truncation selection

We investigate the global convergence of a factorized distribution algorithm (FDA) with truncation selection. Like conventional genetic algorithms, FDAs maintain and successively improve a population of solutions. In FDAs, a distribution model is built based on the statistical information extracted from a set of selected solutions in the current population, and then the model thus built is used to generate new solutions for the next generation. The variable‐dependence structure of the distribution model in FDAs is determined by the variable‐interaction structure of the objective function. We prove that the FDA with truncation selection converges globally for optimization of a class of additively decomposable functions (ADF). Our results imply that the utilization of appropriately selected dependence relationships is sufficient to guarantee the global convergence of estimation of distribution algorithms (EDAs) for optimization of ADFs. © 2004 Wiley Periodicals, Inc. Complexity 9: 17–23, 2004     

A numerically stable optimization method based on A homogeneous function

An improved version of an unconstrained optimization algorithm based upon a homogeneous function is presented. The method is numerically stable and uses the Bartels—Golub factorization instead of Householder's modification formula. Several numerical tests indicate that the proposed method is robust and very efficient.     

On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms

Recently, Mehrotra [3] proposed a predictor—corrector primal—dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra's algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1 [2]. In this paper, we study the theoretical convergence properties of Mehrotra's interior-point algorithmic framework. For generality, we carry out our analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, we establish polynomial complexity bounds for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. These results are summarized in the last section in a table.Research supported in part by NSF DMS-9102761, DOE DE-FG05-91ER25100 and DOE DE-FG02-93ER25171.Corresponding author.     

Computing the probability density function of the stable Paretian distribution

The practical implementation of a stable Paretian model is a nontrivial task, because—with the exception of a few special cases—its probability density function cannot be expressed analytically. Here, we present an algorithm for calculating the probability density function of the asymmetric stable Paretian distribution. Due to the use of the Fast Fourier Transform, the algorithm is computationally efficient, easily implemented, and of similar accuracy as existing algorithms.     

Parallel sparse linear algebra and application to structural mechanics

The framework of this paper is the parallelization of a plasticity algorithm that uses an implicit method and an incremental approach. More precisely, we will focus on some specific parallel sparse linear algebra algorithms which are the most time-consuming steps to solve efficiently such an engineering application. First, we present a general algorithm which computes an efficient static scheduling of block computations for parallel sparse linear factorization. The associated solver, based on a supernodal fan-in approach, is fully driven by this scheduling. Second, we describe a scalable parallel assembly algorithm based on a distribution of elements induced by the previous distribution for the blocks of the sparse matrix. We give an overview of these algorithms and present performance results on an IBM SP2 for a collection of grid and irregular problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Grey prediction evolution algorithm for global optimization

This article uses the grey prediction theory to structure a new metaheuristic: grey prediction evolution algorithm based on the even grey model. The proposed algorithm considers the population series of evolutionary algorithms as a time series, and uses the even grey model as a reproduction operator to forecast the next population (without employing any mutation and crossover operators). It is theoretically proven that the reproduction operator based on the even grey model is adaptive. Additionally, the algorithmic search mechanism and its differences with other evolutionary algorithms are analyzed. The performance of the proposed algorithm is validated on CEC2005 benchmark functions and a test suite composed of six engineering constrained design problems. The comparison experiments show the effectiveness and superiority of the proposed algorithm.The proposed algorithm can be regarded as the first case of structuring metaheuristics by using the prediction theory. The novel algorithm is anticipated to influence two future works. The first is to propose more metaheuristics inspired by prediction theories (including some statistical algorithms). Another is that the theoretical results of these prediction systems can be used for this novel type of metaheuristics.     

连续代数扩域上多项式因式分解的Trager算法

多项式的因式分解是符号计算中最基本的算法,二十世纪六十年代开始出现的关于多项式因式分解的工作被认为是符号计算领域的起源．目前多项式的因式分解已经成熟,并已在Maple等符号计算软件中实现,但代数扩域上的因式分解算法还有待进一步改进．代数扩域上的基本算法是Trager算法．Weinberger等提出了基于Hensel提升的算法．这些算法是在单个扩域上做因式分解．而在吴零点分解定理中,多个代数扩域上的因式分解是非常基本的一步,主要用于不可约升列的计算．为了解决这一问题,吴文俊,胡森、王东明分别提出了基于方程求解的多个扩域上的因式分解算法．王东明、林东岱提出了另外一个算法Trager算法相似,将问题化为有理数域上的分解．他们应用了吴的三角化算法,因此算法的终止性依赖于吴方法的计算．支丽红则将提升技巧用于多个扩域上的因式分解算法．本文将Trager的算法直接推广为连续扩域上的因式分解,只涉及结式计算与有理数域上的因式分解,给出了多个代数扩域上的因式分解一个直接的算法．     

Decomposition of Polytopes and Polynomials

Motivated by a connection with the factorization of multivariate polynomials, we study integral convex polytopes and their integral decompositions in the sense of the Minkowski sum. We first show that deciding decomposability of integral polygons is NP-complete then present a pseudo-polynomial-time algorithm for decomposing polygons. For higher-dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithms include absolute irreducibility testing and factorization of polynomials via their Newton polytopes. Received December 2, 1999, and in revised form November 6, 2000. Online publication May 4, 2001.     

Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.     

Constant potential primal—dual algorithms: A framework

We start with a study of the primal—dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al., Mizuno and Nagasawa, and new potential functions we establish a framework for primal—dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. Our algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.Research performed while the author was Ph.D. student at Cornell University and was supported in part by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027, and also by NSF, AFOSR and ONR through NSF Grant DMS-8920550.     

Linearized factorization techniques for multidimensional reaction—diffusion equations

An iterative predictor—corrector technique for the elimination of the approximate factorization errors which result from the factorization of linearized θ-methods in multidimensional reaction—diffusion equations is proposed, and its convergence and linear stability are analyzed. Four approximate factorization techniques which do not account for the approximate factorization errors are developed. The first technique uses the full Jacobian matrix of the reaction terms, requires the inversion of, in general, dense matrices, and its approximate factorization errors are second-order accurate in time. The second and third methods approximate the Jacobian matrix by diagonal or triangular ones which are easily inverted but their approximate factorization errors are, however, first-order accurate in time. The fourth approximately factorized method has approximate factorization errors which are second-order accurate in time and requires the inversion of lower and upper triangular matrices. The techniques are applied to a nonlinear, two-species, two-dimensional system of reaction—diffusion equations in order to determine the approximate factorization errors and those resulting from the approximations to the Jacobian matrix as functions of the allocation of the reaction terms, space and time.     

A derivative-free approximate gradient sampling algorithm for finite minimax problems

In this paper we present a derivative-free optimization algorithm for finite minimax problems. The algorithm calculates an approximate gradient for each of the active functions of the finite max function and uses these to generate an approximate subdifferential. The negative projection of 0 onto this set is used as a descent direction in an Armijo-like line search. We also present a robust version of the algorithm, which uses the ‘almost active’ functions of the finite max function in the calculation of the approximate subdifferential. Convergence results are presented for both algorithms, showing that either f(x ^k )→?∞ or every cluster point is a Clarke stationary point. Theoretical and numerical results are presented for three specific approximate gradients: the simplex gradient, the centered simplex gradient and the Gupal estimate of the gradient of the Steklov averaged function. A performance comparison is made between the regular and robust algorithms, the three approximate gradients, and a regular and robust stopping condition.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.     

Convex analysis treated by linear programming

The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham).     

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

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

Towards a queueing-based framework for in-network function computation

We seek to develop network algorithms for function computation in sensor networks. Specifically, we want dynamic joint aggregation, routing, and scheduling algorithms that have analytically provable performance benefits due to in-network computation as compared to simple data forwarding. To this end, we define a class of functions, the Fully-Multiplexible functions, which includes several functions such as parity, MAX, and kth-order statistics. For such functions we characterize the maximum achievable refresh rate of the network in terms of an underlying graph primitive, the min-mincut. In acyclic wireline networks we show that the maximum refresh rate is achievable by a simple algorithm that is dynamic, distributed, and only dependent on local information. In the case of wireless networks we provide a MaxWeight-like algorithm with dynamic flow-splitting, which is shown to be throughput-optimal.     

The matrix sign function and computations in systems

The matrix sign function has several interesting properties which form the basis of new solution algorithms for problems which occur frequently in systems and control theory applications. Presented in this paper are new algorithms, based on the matrix sign function, for the solution of algebraic matrix Riccati equations, Lyapunov equations, coupled Riccati equations, spectral factorization, matrix square roots, pole assignment, and the algebraic eigenvalue-eigenvector problem. Examples of the application of each algorithm are also presented.     

A globally convergent primal—dual interior point algorithm for convex programming

In this paper, we study the global convergence of a large class of primal—dual interior point algorithms for solving the linearly constrained convex programming problem. The algorithms in this class decrease the value of a primal—dual potential function and hence belong to the class of so-called potential reduction algorithms. An inexact line search based on Armijo stepsize rule is used to compute the stepsize. The directions used by the algorithms are the same as the ones used in primal—dual path following and potential reduction algorithms and a very mild condition on the choice of the centering parameter is assumed. The algorithms always keep primal and dual feasibility and, in contrast to the polynomial potential reduction algorithms, they do not need to drive the value of the potential function towards — in order to converge. One of the techniques used in the convergence analysis of these algorithms has its root in nonlinear unconstrained optimization theory.Research supported in part by NSF Grant DDM-9109404.     

Multidimensional Cooley–Tukey Algorithms Revisited

The representation theory of Abelian groups is used to obtain an algebraic divide-and-conquer algorithm for computing the finite Fourier transform. The algorithm computes the Fourier transform of a finite Abelian group in terms of the Fourier transforms of an arbitrary subgroup and its quotient. From this algebraic algorithm a procedure is derived for obtaining concrete factorizations of the Fourier transform matrix in terms of smaller Fourier transform matrices, diagonal multiplications, and permutations. For cyclic groups this gives as special cases the Cooley–Tukey and Good–Thomas algorithms. For groups with several generators, the procedure gives a variety of multidimensional Cooley–Tukey type algorithms. This method of designing multidimensional fast Fourier transform algorithms gives different data flow patterns from the standard “row–column” approaches. We present some experimental evidence that suggests that in hierarchical memory environments these data flows are more efficient.