A robust optimization approach to experimental design for model discrimination of dynamical systems

A high-ranking goal of interdisciplinary modeling approaches in science and engineering are quantitative prediction of system dynamics and model based optimization. Quantitative modeling has to be closely related to experimental investigations if the model is supposed to be used for mechanistic analysis and model predictions. Typically, before an appropriate model of an experimental system is found different hypothetical models might be reasonable and consistent with previous knowledge and available data. The parameters of the models up to an estimated confidence region are generally not known a priori. Therefore one has to incorporate possible parameter configurations of different models into a model discrimination algorithm which leads to the need for robustification. In this article we present a numerical algorithm which calculates a design of experiments allowing optimal discrimination of different hypothetic candidate models of a given dynamical system for the most inappropriate (worst case) parameter configurations within a parameter range. The design comprises initial values, system perturbations and the optimal placement of measurement time points, the number of measurements as well as the time points are subject to design. The statistical discrimination criterion is worked out rigorously for these settings, a derivation from the Kullback-Leibler divergence as optimization objective is presented for the case of discontinuous Heaviside-functions modeling the measurement decision which are replaced by continuous approximations during the optimization procedure. The resulting problem can be classified as a semi-infinite optimization problem which we solve in an outer approximations approach stabilized by a suggested homotopy strategy whose efficiency is demonstrated. We present the theoretical framework, algorithmic realization and numerical results.     

Application of the sequential parametric convex approximation method to the design of robust trusses

We study an algorithm recently proposed, which is called sequential parametric approximation method, that finds the solution of a differentiable nonconvex optimization problem by solving a sequence of differentiable convex approximations from the original one. We show as well the global convergence of this method under weaker assumptions than those made in the literature. The optimization method is applied to the design of robust truss structures. The optimal structure of the model considered minimizes the total amount of material under mechanical equilibrium, displacements and stress constraints. Finally, Robust designs are found by considering load perturbations.     

Homotopy Algorithm for Optimal Control Problems with a Second-order State Constraint

This paper deals with optimal control problems with a regular second-order state constraint and a scalar control, satisfying the strengthened Legendre-Clebsch condition. We study the stability of structure of stationary points. It is shown that under a uniform strict complementarity assumption, boundary arcs are stable under sufficiently smooth perturbations of the data. On the contrary, nonreducible touch points are not stable under perturbations. We show that under some reasonable conditions, either a boundary arc or a second touch point may appear. Those results allow us to design an homotopy algorithm which automatically detects the structure of the trajectory and initializes the shooting parameters associated with boundary arcs and touch points.     

Relative Convergence Estimates for the Spectral Asymptotic in the Large Coupling Limit

We prove optimal convergence estimates for eigenvalues and eigenvectors of a class of singular/stiff perturbed problems. Our profs are constructive in nature and use (elementary) techniques which are of current interest in computational Linear Algebra to obtain estimates even for eigenvalues which are in gaps of the essential spectrum. Further, we also identify a class of “regular” stiff perturbations with (provably) good asymptotic properties. The Arch Model from the theory of elasticity is presented as a prototype for this class of perturbations. We also show that we are able to study model problems which do not satisfy this regularity assumption by presenting a study of a Schroedinger operator with singular obstacle potential.     

Conditions for stability and stabilization of systems of neutral type with nonmonotone Lyapunov functionals

We suggest new tests for the stability and uniform asymptotic stability of an equilibrium in systems of neutral type. By using these tests, we prove conditions for optimal stabilization and derive new estimates for perturbations that can be countered by a system closed by an optimal control. We show that, by using nonmonotone sign-indefinite functionals as Lyapunov functionals, one can obtain conditions for uniform asymptotic stability that do not contain the a priori requirement of stability of the difference operator and do not imply the boundedness of the right-hand side of the system. When studying the action of perturbations on the stabilized systems, these conditions permit one to obtain new estimates of perturbations preserving the stabilizing properties of optimal controls. The obtained estimates do not imply any constraint on the value of perturbations in some domains of the phase space that are defined when constructing an optimal stabilizing control. Some examples are considered.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现:项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

基于灵敏性分析的Q-MSGSID的优化及应用

本文针对绝对关联度、综合关联度以及相对关联度的取值范围存在的不足,首先,设置了控制因子λ以及空间中的距离d,以此来调节关联度值的范围,建立了新模型。其次,研究了它的一些性质,并在理论上证明了新模型满足灰色关联公理。另外,提出了新模型的准优值所满足的几个原则,并结合灵敏性分析原理给出了准优值的算法步骤。最后,通过实例研究,验证了新模型所得结果不但能够使关联度的值扩充到(0,1]这一更大的范围,而且提高了区分度和分辨效果。     

Shape optimization of rigid inclusions for elastic plates with cracks

In the paper, we consider an optimal control problem of finding the most safe rigid inclusion shapes in elastic plates with cracks from the viewpoint of the Griffith rupture criterion. We make use of a general Kirchhoff–Love plate model with both vertical and horizontal displacements, and nonpenetration conditions are fulfilled on the crack faces. The dependence of the first derivative of the energy functional with respect to the crack length on regular shape perturbations of the rigid inclusion is analyzed. It is shown that there exists a solution of the optimal control problem.     

A combination selection algorithm on forecasting

It is widely accepted in forecasting that a combination model can improve forecasting accuracy. One important challenge is how to select the optimal subset of individual models from all available models without having to try all possible combinations of these models. This paper proposes an optimal subset selection algorithm from all individual models using information theory. The experimental results in tourism demand forecasting demonstrate that the combination of the individual models from the selected optimal subset significantly outperforms the combination of all available individual models. The proposed optimal subset selection algorithm provides a theoretical approach rather than experimental assessments which dominate literature.     

A nonisolated optimal solution for special reverse convex programming problems

In this paper, an efficient algorithm is proposed for globally solving special reverse convex programming problems with more than one reverse convex constraints. The proposed algorithm provides a nonisolated global optimal solution which is also stable under small perturbations of the constraints, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiment is given to illustrate the feasibility of the presented algorithm.     

Recent Progress in Applications of the Conditional Nonlinear Optimal Perturbation Approach to Atmosphere-Ocean Sciences

The conditional nonlinear optimal perturbation (CNOP for short) approach is a powerful tool for predictability and targeted observation studies in atmosphere-ocean sciences. By fully considering nonlinearity under appropriate physical constraints, the CNOP approach can reveal the optimal perturbations of initial conditions, boundary conditions, model parameters, and model tendencies that cause the largest simulation or prediction uncertainties. This paper reviews the progress of applying the CNOP approach to atmosphere-ocean sciences during the past five years. Following an introduction of the CNOP approach, the algorithm developments for solving the CNOP are discussed.Then, recent CNOP applications, including predictability studies of some high-impact ocean-atmospheric environmental events, ensemble forecast, parameter sensitivity analysis, uncertainty estimation caused by errors of model tendency or boundary condition, are reviewed. Finally, a summary and discussion on future applications and challenges of the CNOP approach are presented.     

A novel clustering approach and prediction of optimal number of clusters: global optimum search with enhanced positioning

Cluster analysis of genome-wide expression data from DNA microarray hybridization studies is a useful tool for identifying biologically relevant gene groupings (DeRisi et al. 1997; Weiler et al. 1997). It is hence important to apply a rigorous yet intuitive clustering algorithm to uncover these genomic relationships. In this study, we describe a novel clustering algorithm framework based on a variant of the Generalized Benders Decomposition, denoted as the Global Optimum Search (Floudas et al. 1989; Floudas 1995), which includes a procedure to determine the optimal number of clusters to be used. The approach involves a pre-clustering of data points to define an initial number of clusters and the iterative solution of a Linear Programming problem (the primal problem) and a Mixed-Integer Linear Programming problem (the master problem), that are derived from a Mixed Integer Nonlinear Programming problem formulation. Badly placed data points are removed to form new clusters, thus ensuring tight groupings amongst the data points and incrementing the number of clusters until the optimum number is reached. We apply the proposed clustering algorithm to experimental DNA microarray data centered on the Ras signaling pathway in the yeast Saccharomyces cerevisiae and compare the results to that obtained with some commonly used clustering algorithms. Our algorithm compares favorably against these algorithms in the aspects of intra-cluster similarity and inter-cluster dissimilarity, often considered two key tenets of clustering. Furthermore, our algorithm can predict the optimal number of clusters, and the biological coherence of the predicted clusters is analyzed through gene ontology.     

Adjoint-free calculation method for conditional nonlinear optimal perturbations

Adjoint-free calculation method is proposed to compute conditional nonlinear optimal perturbations(CNOP) combined with initial perturbations and model parameter perturbations. The new approach avoids the use of adjoint technique in the optimization process. CNOPs respectively generated by ensemble-based and adjoint-based methods are compared based on a simple theoretical model.     

A robust algorithm for generalized geometric programming

Most existing methods of global optimization for generalized geometric programming (GGP) actually compute an approximate optimal solution of a linear or convex relaxation of the original problem. However, these approaches may sometimes provide an infeasible solution, or far from the true optimum. To overcome these limitations, a robust solution algorithm is proposed for global optimization of (GGP) problem. This algorithm guarantees adequately to obtain a robust optimal solution, which is feasible and close to the actual optimal solution, and is also stable under small perturbations of the constraints.     

A stability concept for matrix game optimal strategies and its application to linear programming sensitivity analysis

This paper studies a class of perturbations of a game matrix that alters each row by a different amount. We find that completely mixed optimal strategies are stable under these perturbations provided the norm of the vector of additive amounts is sufficiently small. Using this concept we give a new characterization of completely mixed grames. We also obtain a sensitivity result for a class of perturbations of the technological coefficient matrix of positive linear programs. The stability of an optimal strategy holds throughout at least a spherical neighborhood of the zero perturbation. We give a computational formula and equivalent programming formulations for the radius of this neighborhood.     

Application research on FSDM-based GA in optimizing curriculum schedule model in universities

In this paper, we first analyze the relationship between curricula, teachers, classes, time slices and classrooms in a graph. Then on the basis of constraint conditions in curriculum schedule practically in universities, we presents its optimization model, in which the fuzzy synthetic decision-making (FSDM) is used to optimize genetic algorithm (GA), and a new GA encoding scheme is employed to design fitness and punishment functions for the curriculum schedule problem. This model effectively improved a running performance, which provides a better implementation approach to improvements of the existing curriculum schedule systems. The experimental results show that fitness values of the FSDM-based GA are of obvious evolutional tendency, the chromosome encoding scheme and the fitness function can meet its requirements preferably, and the more adequate computation resources, the greater possibilities of no restoration for the obtained optimal individual.     

Singular spectrum analysis based on the perturbation theory

Singular Spectrum Analysis (SSA) has been exploited in different applications. It is well known that perturbations from various sources can seriously degrade the performance of the methods and techniques. In this paper, we consider the SSA technique based on the perturbation theory and examine its performance in both reconstructing and forecasting noisy series. We also consider the sensitivity of the technique to different window lengths, noise levels and series lengths. To cover a broad application range, various simulated series, from dynamic to chaotic, are used to verify the proposed algorithm. We then evaluate the performance of the technique using two real well-known series, namely, monthly accidental deaths in the USA, and the daily closing prices of several stock market indices. The results are compared with several classical methods namely, Box–Jenkins SARIMA models, the ARAR algorithm, GARCH model and the Holt–Winter algorithm.     

Engineering graph-based models for dynamic timetable information systems

In the last years we have witnessed remarkable progress in providing efficient algorithmic solutions to the problem of computing best journeys (or routes) in schedule-based public transportation systems. We have now models to represent timetables that allow us to answer queries for optimal journeys in a few milliseconds, also at a very large scale. Such models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. Array-based models have been shown to be very effective in terms of query time, while graph-based ones usually answer queries by computing shortest paths, and hence they are suitable to be combined with the speed-up techniques developed for road networks.In this paper, we study the behavior of graph-based models in the prominent case of dynamic scenarios, i.e., when delays might occur to the original timetable. In particular, we make the following contributions. First, we consider the graph-based reduced time-expanded model and give a simplified and optimized routine for handling delays, and a re-engineered and fine-tuned query algorithm. Second, we propose a new graph-based model, namely the dynamic timetable model, natively tailored to efficiently incorporate dynamic updates, along with a query algorithm and a routine for handling delays. Third, we show how to adapt the ALT algorithm to such graph-based models. We have chosen this speed-up technique since it supports dynamic changes, and a careful implementation of it can significantly boost its performance. Finally, we provide an experimental study to assess the effectiveness of all proposed models and algorithms, and to compare them with the array-based state of the art solution for the dynamic case. We evaluate both new and existing approaches by implementing and testing them on real-world timetables subject to synthetic delays.Our experimental results show that: (i) the dynamic timetable model is the best model for handling delays; (ii) graph-based models are competitive to array-based models with respect to query time in the dynamic case; (iii) the dynamic timetable model compares favorably with both the original and the reduced time-expanded model regarding space; (iv) combining the graph-based models with speed-up techniques designed for road networks, such as ALT, is a very promising approach.