Resource-saving tracking problem with infinite time horizon

We consider the problem on the infinite-duration tracking of a prescribed trajectory of an inaccurately observed control system subjected to an unobservable dynamic disturbance. We construct a solution algorithm that is resource-saving in the sense that the control resources used for solving the problem for small noise values in the state observation channel are little different from the corresponding resources in the “ideal case” where the current values of the dynamic disturbance are available to direct observation.     

On dynamical regularization under random noise

We consider the problem of constructing a robust dynamic approximation of a timevarying input to a control system from the results of inaccurate observation of the states of the system. In contrast to the earlier studied cases in which the observation errors are assumed to be small in the metric sense, the errors in the present case are allowed to take, generally, large values and are subject to a certain probability distribution. The observation errors occurring at different instants are supposed to be statistically independent. Under the assumption that the expected values of the observation errors are small, we construct a dynamical algorithm for approximating the normal (minimal in the sense of the mean-square norm) input; the algorithm ensures an arbitrarily high level of the mean-square approximation accuracy with an arbitrarily high probability.     

Exploiting correlation effects within multiple-hypothesis tracking

The need to track closely spaced targets in clutter is essential in support of military operations. This paper presents a Multiple-Hypothesis Tracking (MHT) algorithm which uses an efficient structure to represent the dependency which naturally arises between targets due to the joint observation process, and an Integral Square Error (ISE) mixture reduction algorithm for hypothesis control. The resulting algorithm, denoted as MHT with ISE Reduction (MISER), is tested against performance metrics including track life, coalescence and track swap. The results demonstrate track life performance similar to that of ISE-based methods in the single-target case, and a significant improvement in track swap metric due to the preservation of correlation between targets. The result that correlation reduces the track life performance for formation targets requires further investigation, although it appears to demonstrate that the inherent coupling of dynamics noises for such problems eliminates much of the benefit of representing correlation only due to the joint observation process.     

Postponing the choice of the barrier parameter in Mehrotra-type predictor–corrector algorithms

Recently Salahi et al. have considered a variant of Mehrotra’s celebrated predictor–corrector algorithm. By a numerical example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of the algorithm. This observation motivated them to incorporate a safeguard in their algorithmic scheme that gives a lower bound for the step size at each iteration and thus imply polynomial iteration complexity. In this paper we propose a different approach that enables us to have control on the iterates.     

带损伤弹性反问题的数值分析

考虑一类由椭圆性方程和热传导方程共同来刻画的准静态弹性模型,通过给定观测值来反演边界的牵引力.首先构造一个凸目标泛函,并引入Tikhonov正则化方法,使之极小化得到一个稳定的近似解.再用有限元离散求解,导出误差估计.最后,用数值例子说明算法的可行性和有效性.     

Nonlinear estimation applying an unscented transformation in systems with correlated uncertain observations

An approximation to the least squares filter is proposed for discrete signals whose evolution is governed by nonlinear functions, when the estimation is based on nonlinear observations with additive noise which can consist only of random noise; this uncertainty in the observation process is modelled by Bernoulli random variables which are correlated at consecutive time instants and are otherwise independent. The proposed recursive approximation is based on the unscented principle; successive applications of the unscented transformation to a suitable augmented state vector enable us to approximate the one-stage state and observation predictors from the state filter at the previous time instant. The performance of the proposed algorithm is compared with that of an extended algorithm in a numerical simulation example.     

A real time algorithm for the location search of discontinuous conductivities with one measurement

We consider an inverse problem for finding the anomaly of discontinuous electrical conductivity by one current‐voltage observation. We develop a real time algorithm for determining the location of the anomaly. This new idea is based on the observation of the pattern of a simple weighted combination of the input current and the output voltage. Combined with the size estimation result, this algorithm gives a good initial guess for Newton‐type schemes. We give the rigorous proof for the location search algorithm. Both the mathematical analysis and its numerical implementation indicate our location search algorithm is very fast, stable and efficient. © 2001 John Wiley & Sons, Inc.     

输电系统的部分可观Petri网故障诊断器设计

采用部分可观Petri网的故障诊断方法来解决变电站输电系统中不可观事件和不可观运行状态的故障诊断问题.首先,将系统可观测序列分解为长度为1的基础观测序列,应用线性不等式矩阵计算与基础观测序列相符的点火序列集;然后,基于整数线性规划问题,利用向前向后函数拓宽诊断区间,同时应用参数K限定故障诊断序列长度,通过分析系统可观事件和系统部分可观状态,给出故障诊断结果.最后,构造变电站输电系统的部分可观Petri网模型,应用提出的故障诊断算法对输电系统进行诊断,诊断结果准确给出了故障发生与否及故障发生位置.算法适用于在线故障诊断,计算复杂性线性相关于观序列长度.     

An inverse problem of identifying the coefficient of parabolic equation

This paper studies an inverse problem of identifying the coefficient of parabolic equation when the final observation is given, which has important application in a large fields of applied science. Based on the optimal control framework, the existence and necessary condition of the minimum for the control functional are established. Since the optimal control problem is nonconvex, one may not expect a unique solution. However, in this paper the solution is proved to be locally unique. After the necessary condition is transformed into an elliptic bilateral variational inequality, an algorithm and some numerical experiments are proposed in the paper. The numerical results show that the algorithm designed in this paper is stable and that the coefficient is recovered very well.     

Dynamical reconstruction of unknown inputs in nonlinear differential equations

We present an algorithm for the identification of an unknown but bounded input to a nonlinear finite-dimensional system, based on observations taken at discrete time instants and corrupted by observation errors. This algorithm is stable with respect to observation and computational errors.If we have the further information that the unknown input is a signal of bounded variation, then we can give explicit convergence estimates of the algorithm.     

Unscented filtering algorithm using two-step randomly delayed observations in nonlinear systems

An unscented filtering algorithm is derived for a class of nonlinear discrete-time stochastic systems using noisy observations which can be randomly delayed by one or two sample times. The update and the possible delays (of one and two sampling times) of any observation are modelled by using three Bernoulli random variables such that only one of them takes the value one. The algorithm performs in two-steps, prediction and update, and it uses a scaled unscented transformation to approximate the conditional mean and covariance of the state and observation at each time. The performance of the proposed filter is shown in a simulation example which uses a growth model with randomly delayed observations; in this example, the proposed filter is compared with the extended one obtained by linearizing the state and the observation equations and, also, with the unscented Kalman filter. A clear superiority of the proposed filter over the others is inferred.     

处理噪声问题的泰勒展开交替最小化算法

为了处理图像、计算机视觉和生物信息等领域中广泛存在的稀疏大噪声和高斯噪声问题,提出了一种利用交替方向最小化思想求解主成分追求松弛模型的泰勒展开交替最小化算法(TEAM).采用推广泰勒展开和收缩算子等技术推导出低秩矩阵和稀疏大噪声矩阵的迭代方向矩阵,加入连续技术提高算法的收敛速率,设计出TEAM算法的求解步骤.实验中,将TEAM算法与该领域的顶级算法作分析对比.结果表明,TEAM算法时间优势明显,误差优势略好.     

A note on scheduling flowshops with flexible stage ordering

We develop an asymptotically optimal heuristic for the m-stage flowshop problem with flexible stage ordering. Our algorithm supplies a job permutation which has the same worst case absolute bound for all possible m! orderings of the m stages. The development of our algorithm is motivated by the observation that it is sometimes beneficial to reverse the processing order in multi-stage manufacturing processes. Our algorithm facilitates the development of a job sequence a priori before the processing order is determined.     

Fast algorithms for robust classification with Bayesian nets

We focus on a well-known classification task with expert systems based on Bayesian networks: predicting the state of a target variable given an incomplete observation of the other variables in the network, i.e., an observation of a subset of all the possible variables. To provide conclusions robust to near-ignorance about the process that prevents some of the variables from being observed, it has recently been derived a new rule, called conservative updating. With this paper we address the problem to efficiently compute the conservative updating rule for robust classification with Bayesian networks. We show first that the general problem is NP-hard, thus establishing a fundamental limit to the possibility to do robust classification efficiently. Then we define a wide subclass of Bayesian networks that does admit efficient computation. We show this by developing a new classification algorithm for such a class, which extends substantially the limits of efficient computation with respect to the previously existing algorithm. The algorithm is formulated as a variable elimination procedure, whose computation time is linear in the input size.     

A simulation approach to optimal stopping under partial information

We study the numerical solution of nonlinear partially observed optimal stopping problems. The system state is taken to be a multi-dimensional diffusion and drives the drift of the observation process, which is another multi-dimensional diffusion with correlated noise. Such models where the controller is not fully aware of her environment are of interest in applied probability and financial mathematics. We propose a new approximate numerical algorithm based on the particle filtering and regression Monte Carlo methods. The algorithm maintains a continuous state space and yields an integrated approach to the filtering and control sub-problems. Our approach is entirely simulation-based and therefore allows for a robust implementation with respect to model specification. We carry out the error analysis of our scheme and illustrate with several computational examples. An extension to discretely observed stochastic volatility models is also considered.     

LLL & ABC

This note is an observation that the LLL algorithm applied to prime powers can be used to find “good” examples for the ABC and Szpiro conjectures.     

卫星数传接收规划模型与算法研究

作为对地观测卫星任务执行的两个重要阶段之一,数传接收的规划任务是一个具有多时间窗口、多优化目标和多资源约束的NP-Hard优化问题。中继星的引入为数据全天候近实时传输提供可能,同时也为数传规划提出新的问题。本文主要完成两项工作:第一,建立风险控制的卫星数传接收规划模型;第二,阐述基于遗传禁忌的模型求解方法,进一步采用分布式并行求解策略,改善了求解算法的收敛速度和鲁棒性。最后,通过STK提供基础仿真数据,验证了本文规划模型和求解算法的有效性。     

Simultaneous identification of diffusion coefficient,spacewise dependent source and initial value for one‐dimensional heat equation

This paper deals with an inverse problem of determining the diffusion coefficient, spacewise dependent source term, and the initial value simultaneously for a one‐dimensional heat equation based on the boundary control, boundary measurement, and temperature distribution at a given single instant in time. By a Dirichlet series representation for the boundary observation, the identification of the diffusion coefficient and initial value can be transformed into a spectral estimation problem of an exponential series with measurement error, which is solved by the matrix pencil method. For the identification of the source term, a finite difference approximation method in conjunction with the truncated singular value decomposition is adopted, where the regularization parameter is determined by the generalized cross‐validation criterion. Numerical simulations are performed to verify the result of the proposed algorithm. Copyright © 2016 John Wiley & Sons, Ltd.     

Efficient Constraint Propagation for Graph Coloring

In this paper, we investigate constraint propagation, a mechanism that is run at each basic step of a backtrack search algorithm such as the popular MAC. From a statistical analysis of some relevant features concerning propagation on a large set of graph coloring instances, we show that it is possible to make reasonable predictions about the capability of constraint propagation to detect inconsistency. Using this observation in order to control propagation effort, we show its practical effectiveness.     

Adaptive filter for systems with unknown noise covariances using an instrumental performance functional

An original approach is proposed to constructing algorithms that estimate the unknown model parameters and the state vector of a linear dynamic system using an instrumental performance functional that leads to algorithms with a built-in start/stop rule. The particular case of a nonsingular observation matrix is considered in detail, as it is often observed in applied problems. The theoretical algorithm is presented in two versions that can be used in practice. Some practical recommendations concerning the implementation and application of the algorithm are offered. Translated from Algoritmy Upravleniya i Identifikatsii, pp. 26–39, 1997.