Convex polyhedra of doubly stochastic matrices—IV

Basic geometrical properties of general convex polyhedra of doubly stochastic matrices are investigated. The faces of such polyhedra are characterized, and their dimensions and facets are determined. A connection between bounded faces of doubly stochastic polyhedra and faces of transportation polytopes is established, and it is shown that there exists an absolute bound for the number of extreme points of d-dimensional bounded faces of these polyhedra.     

Divisible points of compact convex sets

By associating with an affine dependence the resultant of a related probability measure, we are able to define the set ofdivisible points, D(K), of a compact convex setK. Some general properties ofD(K) are discussed, and its equivalence with a set recently introduced by Reay for convex polytopes demonstrated. For polytopes,D(K) is a continuous image of a projective space. A conjecture concerningD(K) is settled affirmatively for cubes.     

Barycentric coordinates for convex sets

In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in the discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations.      

Convex and Linear Orientations of Polytopal Graphs

This paper examines directed graphs related to convex polytopes. For each fixed d -polytope and any acyclic orientation of its graph, we prove there exist both convex and concave functions that induce the given orientation. For each combinatorial class of 3 -polytopes, we provide a good characterization of the orientations that are induced by an affine function acting on some member of the class. Received March 10, 1999, and in revised form May 30, 1999. Online publication May 16, 2000.     

Steered sequential projections for the inconsistent convex feasibility problem

We study a steered sequential gradient algorithm which minimizes the sum of convex functions by proceeding cyclically in the directions of the negative gradients of the functions and using steered step-sizes. This algorithm is applied to the convex feasibility problem by minimizing a proximity function which measures the sum of the Bregman distances to the members of the family of convex sets. The resulting algorithm is a new steered sequential Bregman projection method which generates sequences that converge if they are bounded, regardless of whether the convex feasibility problem is or is not consistent. For orthogonal projections and affine sets the boundedness condition is always fulfilled.     

Unital affine semigroups

Affine semigroups are convex sets on which there exists an associative binary operation which is affine separately in either variable. They were introduced by Cohen and Collins in 1959. We look at examples of affine semigroups which are of interest to matrix and operator theory and we prove some new results on the extreme points and the absorbing elements of certain types of affine semigroups. Most notably we improve a result of Wendel that every invertible element in a compact affine semigroup is extreme by extending this result to linearly bounded affine semigroups.     

On the strong CE-property of convex sets

We consider a class of convex bounded subsets of a separable Banach space. This class includes all convex compact sets as well as some noncompact sets important in applications. For sets in this class, we obtain a simple criterion for the strong CE-property, i.e., the property that the convex closure of any continuous bounded function is a continuous bounded function. Some results are obtained concerning the extension of functions defined at the extreme points of a set in this class to convex or concave functions defined on the entire set with preservation of closedness and continuity. Some applications of the results in quantum information theory are considered.     

Minimizing the sum of a convex function and the product of two affine functions over a convex set

An efficient branch-and-bound algorithm for minimizing the sum of a convex function and the product of two affine functions over a convex set is proposed. The branching takes place in an interval of R the bounding is a relaxation     

Epigraphical and Uniform Convergence of Convex Functions

We examine when a sequence of lsc convex functions on a Banach space converges uniformly on bounded sets (resp. compact sets) provided it converges Attouch-Wets (resp. Painlevé-Kuratowski). We also obtain related results for pointwise convergence and uniform convergence on weakly compact sets. Some known results concerning the convergence of sequences of linear functionals are shown to also hold for lsc convex functions. For example, a sequence of lsc convex functions converges uniformly on bounded sets to a continuous affine function provided that the convergence is uniform on weakly compact sets and the space does not contain an isomorphic copy of .

     

On the Conjecture by Demyanov–Ryabova in Converting Finite Exhausters

The Demyanov–Ryabova conjecture is a geometric problem originating from duality relations between nonconvex objects. Given a finite collection of polytopes, one obtains its dual collection as convex hulls of the maximal facet of sets in the original collection, for each direction in the space (thus constructing upper convex representations of positively homogeneous functions from lower ones and, vice versa, via Minkowski duality). It is conjectured that an iterative application of this conversion procedure to finite families of polytopes results in a cycle of length at most two. We prove a special case of the conjecture assuming an affine independence condition on the vertices of polytopes in the collection. We also obtain a purely combinatorial reformulation of the conjecture.     

On the convergence of the coordinate descent method for convex differentiable minimization

The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.This work was partially supported by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171, by the National Science Foundation, Grant No. ECS-8519058, and by the Science and Engineering Research Board of McMaster University.     

Lattice-free polytopes and their diameter

A convex polytope in real Euclidean space islattice-free if it intersects some lattice in space exactly in its vertex set. Lattice-free polytopes form a large and computationally hard class, and arise in many combinatorial and algorithmic contexts. In this article, affine and combinatorial properties of such polytopes are studied. First, bounds on some invariants, such as the diameter and layer-number, are given. It is shown that the diameter of ad-dimensional lattice-free polytope isO(d ³). A bound ofO(nd+d ³) on the diameter of ad-polytope withn facets is deduced for a large class of integer polytopes. Second, Delaunay polytopes and [0, 1]-polytopes, which form major subclasses of lattice-free polytopes, are considered. It is shown that, up to affine equivalence, for anyd≥3 there are infinitely manyd-dimensional lattice-free polytopes but only finitely many Delaunay and [0, 1]-polytopes. Combinatorial-types of lattice-free polytopes are discussed, and the inclusion relations among the subclasses above are examined. It is shown that the classes of combinatorial-types of Delaunay polytopes and [0,1]-polytopes are mutually incomparable starting in dimension six, and that both are strictly contained in the class of combinatorial-types of all lattice-free polytopes. This research was supported by DIMACS—the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University.     

Stability Constants in Linear Spaces

We investigate the stability constants of convex sets in linear spaces. We prove that the stability constants of affinity and of the Jensen equation are of the same order of magnitude for every convex set in arbitrary linear spaces, even for functions mapping into an arbitrary Banach space. We also show that the second Whitney constant corresponding to the bounded functions equals half of the stability constant of the Jensen equation whenever the latter is finite. We show that if a convex set contains arbitrarily long segments in every direction, then its Jensen and Whitney constants are uniformly bounded. We prove a result that reduces the investigation of the stability constants to the case when the underlying set is the unit ball of a Banach space. As an application we prove that if D is convex and every δ-Jensen function on D differs from a Jensen function by a bounded function, then the stability constants of D are finite.     

Smooth approximation of convex functions in Banach spaces

This paper shows that every extended-real-valued lower semi-continuous proper (respectively Lipschitzian) convex function defined on an Asplund space can be represented as the point-wise limit (respectively uniform limit on every bounded set) of a sequence of Lipschitzian convex functions which are locally affine (hence, C^∞) at all points of a dense open subset; and shows an analogous for w^∗-lower semi-continuous proper (respectively Lipschitzian) convex functions defined on dual spaces whose pre-duals have the Radon-Nikodym property.     

A parametric smooth variational principle and support properties of convex sets and functions

We show a modified version of Georgiev's parametric smooth variational principle, and we use it to derive new support properties of convex functions and sets. For example, our results imply that, for any proper l.s.c. convex nonaffine function h on a Banach space Y, D(∂h) is pathwise connected and R(∂h) has cardinality at least continuum. If, in addition, Y is Fréchet-smooth renormable, then R(∂h) is pathwise connected and locally pathwise connected. Analogous properties for support points and normalized support functionals of closed convex sets are proved; they extend and strengthen recent results proved by C. De Bernardi and the author for bounded closed convex sets.     

On approximation of affine Baire-one functions

It is known (G. Choquet, G. Mokobodzki) that a Baire-one affine function on a compact convex set satisfies the barycentric formula and can be expressed as a pointwise limit of a sequence of continuous affine functions. Moreover, the space of Baire-one affine functions is uniformly closed. The aim of this paper is to discuss to what extent analogous properties are true in the context of general function spaces. In particular, we investigate the function spaceH(U), consisting of the functions continuous on the closure of a bounded open setU⊂ℝ ^m and harmonic onU, which has been extensively studied in potential theory. We demonstrate that the barycentric formula does not hold for the spaceB ₁ ^b (H(U)) of bounded functions which are pointwise limits of functions from the spaceH(U) and thatB ₁ ^b (H(U)) is not uniformly closed. On the other hand, every Baire-oneH(U)-affine function (in particular a solution of the generalized Dirichlet problem for continuous boundary data) is a pointwise limit of a bounded sequence of functions belonging toH(U). It turns out that such a situation always occurs for simplicial spaces whereas it is not the case for general function spaces. The paper provides several characterizations of those Baire-one functions which can be approximated pointwise by bounded sequences of elements of a given function space. Research supported in part by grants GA ČR No. 201/00/0767 from the Grant Agency of the Czech Republic, GA UK 165/99 from the Grant Agency of Charles University, and in part by grant number MSM 113200007 from the Czech Ministry of Education.     

The Dirichlet problem for Baire-one functions

Let X be a compact convex set and let ext X stand for the set of all extreme points of X. We characterize those bounded function defined on ext X which can be extended to an affine Baire-one function on the whole set X.     

Alcoved Polytopes,I

The aim of this paper is to study alcoved polytopes, which are polytopes arising from affine Coxeter arrangements. This class of convex polytopes includes many classical polytopes, for example, the hypersimplices. We compare two constructions of triangulations of hypersimplices due to Stanley and Sturmfels and explain them in terms of alcoved polytopes. We study triangulations of alcoved polytopes, the adjacency graphs of these triangulations, and give a combinatorial formula for volumes of these polytopes. In particular, we study a class of matroid polytopes, which we call the multi-hypersimplices.     

On the minimum problem for nonconvex, multiple integrals of product type

We consider the problem of minimizing multiple integrals of product type, i.e. where is a bounded, open set in , is a possibly nonconvex, lower semicontinuous function with p-growth at infinity for some and the boundary datum is in (or simply in if ). Assuming that the convex envelope off is affine on each connected component of the set , we prove attainment for () for every continuous, positively bounded below function g such that (i) every point is squeezed between two intervals where g is monotone and (ii) g has no strict local minima. This shows in particular that the class of coefficents g that yield existence to () is dense in the space of continuous, positive functions on . We present examples which show that these conditions for attainment are essentially sharp. Received April 12, 2000 / Accepted May 9, 2000 / Published online November 9, 2000