An alternative to the Bathe algorithm

This paper presents a new composite sub-steps algorithm for solving reliable numerical responses in structural dynamics. The newly developed algorithm is a two sub-steps, second-order accurate and unconditionally stable implicit algorithm with the same numerical properties as the Bathe algorithm. The detailed analysis of the stability and numerical accuracy is presented for the new algorithm, which shows that its numerical characteristics are identical to those of the Bathe algorithm. Hence, the new sub-steps scheme could be considered as an alternative to the Bathe algorithm. Meanwhile, the new algorithm possesses the following properties: (a) it produces the same accurate solutions as the Bathe algorithm for solving linear and nonlinear problems; (b) it does not involve any artificial parameters and additional variables, such as the Lagrange multipliers; (c) The identical effective stiffness matrices can be obtained inside two sub-steps; (d) it is a self-starting algorithm. Some numerical experiments are given to show the superiority of the new algorithm and the Bathe algorithm over the dissipative CH-α algorithm and the non-dissipative trapezoidal rule.     

Accurate evaluation of a polynomial in Chebyshev form

This paper presents a compensated algorithm to accurately evaluate a polynomial expressed in Chebyshev basis of the first and second kind with floating-point coefficients. The principle is to apply error-free transformations to improve the traditional Clenshaw algorithm. The new algorithm is as accurate as the Clenshaw algorithm performed in twice the working precision. Forward error analysis and numerical experiments illustrate the accuracy and properties of the proposed algorithm.     

混沌遗传算法对BP神经网络的改进研究

BP神经网络算法是目前应用最广泛的一种神经网络算法,但有收敛速度慢和易陷入局部极小值等缺陷.本文利用混沌遗传算法(CGA)具有混沌运动遍历性、遗传算法反演性的特性来改进BP神经网络算法.该算法的基本思想是用混沌遗传算法对BP神经网络算法的初始权值和初始阈值进行优化.把混沌变量加入遗传算法中,提高遗传算法的全局搜索能力和收敛速度;用混沌遗传算法优化后得到的最优解作为BP神经网络算法的初始权值和阈值.通过实验观察,改进后的结果与普通的BP神经网络算法的结果相比,具有更高的准确率.     

Affine-scaling for linear programs with free variables

The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.     

A combined direction stochastic approximation algorithm

The stochastic approximation problem is to find some root or minimum of a nonlinear function in the presence of noisy measurements. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy negative gradient direction as the iterative direction. In order to accelerate the classical RM algorithm, this paper gives a new combined direction stochastic approximation algorithm which employs a weighted combination of the current noisy negative gradient and some former noisy negative gradient as iterative direction. Both the almost sure convergence and the asymptotic rate of convergence of the new algorithm are established. Numerical experiments show that the new algorithm outperforms the classical RM algorithm.     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

A New Version of the Price's Algorithm for Global Optimization

We present an algorithm for finding a global minimum of a multimodal,multivariate function whose evaluation is very expensive, affected by noise andwhose derivatives are not available. The proposed algorithm is a new version ofthe well known Price's algorithm and its distinguishing feature is that ittries to employ as much as possible the information about the objectivefunction obtained at previous iterates. The algorithm has been tested on alarge set of standard test problems and it has shown a satisfactorycomputational behaviour. The proposed algorithm has been used to solveefficiently some difficult optimization problems deriving from the study ofeclipsing binary star light curves.     

Axiomatic characterization of a global optimization algorithm and investigation of its search strategy

A new axiomatic characterization of a rational algorithm for global minimization based on a statistical model of the objective function is suggested. The globality of the search strategy of such an algorithm is investigated as well as the convergence of the algorithm.     

A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity among second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such a scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second-order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large-scale optimization problems.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.     

Bayesian variable selection in generalized linear models using a combination of stochastic optimization methods

In this paper the usage of a stochastic optimization algorithm as a model search tool is proposed for the Bayesian variable selection problem in generalized linear models. Combining aspects of three well known stochastic optimization algorithms, namely, simulated annealing, genetic algorithm and tabu search, a powerful model search algorithm is produced. After choosing suitable priors, the posterior model probability is used as a criterion function for the algorithm; in cases when it is not analytically tractable Laplace approximation is used. The proposed algorithm is illustrated on normal linear and logistic regression models, for simulated and real-life examples, and it is shown that, with a very low computational cost, it achieves improved performance when compared with popular MCMC algorithms, such as the MCMC model composition, as well as with “vanilla” versions of simulated annealing, genetic algorithm and tabu search.     

Some Applications of a Polynomial Inequality to Global Optimization

In this paper, we use the Ehlich-Zeller-Gärtel inequality to derive an algorithm for finding the global minima of polynomials over hyperrectangles as well as to provide a bounding method for the branch-and-bound algorithm. The latter application of the inequality results in an improved algorithm which gives simultaneously a decreasing upper bound and an increasing lower bound for the global minimum at each iteration. The algorithm can be used also to find the Lipschitz constant of a polynomial.     

Studies in possibilistic recognition

This paper introduces an algorithm for pattern recognition. The algorithm will classify a measured object as belonging to one of N known classes or none of the classes. The algorithm makes use of fuzzy techniques and possibility is used instead of probability. The algorithm was conceived with the idea of recognizing fast moving objects, but it is shown to be more general. Fuzzy ISODATA's use as a front end to the algorithm is shown. The algorithm is shown to accomplish the objectives of correct classification or no classification. Values that describe possibility distributions are introduced with some of their properties investigated and illustrated. An expected value for a possibility distribution is also investigated. The algorithm actually proves to be adaptable to a wide variety of imprecise recognition problems. Some test results illustrate the use of the technique embodied in the algorithm and indicate its viability.     

Finding the shortest paths by node combination

By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.     

Using Gauss-Jordan elimination to compute the index,generalized nullspaces,and Drazin inverse

We develop and analyze a new algorithm that computes bases for the null spaces of all powers of a given matrix, as well as its index. The algorithm uses row operations and “shuffling” steps in which rows of pairs of matrices are interchanged. In particular, the new algorithm may be viewed as an extension of the classic Gauss-Jordan elimination method for inverting a nonsingular matrix. It is also shown that the Drazin inverse has a simple representation in terms of the output of the algorithm and the original matrix.     

非线性算子方程的泰勒展式算法

本文的目的是给出一种解Ｈｉｌｂｅｒｔ空间中非线性方程的ｋ阶泰勒展式算法（ｋ１）．标准Ｇａｌｅｒｋｉｎ方法可以看作１阶泰勒展式算法，而最优非线性Ｇａｌｅｒｋｉｎ方法可视为２阶泰勒展式算法．我们应用这种算法于定常的Ｎａｖｉｅｒ－Ｓｔｏｋｅｓ方程的数值逼近．在一定情景下，最优非线性Ｇａｌｅｒｋｉｎ方法提供比标准Ｇａｌｅｒｋｉｎ方法和非线性Ｇａｌｅｒｋｉｎ方法更高阶的收敛速度．     

An adaptive simulated annealing algorithm

In this paper, inspired by the idea of Metropolis algorithm, a new sample adaptive simulated annealing algorithm is constructed on finite state space. This new algorithm can be considered as a substitute of the annealing of iterative stochastic schemes. The convergence of the algorithm is shown.     

An effective heuristic algorithm to minimise stack shuffles in selecting steel slabs from the slab yard for heating and rolling

Steel production is a multi-stage process. A slab yard serves as a buffer between the continuous casting stage and the steel rolling stage. Steel slabs are stored in stacks in the yard. Shuffling is needed when picking up a slab for heating and rolling, if it is not in the top position of a stack. This paper studies the problem of selecting appropriate slabs in the yard for a given rolling schedule so as to minimise the total shuffling cost. The study uses the hot strip rolling mill in Shanghai Baoshan Iron and Steel Complex as an application background. We propose a new heuristic algorithm to solve the problem. This is a two-phase algorithm that first generates an initial feasible solution and then improves it using local search. The new algorithm is compared with the algorithm in use on randomly generated test problems and on real data. Experimental results show that the proposed algorithm yields significant better solutions. The average improvement over the old algorithm is 15%.     

Correctness proof of an in-place permutation

The correctness of an in-place permutation algorithm is proved. The algorithm exchanges elements belonging to a permutation cycle. A suitable assertion is constructed from which the correctness can be deduced after completion of the algorithm.An in-place rectangular matrix transposition algorithm is given as an example.     

The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems

We study both weighted and unweighted unconstrained two-dimensional guillotine cutting problems. We develop a hybrid approach which combines two heuristics from the literature. The first one (DH) uses a tree-search procedure introducing two strategies: Depth-first search and Hill-climbing. The second one (KD) is based on a series of one-dimensional Knapsack problems using Dynamic programming techniques. The DH /KD algorithm starts with a good initial lower bound obtained by using the KD algorithm. At each level of the tree-search, the proposed algorithm uses also the KD algorithm for constructing new lower bounds and uses another one-dimensional knapsack for constructing refinement upper bounds. The resulting algorithm can be seen as a generalization of the two heuristics and solves large problem instances very well within small computational time. Our algorithm is compared to Morabito et al.'s algorithm (the unweighted case), and to Beasley's [2] approach (the weighted case) on some examples taken from the literature as well as randomly generated instances.