Multiple solution of systems of linear algebraic equations by an iterative method with the adaptive recalculation of the preconditioner

The mean time needed to solve a series of systems of linear algebraic equations (SLAEs) as a function of the number of SLAEs is investigated. It is proved that this function has an extremum point. An algorithm for adaptively determining the time when the preconditioner matrix should be recalculated when a series of SLAEs is solved is developed. A numerical experiment with multiply solving a series of SLAEs using the proposed algorithm for computing 100 capacitance matrices with two different structures—microstrip when its thickness varies and a modal filter as the gap between the conductors varies—is carried out. The speedups turned out to be close to the optimal ones.     

Sequencing by hybridization: an enhanced crossover operator for a hybrid genetic algorithm

This paper presents a genetic algorithm for an important computational biology problem. The problem appears in the computational part of a new proposal for DNA sequencing denominated sequencing by hybridization. The general usage of this method for real sequencing purposes depends mainly on the development of good algorithmic procedures for solving its computational phase. The proposed genetic algorithm is a modified version of a previously proposed hybrid genetic algorithm for the same problem. It is compared with two well suited meta-heuristic approaches reported in the literature: the hybrid genetic algorithm, which is the origin of our proposed variant, and a tabu-scatter search algorithm. Experimental results carried out on real DNA data show the advantages of using the proposed algorithm. Furthermore, statistical tests confirm the superiority of the proposed variant over the state-of-the-art heuristics.     

Weighted decision trees where the cost of a test depends on its outcome

The problem of choosing strategies which minimize the cost of decision tree testing is considered in the case where the cost of each test depends on its outcome. The classical entropy bound on the cost is derived and we propose an algorithm for decision tree design based on an extension of Huffman's construction. By comparing the mean costs for a large sample of randomly chosen situations, we show that this algorithm performs well compared with a number of previously published algorithms. The algorithms are also compared with optimal performance for a range of simple cases.     

Efficient experimental designs when most treatments are unreplicated

In early generation variety trials, large numbers of new breeders’ lines (varieties) may be compared, with each having little seed available. A so-called unreplicated trial has each new variety on just one plot at a site, but includes several replicated control varieties, making up around 10% and 20% of the trial. The aim of the trial is to choose some (usually around one third) good performing new varieties to go on for further testing, rather than precise estimation of their mean yields.Now that spatial analyses of data from field experiments are becoming more common, there is interest in an efficient layout of an experiment given a proposed spatial analysis and an efficiency criterion. Common optimal design criteria values depend on the usual C-matrix, which is very large, and hence it is time consuming to calculate its inverse. Since most varieties are unreplicated, the variety incidence matrix has a simple form, and some matrix manipulations can dramatically reduce the computation needed. However, there are many designs to compare, and numerical optimisation lacks insight into good design features. Some possible design criteria are discussed, and approximations to their values considered. These allow the features of efficient layouts under spatial dependence to be given and compared.     

A spectral algorithm for envelope reduction of sparse matrices

The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope-reducing reordering is obtained by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. This Laplacian eigenvector solves a continuous relaxation of a discrete problem related to envelope minimization called the minimum 2-sum problem. The permutation vector computed by the spectral algorithm is a closest permutation vector to the specified Laplacian eigenvector. Numerical results show that the new reording algorithm usually computes smaller envelope sizes than those obtained from the current standards such as the Gibbs—Poole—Stockmeyer (GPS) algorithm or the reverse Cuthill—McKee (RCM) algorithm in SPARSPAK, in some cases reducing the envelope by more than a factor of two.     

Mining time series data for segmentation by using Ant Colony Optimization

In trying to distinguish data features within time series data for specific time intervals, time series segmentation technology is often required. This research divides time series data into segments of varying lengths. A time series segmentation algorithm based on the Ant Colony Optimization (ACO) algorithm is proposed to exhibit the changeability of the time series data. In order to verify the effect of the proposed algorithm, we experiment with the Bottom-Up method, which has been reported in available literature to give good results for time series segmentation. Simulation data and genuine stock price data are also used in some of our experiments. The research result shows that time series segmentation run by the ACO algorithm not only automatically identifies the number of segments, but its segmentation cost was lower than that of the time series segmentation using the Bottom-Up method. More importantly, during the ACO algorithm process, the degree of data loss is also less compared to that of the Bottom-Up method.     

Structured Markov Chain Monte Carlo

Abstract

This article introduces a general method for Bayesian computing in richly parameterized models, structured Markov chain Monte Carlo (SMCMC), that is based on a blocked hybrid of the Gibbs sampling and Metropolis—Hastings algorithms. SMCMC speeds algorithm convergence by using the structure that is present in the problem to suggest an appropriate Metropolis—Hastings candidate distribution. Although the approach is easiest to describe for hierarchical normal linear models, we show that its extension to both nonnormal and nonlinear cases is straightforward. After describing the method in detail we compare its performance (in terms of run time and autocorrelation in the samples) to other existing methods, including the single-site updating Gibbs sampler available in the popular BUGS software package. Our results suggest significant improvements in convergence for many problems using SMCMC, as well as broad applicability of the method, including previously intractable hierarchical nonlinear model settings.     

Computationally Efficient Estimation for the Generalized Odds Rate Mixture Cure Model With Interval-Censored Data

For semiparametric survival models with interval-censored data and a cure fraction, it is often difficult to derive nonparametric maximum likelihood estimation due to the challenge in maximizing the complex likelihood function. In this article, we propose a computationally efficient EM algorithm, facilitated by a gamma-Poisson data augmentation, for maximum likelihood estimation in a class of generalized odds rate mixture cure (GORMC) models with interval-censored data. The gamma-Poisson data augmentation greatly simplifies the EM estimation and enhances the convergence speed of the EM algorithm. The empirical properties of the proposed method are examined through extensive simulation studies and compared with numerical maximum likelihood estimates. An R package “GORCure” is developed to implement the proposed method and its use is illustrated by an application to the Aerobic Center Longitudinal Study dataset. Supplementary material for this article is available online.     

A Bayesian approach to constrained single- and multi-objective optimization

This article addresses the problem of derivative-free (single- or multi-objective) optimization subject to multiple inequality constraints. Both the objective and constraint functions are assumed to be smooth, non-linear and expensive to evaluate. As a consequence, the number of evaluations that can be used to carry out the optimization is very limited, as in complex industrial design optimization problems. The method we propose to overcome this difficulty has its roots in both the Bayesian and the multi-objective optimization literatures. More specifically, an extended domination rule is used to handle objectives and constraints in a unified way, and a corresponding expected hyper-volume improvement sampling criterion is proposed. This new criterion is naturally adapted to the search of a feasible point when none is available, and reduces to existing Bayesian sampling criteria—the classical Expected Improvement (EI) criterion and some of its constrained/multi-objective extensions—as soon as at least one feasible point is available. The calculation and optimization of the criterion are performed using Sequential Monte Carlo techniques. In particular, an algorithm similar to the subset simulation method, which is well known in the field of structural reliability, is used to estimate the criterion. The method, which we call BMOO (for Bayesian Multi-Objective Optimization), is compared to state-of-the-art algorithms for single- and multi-objective constrained optimization.     

On Stability and Stabilizability of Singular Stochastic Systems with Delays

This paper deals with the class of continuous-time singular linear systems with Markovian jump parameters and time delays. Sufficient conditions on the stochastic stability and stochastic stabilizability are developed. A design algorithm for a state feedback controller which guarantees that the closed-loop dynamics will be regular, impulse free, and stochastically stable is proposed in terms of the solutions to linear matrix inequalities. The research of this author was supported by NSERC Grant RGPIN36444-02. The research of this author was supported by the Program for a New Century of Excellent Talents in the Universities and by the Foundation for the Authors of National Excellent Doctoral Dissertations of P. R. China, Grant 200240. The research of this author was supported by HKU Grant RGC 7029/05P.     

Multi-ant colony system (MACS) for a vehicle routing problem with backhauls

The vehicle routing problem with backhaul (VRPB) is an extension of the capacitated vehicle routing problem (CVRP). In VRPB, there are linehaul as well as backhaul customers. The number of vehicles is considered to be fixed and deliveries for linehaul customers must be made before any pickups from backhaul customers. The objective is to design routes for the vehicles so that the total distance traveled is minimized. We use multi-ant colony system (MACS) to solve VRPB which is a combinatorial optimization problem. Ant colony system (ACS) is an algorithmic approach inspired by foraging behavior of real ants. Artificial ants are used to construct a solution by using pheromone information from previously generated solutions. The proposed MACS algorithm uses a new construction rule as well as two multi-route local search schemes. An extensive numerical experiment is performed on benchmark problems available in the literature.     

悬索桥竖向自由振动的传递矩阵解

该文将传递矩阵方法引入悬索桥竖向自由振动求解.首先,提出了悬索桥竖向自由振动微分方程的求解方法,由此求解方法可直接得到结构自由振动解析式.在此基础上,得出了悬索桥竖向自由振动分析的传递矩阵.应用此方法,该文研究了等截面悬索桥及变截面悬索桥竖向自由振动问题.研究结果表明,传递矩阵法能高效地进行悬索桥竖向自由振动分析,并对变截面问题的处理有独特的优势.研究工作对悬索桥在方案设计阶段的动力学分析有一定的参考价值和借鉴意义.     

Computation of M. L. estimates for the parameters of a negative binomial distribution from grouped data. A comparison of the scoring,Newton—Raphson and E-M algorithms

Computation of M. L. estimates for the parameters of a negative binomial distribution from grouped data is considered. For this problem the Scoring, Newton—Raphson and E-M algorithm is derived. Using simulated data the performance of the algorithms is compared with respect to convergence, number of iterations and computing time. Finally an empirical example drawn from actuarial science is given.     

An Exact Least Trimmed Squares Algorithm for a Range of Coverage Values

A new algorithm to solve exact least trimmed squares (LTS) regression is presented. The adding row algorithm (ARA) extends existing methods that compute the LTS estimator for a given coverage. It employs a tree-based strategy to compute a set of LTS regressors for a range of coverage values. Thus, prior knowledge of the optimal coverage is not required. New nodes in the regression tree are generated by updating the QR decomposition of the data matrix after adding one observation to the regression model. The ARA is enhanced by employing a branch and bound strategy. The branch and bound algorithm is an exhaustive algorithm that uses a cutting test to prune nonoptimal subtrees. It significantly improves over the ARA in computational performance. Observation preordering throughout the traversal of the regression tree is investigated. A computationally efficient and numerically stable calculation of the bounds using Givens rotations is designed around the QR decomposition, avoiding the need to explicitly update the triangular factor when an observation is added. This reduces the overall computational load of the preordering device by approximately half. A solution is proposed to allow preordering when the model is underdetermined. It employs pseudo-orthogonal rotations to downdate the QR decomposition. The strategies are illustrated by example. Experimental results confirm the computational efficiency of the proposed algorithms. Supplemental materials (R package and formal proofs) are available online.     

Algorithm for computing the mechanical impedances of reinforcing ribs of various shapes

The problem is considered of finding the mechanical impedances of reinforcing ribs of various shapes. The rib is modeled by a narrow plate. The thickness of the rib (the thickness of the plate from which the rib is made) is thus considered small as compared with the height of the rib (the width of the plate). The height of the rib h is assumed small as compared with the lengths of waves propagating in the material of the plate. One of the edges of the rib is assumed to be free of stresses. The matrix giving the relation between the stresses and the velocities of displacements on the second (loaded) edge is called the impedance matrix. An algorithm is proposed for computing the coefficients of the expansion of the impedance matrix in a Taylor series in powers of h. The method is illustrated by the computation of the mechanical impedances of rectilinear and annular reinforcing ribs.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.     

Sparse Distance Weighted Discrimination

Distance weighted discrimination (DWD) was originally proposed to handle the data piling issue in the support vector machine. In this article, we consider the sparse penalized DWD for high-dimensional classification. The state-of-the-art algorithm for solving the standard DWD is based on second-order cone programming, however such an algorithm does not work well for the sparse penalized DWD with high-dimensional data. To overcome the challenging computation difficulty, we develop a very efficient algorithm to compute the solution path of the sparse DWD at a given fine grid of regularization parameters. We implement the algorithm in a publicly available R package sdwd. We conduct extensive numerical experiments to demonstrate the computational efficiency and classification performance of our method.     

The structure matrix of (0,1)-matrices: Its rank,trace, and eigenvalues. An application to econometric models

This paper deals with questions raised by R.A. Brualdi concerning the structure matrix of (0,1)-matrices with fixed row and column sum vectors; namely, determining its rank and—in case the matrices are square—its eigenvalues. It turns out that the trace of the structure matrix has some interesting properties. The rank of the structure matrix has the values 1,2, or 3; this yields a classification of econometric models.     

MEASURING OPTIMAL CONNECTIONS IN LARGE NETWORKS: A NEW ALGORITHM AND ITS APPLICATIONS

Researchers have identified several problems in measuring the strongest path connecting pairs of actors in valued graphs. To address these problems, it has been proposed that average path value be used to indicate optimal connections between dyads. However, a lack of proper computer algorithm and its implementation has hindered a wide-range application of the proposed solution. In this paper we develop a computer algorithm and fully implement it with four JAVA programs, which are available on request. These programs produce an optimal connection matrix, which is subsequently inputted into UCINET for further multidimensional scaling and clustering analysis. We demonstrate this procedure with a data matrix containing 38 organizations in information technology. We discuss the methodological implications of the application of our algorithm to future social network studies.     

A traffic control algorithm for Clos network type ATM switches

This paper presents a new traffic control algorithm for asynchronous transfer mode (ATM) switches composed of Clos network type switch fabric. In most traffic control algorithms previously proposed, an ATM switch has been considered as a single node, although the switch fabric of an ATM switch is usually of a network type. In this paper, we suggest a new control algorithm that is designed not only for the ATM network but also for the switch fabric and that can maintain high speed even in cases where buffer capacity of the switch fabric is limited. Main modules of the suggested algorithm are a traffic status detection mechanism based on non-parametric statistical tests, a cell-loss detection mechanism, and a cluster-based fair share computation procedure. Results of simulation experiments show that the suggested algorithm satisfactorily adjusts traffic rate of available bit rate services according to changes in traffic rate used by quality of service (QoS) guaranteed services. The results also show that the algorithm prevents cell losses relatively well and keeps the delay time of QoS guaranteed services short enough.