Cluster analysis and mathematical programming

Given a set of entities, Cluster Analysis aims at finding subsets, called clusters, which are homogeneous and/or well separated. As many types of clustering and criteria for homogeneity or separation are of interest, this is a vast field. A survey is given from a mathematical programming viewpoint. Steps of a clustering study, types of clustering and criteria are discussed. Then algorithms for hierarchical, partitioning, sequential, and additive clustering are studied. Emphasis is on solution methods, i.e., dynamic programming, graph theoretical algorithms, branch-and-bound, cutting planes, column generation and heuristics. Research supported by ONR grant N00014-95-1-0917, FCAR grant 95-ER-1048 and NSERC grants GP0105574 and GP0036426. The authors thank Olivier Gascuel and an anonymous referee for insightful remarks.     

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.     

Boole''s conditions of possible experience and reasoning under uncertainty

Consider a set of logical sentences together with probabilities that they are true. These probabilities must satisfy certain conditions for this system to be consistent. It is shown that an analytical form of these conditions can be obtained by enumerating the extreme rays of a polyhedron. We also consider the cases when (i) intervals of probabilities are given, instead of single values; and (ii) best lower and upper bounds on the probability of an additional logical sentence to be true are sought. Enumeration of vertices and extreme rays is used. Each vertex defines a finear expression and the maximum (minimum) of these defines a best possible lower (upper) bound on the probability of the additional logical sentence to be true. Each extreme ray leads to a constraint on the probabilities assigned to the initial set of logical sentences. Redundancy in these expressions is studied. Illustrations are provided in the domain of reasoning under uncertainty.     

A Simplified Convergence Proof for the Cone Partitioning Algorithm

We present a new convergence result for the cone partitioning algorithm with a pure -subdivision strategy, for the minimization of a quasiconcave function over a polytope. It is shown that the algorithm is finite when -optimal solution with > 0 are looked for, and that any cluster point of the points generated by the algorithm is an optimal solution in the case = 0. This result improves on the one given previously by the authors, its proof is simpler and relies more directly on a new class of hyperplanes and its associated simplicial lower bound.     

Global optimization of univariate Lipschitz functions: I. Survey and properties

We consider the following global optimization problems for a univariate Lipschitz functionf defined on an interval [a, b]: Problem P: find a globally optimal value off and a corresponding point; Problem P: find a globally-optimal value off and a corresponding point; Problem Q: localize all globally optimal points; Problem Q: find a set of disjoint subintervals of small length whose union contains all globally optimal points; Problem Q: find a set of disjoint subintervals containing only points with a globally-optimal value and whose union contains all globally optimal points.We present necessary conditions onf for finite convergence in Problem P and Problem Q, recall the concepts necessary for a worst-case and an empirical study of algorithms (i.e., those ofpassive and ofbest possible algorithms), summarize and discuss algorithms of Evtushenko, Piyavskii-Shubert, Timonov, Schoen, Galperin, Shen and Zhu, presenting them in a simplified and uniform way, in a high-level computer language. We address in particular the problems of using an approximation for the Lipschitz constant, reducing as much as possible the expected length of the region of indeterminacy which contains all globally optimal points and avoiding remaining subintervals without points with a globally-optimal value. New algorithms for Problems P and Q and an extensive computational comparison of algorithms are presented in a companion paper.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426 and FCAR grant 89EQ4144. We thank N. Paradis for drawing some of the figures.     

On the Convergence of Cone Splitting Algorithms with ω-Subdivisions

We present a convergence proof of the Tuy cone splitting algorithm with a pure -subdivision strategy for the minimization of a concave function over a polytope. The key idea of the convergence proof is to associate with the current hyperplane a new hyperplane that supports the whole polytope instead of only the portion of it contained in the current cone. A branch-and-bound variant of the algorithm is also discussed.