Optimally Adjusted Mixture Sampling and Locally Weighted Histogram Analysis

Consider the two problems of simulating observations and estimating expectations and normalizing constants for multiple distributions. First, we present a self-adjusted mixture sampling method, which accommodates both adaptive serial tempering and a generalized Wang–Landau algorithm. The set of distributions are combined into a labeled mixture, with the mixture weights depending on the initial estimates of log normalizing constants (or free energies). Then, observations are generated by Markov transitions, and free energy estimates are adjusted online by stochastic approximation. We propose two stochastic approximation schemes by Rao–Blackwellization of the scheme commonly used, and derive the optimal choice of a gain matrix, resulting in the minimum asymptotic variance for free energy estimation, in a simple and feasible form. Second, we develop an offline method, locally weighted histogram analysis, for estimating free energies and expectations, using all the simulated data from multiple distributions by either self-adjusted mixture sampling or other sampling algorithms. This method can be computationally much faster, with little sacrifice of statistical efficiency, than a global method currently used, especially when a large number of distributions are involved. We provide both theoretical results and numerical studies to demonstrate the advantages of the proposed methods.     

A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.     

Finding the K best policies in a finite-horizon Markov decision process

Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best deterministic Markov policies. That is, we are interested in ranking the first K deterministic Markov policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.     

Consistance d'un estimateur de minimum de variance étendue

We consider a generalization of the criterion minimized by the K-means algorithm, where a neighborhood structure is used in the calculus of the variance. Such a tool is used, for example with Kohonen maps, to measure the quality of the quantification preserving the neighborhood relationships. If we assume that the parameter vector is in a compact Euclidean space and all its components are separated by a minimal distance, we show the strong consistency of the set of parameters almost realizing the minimum of the empirical extended variance. To cite this article: J. Rynkiewicz, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

A Generic Global Optimization Algorithm for the Chemical and Phase Equilibrium Problem

This paper addresses the problem of finding the number, K, of phases present at equilibrium and their composition, in a chemical mixture of n _s substances. This corresponds to the global minimum of the Gibbs free energy of the system, subject to constraints representing m _b independent conserved quantities, where m _b=n _s when no reaction is possible and m _b n _e +1 when reaction is possible and n _e is the number of elements present. After surveying previous work in the field and pointing out the main issues, we extend the necessary and sufficient condition for global optimality based on the reaction tangent-plane criterion, to the case involving different thermodynamical models (multiple phase classes). We then present an algorithmic approach that reduces this global optimization problem (involving a search space of m _b(n _s-1) dimensions) to a finite sequence of local optimization steps inK(n _s-1) -space, K m _b, and global optimization steps in (n _s-1)-space. The global step uses the tangent-plane criterion to determine whether the current solution is optimal, and, if it is not, it finds an improved feasible solution either with the same number of phases or with one added phase. The global step also determines what class of phase (e.g. liquid or vapour) is to be added, if any phase is to be added. Given a local minimization procedure returning a Kuhn–Tucker point and a global optimization procedure (for a lower-dimensional search space) returning a global minimum, the algorithm is proved to converge to a global minimum in a finite number of the above local and global steps. The theory is supported by encouraging computational results.     

Geometric criteria for tame ramification

We prove an A’Campo type formula for the tame monodromy zeta function of a smooth and proper variety over a discretely valued field K. As a first application, we relate the orders of the tame monodromy eigenvalues on the ?-adic cohomology of a K-curve to the geometry of a relatively minimal sncd-model, and we show that the semi-stable reduction theorem and Saito’s criterion for cohomological tameness are immediate consequences of this result. As a second application, we compute the error term in the trace formula for smooth and proper K-varieties. We see that the validity of the trace formula would imply a partial generalization of Saito’s criterion to arbitrary dimension.     

Competitive clustering algorithms based on ultrametric properties

We propose in this paper two new competitive unsupervised clustering algorithms: the first algorithm deals with ultrametric data, it has a computational cost of O(n). The second algorithm has two strong features: it is fast and flexible on the processed data type as well as in terms of precision. The second algorithm has a computational cost, in the worst case, of O(n²), and in the average case, of O(n). These complexities are due to exploitation of ultrametric distance properties. In the first method, we use the order induced by an ultrametric in a given space to demonstrate how we can explore quickly data proximity. In the second method, we create an ultrametric space from a sample data, chosen uniformly at random, in order to obtain a global view of proximities in the data set according to the similarity criterion. Then, we use this proximity profile to cluster the global set. We present an example of our algorithms and compare their results with those of a classic clustering method.     

Easy and hard bottleneck location problems

We consider a bottleneck location problem on a graph and present an efficient (polynomial time) algorithm for solving it. The problem involve the location of K noxious facilities that are to be placed as far as possilbe from the other facilities, and the objective is to maximize the minimum distance from the noxious facilities to the others. We then show that two other bottleneck (min-max) location problems, finding K-centers and absolute K-centers of a graph appear to be very difficult to solve even for reasonably good approximate solutions.     

Robust Parametric Classification and Variable Selection by a Minimum Distance Criterion

We investigate a robust penalized logistic regression algorithm based on a minimum distance criterion. Influential outliers are often associated with the explosion of parameter vector estimates, but in the context of standard logistic regression, the bias due to outliers always causes the parameter vector to implode, that is, shrink toward the zero vector. Thus, using LASSO-like penalties to perform variable selection in the presence of outliers can result in missed detections of relevant covariates. We show that by choosing a minimum distance criterion together with an elastic net penalty, we can simultaneously find a parsimonious model and avoid estimation implosion even in the presence of many outliers in the important small n large p situation. Minimizing the penalized minimum distance criterion is a challenging problem due to its nonconvexity. To meet the challenge, we develop a simple and efficient MM (majorization–minimization) algorithm that can be adapted gracefully to the small n large p context. Performance of our algorithm is evaluated on simulated and real datasets. This article has supplementary materials available online.     

Clustering via finite nonparametric ICA mixture models

We propose a novel extension of nonparametric multivariate finite mixture models by dropping the standard conditional independence assumption and incorporating the independent component analysis (ICA) structure instead. This innovation extends nonparametric mixture model estimation methods to situations in which conditional independence, a necessary assumption for the unique identifiability of the parameters in such models, is clearly violated. We formulate an objective function in terms of penalized smoothed Kullback–Leibler distance and introduce the nonlinear smoothed majorization-minimization independent component analysis algorithm for optimizing this function and estimating the model parameters. Our algorithm does not require any labeled observations a priori; it may be used for fully unsupervised clustering problems in a multivariate setting. We have implemented a practical version of this algorithm, which utilizes the FastICA algorithm, in the R package icamix. We illustrate this new methodology using several applications in unsupervised learning and image processing.

     

The decompositions of line graphs,middle graphs and total graphs of complete graphs into forests

We construct decompositions of L(K_n), M(K_n) and T(K_n) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs.     

Solving matching problems with linear programming

In this paper we describe an implementation of a cutting plane algorithm for the perfect matching problem which is based on the simplex method. The algorithm has the following features:

-It works on very sparse subgraphs ofK _n which are determined heuristically, global optimality is checked using the reduced cost criterion.

-Cutting plane recognition is usually accomplished by heuristics. Only if these fail, the Padberg-Rao procedure is invoked to guarantee finite convergence.

Our computational study shows that—on the average—very few variables and very few cutting planes suffice to find a globally optimal solution. We could solve this way matching problems on complete graphs with up to 1000 nodes. Moreover, it turned out that our cutting plane algorithm is competitive with the fast combinatorial matching algorithms known to date.     

Nonnegatively curved homogeneous metrics obtained by scaling fibers of submersions

We consider invariant Riemannian metrics on compact homogeneous spaces G/H where an intermediate subgroup K between G and H exists, so that the homogeneous space G/H is the total space of a Riemannian submersion. We study the question as to whether enlarging the fibers of the submersion by a constant scaling factor retains the nonnegative curvature in the case that the deformation starts at a normal homogeneous metric. We classify triples of groups (H, K, G) where nonnegative curvature is maintained for small deformations, using a criterion proved by Schwachhöfer and Tapp. We obtain a complete classification in case the subgroup H has full rank and an almost complete classification in the case of regular subgroups.     

The KP hierarchy, branched covers, and triangulations

The KP hierarchy is a completely integrable system of quadratic, partial differential equations that generalizes the KdV hierarchy. A linear combination of Schur functions is a solution to the KP hierarchy if and only if its coefficients satisfy the Plücker relations from geometry. We give a solution to the Plücker relations involving products of variables marking contents for a partition, and thus give a new proof of a content product solution to the KP hierarchy, previously given by Orlov and Shcherbin. In our main result, we specialize this content product solution to prove that the generating series for a general class of transitive ordered factorizations in the symmetric group satisfies the KP hierarchy. These factorizations appear in geometry as encodings of branched covers, and thus by specializing our transitive factorization result, we are able to prove that the generating series for two classes of branched covers satisfies the KP hierarchy. For the first of these, the double Hurwitz series, this result has been previously given by Okounkov. The second of these, that we call the m-hypermap series, contains the double Hurwitz series polynomially, as the leading coefficient in m. The m-hypermap series also specializes further, first to the series for hypermaps and then to the series for maps, both in an orientable surface. For the latter series, we apply one of the KP equations to obtain a new and remarkably simple recurrence for triangulations in a surface of given genus, with a given number of faces. This recurrence leads to explicit asymptotics for the number of triangulations with given genus and number of faces, in recent work by Bender, Gao and Richmond.     

Differential Algebras with Banach-Algebra Coefficients II: The Operator Cross-Ratio Tau-Function and the Schwarzian Derivative

Several features of an analytic (infinite-dimensional) Grassmannian of (commensurable) subspaces of a Hilbert space were developed in the context of integrable PDEs (KP hierarchy). We extended some of those features when polarized separable Hilbert spaces are generalized to a class of polarized Hilbert modules and then consider the classical Baker and τ-functions as operator-valued. Following from Part I we produce a pre-determinant structure for a class of τ-functions defined in the setting of the similarity class of projections of a certain Banach *-algebra. This structure is explicitly derived from the transition map of a corresponding principal bundle. The determinant of this map leads to an operator τ-function. We extend to this setting the operator cross-ratio which had previously been used to produce the scalar-valued τ-function, as well as the associated notion of a Schwarzian derivative along curves inside the space of similarity classes of a given projection. We link directly this cross-ratio with Fay’s trisecant identity for the τ-function. By restriction to the image of the Krichever map, we use the Schwarzian to introduce the notion of an operator-valued projective structure on a compact Riemann surface: this allows a deformation inside the Grassmannian (as it varies its complex structure). Lastly, we use our identification of the Jacobian of the Riemann surface in terms of extensions of the Burchnall–Chaundy C*-algebra (Part I) provides a link to the study of the KP hierarchy.     

Galois structure and de Rham invariants of elliptic curves

Let K be a number field with ring of integers OK. Suppose a finite group G acts numerically tamely on a regular scheme X over OK. One can then define a de Rham invariant class in the class group Cl(OK[G]), which is a refined Euler characteristic of the de Rham complex of X. Our results concern the classification of numerically tame actions and the de Rham invariant classes. We first describe how all Galois étale G-covers of a K-variety may be built up from finite Galois extensions of K and from geometric covers. When X is a curve of positive genus, we show that a given étale action of G on X extends to a numerically tame action on a regular model if and only if this is possible on the minimal model. Finally, we characterize the classes in Cl(OK[G]) which are realizable as the de Rham invariants for minimal models of elliptic curves when G has prime order.     

On the Hierarchical Chinese Postman Problem with linear ordered classes

The Hierarchical Chinese Postman Problem (HCPP) is a Chinese Postman Problem with the arcs partitioned into priority classes ordered by a precedence relation. The problem under the sum criterion is polynomially solvable if the ordering is linear and each class is connected. For a known HCPP algorithm we give an O(n) improvement (n the number of nodes) leading to O(kn⁴) with k the number of classes. The same complexity appears to hold for the lexicographic criterion which minimises the costs of the first priority class, then the costs of the second class, etc. The notions of servicing and traversing related to arcs, allow for more real life models of arc routing problems. We show how to incorporate these notions in known algorithms, without increasing the complexity.     

Embedding problems with local conditions and the admissibility of finite groups

Let K be a field of characteristic p > 0, which has infinitely many discrete valuations. We show that every finite embedding problem for Gal(K) with finitely many prescribed local conditions, whose kernel is a p-group, is properly solvable. We then apply this result in studying the admissibility of finite groups over global fields of positive characteristic. We also give another proof for a result of Sonn.     

The first <Emphasis Type="Italic">K</Emphasis> minimum cost paths in a time-schedule network

The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.     

The graded Grothendieck group and the classification of Leavitt path algebras

This paper is an attempt to show that, parallel to Elliott’s classification of AF C*-algebras by means of K-theory, the graded K ₀-group classifies Leavitt path algebras completely. In this direction, we prove this claim at two extremes, namely, for the class of acyclic graphs (graphs with no cycles) and multi-headed comets or rose graphs (graphs in which each head is connected to a cycle or to a collection of loops), or a mixture of these graphs (i.e., polycephaly graphs).