A generalized localization theorem and geometric inequalities for convex bodies

In this article, we generalize a localization theorem of Lovász and Simonovits [Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms 4-4 (1993) 359-412] which is an important tool to prove dimension-free functional inequalities for log-concave measures. In a previous paper [Fradelizi and Guédon, The extreme points of subsets of s-concave probabilities and a geometric localization theorem, Discrete Comput. Geom. 31 (2004) 327-335], we proved that the localization may be deduced from a suitable application of Krein-Milman's theorem to a subset of log-concave probabilities satisfying one linear constraint and from the determination of the extreme points of its convex hull. Here, we generalize this result to more constraints, give some necessary conditions satisfied by such extreme points and explain how it may be understood as a generalized localization theorem. Finally, using this new localization theorem, we solve an open question on the comparison of the volume of sections of non-symmetric convex bodies in Rⁿ by hyperplanes. A surprising feature of the result is that the extremal case in this geometric inequality is reached by an unusual convex set that we manage to identify.     

Slow decay of Gibbs measures with heavy tails

We consider Glauber dynamics reversible with respect to Gibbs measures with heavy tails in the case when spins are unbounded. The interactions are bounded and of finite range. The self-potential enters into two classes of measures, κ-concave probability measures and sub-exponential laws, for which it is known that no exponential decay can occur. Using coercive inequalities we prove that, for κ-concave probability measures, the associated infinite volume semi-group decays to equilibrium polynomially and stretched exponentially for sub-exponential laws. This improves and extends previous results by Bobkov and Zegarlinski.     

Affine isoperimetric inequalities in the functional Orlicz–Brunn–Minkowski theory

In this paper, we develop a basic theory of Orlicz affine and geominimal surface areas for convex and s-concave functions. We prove some basic properties for these newly introduced functional affine invariants and establish related functional affine isoperimetric inequalities as well as functional Santaló type inequalities.     

Divergence for s-concave and log concave functions

We prove new entropy inequalities for log concave and s-concave functions that strengthen and generalize recently established reverse log Sobolev and Poincaré inequalities for such functions. This leads naturally to the concept of f-divergence and, in particular, relative entropy for s-concave and log concave functions. We establish their basic properties, among them the affine invariant valuation property. Applications are given in the theory of convex bodies.     

Exact order of Hoffman’s error bounds for elliptic quadratic inequalities derived from vector-valued Chebyshev approximation

In this paper, we introduce the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities. Elliptic quadratic inequalities are closely related to Chebyshev approximation of vector-valued functions (including complex-valued functions). The set of Chebyshev approximations of a vector-valued function defined on a finite set is shown to be Hausdorff strongly unique of order exactly 2 ^s for some nonnegative integer s. As a consequence, the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities is exactly 2 ^-s for some nonnegative integer s. The integer s, called the order of deficiency (which is computable), quantifies how much the Abadie constraint qualification is violated by the elliptic quadratic inequalities. Received: April 15, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

The geometry of p-convex intersection bodies

Busemann's theorem states that the intersection body of an origin-symmetric convex body is also convex. In this paper we provide a version of Busemann's theorem for p-convex bodies. We show that the intersection body of a p-convex body is q-convex for certain q. Furthermore, we discuss the sharpness of the previous result by constructing an appropriate example. This example is also used to show that IK, the intersection body of K, can be much farther away from the Euclidean ball than K. Finally, we extend these theorems to some general measure spaces with log-concave and s-concave measures.     

Invariant measures of minimal post-critical sets of logistic maps

We construct logistic maps whose restriction to the ω-limit set of its critical point is a minimal Cantor system having a prescribed number of distinct ergodic and invariant probability measures. In fact, we show that every metrizable Choquet simplex whose set of extreme points is compact and totally disconnected can be realized as the set of invariant probability measures of a minimal Cantor system corresponding to the restriction of a logistic map to the ω-limit set of its critical point. Furthermore, we show that such a logistic map f can be taken so that each such invariant measure has zero Lyapunov exponent and is an equilibrium state of f for the potential −ln |f′|.     

Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.     

Landau's inequalities for tournament scores and a short proof of a theorem on transitive sub‐tournaments

Ao and Hanson, and Guiduli, Gyárfás, Thomassé and Weidl independently, proved the following result: For any tournament score sequence S = (s₁, s₂, … ,s_n) with s₁≤s₂ ≤ … ≤ s_n, there exists a tournament T on vertex set {1,2, …, n} such that the score of each vertex i is s_i and the sub‐tournaments of T on both the even and the odd indexed vertices are transitive in the given order; that is, i dominates j whenever i > j and i ≡ j (mod 2). In this note, we give a much shorter proof of the result. In the course of doing so, we show that the score sequence of a tournament satisfies a set of inequalities which are individually stronger than the well‐known set of inequalities of Landau, but collectively the two sets of inequalities are equivalent. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 244–254, 2001     

Wasserstein geometry of porous medium equation

We study the porous medium equation with emphasis on q-Gaussian measures, which are generalizations of Gaussian measures by using power-law distribution. On the space of q-Gaussian measures, the porous medium equation is reduced to an ordinary differential equation for covariance matrix. We introduce a set of inequalities among functionals which gauge the difference between pairs of probability measures and are useful in the analysis of the porous medium equation. We show that any q-Gaussian measure provides a nontrivial pair attaining equality in these inequalities.     

Singular Probability Distributions and Fractal Properties of Sets of Real Numbers Defined by the Asymptotic Frequencies of Their <Emphasis Type="Italic">s</Emphasis>-Adic Digits

Properties of the set T _s of “particularly nonnormal numbers” of the unit interval are studied in detail (T _s consists of real numbers x some of whose s-adic digits have the asymptotic frequencies in the nonterminating s-adic expansion of x, and some do not). It is proved that the set T _s is residual in the topological sense (i.e., it is of the first Baire category) and is generic in the sense of fractal geometry (T _s is a superfractal set, i.e., its Hausdorff-Besicovitch dimension is equal to 1). A topological and fractal classification of sets of real numbers via analysis of asymptotic frequencies of digits in their s-adic expansions is presented. Dedicated to V. S. Korolyuk on occasion of his 80th birthday __________ Published in Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 9, pp. 1163–1170, September, 2005.     

Iterative Methods for Equilibrium and Fixed Point Problems for Nonexpansive Semigroups in Hilbert Spaces

In this paper, we introduce two iterative schemes (one implicit and one explicit) for finding a common element of the set of an equilibrium problem and the set of common fixed points of a nonexpansive semigroup (T(s)) _s≥0 in Hilbert spaces. We prove that both approaches converge strongly to a common element z of the set of the equilibrium points and the set of common fixed points of (T(s)) _s≥0. Such common element z is the unique solution of a variational inequality, which is the optimality condition for a minimization problem.     

Hölder and Lipschitz stability of solution sets in programs with probabilistic constraints

We study perturbations of a stochastic program with a probabilistic constraint and r-concave original probability distribution. First we improve our earlier results substantially and provide conditions implying Hölder continuity properties of the solution sets w.r.t. the Kolmogorov distance of probability distributions. Secondly, we derive an upper Lipschitz continuity property for solution sets under more restrictive conditions on the original program and on the perturbed probability measures. The latter analysis applies to linear-quadratic models and is based on work by Bonnans and Shapiro. The stability results are illustrated by numerical tests showing the different asymptotic behaviour of parametric and nonparametric estimates in a program with a normal probabilistic constraint.Mathematics Subject Classification (2000): 90C15, 90C31     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Antiweb-wheel inequalities and their separation problems over the stable set polytopes

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic ℕℙ-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets. Since it is impossible (unless ℕℙ=coℕℙ) to obtain a “concise” characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities with the property that the corresponding separation problem (given a point x ^*, find, if possible, an inequality in the class that x ^* violates) is efficiently solvable.?Some known large classes of separable inequalities are the trivial, edge, cycle and wheel inequalities. In this paper, we give a polynomial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities, called (t)-antiweb-s-wheel inequalities. This class is a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them. Received: June 2000 / Accepted: August 2001?Published online February 14, 2002     

An Analog of the Krein--Mil'man Theorem for Strongly Convex Hulls in Hilbert Space

We prove the following theorem: in Hilbert space a closed bounded set is contained in the strongly convex R-hull of its R-strong extreme points. R-strong extreme points are a subset of the set of extreme points (it may happen that these two sets do not coincide); the strongly convex R-hull of a set contains the closure of the convex hull of the set.