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

Sequential randomized algorithms for Convex Optimization in the Presence of Uncertainty

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2016年第9期61卷 2565-2571页

作者： Chamanbaz, Mohammadreza Dabbene, Fabrizio Tempo, Roberto Venkataramanan, Venkatakrishnan Wang, Qing-Guo Data Storage Inst Singapore 138632 Singapore Natl Univ Singapore Dept Elect & Comp Engn Singapore 119077 Singapore Politecn Torino CNR IEIIT I-10129 Turin Italy

In this technical note, we propose new sequential randomized algorithms for convex optimization problems in the presence of uncertainty. A rigorous analysis of the theoretical properties of the solutions obtained by these algorithms, for full constraint satisfaction and partial constraint satisfaction, respectively, is given. The proposed methods allow to enlarge the applicability of the existing randomized methods to real-world applications involving a large number of design variables. Since the proposed approach does not provide a priori bounds on the sample complexity, extensive numerical simulations, dealing with an application to hard-disk drive servo design, are provided. These simulations testify the goodness of the proposed solution.

关键词： Convex optimization hard-disk servo design randomized algorithms sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane

引用

ALGORITHMICA 2002年第4期33卷 436-460页

作者： Rajasekaran, S Ramaswami, S Univ Florida Dept Comp & Informat Sci Gainesville FL 32606 USA Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA

We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O (n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem is O(n log n). Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, O'Dunlaing, and Yap, which runs in O(log(2) n) time using O(n) processors. We obtain this result by using a new "two-stage" random sampling technique. By choosing large samples in the first stage of the algorithm, we avoid the hurdle of problem-size "blow-up" that is typical in recursive parallel geometric algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm. This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use the transformation to three-dimensional half-space intersection).

关键词： Voronoi diagrams line segments parallel algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Some randomized algorithms for convex quadratic programming

引用

APPLIED MATHEMATICS AND OPTIMIZATION 1999年第1期39卷 121-142页

作者： Goldbach, R Univ Wurzburg Inst Angew Math & Stat D-97074 Wurzburg Germany

We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems, which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present. We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods.

关键词： randomized algorithms convex programming quadratic programming linear programming

来源：评论

学校读者我要写书评

暂无评论

A survey of randomized algorithms for control synthesis and performance verification

引用

JOURNAL OF COMPLEXITY 2007年第3期23卷 301-316页

作者： Calafiore, Giuseppe Dabbene, Fabrizio Tempo, Roberto Politecn Torino IEIIT CNR I-10129 Turin Italy Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy

In this paper, we present an overview of probabilistic techniques based on randomized algorithms for solving "hard" problems arising in performance verification and control of complex systems. This area is fairly recent, even though its roots lie in the robustness techniques for handling uncertain control systems developed in the 1980s. In contrast to these deterministic techniques, the main ingredient of the methods discussed in this survey is the use of probabilistic concepts. The introduction of probability and random sampling permits overcoming the fundamental tradeoff between numerical complexity and conservatism that lie at the roots of the worst-case deterministic methodology. The simplicity of implementation of randomized techniques may also help bridging the gap between theory and practical applications. (c) 2007 Elsevier Inc. All rights reserved.

关键词： complex control systems randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuning- and LUT-based voting platform

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第1期190卷 132-149页

作者： Chung, Kuo-Liang Huang, Yong-Huai Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 10672 Taiwan

Shape detection is a fundamental problem in image processing field. In shape detection, lines, circles, and ellipses are the three most important features. In the past four decades, the robustness and the time speedup are two main concerned issues in most developed algorithms. Previously, many randomized algorithms were developed to speed up the computation of the relevant detection successfully. This paper does focus on the time speedup issue. Based on Bresenham's drawing paradigm, this paper first presents a novel lookup table (LUT)-based voting platform. According to the proposed LUT-based voting platform, we next present a novel computational scheme to significantly speed up the computation of some existing randomized algorithms for detecting lines, circles, and ellipses. Moreover, the detailed time complexity analyses are provided for the three concerned features under our proposed computational scheme and these derived nontrivial analyses also show the relevant computational advantage. Under some real images, experimental results illustrate that our proposed computational scheme can significantly speed up the computation of some existing randomized algorithms. In average, the execution-time improvement ratios are about 28%, 56%, and 48% for detecting lines, circles, and ellipses, respectively, and these improvement ratios are vary close to the theoretic analyses. (C) 2007 Elsevier Inc. All rights reserved.

关键词： Bresenham's drawing paradigm circles ellipses lines randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Insights into randomized algorithms for neural networks: Practical issues and common pitfalls

引用

INFORMATION SCIENCES 2017年 382卷 170-178页

作者： Li, Ming Wang, Dianhui La Trobe Univ Dept Comp Sci & Informat Technol Melbourne Vic 3086 Australia

Random Vector Functional-link (RVFL) networks, a class of learner models, can be regarded as feed-forward neural networks built with a specific randomized algorithm, i.e., the input weights and biases are randomly assigned and fixed during the training phase, and the output weights are analytically evaluated by the least square method. In this paper, we provide some insights into RVFL networks and highlight some practical issues and common pitfalls associated with RVFL-based modelling techniques. Inspired by the folklore that "all high-dimensional random vectors are almost always nearly orthogonal to each other", we establish a theoretical result on the infeasibility of RVFL networks for universal approximation, if a RVFL network is built incrementally with random selection of the input weights and biases from a fixed scope, and constructive evaluation of its output weights. This work also addresses the significance of the scope setting of random weights and biases in respect to modelling performance. Two numerical examples are employed to illustrate our findings, which theoretically and empirically reveal some facts and limits of such class of randomized learning algorithms. (C) 2016 Elsevier Inc. All rights reserved.

关键词： randomized algorithms Neural networks Incremental learning Function approximation

来源：评论

学校读者我要写书评

暂无评论

Proofs of randomized algorithms in COQ

引用

SCIENCE OF COMPUTER PROGRAMMING 2009年第8期74卷 568-589页

作者： Audebaud, Philippe Paulin-Mohring, Christine INRIA Saclay Ile France F-91893 Orsay France Ecole Normale Super Lyon LIP F-69437 Lyon France CNRS F-91405 Orsay France Univ Paris Sud LRI F-91405 Orsay France

randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions. We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the CoQ proof assistant. (C) 2009 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Proof of partial and total correctness Functional language Axiomatic semantics Probability framing Call-by-value Monadic interpretation

来源：评论

学校读者我要写书评

暂无评论

A BETTER BOUND OF randomized algorithms FOR THE MULTISLOPE SKI-RENTAL PROBLEM

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2017年第2期51卷 91-98页

作者： Hu, Maolin Xu, Weijun Huaiyin Normal Univ Sch Math Sci Huaian 223300 Jiangsu Peoples R China South China Univ Technol Sch Business Adm Guangzhou 510641 Guangdong Peoples R China

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options in addition to the pure rent and buy options. For the additive general model, Lotker, Patt-Shamir and Rawitz [in: SIAM J. Discr. Math. 26 (2012) 718-736] obtained a randomized algorithm with the competitive ratio bounded by e-r(k)/r(0) /e-1. However, obtaining a better bound on the competitive factor as a function of the slopes parameters remains an open problem in their paper. In this paper, we study randomized algorithm for the additive multislope ski rental problem, and extend the competitive ratio bound e-r(k)/r(0) /e-1 proposed by Lotker et al. to e/e-1+r(k)/r(0)

关键词： Online algorithms ski rental randomized algorithms competitive ratio

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL randomized algorithms FOR LOCAL SORTING AND SET-MAXIMA

引用

SIAM JOURNAL ON COMPUTING 1993年第2期22卷 272-283页

作者： GODDARD, W KENYON, C KING, V SCHULMAN, LJ ECOLE NORM SUPER LIENSF-75230 PARIS 05FRANCE NEC CORP LTD PRINCETONNJ 08540

randomized algorithms for two sorting problems are presented. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order of every pair of adjacent vertices. In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set. Lower bounds for the problems in the comparison model are described and it is shown that the algorithms are optimal within a constant factor.

关键词： SORTING randomized algorithms COMPARISON MODEL PARTIAL ORDER GRAPH algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust computation of aggregates in wireless sensor networks: Distributed randomized algorithms and analysis

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2006年第9期17卷 987-1000页

作者： Chen, Jen-Yeu Pandurangan, Gopal Xu, Dongyan Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

A wireless sensor network consists of a large number of small, resource-constrained devices and usually operates in hostile environments that are prone to link and node failures. Computing aggregates such as average, minimum, maximum and sum is fundamental to various primitive functions of a sensor network, such as system monitoring, data querying, and collaborative information processing. In this paper, we present and analyze a suite of randomized distributed algorithms to efficiently and robustly compute aggregates. Our Distributed Random Grouping (DRG) algorithm is simple and natural and uses probabilistic grouping to progressively converge to the aggregate value. DRG is local and randomized and is naturally robust against dynamic topology changes from link/node failures. Although our algorithm is natural and simple, it is nontrivial to show that it converges to the correct aggregate value and to bound the time needed for convergence. Our analysis uses the eigenstructure of the underlying graph in a novel way to show convergence and to bound the running time of our algorithms. We also present simulation results of our algorithm and compare its performance to various other known distributed algorithms. Simulations show that DRG needs far fewer transmissions than other distributed localized schemes.

关键词： probabilistic algorithms randomized algorithms distributed algorithms sensor networks fault tolerance graph theory aggregate data query stochastic processes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：