Decentralised sampled-data control for large-scale systems with nonlinear interconnections

This paper presents a decentralised sampled-data control technique for a class of large-scale systems, which are considered to consist of linear subsystems and nonlinear interconnections. The decentralised sampled-data controller design problem is established using a closed-loop subsystem. Based on the controller design problem, the stability condition is derived for a closed-loop large-scale system, and the maximum interconnection bound is guaranteed to satisfy the stability condition. Also, its sufficient condition is formulated in terms of linear matrix inequalities. Finally, the effectiveness of the proposed technique is verified by using an example of the multi-machine power system.     

On Convergence of Volterra Series Expansion of a Class of Nonlinear Systems

A fundamental issue in conducting the analysis and design of a nonlinear system via Volterra series theory is how to ensure the excitation magnitude and/or model parameters will be in the appropriate range such that the nonlinear system has a convergent Volterra series expansion. To this aim, parametric convergence bounds of Volterra series expansion of nonlinear systems described by a NARX model, which can reveal under what excitation magnitude or within what parameter range a given NARX system is able to have a convergent Volterra series expansion subject to any given input signal, are investigated systematically in this paper. The existing bound results often are given as a function of the maximum input magnitude, which could be suitable for single‐tone harmonic inputs but very conservative for complicated inputs (e.g. multi‐tone or arbitrary inputs). In this study, the output response of nonlinear systems is expressed in a closed form, which is not only determined by the input magnitude but also related to the input energy or waveform. These new techniques result in more accurate bound criteria, which are not only functions of model parameters and the maximum input magnitude but also consider a factor reflecting the overall input energy or wave form. This is significant to practical applications, since the same nonlinear system could exhibit chaotic behavior subject to a simple single‐tone input but might not with respect to other different input signals (e.g. multi‐tone inputs) of the same input magnitude. The results provide useful guidance for the application of Volterra series‐based theory and methods from an engineering point of view. The Duffing equation is used as a benchmark example to show the effectiveness of the results.     

The ski-rental problem with multiple discount options

We propose the ski-rental problem with multiple discount options in which there are n options to rent an equipment. Every option has a rental duration; the longer the duration, the more the discount. This generalizes the standard ski-rental problem where one can only rent or buy. We present a 4-competitive on-line algorithm for our problem and show that no deterministic algorithm can have a smaller competitive ratio when n is large enough. Comparing with the original ski-rental problem, the competitive ratio becomes larger when there are more options.     

Dynamic normal forms and dynamic characteristic polynomial

We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n²logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n²klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2^−b in additional O(nlog²nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n²) lower bound for rank-one updates and an Ω(n) lower bound for element updates.     

一种O(2.983n)时间复杂度的最优联盟结构生成算法

首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS(effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS算法时间复杂度的下界是O(2.818n),用时间序列分析方法求出了EOCS算法的上界是O(2.983n).最后,将EOCS算法与其他算法作了对比,指出无论联盟值满足何种概率分布,EOCS算法都能在O(2.983n)时间内找出最优联盟结构.Rothkopf提出的DP(dynamic programming)算法和Rahwan提出的IDP(improved dynamic programming)算法能够在O(3n)时间内求出最优联盟结构.所作的EOCS算法设计、正确性证明、时间复杂度的上下界分析都是对Rothkopf及Rahwan等人相关工作的改进和提高.     

考虑切换时间的多品种印刷电路板表面贴装生产线调度优化

考虑了多品种小批量生产环境下的印刷电路板生产调度优化问题,建立了以包括切换时间在内的多品种平均流程时间最小化为目标的调度优化模型.针对电了产品组装独特的切换后效性,开发了主动禁忌搜索算法,分组间搜索和组内搜索2个层次对印刷电路板的排序问题进行优化.通过与理论下界值比较的仿真实验显示了模型与算法的有效性及现实应用的可行性...     

Point Light Source Estimation from Two Images and Its Limits

In this paper, the performance of parameter estimation of a single static distant point light source from two video images is analyzed in terms of estimation theory. The illumination parameters are the intensity and direction of the light source.In the first part of this paper, estimators from the literature are reviewed. Most recent estimators evaluate as input data two video images as well as the 3D shape and the 3D motion of the visible moving objects.In the second part of the paper, the performance of these recent methods is analyzed. The input data to estimation as well as the inherent input data errors are described by a stochastic observation model. Based on this model, the performance is analyzed regarding the Cramér-Rao theoretical lower bound of estimation error variances. The bound is derived for a variety of cases of scene illumination, object motion and errors in input data. For simplification purpose, the bound is valid only for object motions with the rotation axis lying in the image plane. The analysis shows in which cases which estimation accuracy can be expected with current methods.Finally, a comparison of the bound with one of the recent estimators shows that recent estimators are suboptimal in case of errors in the 3D shape of the objects. In future work, the stochastic observation model presented in this paper can be used to improve illumination estimation.     

Entanglement of formation and concurrence for mixed states

We review some results on analytical computations of the measures for quantum entanglement: entanglement of formation and concurrence. We introduce some estimations of the lower bounds for the entanglement of formation in bipartite mixed states, and of lower bounds for the concurrence in bipartite and tripartite systems. The results on lower bounds for the concurrence are also generalized to arbitrary multipartite systems.     

收缩背包问题的并行分枝界限算法

收缩背包问题（collapsing knapsack problem,CKP)是0－1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需求,在对CKP问题分解的基础上,给出了求解每个子问题的权分枝界限算法,提出了基于MIMD－DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。     

一类不确定非线性系统的鲁棒自适应控制

针对一类具有一般不确定性和未知参数的非线性系统,设计出一种适用于输出跟踪 的鲁棒自适应控制器.该控制器对系统的参数和状态的不确定性具有鲁棒性,能保证闭环系 统的全局稳定性,并解决了ε-跟踪问题.仿真实例表明,所设计的鲁棒自适应控制器具有良好 的跟踪性能.