Stochastic algorithms for robustness of control performances

In recent years, there has been a growing interest in developing statistical learning methods to provide approximate solutions to “difficult” control problems. In particular, randomized algorithms have become a very popular tool used for stability and performance analysis as well as for design of control systems. However, as randomized algorithms provide an efficient solution procedure to the “intractable” problems, stochastic methods bring closer to understanding the properties of the real systems. The topic of this paper is the use of stochastic methods in order to solve the problem of control robustness: the case of parametric stochastic uncertainty is considered. Necessary concepts regarding stochastic control theory and stochastic differential equations are introduced. Then a convergence analysis is provided by means of the Chernoff bounds, which guarantees robustness in mean and in probability. As an illustration, the robustness of control performances of example control systems is computed.     

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.     

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.     

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 method for obtaining randomized algorithms with small tail probabilities

We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.Supported by ESPRIT U Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).Supported by ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (Project ALCOM).Research supported by NSF Grant No. CCR-9005448.Partially supported by a Wolfson Research Award administered by the Israel Academy of Sciences and Humanities.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

On the power of randomization in on-line algorithms

Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient simulation of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.A previous version of this paper appeared in the22nd ACM STOC Conference Proceedings. Part of this research was performed while A. Borodin and A. Wigderson were visitors at the International Computer Science Institute, and while G. Tardos was a visitor at the Hebrew University.     

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.     

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.     

遗传算法中自适应方法的比较和分析

分析了前人提出的具有代表性的自适应遗传算法,使用23个测试函数对SGA和3种AGA进行实验比较,讨论并总结出各种AGA的优劣所在,为新研究理念的提出提供基础,也为工业应用提供一个参考标准.实验结果表明,基于聚类分析的AGA在算法性能上较其它自适应遗传算法更优,具有很高的实用价值和发展前景.     

Probabilistic robustness analysis: Explicit bounds for the minimum number of samples

In this paper, we study robustness analysis of control systems affected by bounded uncertainty. Motivated by the difficulty to perform this analysis when the uncertainty enters into the plant coefficients in a nonlinear fashion, we study a probabilistic approach. In this setting, the uncertain parameters q are random variables bounded in a set Q and described by a multivariate density function f(q). We then pose the following question: Given a performance level, what is the probability that this level is attained? The main content of this paper is to derive explicit bounds for the number of samples required to estimate this probability with a certain accuracy and confidence a priori specified. It is shown that the number obtained is inversely proportional to these thresholds and it is much smaller than that of classical results. Finally, we remark that the same approach can be followed to study several problems in a control system context. For example, we can evaluate the worst-case H_∞ norm of the sensitivity function of multi-input multi-output systems or compute μ when the robustness margin is of interest.     

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.     

A randomized approximation algorithm for computing bucket orders

We show that a simple randomized algorithm has an expected constant factor approximation guarantee for fitting bucket orders to a set of pairwise preferences.     

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.     

Optimal randomized algorithm for a generalized ski-rental with interest rate

We introduce the continuously compounded interest rate into a generalized ski-rental problem with two options: either pay some rental proportionally to the usage time (the rent option), or buy the equipment and then pay some reduced rental proportionally to the usage time (the generalized buy option). Under the framework of competitive analysis, a randomized algorithm for the modified model is constructed and then is proved optimal by Yao?s Lemma, and thus the optimal competitive ratio is obtained. The result shows that the introduction of the interest rate puts off the optimal purchase date and diminishes the uncertainty involved in the decision making.     

Randomized geometric algorithms and pseudorandom generators

It is shown that the bounds on the expected running times of most of the randomized incremental algorithms in computational geometry do not change by more than a constant factor when they are made pseudorandom using a very simple scheme. This reduces the number of random bits used by these algorithms from (nlogn) toO(logn).This research was supported by Packard fellowship.     

A randomized sublinear time parallel GCD algorithm for the EREW PRAM

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(nloglogn/logn) time using O(n6+?) processors for any ?>0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure.We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.