The Existence of Good Extensible Polynomial Lattice Rules

Extensible (polynomial) lattice rules have been introduced recently and they are convenient tools for quasi-Monte Carlo integration. It is shown in this paper that for suitable infinite families of polynomial moduli there exist generating parameters for extensible rank-1 polynomial lattice rules such that for all these infinitely many moduli and all dimensions s the quantity R ^(s) and the star discrepancy are small. The case of Korobov-type polynomial lattice rules is also considered.Received April 30, 2002; in revised form August 21, 2002 Published online April 4, 2003     

The Existence of Good Extensible Polynomial Lattice Rules

Extensible (polynomial) lattice rules have been introduced recently and they are convenient tools for quasi-Monte Carlo integration. It is shown in this paper that for suitable infinite families of polynomial moduli there exist generating parameters for extensible rank-1 polynomial lattice rules such that for all these infinitely many moduli and all dimensions s the quantity R ^(s) and the star discrepancy are small. The case of Korobov-type polynomial lattice rules is also considered.     

Component-by-Component Construction of Good Lattice Rules with a Composite Number of Points

We develop algorithms to construct rank-1 lattice rules in weighted Korobov spaces of periodic functions and shifted rank-1 lattice rules in weighted Sobolev spaces of non-periodic functions. Analyses are given which show that the rules so constructed achieve strong QMC tractability error bounds. Unlike earlier analyses, there is no assumption that n, the number of quadrature points, be a prime number. However, we do assume that there is an upper bound on the number of distinct prime factors of n. The generating vectors and shifts characterizing the rules are constructed ‘component-by-component,’ that is, the (d+1)th components of the generating vectors and shifts are obtained using one-dimensional searches, with the previous d components kept unchanged.     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

Different Quality Indexes for Lattice Rules

We consider lattice rules (i.e. cubature formulas with equal coefficients whose nodes lie on a lattice) which are exact for trigonometric polynomials in two variables with different spectra. Various quality indexes are characterized. Extremal properties of indexes are obtained. A new family of lattice rules of trigonometric degree is presented. Also a family of lattice rules exact on trigonometric polynomials of a hexagonal spectrum is constructed.     

Improved Error Bounds for Lattice Rules

We establish results on the worst-case errors that can be achieved by well-chosen lattice rules for standard classes of multivariate periodic functions. These theorems improve or generalize earlier results of this type.     

On Some Interpolation Rules for Lattice Ordered Groups

Let be an infinite cardinal. In this paper we define an interpolation rule IR() for lattice ordered groups. We denote by C() the class of all lattice ordered groups satisfying IR(), and prove that C() is a radical class.     

Characteristics of Good Meta-Heuristic Algorithms for the Frequency Assignment Problem

Most writers on frequency assignment algorithms have described the details of a single algorithm, and evaluated the algorithm on selected data sets. There has been relatively little emphasis on describing the common features that are important if an algorithm is to have good performance. This paper describes the key features, with particular emphasis on algorithms for weighted fixed spectrum problems. The use of algorithms handling weighted constraints has become increasingly common in recent years. The advantages and disadvantages of weighting constraints are demonstrated.     

An Introduction to Lattice Rules and their Generator Matrices

For the one-dimensional quadrature of a naturally periodic functionover its period, the trapezoidal rule is an excellent choice,its efficiency being predicted theoretically and confirmed inpractice. However, for s-dimensional quadrature over a hypercube,the s-dimensional product trapezoidal rule is not generallycost effective even for naturally periodic functions. The searchfor more effective rules has led first to number theoretic rulesand then more recently to lattice rules. This survey outlinesthe motivation for and present results of this theory. It isparticularly designed to introduce the reader to lattice rules.     

Inducing Stock Screening Rules for Portfolio Construction

This study describes a technique originated from the emerging field of machine learning and demonstrates its effectiveness in stock screening. We have derived screening rules by applying a rule induction method, constructed portfolios using the rules, and evaluated the portfolios' performance using the Sharpe, Treynor and Jensen indexes. Results indicate that regularities among stocks can be identified, and portfolios so constructed outperformed the NYSE Composite index and the S&P 500 over the same period.     

Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).     

Strong Rules for Nonconvex Penalties and Their Implications for Efficient Algorithms in High-Dimensional Regression

We consider approaches for improving the efficiency of algorithms for fitting nonconvex penalized regression models such as smoothly clipped absolute deviation (SCAD) and the minimax concave penalty (MCP) in high dimensions. In particular, we develop rules for discarding variables during cyclic coordinate descent. This dimension reduction leads to an improvement in the speed of these algorithms for high-dimensional problems. The rules we propose here eliminate a substantial fraction of the variables from the coordinate descent algorithm. Violations are quite rare, especially in the locally convex region of the solution path, and furthermore, may be easily corrected by checking the Karush–Kuhn–Tucker conditions. We extend these rules to generalized linear models, as well as to other nonconvex penalties such as the ?₂-stabilized Mnet penalty, group MCP, and group SCAD. We explore three variants of the coordinate decent algorithm that incorporate these rules and study the efficiency of these algorithms in fitting models to both simulated data and on real data from a genome-wide association study. Supplementary materials for this article are available online.     

The Number of Lattice Rules of Specified Upper Class and Rank

The upper class of a lattice rule is a convenient entity for classification and other purposes. The rank of a lattice rule is a basic characteristic, also used for classification. By introducing a rank proportionality factor and obtaining certain recurrence relations, we show how many lattice rules of each rank exist in any prime upper class. The Sylow p-decomposition may be used to obtain corresponding results for any upper class.     

基于对象导出三支概念格的决策背景规则获取

规则获取是当前形式概念分析领域的研究热点.首先给出了基于对象导出三支概念格间的细于关系,定义了基于对象导出三支概念格的三支弱协调性,并研究了其与经典概念格下的二支弱协调性之间的关系.然后,研究了基于对象导出三支概念格的规则获取,并与经典概念格的规则获取进行了比较.最后,定义了对象导出三支概念的弱闭标记,研究了基于弱闭标记的三支弱协调决策形式背景的规则获取,剔除了冗余规则,并且得到一些新的更为精简的三支规则.     

Clustering Rules: A Comparison of Partitioning and Hierarchical Clustering Algorithms

Previous research has resulted in a number of different algorithms for rule discovery. Two approaches discussed here, the ‘all-rules’ algorithm and multi-objective metaheuristics, both result in the production of a large number of partial classification rules, or ‘nuggets’, for describing different subsets of the records in the class of interest. This paper describes the application of a number of different clustering algorithms to these rules, in order to identify similar rules and to better understand the data.     

基于概念格的决策形式背景属性约简及规则提取

给出了决策形式背景下的属性约简与规则提取方法.为此,针对属性约简中起不同作用的属性,区分了必要属性与不必要属性,给出了各类属性的特征和判别方法;在此基础上得到了决策形式背景下的规则提取与属性约简方法,并通过实例表明了该约简方法的可行性与有效性.     

轴向拉伸细长杆的非线性力学模型

聚酯系泊缆是深海工程中具备一定抗弯刚度、易拉伸变形的细长杆件结构.聚酯缆的轴向变形属大拉伸范畴,分析中应当区分变形前后状态,特别是缆索长度的改变使得基于小拉伸假设的细长杆模型需要予以改进.因此,基于Garrett细长杆模型,应用总体坐标和斜率取代Euler-Bernoulli(欧拉 伯努利)梁元的转角,解决缆索在空间中大转动变形的几何非线性问题;使用轴向拉伸变形前后物质点对应的方法,借助单元两个节点和一个中点,以及3个二次多项式形函数描述轴向拉伸变形下细长杆元的运动微分方程.通过与轴向拉伸悬臂梁的对比分析,验证了该拉伸杆元的收敛性和准确性.     

Completeness Criteria for a Linear Model of Classification Algorithms with Respect to Families of Decision Rules

Doklady Mathematics - In the framework of Zhuravlev’s algebraic approach to classification problems, a linear model of algorithms is investigated (estimates of class membership are generated...