检索结果-内蒙古大学图书馆

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

AUTOMATICA 2010年第8期46卷 1339-1345页

作者： Wada, Takayuki Fujisaki, Yasumasa Kobe Univ Dept Syst Sci Grad Sch Syst Informat Nada Ku Kobe Hyogo 6578501 Japan

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. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Robust control randomized algorithms Stochastic ellipsoid methods Robust feasibility problems Parameter-dependent linear matrix inequalities Probabilistic robustness

来源：评论

学校读者我要写书评

暂无评论

ON THE RELATIONSHIP BETWEEN EPSILON-BIASED RANDOM-VARIABLES AND EPSILON-DEPENDENT RANDOM-VARIABLES

引用

INFORMATION PROCESSING LETTERS 1994年第1期51卷 17-23页

作者： JIMBO, S MARUOKA, A Department of Information Engineering Faculty of Engineering Tohoku University Sendai 980 Japan

The notions of ''k-wise epsilon-dependent'' and ''k-wise epsilon-biased'' are somewhat weaker in randomness than those of independent random variables. Random variables with these properties could be substitutes for independent random variables of randomized algorithms. In this paper, after giving relevant definitions for these notions, the relationship between these notions is presented: For any integer k and n with 1 less-than-or-equal-to k less-than-or-equal-to n, if a system of n random variables is k-wise epsilon-biased, then it is k-wise 4(1 - 2-k)epsilon-dependent in maximum norm and k-wise 2(1 - 2-k)epsilon-dependent in L1 norm with respect to the uniform distribution. It has been presented, in literature, that k-wise epsilon-biased random variables are substituted for k-wise delta-dependent random variables in many randomized algorithms, so the results of this paper are expected to reduce the running time of resultant algorithms due to derandomization.

关键词： RANDOM VARIABLES DISTRIBUTION INDEPENDENCE LINEAR ALGEBRA SAMPLE SPACE algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Sparse Sums of Positive Semidefinite Matrices

引用

ACM TRANSACTIONS ON algorithms 2016年第1期12卷 1–17页

作者： De Carli Silva, Marcel K. Harvey, Nicholas J. A. Sato, Cristiane M. Univ Waterloo Waterloo ON N2L 3G1 Canada Univ British Columbia Dept Comp Sci Vancouver BC V5Z 1M9 Canada Univ Sap Paulo Inst Matemat & Estat Rua Matao 1010 BR-05508090 Sao Paulo SP Brazil Univ Fed ABC Ctr Matemat Comput & Cognicao Av Estados 5001 BR-09210580 Santo Andre SP Brazil

Many fast graph algorithms begin by preprocessing the graph to improve its sparsity. A common form of this is spectral sparsification, which involves removing and reweighting the edges of the graph while approximately preserving its spectral properties. This task has a more general linear algebraic formulation in terms of approximating sums of rank-one matrices. This article considers a more general task of approximating sums of symmetric, positive semidefinite matrices of arbitrary rank. We present two deterministic, polynomial time algorithms for solving this problem. The first algorithm applies the pessimistic estimators of Wigderson and Xiao, and the second involves an extension of the method of Batson, Spielman, and Srivastava. These algorithms have several applications, including sparsifiers of hypergraphs, sparse solutions to semidefinite programs, sparsifiers of unique games, and graph sparsifiers with various auxiliary constraints.

关键词： Spectral sparsifiers positive semidefinite matrices Laplacian matrix randomized algorithms derandomization

来源：评论

学校读者我要写书评

暂无评论

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

引用

ALGORITHMICA 2009年第1期55卷 205-226页

作者： Kumar, V. S. Anil Marathe, Madhav V. Parthasarathy, Srinivasan Srinivasan, Aravind Virginia Tech Virginia Bioinformat Inst Blacksburg VA 24061 USA IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA

We present polylogarithmic approximations for the R vertical bar prec vertical bar C-max and R vertical bar prec vertical bar Sigma(j) w(j)C(j) problems, when the precedence constraints are "treelike"-i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment-this generalizes the job shop problem to these objective functions. We use the same lower bound of "congestion + dilation", as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617-632, 1994). The first step in our algorithm for the R vertical bar prec vertical bar C-max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.

关键词： Precedence-constrained scheduling Job-shop scheduling Approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-aircraft Conflict Detection and Resolution Based on Probabilistic Reach Sets

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2017年第1期25卷 309-316页

作者： Yang, Yang Zhang, Jun Cai, Kai-Quan Prandini, Maria Beihang Univ Sch Elect & Informat Engn Beijing 100191 Peoples R China Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

In this brief, a novel scheme to multi-aircraft conflict detection and resolution is introduced. A key feature of the proposed scheme is that uncertainty affecting the aircraft future positions along some look-ahead prediction horizon is accounted for via a probabilistic reachability analysis approach. In particular, ellipsoidal probabilistic reach sets are determined by formulating a chance-constrained optimization problem and solving it via a simulation-based method called scenario approach. Conflict detection is then performed by verifying if the ellipsoidal reach sets of different aircraft intersect. If a conflict is detected, then the aircraft flight plans are redesigned by solving a second-order cone program resting on the approximation of the ellipsoidal reach sets with spheres with constant radius along the look-ahead horizon. A bisection procedure allows one to determine the minimum radius such that the ellipsoidal reach sets of different aircraft along the corresponding new flight plans do not intersect. Some numerical examples are presented to show the efficacy of the proposed scheme.

关键词： Air traffic control multi-aircraft conflict detection and resolution (CD&R) probabilistic reachability randomized algorithms stochastic/uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Routing on networks of optical crossbars

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期196卷 181-200页

作者： auf der Heide, FM Schroder, K Schwarze, F Univ Gesamthsch Paderborn Heinz Nixdorf Inst D-33095 Paderborn Germany Univ Gesamthsch Paderborn Dept Math & Comp Sci D-33095 Paderborn Germany

We describe routing algorithms on networks composed of optical busses. Using networks with short busses and small degree we are able to give very fast routing algorithms. First, we describe a leveled optical network and a routing algorithm for it. Next, we show how to simulate this network on high-dimensional meshes of optical busses (MOBs). We present algorithms for routing, e.g., h-relations with runtime being linear in h, doubly logarithmic in size and polynomial in the dimension of the mesh. Previous results are exponential in the dimension. E.g., routing an h-relation on a d-dimensional MOB of size N requires O(d(5) log d log log N + d(3)h) steps, with high probability. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： parallel algorithms randomized algorithms optical networks adaptive routing multibutterflies

来源：评论

学校读者我要写书评

暂无评论

Combining shared-coin algorithms

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2010年第3期70卷 317-322页

作者： Aspnes, James Attiya, Hagit Censor, Keren Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Yale Univ Dept Comp Sci New Haven CT 06520 USA

This paper shows that shared-coin algorithms can be combined to optimize several complexity measures, even in the presence of a strong adversary. By combining shared coins of Bracha and Rachman (1991) [10] and of Aspnes and Waarts (1996) [7], this yields a shared-coin algorithm, and hence, a randomized consensus algorithm, with O(n log(2) n) individual work and O(n(2) log n) total work, using single-writer registers. This improves upon each of the above shared coins (where the former has a high cost for individual work, while the latter reduces it but pays in the total work), and is currently the best for this model. Another application is to prove a construction of Saks, Shavit, and Woll (1991) [16], which combines a shared-coin algorithm that takes O(1) time in failure-free executions, with one that takes O(log n) time in executions where at most root n processes fail, and another one that takes O(n(3)/n-f) time in any other execution. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Distributed computing Shared memory randomized algorithms Consensus Shared coins

来源：评论

学校读者我要写书评

暂无评论

Combining Markov-Chain Analysis and Drift Analysis The (1+1) Evolutionary Algorithm on Linear Functions Reloaded

引用

ALGORITHMICA 2011年第3期59卷 409-424页

作者： Jaegerskuepper, Jens German Aerosp Ctr DLR Inst Aerodynam & Flow Technol Ctr Comp Applicat Aerosp Sci & Engn C2A2S2E Braunschweig Germany

In their seminal article Droste, Jansen, and Wegener (Theor. Comput. Sci. 276:51-82, 2002) consider a basic direct-search heuristic with a global search operator, namely the so-called (1+1) Evolutionary Algorithm ((1+1) EA). They present the first theoretical analysis of the (1+1) EA's expected runtime for the class of linear functions over the search space {0,1} (n) . In a rather long and involved proof they show that, for any linear function, the expected runtime is O(nlog n), i.e., that there are two constants c and n' such that, for na parts per thousand yenn', the expected number of iterations until a global optimum is generated is bounded above by ca <...nlog (2) n. However, neither c nor n' are specified-they would be pretty large. Here we reconsider this optimization scenario to demonstrate the potential of an analytical method that makes use of the distribution of the evolving candidate solution over the search space {0,1} (n) . Actually, an invariance property of this distribution is proved, which is then used to obtain a significantly improved bound on the drift, namely the expected change of a potential function, here the number of bits set correctly. Finally, this better estimate of the drift enables an upper bound on the expected number of iterations of 3.8nlog (2) n+7.6log (2) n for na parts per thousand yen2.

关键词： Heuristic optimization Direct search Evolutionary algorithms Genetic algorithms randomized algorithms Drift analysis Markov-Chain analysis

来源：评论

学校读者我要写书评

暂无评论

Revisiting the Nystrom Method for Improved Large-scale Machine Learning

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2016年 17卷 1-65页

作者： Gittens, Alex Mahoney, Michael W. Univ Calif Berkeley Int Comp Sci Inst Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods;they characterize the effects of common data preprocessing steps on the performance of these algorithms;and they point to important differences between uniform sampling and nonuniform sampling methods based on leverage scores. In addition, our empirical results illustrate that existing theory is so weak that it does not provide even a qualitative guide to practice. Thus, we complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds-e.g., improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error-and they point to future directions to make these algorithms useful in even larger-scale machine learning applications.

关键词： Nystrom approximation low-rank approximation kernel methods randomized algorithms numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Learning to Act Safely With Limited Exposure and Almost Sure Certainty

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2023年第5期68卷 2979-2994页

作者： Castellano, Agustin Min, Hancheng Bazerque, Juan Andres Mallada, Enrique Johns Hopkins Univ Dept Elect & Comp Engn Baltimore MD 21218 USA Univ Pittsburgh Dept Elect Engn Pittsburgh PA 15213 USA

This article puts forward the concept that learning to take safe actions in unknown environments, even with probability one guarantees, can be achieved without the need for an unbounded number of exploratory trials. This is indeed possible, provided that one is willing to navigate tradeoffs between optimality, level of exposure to unsafe events, and the maximum detection time of unsafe actions. We illustrate this concept in two complementary settings. We first focus on the canonical multiarmed bandit problem and study the intrinsic tradeoffs of learning safety in the presence of uncertainty. Under mild assumptions on sufficient exploration, we provide an algorithm that provably detects all unsafe machines in an (expected) finite number of rounds. The analysis also unveils a tradeoff between the number of rounds needed to secure the environment and the probability of discarding safe machines. We then consider the problem of finding optimal policies for a Markov decision process (MDP) with almost sure constraints. We show that the action-value function satisfies a barrier-based decomposition that allows for the identification of feasible policies independently of the reward process. Using this decomposition, we develop a barrier-learning algorithm, that identifies such unsafe state-action pairs in a finite expected number of steps. Our analysis further highlights a tradeoff between the time lag for the underlying MDP necessary to detect unsafe actions, and the level of exposure to unsafe events. Simulations corroborate our theoretical findings, further illustrating the aforementioned tradeoffs, and suggesting that safety constraints can speed up the learning process.

关键词： Safety Uncertainty Program processors Markov processes Training Trajectory Task analysis Iterative learning control optimal control randomized algorithms uncertain systems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：