This paper deals with the sampled scenarios approach to robust convex programming. It has been shown in previous works that by randomly sampling a sufficient number of constraints among the (possibly) infinite constra...
详细信息
ISBN:
(纸本)0780386825
This paper deals with the sampled scenarios approach to robust convex programming. It has been shown in previous works that by randomly sampling a sufficient number of constraints among the (possibly) infinite constraints of a robust convex program, one obtains a standard convex optimization problem whose solution is 'approximately feasible', in a probabilistic sense, for the original robust convex program. This is a generalization property in the learning theoretic sense, since the satisfaction of a certain number of 'training' constraints entails the satisfaction of other 'unseen' constraints. In this paper we provide a new efficient bound on the generalization rate of sampled convex programs, and show an example of application to a robust control design problem.
作者：
Oishi, YKimura, HUniv Tokyo
Grad Sch Informat Sci & Technol Dept Math Informat Bunkyo Ku Tokyo 1130033 Japan
The randomized algorithm of Calafiore and Polyak, which consists of random sampling and subgradient descent, is analyzed in the case that it is used to solve parameter-dependent linear matrix inequalities. This paper ...
详细信息
ISBN:
(纸本)0780370619
The randomized algorithm of Calafiore and Polyak, which consists of random sampling and subgradient descent, is analyzed in the case that it is used to solve parameter-dependent linear matrix inequalities. This paper shows that the expected time to achieve a solution is infinite if this algorithm is used in its original form. However, it is also shown that the algorithm can be improved so that its expected achievement time becomes finite. An explicit upper bound of the expected achievement time is given in a special case. A numerical example is provided.
Fitting two-dimensional conic sections (e.g,, circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. ...
详细信息
Fitting two-dimensional conic sections (e.g,, circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. Recently there has been a great deal of interest in robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. In this paper we introduce nonlinear Theil-Sen and repeated median (RM) variants for estimating the center and radius of a circular are, and for estimating the center and horizontal and Vertical radii of an axis-aligned ellipse. The circular are estimators have breakdown points of approximate to 21% and 50%. respectively, and the ellipse estimators have breakdown points of approximate to 16% and 50%, respectively. We present randomized algorithms for these estimators, whose expected running times are O(n(2) log n) for the circular case and O(n(3) log n) for the elliptical case. All algorithms use O(n) space in the worst case, (C) 2001 Elsevier Science B.V. All rights reserved.
Iterative control is an efficient methodology for the design of highly-performing controllers. In this paper, we discuss many implementation issues of a new iterative scheme which explicitly accounts for the presence ...
详细信息
Iterative control is an efficient methodology for the design of highly-performing controllers. In this paper, we discuss many implementation issues of a new iterative scheme which explicitly accounts for the presence of uncertainty. The developed iterative enables one to improve quickly the performance through subsequent steps, while preserving the robust stability of the closed-loop system.
In this paper a fault diagnosis technique for electronic analog circuits is described. Diagnosis is obtained by comparing input-output measurements with examples contained in a fault dictionary, by means of a neural c...
详细信息
ISBN:
(纸本)0780366468
In this paper a fault diagnosis technique for electronic analog circuits is described. Diagnosis is obtained by comparing input-output measurements with examples contained in a fault dictionary, by means of a neural classifier. A harmonic analysis is used, i.e. the test input stimuli are sinusoidal waves. A novel method for optimizing the fault dictionary construction is proposed. In particular, the stimuli selection is optimized by means of a sensitivity analysis of the Circuit Under Test -CUT- relying on a probabilistic approach based on randomized algorithms. This technique allows removing all the hypothesis assumed by the related literature. In fact it allows to remove the small perturbation assumption and presents a poly-time solution independently from the dimension of the perturbation..
We conduct an experimental analysis of a distributed randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple yet, according to the probabilistic analysis, it computes nearly ...
详细信息
A Radio Network (RN, for short) is a distributed system with no central arbiter, consisting of p radio stations each of which is endowed with a radio transceiver. In this work we consider single-hop, single channel RN...
详细信息
A Radio Network (RN, for short) is a distributed system with no central arbiter, consisting of p radio stations each of which is endowed with a radio transceiver. In this work we consider single-hop, single channel RNs, where each station S(i), (1 less than or equal to i less than or equal to p), initially stores si items which are tagged with the unique destination they must be routed. Since each item must be transmitted at least once, every routing protocol must take at least n = s(1) + s(2) + (. . .) + Sp time slots to route each item to its final destination. Similarly, each station S(i), (1 : i P), must be awake for at least si + d(i) time slots to broadcast si items and to receive di items, where di denotes the number of items destined for S(i). The main contribution of this work is to present a randomized time- and energy-optimal routing protocol on the RN. Let q(i), (1 less than or equal to i less than or equal to p), be the number of stations that have items destined for S(i), q = q(1) + q(2) + (. . .) + q(p), and r(i) be the number of stations for which S(i) has items. When qi is known to station S(i), our routing protocol runs, with probability exceeding 1 - 1/f, (f > 1), in n + O(q + log f) time slots with each f station S(i) being awake for at most si + di + O(qi + ri + log f) time slots. Since qi : di, ri : si, and q ! n always hold, our randomized routing protocol is optimal. We also show that, when the value of di is known to S(i), our routing protocol runs, with probability exceeding I - -1, (f > 1), in 0 (n + log f) time slots f with no station being awake for more than O(s(i) + d(i) + log f) time slots.
In this paper we present a randomized selection algorithm that with high probability 1 - 1/n(rho), for any constant p > 1 requires n + C + o(n) comparisons to determine the Cth order statistic of n keys thus matchi...
详细信息
In this paper we present a randomized selection algorithm that with high probability 1 - 1/n(rho), for any constant p > 1 requires n + C + o(n) comparisons to determine the Cth order statistic of n keys thus matching a corresponding lower bound on the average number of comparisons required. Low order terms in the number of comparisons performed can also be reduced by extending the algorithm of Floyd and Rivest and analyzing its resulting performance more carefully. (C) 2003 Elsevier B.V. All rights reserved.
We prove an exponential lower bound 2(Omega(n/log n)) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new lower bound on Yao's ran...
详细信息
We prove an exponential lower bound 2(Omega(n/log n)) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new lower bound on Yao's randomized one-way communication complexity of certain Boolean functions. It generalizes to some other models of randomized branching programs. In contrast, we prove that testing integer multiplication, contrary even to a non-deterministic situation, can be computed by randomized ordered read-once branching program in polynomial size. It is also known that computing the latter problem with deterministic read-once branching programs is as hard as factoring integers. (C) 2003 Elsevier Science (USA). All rights reserved.
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n-vertex graph the algorithm runs in o((log n)(1+epsilon)) expected time for any epsilon > 0 and p...
详细信息
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n-vertex graph the algorithm runs in o((log n)(1+epsilon)) expected time for any epsilon > 0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation-the QSM and the BSP.
暂无评论