Complément de Schur et sous-différentiel du second ordre d'une fonction convexe

Summary The Schur complement relative to the linear mappingA of a functionf is denotedAf and defined as the image off underA. In this paper we give some estimates for the second-order differential ofAf whenf is either a partially quadratic convex function or aC ² convex function with a nonsingular second-order differential. We then consider an arbitrary convex functionf and study the second-order differentiability ofAf in a more general sense.

     

Expectation of random polytopes

A random polytopeP _n in a convex bodyC is the convex hull ofn identically and independently distributed points inC. Its expectation is a convex body in the interior ofC. We study the deviation of the expectation ofP _n fromC asn→∞: while forC of classC ^k+1,k≥1, precise asymptotic expansions for the deviation exist, the behaviour of the deviation is extremely irregular for most convex bodiesC of classC ¹. Dedicated to my teacher and friend Professor Edmund Hlawka on the occasion of his 80^th birthday     

Sets determined by finitely many X-rays

A measurable set in _n which is uniquely determined among all measurable sets (modulo null sets) by its X-rays in a finite set L of directions, or more generally by its X-rays parallel to a finite set L of subspaces, is called L-unique, or simply unique. Some subclasses of the L-unique sets are known. The L-additive sets are those measurable sets E which can be written E {x _n : _i f _i (x) * 0}. Here, denotes equality modulo null sets, * is either or >, and the terms in the sum are the values of ridge functions f _i orthogonal to subspaces S _i in L. If n=2, the L-inscribable convex sets are those whose interiors are the union of interiors of inscribed convex polygons, all of whose sides are parallel to the lines in L. Relations between these classes are investigated. It is shown that in _n each L-inscribable convex set is L-additive, but L-additive convex sets need not be L-inscribable. It is also shown that every ellipsoid in _n is unique for any set of three directions. Finally, some results are proved concerning the structure of convex sets in _n , unique with respect to certain families of coordinate subspaces.     

On the structure of singular sets of convex functions

Whenf is a convex function ofR ^h, andk is an integer with 0<k, then the set ^k (f)=x:dim(f(x)k may be covered by countably many manifolds of dimensionh–k and classC ² except an _h–k negligible subset.The author is supported by INdAM     

Ona-Wright convexity and the converse of Minkowski's inequality

Summary Leta (0, 1/2] be fixed. A functionf satisfying the inequalityf(ax + (1 – a)y) + f((1 – a)x + ay) f(x) + f(y), called herea-Wright convexity, appears in connection with the converse of Minkowski's inequality. We prove that every lower semicontinuousa-Wright convex function is Jensen convex and we pose an open problem. Moreover, using the fact that 1/2-Wright convexity coincides with Jensen convexity, we prove a converse of Minkowski's inequality without any regularity conditions.     

The maximal monotonicity of the subdifferentials of convex functions: Simons' problem

In the paper we deal with the problem when the graph of the subdifferential operator of a convex lower semicontinuous function has a common point with the product of two convex nonempty weak and weak^* compact sets, i.e. when graph (Q × Q ^*) 0. The results obtained partially solve the problem posed by Simons as well as generalize the Rockafellar Maximal Monotonicity Theorem.     

k-sets and random hulls

We re-examine the probabilistic analysis of Clarkson and Shor [5] involvingk-sets of point sets and related structures. By studying more carefully the equations that they derive, we are able to obtain refined analysis of these quantities, which lead to a collection of interesting relationships involvingk-sets, convex hulls of random samples, and generalizations of these constructs.Work on this paper has been supported by Office of Naval Research Grant N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

On the second differentiability of convex surfaces

Properties of pointwise second differentiability of real-valued convex functions in ⁿ are studied. Some proofs of the Busemann-Feller-Aleksandrov theorem are reviewed and a new proof of this theorem is presented.     

The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

The hypermetric cone is polyhedral

The hypermetric coneH _n is the cone in the spaceR ^n(n–1)/2 of all vectorsd=(d _ij)_1i<jn satisfying the hypermetric inequalities: –_1ijn z _j z _j d _ij 0 for all integer vectorsz inZ ⁿ with –_1in z _i =1. We explore connections of the hypermetric cone with quadratic forms and the geometry of numbers (empty spheres andL-polytopes in lattices). As an application, we show that the hypermetric coneH _n is polyhedral.     

Hessian measures of semi-convex functions and applications to support measures of convex bodies

This paper originates from the investigation of support measures of convex bodies (sets of positive reach), which form a central subject in convex geometry and also represent an important tool in related fields. We show that these measures are absolutely continuous with respect to Hausdorff measures of appropriate dimensions, and we determine the Radon-Nikodym derivatives explicitly on sets of σ-finite Hausdorff measure. The results which we obtain in the setting of the theory of convex bodies (sets of positive reach) are achieved as applications of various new results on Hessian measures of convex (semi-convex) functions. Among these are a Crofton formula, results on the absolute continuity of Hessian measures, and a duality theorem which relates the Hessian measures of a convex function to those of the conjugate function. In particular, it turns out that curvature and surface area measures of a convex body K are the Hessian measures of special functions, namely the distance function and the support function of K. Received: 15 July 1999     

Moment inequalities and central limit properties of isotropic convex bodies

The object of our investigations are isotropic convex bodies , centred at the origin and normed to volume one, in arbitrary dimensions. We show that a certain subset of these bodies – specified by bounds on the second and fourth moments – is invariant under forming ‘expanded joinsrsquo;. Considering a body K as above as a probability space and taking , we define random variables on K. It is known that for subclasses of isotropic convex bodies satisfying a ‘concentration of mass property’, the distributions of these random variables are close to Gaussian distributions, for high dimensions n and ‘most’ directions . We show that this ‘central limit property’, which is known to hold with respect to convergence in law, is also true with respect to -convergence and -convergence of the corresponding densities. Received: 21 March 2001 / in final form: 17 October 2001 / Published online: 4 April 2002     

A functional inequality characterizing convex functions,conjugacy and a generalization of Hölder's and Minkowski's inequalities

Summary The main result says that, iff: _{+ +} satisfies the functional inequalityaf(s) + bf(t) f (as + bt) (s,t 0) for somea, b such that 0 <a < 1 <a + b, thenf(t) = f(1)t, (t 0). A relevant result for the reverse inequality is also discussed. Applying these results we determine the form of all functionsf: _k ⁺ ₊ satisying the above inequalities. This leads to a characterization of both concave and convex functions defined on ₊ ^k–1 , to a notion of conjugate functions and to a general inequality which contains Hölder's and Minkowski's inequalities as very special cases.     

Constructing a polytope to approximate a convex body

We develop an algorithm to construct a convex polytopeP withn vertices, contained in an arbitrary convex bodyK inR ^d , so that the ratio of the volumes |K/P|/|K| is dominated byc ·. d/n ^2/(d–1).Supported in part by the fund for the promotion of research in the Technion     

On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.     

Cyclic polygons with given edge lengths: Existence and uniqueness

Let a₁, ..., a_n be positive numbers satisfying the condition that each of the a_i’s is less than the sum of the rest of them; this condition is necessary for the a_i’s to be the edge lengths of a (closed) polygon. It is proved that then there exists a unique (up to an isometry) convex cyclic polygon with edge lengths a₁, ..., a_n. On the other hand, it is shown that, without the convexity condition, there is no uniqueness—even if the signs of all central angles and the winding number are fixed, in addition to the edge lengths.     

A geometrical approach to monotone functions in \mathbb R^n

The paper is concerned with the fine properties of monotone functions on . We study the continuity and differentiability properties of these functions, the approximability properties, the structure of the distributional derivatives and of the weak Jacobians. Moreover, we exhibit an example of a monotone function u which is the gradient of a convex function and whose weak Jacobian Ju is supported on a purely unrectifiable set. Received October 9, 1996; in final form April 21, 1997     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Constant Minkowskian width in terms of double normals

We extend the notion of a double normal of a convex body from smooth, strictly convex Minkowski planes to arbitrary two-dimensional real, normed, linear spaces in two different ways. Then, for both of these ways, we obtain the following characterization theorem: a convex body K in a Minkowski plane is of constant Minkowskian width iff every chord I of K splits K into two compact convex sets K₁ and K₂ such that I is a Minkowskian double normal of K₁ or K₂. Furthermore, the Euclidean version of this theorem yields a new characterization of d-dimensional Euclidean ball where d 3.