Biased Online Parameter Inference for State-Space Models

We consider Bayesian online static parameter estimation for state-space models. This is a very important problem, but is very computationally challenging as the state-of-the art methods that are exact, often have a computational cost that grows with the time parameter; perhaps the most successful algorithm is that of SM C² (Chopin et al., J R Stat Soc B 75: 397–426 2013). We present a version of the SM C² algorithm which has computational cost that does not grow with the time parameter. In addition, under assumptions, the algorithm is shown to provide consistent estimates of expectations w.r.t. the posterior. However, the cost to achieve this consistency can be exponential in the dimension of the parameter space; if this exponential cost is avoided, typically the algorithm is biased. The bias is investigated from a theoretical perspective and, under assumptions, we find that the bias does not accumulate as the time parameter grows. The algorithm is implemented on several Bayesian statistical models.     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

On Molecular Statics Simulation of Ferroelectric Barium Titanate

The present contribution deals with the atomistic modelling of ferroelectric barium titanate. In this context a core-shell model is implemented in a Molecular Static algorithm. Furthermore, Coulomb forces are simulated by the Wolf summation method in order to allow for a small cut off radius. We discuss the core-shell model, molecular statics as a finite elements approach and present some numerical results. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Reverse-engineering of polynomial dynamical systems

Multivariate polynomial dynamical systems over finite fields have been studied in several contexts, including engineering and mathematical biology. An important problem is to construct models of such systems from a partial specification of dynamic properties, e.g., from a collection of state transition measurements. Here, we consider static models, which are directed graphs that represent the causal relationships between system variables, so-called wiring diagrams. This paper contains an algorithm which computes all possible minimal wiring diagrams for a given set of state transition measurements. The paper also contains several statistical measures for model selection. The algorithm uses primary decomposition of monomial ideals as the principal tool. An application to the reverse-engineering of a gene regulatory network is included. The algorithm and the statistical measures are implemented in Macaulay 2, and are available from the authors.     

A hierarchical multiple kernel support vector machine for customer churn prediction using longitudinal behavioral data

The availability of abundant data posts a challenge to integrate static customer data and longitudinal behavioral data to improve performance in customer churn prediction. Usually, longitudinal behavioral data are transformed into static data before being included in a prediction model. In this study, a framework with ensemble techniques is presented for customer churn prediction directly using longitudinal behavioral data. A novel approach called the hierarchical multiple kernel support vector machine (H-MK-SVM) is formulated. A three phase training algorithm for the H-MK-SVM is developed, implemented and tested. The H-MK-SVM constructs a classification function by estimating the coefficients of both static and longitudinal behavioral variables in the training process without transformation of the longitudinal behavioral data. The training process of the H-MK-SVM is also a feature selection and time subsequence selection process because the sparse non-zero coefficients correspond to the variables selected. Computational experiments using three real-world databases were conducted. Computational results using multiple criteria measuring performance show that the H-MK-SVM directly using longitudinal behavioral data performs better than currently available classifiers.     

An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization

Powerful response surface methods based on kriging and radial basis function (RBF) interpolation have been developed for expensive, i.e. computationally costly, global nonconvex optimization. We have implemented some of these methods in the solvers rbfSolve and EGO in the TOMLAB Optimization Environment (http://www.tomopt.com/tomlab/). In this paper we study algorithms based on RBF interpolation. The practical performance of the RBF algorithm is sensitive to the initial experimental design, and to the static choice of target values. A new adaptive radial basis interpolation (ARBF) algorithm, suitable for parallel implementation, is presented. The algorithm is described in detail and its efficiency is analyzed on the standard test problem set of Dixon–Szegö. Results show that it outperforms the published results of rbfSolve and several other solvers.     

Validation of a Structural Optimization Algorithm Transforming Dynamic Loads into Equivalent Static Loads

Generally, structural optimization is carried out based on external static loads. However, all forces have dynamic characteristics in the real world. Mathematical optimization with dynamic loads is almost impossible in a large-scale problem. Therefore, in engineering practice, dynamic loads are often transformed into static loads via dynamic factors, design codes, and so on. Recently, a systematic transformation of dynamic loads into equivalent static loads has been proposed in Refs. 1–3. Equivalent static loads are made to generate at each time step the same displacement field as the one generated by the dynamic loads. In this research, it is verified that the solution obtained via the algorithm of Refs. 1–3 satisfies the Karush–Kuhn–Tucker necessary conditions. Application of the algorithm is discussed.     

A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.     

Identification of multiple-input single-output Hammerstein models using Bezier curves and Bernstein polynomials

This paper considers the implementation of Bezier–Bernstein polynomials and the Levenberg–Marquart algorithm for identifying multiple-input single-output (MISO) Hammerstein models consisting of nonlinear static functions followed by a linear dynamical subsystem. The nonlinear static functions are approximated by the means of Bezier curves and Bernstein basis functions. The identification method is based on a hybrid scheme including the inverse de Casteljau algorithm, the least squares method, and the Levenberg–Marquart (LM) algorithm. Furthermore, results based on the proposed scheme are given which demonstrate substantial identification performance.     

Adaptive accuracy control for Car-Parrinello simulations

Summary. The Car-Parrinello (CP) approach to ab initio molecular dynamics serves as an approximation to time-dependent Born-Oppenheimer (BO) calculations. It replaces the explicit minimization of the energy functional by a fictitious Newtonian dynamics and therefore introduces an artificial mass parameter which controls the electronic motion. A recent theoretical investigation shows that the CP-error, i.e., the deviation of the CP–solution from the BO-solution decreases like asymptotically. Since the computational effort increases like , the choice of has to find a compromise between efficiency and accuracy. The asymptotical result is used in this paper to construct an easily implemented algorithm which automatically controls : the parameter is repeatedly adapted during the simulation by choosing as large as possible while pushing an error measure below a user-given tolerance. The performance and reliability of the algorithm is illustrated by a typical example. Received March 10, 1998     

A power sparse approximate inverse preconditioning procedure for large sparse linear systems

Motivated by the Cayley–Hamilton theorem, a novel adaptive procedure, called a Power Sparse Approximate Inverse (PSAI) procedure, is proposed that uses a different adaptive sparsity pattern selection approach to constructing a right preconditioner M for the large sparse linear system Ax=b. It determines the sparsity pattern of M dynamically and computes the n independent columns of M that is optimal in the Frobenius norm minimization, subject to the sparsity pattern of M. The PSAI procedure needs a matrix–vector product at each step and updates the solution of a small least squares problem cheaply. To control the sparsity of M and develop a practical PSAI algorithm, two dropping strategies are proposed. The PSAI algorithm can capture an effective approximate sparsity pattern of A^?1 and compute a good sparse approximate inverse M efficiently. Numerical experiments are reported to verify the effectiveness of the PSAI algorithm. Numerical comparisons are made for the PSAI algorithm and the adaptive SPAI algorithm proposed by Grote and Huckle as well as for the PSAI algorithm and three static Sparse Approximate Inverse (SAI) algorithms. The results indicate that the PSAI algorithm is at least comparable to and can be much more effective than the adaptive SPAI algorithm and it often outperforms the static SAI algorithms very considerably and is more robust and practical than the static ones for general problems. Copyright © 2008 John Wiley & Sons, Ltd.     

Parallel constrained molecular dynamics

A block version of the Shake method for heavy atom simulation in biological systems is presented in this paper. The method solves successively, independent blocks of constraints of small size by a Newton method. This algorithm is implemented in TAKAKAW, an efficient parallel molecular dynamics code. This method has been tested on a small system and on an ionic canal of 67671 atoms. This revised version was published online in June 2006 with corrections to the Cover Date.     

A parametric approach for solving a class of generalized quadratic-transformable rank-two nonconvex programs

The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm is based on the so-called “optimal level solutions” method. Various global optimality conditions are discussed and implemented in order to improve the efficiency of the 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.     

Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much simpler than a previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star discrepancy via δ$\delta$-covers, J. Complexity, 21 (2005) 691–709]. Besides leading to better theoretical running time bounds, our approach also can be implemented with reasonable effort. We implemented this algorithm and performed numerical comparisons with other known low-discrepancy constructions. The experiments take place in dimensions ranging from 5 to 21 and indicate that our algorithm leads to superior results if the dimension is relatively high and the number of points that have to be constructed is rather small.     

Adaptive pseudospectral solution of a diffuse interface model

A diffuse interface type model, using an energy-based variational formulation with a free energy that is a function of the density and its gradients is presented. All of the boundary terms are retained and related to external surface forces, which can be of particular interest when considering the fluid–fluid–solid region. The numerical solution of these types of problems can be troublesome if a thin transition layer is desired. Here, Chebyshev pseudospectral methods with mesh adaptation for the solution of diffuse interface type problems are studied. A mesh adaptation algorithm based in the equidistribution principle following a continuation process is derived. In order to achieve high precision for problems exhibiting thin transition layers, a modified version of the arc-length monitor function is proposed which yields a sufficiently smooth coordinate transformation. At every step of the continuation process, a fixed number of iterations is implemented, so that the equidistribution equations are not solved completely at each step, which saves a considerable amount of computational effort. Numerical results for the static phase field model exhibiting thin transition layers are presented.     

Fast paths in large-scale dynamic road networks

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.     

A parallel interior point algorithm for linear programming on a network of transputers

Interior Point algorithms have become a very successful tool for solving large-scale linear programming problems. The Dual Affine algorithm is one of the Interior Point algorithms implemented in the computer program OB1. It is a good candidate for implementation on a parallel computer because it is very computing-intensive. A parallel Dual Affine algorithm is presented which is suitable for a parallel computer with a distributed memory. The algorithm obtains its speedup from parallel sparse linear algebra computations such as Cholesky factorisation, matrix multiplication, and triangular system solving, which form the bulk of the computing work. Efficient algorithms based on the grid distribution of matrices are presented for each of these computations. The algorithm is implemented in occam 2 on a square mesh of transputers. The resulting parallel program is connected to the sequentialFortran 77 program OB1, which performs the preprocessing and the postprocessing. Experimental results on a mesh of 400 transputers are given for a test set of seven realistic planning and scheduling problems from Shell and seven problems from the NETLIB LP collection; the results show a speedup of 88 for the largest problem.     

Static analysis of functionally graded beams using higher order shear deformation theory

Displacement field based on higher order shear deformation theory is implemented to study the static behavior of functionally graded metal–ceramic (FGM) beams under ambient temperature. FGM beams with variation of volume fraction of metal or ceramic based on power law exponent are considered. Using the principle of stationary potential energy, the finite element form of static equilibrium equation for FGM beam is presented. Two stiffness matrices are thus derived so that one among them will reflect the influence of rotation of the normal and the other shear rotation. Numerical results on the transverse deflection, axial and shear stresses in a moderately thick FGM beam under uniform distributed load for clamped–clamped and simply supported boundary conditions are discussed in depth. The effect of power law exponent for various combination of metal–ceramic FGM beam on the deflection and stresses are also commented. The studies reveal that, depending on whether the loading is on the ceramic rich face or metal rich face of the beam, the static deflection and the static stresses in the beam do not remain the same.     

Stability analysis for Lotka–Volterra systems based on an algorithm of real root isolation

Based on the theory of monotone flows of solutions of systems of differential equations, the Routh–Hurwitz theorem and a real root isolation algorithm of multivariate polynomials are applied to a class of Lotka–Volterra diffusion systems. An algorithm to determine the location of equilibria and the stability of the nonlinear dynamics systems is implemented in Maple.