Parameter spaces of separating hyperplanes

Every pair of relatively disjoint polytopes is dual to the parameter space of all their separating hyperplanes, which is also a polytope. For a polytope whose interior is disjoint from the relative interior of another polytope, the parameter space of all separating hyperplanes is a polytope of the same dimension. One face of this parameter space parametrizes the separating hyperplanes that also simultaneously support both polytopes. A separating hyperplane corresponds to a vertex of this face if and only if no other hyperplanes support the polytopes at the same intersection points. If all the vertices of the polytopes have all their coordinates in an ordered field, then the same results and their proofs hold with the same ordered field.     

Adjacency on the order polytope with applications to the theory of fuzzy measures

In this paper we study the adjacency structure of the order polytope of a poset. For a given poset, we determine whether two vertices in the corresponding order polytope are adjacent. This is done through filters in the original poset. We also prove that checking adjacency between two vertices can be done in quadratic time on the number of elements of the poset. As particular cases of order polytopes, we recover the adjacency structure of the set of fuzzy measures and obtain it for the set of p-symmetric measures for a given indifference partition; moreover, we show that the set of p-symmetric measures can be seen as the order polytope of a quotient set of the poset leading to fuzzy measures. From this property, we obtain the diameter of the set of p-symmetric measures. Finally, considering the set of p-symmetric measures as the order polytope of a direct product of chains, we obtain some other properties of these measures, as bounds on the volume and the number of vertices on certain cases.     

Hard Lefschetz theorem for nonrational polytopes

The Hard Lefschetz theorem is known to hold for the intersection cohomology of the toric variety associated to a rational convex polytope. One can construct the intersection cohomology combinatorially from the polytope, hence it is well defined even for nonrational polytopes when there is no variety associated to it. We prove the Hard Lefschetz theorem for the intersection cohomology of a general polytope.     

Local linear convergence of approximate projections onto regularized sets

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.     

A refinement of multivariate value set bounds

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials.In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.     

Linear models for the approximate solution of the problem of packing equal circles into a given domain

The linear models for the approximate solution of the problem of packing the maximum number of equal circles of the given radius into a given closed bounded domain G are proposed. We construct a grid in G; the nodes of this grid form a finite set of points T, and it is assumed that the centers of circles to be packed can be placed only at the points of T. The packing problems of equal circles with the centers at the points of T are reduced to 0–1 linear programming problems. A heuristic algorithm for solving the packing problems based on linear models is proposed. This algorithm makes it possible to solve packing problems for arbitrary connected closed bounded domains independently of their shape in a unified manner. Numerical results demonstrating the effectiveness of this approach are presented.     

A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

Complexity analysis of the analytic center cutting plane method that uses multiple cuts

We analyze the complexity of the analytic center cutting plane or column generation algorithm for solving general convex problems defined by a separation oracle. The oracle is called at the analytic center of a polytope, which contains a solution set and is given by the intersection of the linear inequalities previously generated from the oracle. If the center is not in the solution set, separating hyperplanes will be placed through the center to shrink the containing polytope. While the complexity result has been recently established for the algorithm when one cutting plane is placed in each iteration, the result remains open when multiple cuts are added. Moreover, adding multiple cuts actually is a key to practical effectiveness in solving many problems and it presents theoretical difficulties in analyzing cutting plane methods. In this paper, we show that the analytic center cutting plane algorithm, with multiple cuts added in each iteration, still is a fully polynomial approximation algorithm. The research of the author is supported by NSF grant DDM-9207347, an Iowa Business School Summer Grant, and a University of Iowa Obermann Fellowship.     

Intersection of triadic Cantor sets with their translates— I. Fundamental properties

Motivated by Mandelbrot's [The Fractal Geometry of Nature, Freeman, San Francisco, 1983] idea of referring to lacunarity of Cantor sets in terms of departure from translation invariance, we study the properties of these translation sets and show how they can be used for a classification purpose. This first paper of a series of two will be devoted to set up the fundamental properties of Hausdorff measures of those intersection sets. Using the triadic expansion of the shifting number, we determine the fractal structure of intersection of triadic Cantor sets with their translates. We found that the Hausdorff measure of these sets forms a discrete spectrum whose non-zero values come only from those shifting numbers with a finite triadic expansion. We characterize this set of shifting numbers by giving a partition expression of it and the steps of its construction from a fundamental root set. Finally, we prove that intersection of Cantor sets with their translates verify a measure-conservation law with scales. The second paper will take advantage of the properties exposed here in order to utilize them in a classification context. Mainly, it will deal with the use of the discrete spectrum of measures to distinguish two Cantor-like sets of the same fractal dimension.     

Best Partial Covering of a Convex Domain by Congruent Circles of a Given Total Area

Generalizing results of L. Fejes Toth [3], [5], we prove the following theorem. Let R be a convex domain of area |R| and let S be a finite family of at least two congruent circles of total area t. Then for the area |F| of the part of R covered by the circles of S, the inequality |F|< tf(|R|/t) holds, where f(x) is the area of the intersection of a circle of unit area and a regular hexagon of area x concentric with the circle.     

k-Moments of distances between centers of Ford circles

In this paper, we investigate a problem on the distribution of Ford circles, which concerns moments of distances between centers of these circles that lie above a given horizontal line.     

Some geometric properties of metric ultraproducts of finite simple groups

In this article we prove some previously announced results about metric ultraproducts of finite simple groups. We show that any non-discrete metric ultraproduct of alternating or special linear groups is a geodesic metric space. For more general non-discrete metric ultraproducts of finite simple groups, we are able to establish path-connectedness. As expected, these global properties reflect asymptotic properties of various families of finite simple groups.     

On the finite termination of the Douglas-Rachford method for the convex feasibility problem

In this paper we apply the Douglas–Rachford (DR) method to solve the problem of finding a point in the intersection of the interior of a closed convex cone and a closed convex set in an infinite-dimensional Hilbert space. For this purpose, we propose two variants of the DR method which can find a point in the intersection in a finite number of iterations. In order to analyse the finite termination of the methods, we use some properties of the metric projection and a result regarding the rate of convergence of fixed point iterations. As applications of the results, we propose the methods for solving the conic and semidefinite feasibility problems, which terminate at a solution in a finite number of iterations.     

Partitions of a Polytope and Mappings of a Point Set to Facets

Three theorems of this paper generalize previous results of the author on conjectures of A. Bezdek and V.V. Proizvolov. They show the existence of mappings from a given point set to the set of facets of a given polytope that satistfy some special conditions. Developing the same technique, some results on convex polytope partitions are presented, two of them dealing with partitions with prescribed measures of parts. Then we prove a corollary on the existence of a possibly nonconvex polytope with a given set of vertices, containing given points in its interior. We also consider problems of the following type: find an assignment of vectors from a given set to the parts of a given convex partition of ℝⁿ so that the shifts of the parts by their corresponding vectors either do not intersect by interior points or cover ℝⁿ     

Regular simple games

Using Kelley's intersection number (and a variant of it) we define two classes of simple games, the regular and the strongly regular games. We show that the strongly regular games are those in which the set of winning coalitions and the set of losing coalitions can be strictly separated by a finitely additive probability measure. This, in particular, provides a combinatorial characterization for the class of finite weighted majority games within the finite simple games. We also prove that regular games have some nice properties and show that the finite regular games are exactly those simple games which are uniquely determined by their counting vector. This, in particular, generalizes a result of Chow and Lapidot.     

Separating invariants and finite reflection groups

A separating algebra is, roughly speaking, a subalgebra of the ring of invariants whose elements distinguish between any two orbits that can be distinguished using invariants. In this paper, we introduce a geometric notion of separating algebra. This allows us to prove that only groups generated by reflections may have polynomial separating algebras, and only groups generated by bireflections may have complete intersection separating algebras.     

Apollonian circle packings: number theory

Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. It is possible for every circle in such a packing to have integer radius of curvature, and we call such a packing an integral Apollonian circle packing. This paper studies number-theoretic properties of the set of integer curvatures appearing in such packings. Each Descartes quadruple of four tangent circles in the packing gives an integer solution to the Descartes equation, which relates the radii of curvature of four mutually tangent circles: . Each integral Apollonian circle packing is classified by a certain root quadruple of integers that satisfies the Descartes equation, and that corresponds to a particular quadruple of circles appearing in the packing. We express the number of root quadruples with fixed minimal element −n as a class number, and give an exact formula for it. We study which integers occur in a given integer packing, and determine congruence restrictions which sometimes apply. We present evidence suggesting that the set of integer radii of curvatures that appear in an integral Apollonian circle packing has positive density, and in fact represents all sufficiently large integers not excluded by congruence conditions. Finally, we discuss asymptotic properties of the set of curvatures obtained as the packing is recursively constructed from a root quadruple.     

Retrieving the Bingham model from a bi-viscous model: Some explanatory remarks

In this note we prove some analytical results on the Bingham model. In particular we show how to derive some constitutive and kinematical properties through a limit procedure in which the visco-plastic model is retrieved from a linear bi-viscous model. We also prove that, assuming a no-slip condition at the interface separating the two viscous fluids, no source of entropy can be present on such interface.