A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs

In this paper, a viable bandwidth reduction algorithm based on graphs for reducing the bandwidth of sparse symmetric matrices, arising from standard L-structured and Z-structured graphs, is presented. Bandwidth results for these matrices are obtained using this algorithm and compared with that of existing algorithms. This algorithm can easily be applied to these matrices while the bandwidths obtained are as good as those obtained with the existing algorithms.     

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

A hybrid heuristic for the maximum clique problem

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.     

IMPROVED RANDOMIZED ALGORITHM FOR THE EQUIVALENT 2-CATALOG SEGMENTATION PROBLEM

An improved randomized algorithm of the equivalent 2-catalog segmentation problem is presented. The result obtained in this paper makes some progress to answer the open problem by analyze this algorithm with performance guarantee. A 0.6378-approximation for the equivalent 2-catalog segmentation problem is obtained.     

A new multiobjective simulated annealing algorithm

A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions, suitable for the generation on non-convex fronts, are presented. The effectiveness of the algorithm is shown through five test problems. The parametric study presented shows that more fitness functions as well as more iteration gives more non-dominated points closer to the actual front. The study also compares the linear and elliptic fitness functions. The success of the algorithm is also demonstrated by comparing the quality metrics obtained to those obtained for a well-known evolutionary multiobjective algorithm.     

有界变量线性规划的基线算法

本文对有界变量线性规划的算法进行了研究，得到了一种解此问题的新算法。文中根据基线算法的算法原理，通过对BL表的旋转，在各变量满足界约束的条件下，使目标函数值不断增大，直至得到有界硬上界，从而得到问题的最优解。文中给出了有界变量线性规划基线算法的计算步骤，并给出了一个例子。与单纯形法相比，采用基线算法解有界变量线性规划操作更简单。迭代次数少，解题速度更快。     

THE CONVERGENCE OF APPROACH PENALTY FUNCTION METHOD FOR APPROXIMATE BILEVEL PROGRAMMING PROBLEM

' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com…     

Rehabilitation of the Gauss-Jordan algorithm

Summary In this paper a Gauss-Jordan algorithm with column interchanges is presented and analysed. We show that, in contrast with Gaussian elimination, the Gauss-Jordan algorithm has essentially differing properties when using column interchanges instead of row interchanges for improving the numerical stability. For solutions obtained by Gauss-Jordan with column interchanges, a more satisfactory bound for the residual norm can be given. The analysis gives theoretical evidence that the algorithm yields numerical solutions as good as those obtained by Gaussian elimination and that, in most practical situations, the residuals are equally small. This is confirmed by numerical experiments. Moreover, timing experiments on a Cyber 205 vector computer show that the algorithm presented has good vectorisation properties.     

A trust region algorithm for a class of nonlinear optimization

Abstract. This paper presents a trust region algorithm for nonlinear optimization with linear in-equality constraints. The global convergence of the algorithm is proved. Local quadratic con-vergence is obtained for a strong local minimizer.     

Numerical algorithm for solving diffusion-type equations on the basis of multigrid methods

A new numerical algorithm based on multigrid methods is proposed for solving equations of the parabolic type. Theoretical error estimates are obtained for the algorithm as applied to a two-dimensional initial-boundary value model problem for the heat equation. The good accuracy of the algorithm is demonstrated using model problems including ones with discontinuous coefficients. As applied to initial-boundary value problems for diffusion equations, the algorithm yields considerable savings in computational work compared to implicit schemes on fine grids or explicit schemes with a small time step on fine grids. A parallelization scheme is given for the algorithm.     

A Mixed Heuristic for Circuit Partitioning

As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithms for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. This paper describes a circuit partitioning algorithm which mixes Simulated Annealing (SA) and Tabu Search (TS) heuristics. The goal of such an algorithm is to obtain a balanced distribution of the target circuit among the processors of the multicomputer allowing a parallel CAD application for Test Pattern Generation to provide good efficiency. The results obtained indicate that the proposed algorithm outperforms both a pure Simulated Annealing and a Tabu Search. Moreover, the usefulness of the algorithm in providing a balanced workload distribution is demonstrated by the efficiency results obtained by a topological partitioning parallel test-pattern generator in which the proposed algorithm has been included. An extented algorithm that works with general graphs to compare our approach with other state of the art algorithms has been also included.     

适应性波束形成器的随机变界截尾算法

本文对适应性波束形成器给出一种递推随机变界截尾算法,并在较简单的条件下,证明了算法几乎处处具有大范围收敛性.     

Optimization of the generalized method of Hermitian and skew-Hermitian splitting iterations for solving symmetric saddle-point problems

An algorithm for solving a nonsingular symmetric system of linear equations with a saddle point is examined. This algorithm has two constant iteration parameters and is an extension of the algorithm of Hermitian and skew-Hermitian splitting iterations (the HSS algorithm). Analytical formulas are derived for the optimal values of the iteration parameters. The formulation of the optimization problem is a classical one for the saddle-point problems. The results obtained are sharp.     

An algorithm for minimax

An algorithm is proposed for computing an unconstrained minimax, based on differential equations with suitable stabilization terms. Methods for accelerating the convergence are discussed. For computing a constrained minimax, the augmented Lagrangian algorithm of Powell, Hestenes and Rockafellar is generalized to minimax, assuming the unconstrained minimax algorithm as a subroutine. An estimate of the convergence rate is obtained.     

Convergence analysis of a non-negative matrix factorization algorithm based on Gibbs random field modeling

Non-negative matrix factorization (NMF) is a new approach to deal with the multivariate nonnegative data. Although the classic multiplicative update algorithm can solve the NMF problems, it fails to find sparse and localized object parts. Then a Gibbs random field (GRF) modeling based NMF algorithm, called the GRF-NMF algorithm, try to directly model the prior object structure of the components into the NMF problem. In this paper, the convergence of the GRF-NMF algorithm and its advantages are investigated. Based on a classic model, the equilibrium points are obtained. Some invariant sets are constructed to prepare for the analysis of the convergence of the GRF-NMF algorithm. Then using stability theory of the equilibrium point, the convergence of the algorithm is proved and the convergence conditions of the algorithm are obtained. We theoretically present the advantages of the GRF-NMF algorithm in the end.     

一个新的带线性搜索的信赖域算法

本文对于无约束最优化问题提出了一个新的信赖域方法。在该算法中采用的是线性模型，并且当试探步不成功的时候，采用线性搜索，从而减少了计算量。文中证明了在适当的条件下算法的全局收敛性。     

一类凸优化的加速混合下降算法

凸优化问题的混合下降算法利用近似条件的已知信息和随机数扩张预测校正步得到了一组下降方向.而前向加速收缩算法利用高斯赛德尔迭代算法的技术,结合邻近点算法和近似邻近点算法的思想,构造了富有扩张性的下降方向.本文借鉴混合下降算法和前向加速收缩算法的思想,利用已有近似规则信息改善了混合下降算法的下降方向,得到了一类凸优化问题的加速混合下降算法.随后利用Markov不等式、凸函数性质和投影的基本性质等,实现了算法的依概率收敛证明.一系列数值试验表明了加速混合下降算法的有效性和效率性.     

A truncated Newton method with nonmonotone line search for unconstrained optimization

In this paper, an unconstrained minimization algorithm is defined in which a nonmonotone line search technique is employed in association with a truncated Newton algorithm. Numerical results obtained for a set of standard test problems are reported which indicate that the proposed algorithm is highly effective in the solution of illconditioned as well as of large dimensional problems.     

反射系数的线性最小均方误差估计

从地震记录信号中获取反射系数对岩性分析和寻找储油(气)地层构造是非常重要的,本文对非白噪型反射系数的反褶积模型方法进行了探讨,给出了一个获取反射系数的估计方法.