Simplicial Lipschitz optimization without the Lipschitz constant

In this paper we propose a new simplicial partition-based deterministic algorithm for global optimization of Lipschitz-continuous functions without requiring any knowledge of the Lipschitz constant. Our algorithm is motivated by the well-known Direct algorithm which evaluates the objective function on a set of points that tries to cover the most promising subregions of the feasible region. Almost all previous modifications of Direct algorithm use hyper-rectangular partitions. However, other types of partitions may be more suitable for some optimization problems. Simplicial partitions may be preferable when the initial feasible region is either already a simplex or may be covered by one or a manageable number of simplices. Therefore in this paper we propose and investigate simplicial versions of the partition-based algorithm. In the case of simplicial partitions, definition of potentially optimal subregion cannot be the same as in the rectangular version. In this paper we propose and investigate two definitions of potentially optimal simplices: one involves function values at the vertices of the simplex and another uses function value at the centroid of the simplex. We use experimental investigation to compare performance of the algorithms with different definitions of potentially optimal partitions. The experimental investigation shows, that proposed simplicial algorithm gives very competitive results to Direct algorithm using standard test problems and performs particularly well when the search space and the numbers of local and global optimizers may be reduced by taking into account symmetries of the objective function.     

Data structures for maintaining set partitions

Efficiently maintaining the partition induced by a set of features is an important problem in building decision‐tree classifiers. In order to identify a small set of discriminating features, we need the capability of efficiently adding and removing specific features and determining the effect of these changes on the induced classification or partition. In this paper we introduce a variety of randomized and deterministic data structures to support these operations on both general and geometrically induced set partitions. We give both Monte Carlo and Las Vegas data structures that realize near‐optimal time bounds and are practical to implement. We then provide a faster solution to this problem in the geometric setting. Finally, we present a data structure that efficiently estimates the number of partitions separating elements. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Optimal partitioning of a measurable space into countably many sets

Summary A notion of an optimal partition of a measurable space into countably many sets according to given nonatomic probability measures is defined. It is shown that the set of optimal partitions is nonempty. Bounds for the optimal value are given and the set of optimal partitions is characterized. Finally, an example related to statistical decision theory is presented.     

Localizing combinatorial properties of partitions

The purpose of this paper is to develop a framework for the analysis of combinatorial properties of partitions. Our focus is on the relation between global properties of partitions and their localization to subpartitions. First, we study properties that are characterized by their local behavior. Second, we determine sufficient conditions for classes of partitions to have a member that has a given property. These conditions entail the possibility of being able to move from an arbitrary partition in the class to one that satisfies the given property by sequentially satisfying local variants of the property. We apply our approach to several properties of partitions that include consecutiveness, nestedness, order-consecutiveness, full nestedness and balancedness, and we demonstrate its usefulness in determining the existence of optimal partitions that satisfy such properties.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

The geometry of optimal partitions in location problems

Given the position of some facilities, we study the shape of optimal partitions of the customers’ area in a general planar demand region minimizing total average cost that depends on a set up cost plus some function of the travelling distances. By taking into account different norms, according to the considered situation of the location problem, we characterize optimal consumers’ partitions and describe their geometry. The case of dimensional facilities is also investigated.     

Near-Best Univariate Spline Discrete Quasi-Interpolants on Nonuniform Partitions

The univariate spline quasi-interpolants (QIs) studied in this paper are approximation operators using B-spline expansions with coefficients that are linear combinations of discrete values of the function to be approximated. When working with nonuniform partitions, the main challenge is to find QIs that have both good approximation orders and uniform norms which are bounded independently of the given partition. Near-best QIs are obtained by minimizing an upper bound for the infinity norm of QIs depending on a certain number of free parameters, thus reducing this norm. This paper is devoted to the study of some families of near-best discrete quasi-interpolants (dQIs) of approximation order 3.      

On the equivalence of brushlet and wavelet bases

We prove that the Meyer wavelet basis and a class of brushlet systems associated with exponential type partitions of the frequency axis form a family of equivalent (unconditional) bases for the Besov and Triebel-Lizorkin function spaces. This equivalence is then used to obtain new results on nonlinear approximation with brushlets in Triebel-Lizorkin spaces.     

Adaptive Bayesian Nonstationary Modeling for Large Spatial Datasets Using Covariance Approximations

Gaussian process models have been widely used in spatial statistics but face tremendous modeling and computational challenges for very large nonstationary spatial datasets. To address these challenges, we develop a Bayesian modeling approach using a nonstationary covariance function constructed based on adaptively selected partitions. The partitioned nonstationary class allows one to knit together local covariance parameters into a valid global nonstationary covariance for prediction, where the local covariance parameters are allowed to be estimated within each partition to reduce computational cost. To further facilitate the computations in local covariance estimation and global prediction, we use the full-scale covariance approximation (FSA) approach for the Bayesian inference of our model. One of our contributions is to model the partitions stochastically by embedding a modified treed partitioning process into the hierarchical models that leads to automated partitioning and substantial computational benefits. We illustrate the utility of our method with simulation studies and the global Total Ozone Matrix Spectrometer (TOMS) data. Supplementary materials for this article are available online.     

Set partitions and integrable hierarchies

We demonstrate that statistics for several types of set partitions are described by generating functions arising in the theory of integrable equations.     

Partition Identities Involving Gaps and Weights,II

In this second paper under the same title, some more weighted representations are obtained for various classical partition functions including p(n), the number of unrestricted partitions ofn , Q(n), the number of partitions ofn into distinct parts and the Rogers-Ramanujan partitions ofn (of both types). The weights derived here are given either in terms of congruence conditions satisfied by the parts or in terms of chains of gaps between the parts. Some new connections between partitions of the Rogers-Ramanujan, Schur and Göllnitz–Gordon type are revealed.     

The Dubins–Spanier optimization problem in fair division theory

An optimality criterion for fair division theory, introduced by Dubins and Spanier in 1961, is recalled with the purpose of analyzing its structure in relationship with other optimal solutions (Pareto- and equi-optimal partitions). A geometric dual approach is also defined, with the purpose of characterizing and identifying the Dubins–Spanier optimal solutions.     

On minimum k-modal partitions of permutations

Partitioning a permutation into a minimum number of monotone subsequences is -hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k=1. Based on a network flow interpretation we formulate both, the monotone and the k-modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k+1)-approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs.     

A new simplicial cover technique in constrained global optimization

A simplicial branch and bound-outer approximation technique for solving nonseparable, nonlinearly constrained concave minimization problems is proposed which uses a new simplicial cover rather than classical simplicial partitions. Some geometric properties and convergence results are demonstrated. A report on numerical aspects and experiments is given which shows that the most promising variant of the cover technique can be expected to be more efficient than comparable previous simplicial procedures.     

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

We study the complexity of approximating the smallest eigenvalue of -Δ+q with Dirichlet boundary conditions on the d-dimensional unit cube. Here Δ is the Laplacian, and the function q is non-negative and has continuous first order partial derivatives. We consider deterministic and randomized classical algorithms, as well as quantum algorithms using quantum queries of two types: bit queries and power queries. We seek algorithms that solve the problem with accuracy . We exhibit lower and upper bounds for the problem complexity. The upper bounds follow from the cost of particular algorithms. The classical deterministic algorithm is optimal. Optimality is understood modulo constant factors that depend on d. The randomized algorithm uses an optimal number of function evaluations of q when d≤2. The classical algorithms have cost exponential in d since they need to solve an eigenvalue problem involving a matrix with size exponential in d. We show that the cost of quantum algorithms is not exponential in d, regardless of the type of queries they use. Power queries enjoy a clear advantage over bit queries and lead to an optimal complexity algorithm.     

Supersonic flow past triangular wings with ribs on their surface PMM vol. 31, no. 6, 1967, pp. 1050–1056

Various types of partitions are a common feature of lifting surfaces. These partitions can take the form of stiffening ribs, deflectors for preventing secondary flows or flow separation, etc. The presence of partitions has a marked effect on the character of flow and on the values of the aerodynamic parameters. Flow past such wings cannot be computed in the general case. Wings of a special type are amenable to simple solution, however, and this will be considered below. One special case of interaction between a partition and an infinite wing is also considered in [1].     

有限元插值误差的下界估计

基于一维区域上的拟一致剖分,证明了线性元插值误差的最优下界估计.基于此并利用超收敛理论,我们得到了有限元离散误差的上、下界.     

Automatic clustering of business processes in business systems planning

In this paper, we apply the technique of hierarchical clustering to business processes identified in business systems planning (BSP) which is an important methodology in information systems planning. A measure based on notions of cohesion and coupling is proposed as a guidance in searching for optimal number of clusters of business processes. By optimality, we mean that the net cohesion is maximized and net coupling is minimized. Moreover, we show that optimal number of clusters occurs at level of 0.5 in the hierarchy of partitions.