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

practical algorithms for a family of waterfilling solutions

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2005年第2期53卷 686-695页

作者： Palomar, DP Fonollosa, JR Tech Univ Catalonia UPC Dept Signal Theory & Commun Barcelona 08034 Spain

Many engineering problems that can be formulated as constrained optimization problems result in solutions given by a waterfilling structure;the classical example is the capacity-achieving solution for a frequency-selective channel. For simple waterfilling solutions with a single waterlevel and a single constraint, (typically, a power constraint), some algorithms have been proposed in the literature to compute the solutions numerically. However, some other optimization problems result in significantly more complicated waterfilling solutions that include multiple waterlevels and multiple constraints. For such cases, it may still be possible to obtain practical algorithms to evaluate the solutions numerically but only after a painstaking inspection of the specific waterfilling structure. In addition, a unified view of the different types of waterfilling solutions and the corresponding practical algorithms is missing. The purpose of this paper is twofold. On the one hand, it overviews the waterfilling results existing in the literature from a unified viewpoint. On the other hand, it bridges the gap between a wide family of waterfilling solutions and their efficient implementation in practice;to be more precise, it provides a practical algorithm to evaluate numerically a general waterfilling solution, which includes the currently existing waterfilling solutions and others that may possibly appear in future problems.

关键词： constrained optimization problems MIMO transceiver parallel channels practical algorithms waterfilling waterpouring

来源：评论

学校读者我要写书评

暂无评论

practical algorithms for Generating a Random Ordering of the Elements of a Weighted Set

引用

THEORY OF COMPUTING SYSTEMS 2014年第4期54卷 659-688页

作者： Lang, Kevin J. Yahoo Sunnyvale CA 94089 USA

This paper discusses the problem of efficiently generating a random ordering of the elements of an n-element weighted set, where the elements' weights are interpreted as relative probabilities. It is assumed that only the following randomness primitives are available: flipping a biased coin, and selecting a random non-negative integer smaller than n. We review the existing literature on this problem, focusing on several simple algorithms whose running times are O(n (2)) and O(nlogn). Asymptotically faster algorithms do exist, but they are mostly either very complicated, or require a stronger computational model. The main contribution of this paper is a self-contained specification of and correctness proof for an O(nlogn) mergesort-like folklore algorithm that is often implemented incorrectly. The key piece of the correct algorithm can be viewed as the weighted generalization of the riffle merge operation which appears in mathematical models of card shuffling. Empirical results are also presented which suggest that this algorithm might be faster on a real computer than other simple algorithms which use the same randomness primitives, because its pattern of memory accesses results in fewer cache misses. Finally, three fancier but still implementable algorithms are described, analyzed, and simulated, which are asymptotically faster than O(nlogn), but require that the input weights to be partially sorted.

关键词： practical algorithms Random ordering Random sampling Card shuffling

来源：评论

学校读者我要写书评

暂无评论

Optimality conditions and global convergence for nonlinear semidefinite programming

引用

MATHEMATICAL PROGRAMMING 2020年第1-2期180卷 203-235页

作者： Andreani, Roberto Haeser, Gabriel Viana, Daiana S. Univ Estadual Campinas Dept Appl Math Campinas SP Brazil Univ Sao Paulo Dept Appl Math Sao Paulo SP Brazil Univ Fed Acre Ctr Exact & Technol Sci Rio Branco AC Brazil

Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush-Kuhn-Tucker (AKKT), well known in nonlinear optimization. The second one, called Trace-AKKT, is more natural in the context of semidefinite programming as the computation of eigenvalues is avoided. We propose an augmented Lagrangian algorithm that generates these types of sequences and new constraint qualifications are proposed, weaker than previously considered ones, which are sufficient for the global convergence of the algorithm to a stationary point.

关键词： Nonlinear semidefinite programming Optimality conditions Constraint qualifications practical algorithms

来源：评论

学校读者我要写书评

暂无评论

Computation of Nash equilibria: Admissibility of parallel gradient descent

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1996年第1期90卷 45-61页

作者： Bozma, HI Associate Professor Department of Electrical and Electronic Engineering Boğazici University Bebek Istanbul Turkey

This paper offers some analytical results on the practical computation of Nash equilibria, which has been demonstrated to be relevant in real-world applications. In particular, the parallel gradient descent is analyzed from this perspective, and admissibility conditions are presented. First, the parallel gradient descent is defined in terms of update strategies and iteration times. It is shown that convergence is related to the contraction property. The analysis then derives sufficient conditions for the update strategies and the iteration times that ensure convergence. An illustrative example is presented in order to demonstrate practical implementation aspects and motivate the practical use of game theory in a wide spectrum of applications varying from economics to intelligent sensor systems.

关键词： multiple-objective optimization Nash games practical algorithms parallel decision making

来源：评论

学校读者我要写书评

暂无评论

On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions

引用

OPERATIONS RESEARCH 2006年第3期54卷 464-474页

作者： Chou, Mabel C. Liu, Hui Queyranne, Maurice Simchi-Levi, David Natl Univ Singapore Dept Decis Sci Singapore 117591 Singapore Verizon Labs Boston MA USA Univ British Columbia Sauder Sch Business Vancouver BC V5Z 1M9 Canada MIT Engn Syst Div Cambridge MA 02139 USA MIT Dept Civil & Environm Engn Cambridge MA 02139 USA

We consider the stochastic single-machine problem, when the objective is to minimize the expected total weighted completion time of a set of jobs that are released over time. We assume that the existence and the parameters of each job including its release date, weight, and expected processing times are not known until its release date. The actual processing times are not known until processing is completed. We analyze the performance of the on-line nonpreemptive weighted shortest expected processing time among available jobs (WSEPTA) heuristic. When a scheduling decision needs to be made, this heuristic assigns, among the jobs that have arrived but not yet processed, one with the largest ratio of its weight to its expected processing time. We prove that when the job weights and processing times are bounded and job processing times are mutually independent random variables, WSEPTA is asymptotically optimal for the single-machine problem. This implies that WSEPTA generates a solution whose relative error approaches zero as the number of jobs increases. This result can be extended to the stochastic flow shop and open shop problems, as well as models with stochastic job weights.

关键词： practical algorithms SHOP

来源：评论

学校读者我要写书评

暂无评论

A comparison of sequential Delaunay triangulation algorithms

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1997年第5-6期7卷 361-385页

作者： Su, P Drysdale, RLS JUSTSYST PITTSBURGH RES CTR PITTSBURGHPA 15213 DARTMOUTH COLL DEPT COMP SCISUDIKOFF LAB 6211HANOVERNH 03755

This paper presents an experimental comparison of a number of different algorithms for computing the Delaunay triangulation. The algorithms examined are: Dwyer's divide and conquer algorithm, Fortune's sweepline algorithm, several versions of the incremental algorithm (including one by Ohya, Iri and Murota, a new bucketing-based algorithm described in this paper, and Devillers's version of a Delaunay-tree based algorithm that appears in LEDA), an algorithm that incrementally adds a correct Delaunay triangle adjacent to a current triangle in a manner similar to gift wrapping algorithms for convex hulls, and Barber's convex hull based algorithm. Most of the algorithms examined are designed for good performance on uniformly distributed sites. However, we also test implementations of these algorithms on a number of non-uniform distributions. The experiments go beyond measuring total running time, which tends to be machine-dependent. We also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation. (C) 1997 Elsevier Science B.V.

关键词： Voronoi diagram Delaunay triangulation experimental analysis of algorithms practical algorithms

来源：评论

学校读者我要写书评

暂无评论

On Approximate KKT Condition and its Extension to Continuous Variational Inequalities

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2011年第3期149卷 528-539页

作者： Haeser, Gabriel Laura Schuverdt, Maria Univ La Plata FCE Dept Math CONICET RA-1900 La Plata Buenos Aires Argentina Univ Sao Paulo Inst Math & Stat Sao Paulo Brazil

In this work, we introduce a necessary sequential Approximate-Karush-Kuhn-Tucker (AKKT) condition for a point to be a solution of a continuous variational inequality, and we prove its relation with the Approximate Gradient Projection condition (AGP) of Garciga-Otero and Svaiter. We also prove that a slight variation of the AKKT condition is sufficient for a convex problem, either for variational inequalities or optimization. Sequential necessary conditions are more suitable to iterative methods than usual punctual conditions relying on constraint qualifications. The AKKT property holds at a solution independently of the fulfillment of a constraint qualification, but when a weak one holds, we can guarantee the validity of the KKT conditions.

关键词： Optimality conditions Variational inequalities Constraint qualifications practical algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved SOR method with orderings and direct methods

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 1999年第2期16卷 175-193页

作者： Ishiwata, E Muroya, Y Waseda Univ Dept Math Shinjuku Ku Tokyo 169 Japan

A generalized SOR method with multiple relaxation parameters is considered for solving a linear system of equations. Optimal choices of the parameters are examined under the assumption that the coefficient matrix is tridiagonal and regular, It is shown that the spectral radius of the iterative matrix is reduced to zero for a pair of parameter values which is computed from the pivots of the Gaussian elimination applied to the system. A proper choice of orderings and starting vectors for the iteration is also proposed. When the system is well-conditioned, it is solved stably Ly Gaussian elimination;there is little advantage in using an iterative method. However, when the system is ill-conditioned, the direct method is not necessarily stable and it is often required to improve the numerical solution by a certain iterative algorithm. Some numerical examples are presented which show that the proposed method is more efficient than the standard iterative refinement method. It is also discussed how to apply our technique to a class of systems which includes Hessenberg systems.

关键词： improved SOR method with orderings selection of multiple relaxation parameters UL factorization practical algorithms improved iterative method with orderings

来源：评论

学校读者我要写书评

暂无评论

Quantifying uncertainty in climate change science through empirical information theory

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2010年第34期107卷 14958-14963页

作者： Majda, Andrew J. Gershgorin, Boris NYU Dept Math New York NY 10012 USA NYU Courant Inst Math Sci Ctr Atmosphere Ocean Sci New York NY 10012 USA

Quantifying the uncertainty for the present climate and the predictions of climate change in the suite of imperfect Atmosphere Ocean Science (AOS) computer models is a central issue in climate change science. Here, a systematic approach to these issues with firm mathematical underpinning is developed through empirical information theory. An information metric to quantify AOS model errors in the climate is proposed here which incorporates both coarse-grained mean model errors as well as covariance ratios in a transformation invariant fashion. The subtle behavior of model errors with this information metric is quantified in an instructive statistically exactly solvable test model with direct relevance to climate change science including the prototype behavior of tracer gases such as CO2. Formulas for identifying the most sensitive climate change directions using statistics of the present climate or an AOS model approximation are developed here;these formulas just involve finding the eigenvector associated with the largest eigen-value of a quadratic form computed through suitable unperturbed climate statistics. These climate change concepts are illustrated on a statistically exactly solvable one-dimensional stochastic model with relevance for low frequency variability of the atmosphere. Viable algorithms for implementation of these concepts are discussed throughout the paper.

关键词： model errors practical algorithms unbiased empirical estimates

来源：评论

学校读者我要写书评

暂无评论

Estimation of the Distribution of Random Shifts Deformation

引用

MATHEMATICAL METHODS OF STATISTICS 2009年第1期18卷 21-42页

作者： Castillo, I. Loubes, J. -M. Vrije Univ Amsterdam Fac Exact Sci Amsterdam Netherlands Univ Toulouse III Inst Math Toulouse Toulouse France

Consider discrete values of functions shifted by unobserved translation effects, which are independent realizations of a random variable with unknown distribution mu modeling the variability in the response of each individual. Our aim is to construct a nonparametric estimator of the density of these random translation deformations using semiparametric preliminary estimates of the shifts. Based on the results of Dalalyan et al. [7], semiparametric estimators are obtained in our discrete framework and their performance studied. From these estimates we construct a nonparametric estimator of the target density. Both rates of convergence and an algorithm to construct the estimator are provided.

关键词： semiparametric statistics second-order properties penalized maximum likelihood practical algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：