STABLE DOUBLE LR ALGORITHM AND ITS ERROR ANALYSIS

In this paper, the normative matrices and their double LR transformation with origin shifts are defined, and the essential relationship between the double LR transformation of a normative matrix and the QR transformation of the related symmetric tridiagonal matrix is proved. We obtain a stable double LR algorithm for double LR transformation of normative matrices and give the error analysis of our algorithm. The operation number of the stable double LR algorithm for normative matrices is only four sevenths of the rational QR algorithm for reed symmetric tridiagonal matrices.     

A QR DECOMPOSITION BASED SOLVER FOR THE LEAST SQUARES PROBLEMS FROM THE MINIMAL RESIDUAL METHOD FOR THE SYLVESTER EQUATION

Based on the generalized minimal residual （GMRES） principle, Hu and Reichel proposed a minimal residual algorithm for the Sylvester equation. The algorithm requires the solution of a structured least squares problem. They form the normal equations of the least squares problem and then solve it by a direct solver, so it is susceptible to instability. In this paper, by exploiting the special structure of the least squares problem and working on the problem directly, a numerically stable QR decomposition based algorithm is presented for the problem. The new algorithm is more stable than the normal equations algorithm of Hu and Reichel. Numerical experiments are reported to confirm the superior stability of the new algorithm.     

Cooley-Tukey FFT在高维的算法

A new fast algorithm is presented for multidimensional DFT in this paper. This algorithm is derived based on an interesting coding technique for multidimensional integral point, named the technique vector coding. And called the algorithm VCFFT (vector coding fast Fourier transform). Since the VC-FFT is the extension of Cooley-Tukey algorithm from one-dimensional to multidimensional, its structure of program is simple as Cooley-Tukey FFT, and significantly reduces multiplications and recursive stages.     

DISTRIBUTED OPTIMAL LOCAL DOUBLE LOOP NETWORK

A distibuted optimal local double loop(DOLDL) network is presented. Emphasis is laid on the topology and distributed routing algorithms for the DOLDL. On the basis of building an abstract model, a set of definitions and theorems are described and proved. An algorithm which can optimize the double loop networks is presented. The optimal values of the topologic parameters for the DOLDL have been obtained by the algorithm, and these numer. cal results are analyzed, The study shows that the bounds of the optimal diameter (d) and average hop distance (a) for this class of networks are and, respectively (N is the number of nodes in the network. 「3≤N≤10~4). A class of the distributed routing algorithms for the DOLDL and the implementation procedure of an adaptive fault-tolerant algorithm are proposed. The correctness of the algorithm has been also verified by simulating.     

Convergence analysis of a nonlinear Lagrange algorithm for general nonlinear constrained optimization problems

The convergence analysis of a nonlinear Lagrange algorithm for solving nonlinear constrained optimization problems with both inequality and equality constraints is explored in detail. The estimates for the derivatives of the multiplier mapping and the solution mapping of the proposed algorithm are discussed via the technique of the singular value decomposition of matrix. Based on the estimates, the local convergence results and the rate of convergence of the algorithm are presented when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions. Furthermore, the condition number of the Hessian of the nonlinear Lagrange function with respect to the decision variables is analyzed, which is closely related to efficiency of the algorithm. Finally, the preliminary numericM results for several typical test problems are reported.     

A NEW ALGORITHM FOR COMPUTING LARGEST REAL PART EIGENVALUE OF MATRICES：COLLATZ ＆ PERRON-FROBERNIUS＇ APPROACH

This paper describes a new method and algorithm for the numerical solution of eigenvalues with the largest real part of positive matrices.The method is based on a numerical implementation of Collatz’s eigenvalue inclusion theorem for non-negative irreducible matrices.Eigenvalues are analyzed for the studies of the stability of linear systems.Finally, a numerical discussion is given to derive the required number of mathematical operations of the new algorithm. Comparisons between the new algorithm and several well known ones, such as Power, and QR methods, are discussed.     

THE OPTIMIZATION PROBLEM AND ITS SOLUTION IN MIXED-ACIDS TITRATION ANALYSIS

Based on the general formula of acid-base titration in analytical chemistry, an optimization model for evaluation of dissociation constants and concentrations of acids in mixed-acids is proposed in this paper. The mathematical properties of the optimization model are discussed, and then an algorithm for solving the problem is given, the convergence and the reliability of the algorithm are proved both by theoretical analysis and experimental examples.     

A DIRECT SEARCH FRAME-BASED CONJUGATE GRADIENTS METHOD

A derivative-free frame-based conjugate gradients algorithm is presented.Convergenceis shown for C~1 functions,and this is verified in numerical trials.The algorithm is tested ona variety of low dimensional problems,some of which are ill-conditioned,and is also testedon problems of high dimension.Numerical results show that the algorithm is effectiveon both classes of problems.The results are compared with those from a discrete quasi-Newton method,showing that the conjugate gradients algorithm is competitive.Thealgorithm exhibits the conjugate gradients speed-up on problems for which the Hessian atthe solution has repeated or clustered eigenvalues.The algorithm is easily parallelizable.     

Two algorithms for two-phase Stefan type problems

In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is presented and the upper bounds of the convergence rates are derived.Some numerical experiments are shown to demonstrate that for the second Uzawa algorithm which is an improved version of the first Uzawa algorithm,the convergence rate is uniformly bounded away from 1 if τh^-2 is kept bounded,where τ is the time step size and h the space mesh size.     

A superlinearly and quadratically convergent SQP type feasible method for constrained optimization

A new SQP type feasible method for inequality constrained optimization is presented, it is a combination of a master algorithm and an auxiliary algorithm which is taken only in finite iterations. The directions of the master algorithm are generated by only one quadratic programming, and its step-size is always one, the directions of the auxiliary algorithm are new “secondorder“ feasible descent. Under suitable assumptions, the algorithm is proved to possess global and strong convergence, superlinear and quadratic convergence.     

A rank-one algorithm for unconstrained function minimization

A rank-one algorithm is presented for unconstrained function minimization. The algorithm is a modified version of Davidon's variance algorithm and incorporates a limited line search. It is shown that the algorithm is a descent algorithm; for quadratic forms, it exhibits finite convergence, in certain cases. Numerical studies indicate that it is considerably superior to both the Davidon-Fletcher-Powell algorithm and the conjugate-gradient algorithm.     

A descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

An algorithm for local continuous optimization of traffic signals

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.     

一个新的线性规划无人工变量算法

本文研究了线性规划的求解问题.利用对偶转化的方法,获得了一个计算效率高的新的无人工变量通用算法.该新算法比最近提出的无人工变量算法push-to-pull算法效率更高.     

遗传算法的物理解释

提出了一种理想化的模拟仿生搜索算法——扰动算法 ,以此方法为基础 ,分析了遗传算法的搜索过程和效率问题 ,阐明了遗传算法作为一种次优算法的有效性 .相对于遗传算法的生物解释 ,本文给出了相应的物理解释 .同时 ,本文为遗传算法、进化策略和模拟退火算法找到了一种统一的物理解释 ,揭示了这些重要的仿生类算法实质上的相似性 .     

An Arnoldi-Extrapolation algorithm for computing PageRank

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.     

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.     

一种新的双模式盲均衡算法研究

针对恒模算法(CMA)收敛速度较慢、收敛后均方误差较大的缺点,提出一种新的双模式盲均衡算法.在算法初期,利用能快速收敛的归一化恒模算法(NCMA)进行冷启动,在算法收敛后切换到判决引导(DD-LMS)算法,减少误码率.计算机仿真表明,提出的新算法有较快的收敛速度和较低的误码率.     

Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

A DERIVATIVE-FREE ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

In this paper a hybrid algorithm which combines the pattern search method and the genetic algorithm for unconstrained optimization is presented. The algorithm is a deterministic pattern search algorithm,but in the search step of pattern search algorithm,the trial points are produced by a way like the genetic algorithm. At each iterate, by reduplication,crossover and mutation, a finite set of points can be used. In theory,the algorithm is globally convergent. The most stir is the numerical results showing that it can find the global minimizer for some problems ,which other pattern search algorithms don＇t bear.