Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis

In this paper we study aprobabilistic approach which is an alternative to the classical worst-case algorithms for robustness analysis and design of uncertain control systems. That is, we aim to estimate the probability that a control system with uncertain parametersq restricted to a boxQ attains a given level of performance γ. Since this probability depends on the underlying distribution, we address the following question: What is a “reasonable” distribution so that the estimated probability makes sense? To answer this question, we define two worstcase criteria and prove that the uniform distribution is optimal in both cases. In the second part of the paper we turn our attention to a subsequent problem. That is, we estimate the sizes of both the so-called “good” and “bad” sets via sampling. Roughly speaking, the good set contains the parametersq∈Q with a performance level better than or equal to γ while the bad set is the set of parametersq∈Q with a performance level worse than γ. We give bounds on the minimum sample size to attain a good estimate of these sets in a certain probabilistic sense.     

A robustness result for stochastic control

The solution of a stochastic control problem depends on the underlying model. The actual real world model may not be known precisely and so one solves the problem for a hypothetical model, that is in general different but close to the real one; the optimal (or nearly optimal) control of the hypothetical model is then used as solution for the real problem.In this paper, we assume that, what is not precisely known, is the underlying probability measure that determines the distribution of the random quantities driving the model. We investigate two ways to derive a bound on the suboptimality of the optimal control of the hypothetical problem when this control is used in the real problem. Both bounds are in terms of the Radon–Nikodym derivative of the underlying real world measure with respect to the hypothetical one. We finally investigate how the bounds compare to each other.     

Attraction, stability and robustness for stochastic functional differential equations with infinite delay

This paper establishes the stochastic LaSalle theorem to locate limit sets for stochastic functional differential equations with infinite delay, from which some criteria on attraction, boundedness, stability and robustness are obtained. To illustrate the applications of our results clearly, this paper considers a scalar stochastic integro-differential equation with infinite delay as an example.     

Probabilistic enhancement of classical robustness margins: The unirectangularity concept

The focal point of this paper is a control system subjected to parametric uncertainty. Motivated by the newly emerging theory of probabilistic robustness, the risk of performance violation is assessed with uncertainty bounds which exceed classical deterministic margins. For a wide class of problems, the Uniformity Principle (UP) developed by Barmish and Lagoa (Math. Control Signals Systems 10 (1997) 203–222), makes it possible to estimate the probability of performance satisfaction with almost no a priori statistical information about the uncertainty. The application of the UP is, however, limited to problems satisfying certain convexity and symmetricity conditions. Since such conditions are violated in many practical problems, the objective in this paper is to extend the application of the UP. To this end, by working with a so-called unirectangularity condition, a procedure is implemented for computing probabilities of performance and the associated improvements of deterministic robustness margins. That is, given any robustness radius r₀ which is computable via deterministic methods, a probabilistic enhancement of this margin R₀()r₀ with pre-specified level of risk >0 is provided. The radius R₀() is called a risk-adjusted robustness margin.     

A probabilistic framework for problems with real structured uncertainty in systems and control

The objective of this paper is twofold. First, the problem of generation of real random matrix samples with uniform distribution in structured (spectral) norm bounded sets is studied. This includes an analysis of the distribution of the singular values of uniformly distributed real matrices, and an efficient (i.e. polynomial-time) algorithm for their generation. Second, it is shown how the developed techniques may be used to solve in a probabilistic setting several hard problems involving systems subject to real structured uncertainty.     

Stochastic robustness metric and its use for static resource allocations

This research investigates the problem of robust static resource allocation for distributed computing systems operating under imposed Quality of Service (QoS) constraints. Often, such systems are expected to function in a physical environment replete with uncertainty, which causes the amount of processing required to fluctuate substantially over time. Determining a resource allocation that accounts for this uncertainty in a way that can provide a probabilistic guarantee that a given level of QoS is achieved is an important research problem. The stochastic robustness metric proposed in this research is based on a mathematical model where the relationship between uncertainty in system parameters and its impact on system performance are described stochastically.The utility of the established metric is then exploited in the design of optimization techniques based on greedy and iterative approaches that address the problem of resource allocation in a large class of distributed systems operating on periodically updated data sets. The performance results are presented for a simulated environment that replicates a heterogeneous cluster-based radar data processing center. A mathematical performance lower bound is presented for comparison analysis of the heuristic results. The lower bound is derived based on a relaxation of the Integer Linear Programming formulation for a given resource allocation problem.     

Probabilistic enhancement of classical robustness margins: The unirectangularity concept

The focal point of this paper is a control system subjected to parametric uncertainty. Motivated by the newly emerging theory of probabilistic robustness, the risk of performance violation is assessed with uncertainty bounds which exceed classical deterministic margins. For a wide class of problems, the Uniformity Principle (UP) developed by Barmish and Lagoa (Math. Control Signals Systems 10 (1997) 203–222), makes it possible to estimate the probability of performance satisfaction with almost no a priori statistical information about the uncertainty. The application of the UP is, however, limited to problems satisfying certain convexity and symmetricity conditions. Since such conditions are violated in many practical problems, the objective in this paper is to extend the application of the UP. To this end, by working with a so-called unirectangularity condition, a procedure is implemented for computing probabilities of performance and the associated improvements of deterministic robustness margins. That is, given any robustness radius r₀ which is computable via deterministic methods, a probabilistic enhancement of this margin R₀(ε)?r₀ with pre-specified level of risk ε>0 is provided. The radius R₀(ε) is called a risk-adjusted robustness margin.     

Stochastic ellipsoid methods for robust control: Multiple updates and multiple cuts

Efficient randomized algorithms are developed for solving robust feasibility problems with multiple parameter-dependent convex constraints. Two complementary strategies are presented, both of which exploit the multiplicity to achieve fast convergence. One is the stochastic ellipsoid method with multiple updates. In each iteration of this algorithm, an ellipsoid which describes a candidate of the solution set is updated many times via the multiple constraints with one random sample, while at most one update is allowed in the original method. The other is the stochastic ellipsoid method with multiple cuts. Here, a new update rule is presented to construct a smaller ellipsoid directly via multiple subgradients given by the constraints. A quantitative analysis of the volume of the ellipsoid is also provided, which guarantees the advantage of the proposed algorithm over the original one. The above features lead to a reduction of the total number of random samples necessary for convergence, which is extensively demonstrated through numerical examples.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

Randomized algorithms for the synthesis of cautious adaptive controllers

We introduce a new methodology for the design of cautious adaptive controllers based on the following two-step procedure: (i) a probability measure describing the likelihood of different models is updated on-line based on observations, and (ii) a controller with certain robust control specifications is tuned to the updated probability by means of randomized algorithms. The robust control specifications are assigned as average specifications with respect to the estimated probability measure, and randomized algorithms are used to make the controller tuning computationally tractable.This paper provides a general overview of the proposed new methodology. Still, many issues remain open and represent interesting topics for future research.     

Competitive randomized algorithms for nonuniform problems

Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approachinge/(e–1) 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approachinge/(e–1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approache/(e–1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.Supported in part by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), an NSF Science and Technology Center funded under NSF Contract STC-88-09648 and supported by the New Jersey Commission on Science and Technology.     

Stochastic model predictive control for constrained discrete-time Markovian switching systems

In this paper we study constrained stochastic optimal control problems for Markovian switching systems, an extension of Markovian jump linear systems (MJLS), where the subsystems are allowed to be nonlinear. We develop appropriate notions of invariance and stability for such systems and provide terminal conditions for stochastic model predictive control (SMPC) that guarantee mean-square stability and robust constraint fulfillment of the Markovian switching system in closed-loop with the SMPC law under very weak assumptions. In the special but important case of constrained MJLS we present an algorithm for computing explicitly the SMPC control law off-line, that combines dynamic programming with parametric piecewise quadratic optimization.     

Research on probabilistic methods for control system design

A novel approach based on probability and randomization has emerged to synergize with the standard deterministic methods for control of systems with uncertainty. The main objective of this paper is to provide a broad perspective on this area of research known as “probabilistic robust control”, and to address in a systematic manner recent advances. The focal point is on design methods, based on the interplay between uncertainty randomization and convex optimization, and on the illustration of specific control applications.     

随机线性系统模型的集结简化

讨论集结法在简化随机线性系统模型中的应用,它可将n维状态空间模型的主要特征集结简化到r维（r〈n）状态空间模型上,优化地再现原系统的基本性能和模裂数据。在简化模型中,动态系统集结矩阵选定为原系统矩阵特征值的子集。这种方法既适用于离散系统,也适用于连续系统。高阶系统动态模型的这种简化处理方法,不仅克服与避免了对这类系统进行仿真分析时,占用较大内存空间与耗费大量机时的缺陷,而且提高厂仿真与控制过程的稳定性和结果的准确性。     

Some applications of randomized algorithms for control system design

In this paper a few “difficult” problems related to simultaneous stabilization of three plants (equivalent to a certain problem related to unit interpolation in H_∞) have been addressed through the framework of randomized algorithms. These problems which were proposed by Blondel (Simultaneous Stabilization of Linear Systems, Springer, Berlin, 1994) and Blondel and Gevers (Math. Control Signals Systems 6 (1994) 135) concern the existence of a controller.     

Stochastic maximum principle for SPDEs with noise and control on the boundary

In this paper we prove necessary conditions for optimality of a stochastic control problem for a class of stochastic partial differential equations that is controlled through the boundary. This kind of problem can be interpreted as a stochastic control problem for an evolution system in a Hilbert space. The regularity of the solution of the adjoint equation, that is a backward stochastic equation in infinite dimension, plays a crucial role in the formulation of the maximum principle.     

On delay robustness analysis of a simple control algorithm in high-speed networks

This paper focuses on the robustness analysis of a simple (second-order) control algorithm for data transfer in high-speed networks. The model under consideration (derived using a fluid approximation technique) can be found in Izmailov (SIAM J. Contr. Optimiz. 34 (1996) 1767). The novelty of the approach lies in characterizing the stability of the scheme in the delay-parameter space (where the delays correspond to the control-time interval, and to the round-trip time, respectively). Thus, we shall compute some delay-insensitive measures for the algorithm which give upper and lower bounds for the uncertainty in the knowledge of the round-trip times.     

BubbleSearch: A simple heuristic for improving priority-based greedy algorithms

We introduce BubbleSearch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness.