Slice-Continuous Sets in Reflexive Banach Spaces: Some Complements

In this paper we study a class of closed convex sets introduced recently by Ernst et al. (J Funct Anal 223:179–203, 2005) and called by these authors slice-continuous sets. This class, which plays an important role in the strong separation of convex sets, coincides in ℝ ⁿ with the well known class of continuous sets defined by Gale and Klee in the 1960s. In this article we achieve, in the setting of reflexive Banach spaces, two new characterizations of slice-continuous sets, similar to those provided for continuous sets in ℝ ⁿ by Gale and Klee. Thus, we prove that a slice-continuous set is precisely a closed and convex set which does not possess neither boundary rays, nor flat asymptotes of any dimension. Moreover, a slice-continuous set may also be characterized as being a closed and convex set of non-void interior for which the support function is continuous except at the origin. Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

Convex Sets in Acyclic Digraphs

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with and . We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n − k + 1. This is a strengthening of a theorem of Gutin and Yeo.     

On the lack of directional quasiconcavity of the fundamental mode in the clamped membrane problem

We consider the principal Dirichlet eigenfunction u of the Laplacian in a bounded region in \mathbbR²{\mathbb{R}^2} which is convex in one direction, say in x ₁. It has been asked by Kawohl (Remarks on some old and current eigenvalue problems, Cambridge University Press, pp 165–183, 1994) whether in this case u is quasiconcave in x ₁, i.e., all superlevel sets of u are convex in x ₁. In this note we provide a negative answer to this question by giving an explicit counterexample.     

Several modifications of DPR estimator of the tail index

In this paper, we continue the investigation of an estimator proposed in [Yu. Davydov, V. Paulauskas, and A. Račkauskas, More on p-stable convex sets in Banach spaces, J. Theor. Probab., 13:39–64, 2000] and [V. Paulauskas, A new estimator for tail index, Acta Appl. Math., 79:55–67, 2003] and considered in [V. Paulauskas and M. Vaičiulis, Once more on comparison of tail index estimators, preprint, 2010]. We propose a class of modifications of the so-called DPR estimator and demonstrate that these modifications can have better asymptotic properties than the original DPR estimator.     

Rate of Approximation of Regular Convex Bodies by?Convex Algebraic Level Surfaces

We consider the problem of the approximation of regular convex bodies in ℝ ^d by level surfaces of convex algebraic polynomials. Hammer (in Mathematika 10, 67–71, 1963) verified that any convex body in ℝ ^d can be approximated by a level surface of a convex algebraic polynomial. In Jaen J. Approx. 1, 97–109, 2009 and subsequently in J. Approx. Theory 162, 628–637, 2010 a quantitative version of Hammer’s approximation theorem was given by showing that the order of approximation of convex bodies by convex algebraic level surfaces of degree n is \frac1n\frac{1}{n}. Moreover, it was also shown that whenever the convex body is not regular (that is, there exists a point on its boundary at which the convex body possesses two distinct supporting hyperplanes), then \frac1n\frac{1}{n} is essentially the sharp rate of approximation. This leads to the natural question whether this rate of approximation can be improved further when the convex body is regular. In this paper we shall give an affirmative answer to this question. It turns out that for regular convex bodies a o(1/n) rate of convergence holds. In addition, if the body satisfies the condition of C ²-smoothness the rate of approximation is O(\frac1n²)O(\frac{1}{n^{2}}).     

The embracing Voronoi diagram and closest embracing number

A point q is embraced by a set of points S if q is interior to the convex hull of S [8]. In some illumination applications where points of S are lights and q is a point to be illuminated, the embracing concept is related to a good illumination [4, 6], also known as the ∆-guarding [12] and the well-covering [10]. In this paper, we are not only interested in convex dependency (which is actually the embracing notion) but also in proximity. Suppose that the sites of S are lights or antennas with limited range; due to their limited power, they cover a disk of a given radius r centered at the sites of S. Only the points lying in such disks are illuminated. If we want to embrace the point q with the minimum range r, we need to know which is the closest light s _q to q such that q lies in the convex hull formed by s _q and the lights of S closer to q than s _q . This subset of S related to point q is called the closest embracing set for q in relation to S and its cardinality is the closest embracing number of q. By assigning every point q in the convex hull of S to its closest embracing site s _q , we obtain a partition of the convex hull that we call the embracing Voronoi diagram of S. This paper proves some properties of the embracing Voronoi diagrams and describes algorithms to compute such diagrams, as well as the levels in which the convex hull is decomposed regarding the closest embracing number.     

On Partially Ordered Semigroups and an Abstract Set-Difference

In this paper we prove the independence of a system of five axioms (S1)–(S5), which was proposed in the book of Pallaschke and Urbański (Pairs of Compact Convex Sets, vol. 548, Kluwer Academic Publishers, Dordrecht, 2002) for partially ordered commutative semigroups. These five axioms (S1)–(S5) are stated in the introduction below. A partially ordered commutative semigroup satisfying these axioms is called a F-semigroup. By the use of a further axiom (S6) we define an abstract difference for the elements of a F-semigroup and prove some basic properties. The most interesting example of a F-semigroup are the nonempty compact convex sets of a topological vector space endowed with the Minkowski sum as operation and the inclusion as partial order. In Section 4 we apply the abstract difference to the problem of minimality of convex fractions. Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

An Isometric Representation of the Dual of {\user1{\mathcal{C}}}{\left( {X,\mathbb{R}} \right)}

Many structures in functional analysis are introduced as the limit of an inverse (aka projective) system of seminormed spaces [2, 3, 8]. In these situations, the dual is moreover equipped with a seminorm. Although the topology of the inverse limit is seldom metrizable, there is always a natural overlying locally convex approach structure. We provide a method for computing the adjoint of this space, by showing that the dual of a limit of locally convex approach spaces becomes a co-limit in the category of seminormed spaces. As an application we obtain an isometric representation of the dual space of real valued continuous functions on a locally compact Hausdorff space X, equipped with the compact open structure.     

Covering Convex Bodies by Cylinders and Lattice Points by Flats

In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of a given convex body in d-dimensional Euclidean space for 1≤k≤d−1. K. Bezdek and A.E. Litvak are partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

Boundary Behavior of Harmonic Functions for Truncated Stable Processes

For any α∈(0,2), a truncated symmetric α-stable process in ℝ ^d is a symmetric Lévy process in ℝ ^d with no diffusion part and with a Lévy density given by c|x|^−d−α 1_{|x|<1} for some constant c. In (Kim and Song in Math. Z. 256(1): 139–173, [2007]) we have studied the potential theory of truncated symmetric stable processes. Among other things, we proved that the boundary Harnack principle is valid for the positive harmonic functions of this process in any bounded convex domain and showed that the Martin boundary of any bounded convex domain with respect to this process is the same as the Euclidean boundary. However, for truncated symmetric stable processes, the boundary Harnack principle is not valid in non-convex domains. In this paper, we show that, for a large class of not necessarily convex bounded open sets in ℝ ^d called bounded roughly connected κ-fat open sets (including bounded non-convex κ-fat domains), the Martin boundary with respect to any truncated symmetric stable process is still the same as the Euclidean boundary. We also show that, for truncated symmetric stable processes a relative Fatou type theorem is true in bounded roughly connected κ-fat open sets. The research of P. Kim is supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2007-331-C00037). The research of R. Song is supported in part by a joint US-Croatia grant INT 0302167.     

On Aleksandrov-Fenchel Inequalities for <Emphasis Type="Italic">k</Emphasis>-Convex Domains

In this lecture notes, we will discuss the classical Aleksandrov-Fenchel inequalities for quermassintegrals on convex domains and pose the problem of how to extend the inequalities to non-convex domains. We will survey some recent progress on the problem, then report some of our joint work [9] in which we generalize the k-th stage of the inequalities to a class of (k + 1)-convex domains. Our proof, following the earlier work of Castillion [8] for k =  1 case of the inequalities, uses the method of optimal transport.     

On the Expected Probability of Constraint Violation in Sampled Convex Programs

In this note, we derive an exact expression for the expected probability V of constraint violation in a sampled convex program (see Calafiore and Campi in Math. Program. 102(1):25–46, 2005; IEEE Trans. Autom. Control 51(5):742–753, 2006 for definitions and an introduction to this topic):

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

Lipschitzian stability of parametric variational inequalities over perturbed polyhedral convex sets

In this paper we investigate the Lipschitz-like property of the solution mapping of parametric variational inequalities over perturbed polyhedral convex sets. By establishing some lower and upper estimates for the coderivatives of the solution mapping, among other things, we prove that the solution mapping could not be Lipschitz-like around points where the positive linear independence condition is invalid. Our analysis is based heavily on the Mordukhovich criterion (Mordukhovich in Variational Analysis and Generalized Differentiation. vol. I: Basic Theory, vol. II: Applications. Springer, Berlin, 2006) of the Lipschitz-like property for set-valued mappings between Banach spaces and recent advances in variational analysis. The obtained result complements the corresponding ones of Nam (Nonlinear Anal 73:2271–2282, 2010) and Qui (Nonlinear Anal 74:1674–1689, 2011).     

Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.     

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Two convex disks K and L in the plane are said to cross each other if the removal of their intersection causes each disk to fall into disjoint components. Almost all major theorems concerning the covering density of a convex disk were proved only for crossing-free coverings. This includes the classical theorem of L. Fejes Tóth (Acta Sci. Math. Szeged 12/A:62–67, 1950) that uses the maximum area hexagon inscribed in the disk to give a significant lower bound for the covering density of the disk. From the early seventies, all attempts of generalizing this theorem were based on the common belief that crossings in a plane covering by congruent convex disks, being counterproductive for producing low density, are always avoidable. Partial success was achieved not long ago, first for “fat” ellipses (A. Heppes in Discrete Comput. Geom. 29:477–481, 2003) and then for “fat” convex disks (G. Fejes Tóth in Discrete Comput. Geom. 34(1):129–141, 2005), where “fat” means of shape sufficiently close to a circle. A recently constructed example will be presented here, showing that, in general, all such attempts must fail. Three perpendiculars drawn from the center of a regular hexagon to its three nonadjacent sides partition the hexagon into three congruent pentagons. Obviously, the plane can be tiled by such pentagons. But a slight modification produces a (non-tiling) pentagon with an unexpected covering property: every thinnest covering of the plane by congruent copies of the modified pentagon must contain crossing pairs. The example has no bearing on the validity of Fejes Tóth’s bound in general, but it shows that any prospective proof must take into consideration the existence of unavoidable crossings.     

A characterization of convex TU games by means of the Mas-Colell bargaining set (à la Shimomura)

Within the class of zero-monotonic games, we prove that a cooperative game with transferable utility is convex if and only if the core of the game coincides with the Mas-Colell bargaining set (à la Shimomura, in Int J Game Theory 26:283–302, 1997).     

Convergence rate of McCormick relaxations

Theory for the convergence order of the convex relaxations by McCormick (Math Program 10(1):147–175, 1976) for factorable functions is developed. Convergence rules are established for the addition, multiplication and composition operations. The convergence order is considered both in terms of pointwise convergence and of convergence in the Hausdorff metric. The convergence order of the composite function depends on the convergence order of the relaxations of the factors. No improvement in the order of convergence compared to that of the underlying bound calculation, e.g., via interval extensions, can be guaranteed unless the relaxations of the factors have pointwise convergence of high order. The McCormick relaxations are compared with the αBB relaxations by Floudas and coworkers (J Chem Phys, 1992, J Glob Optim, 1995, 1996), which guarantee quadratic convergence. Illustrative and numerical examples are given.     

Duality, Vector Spaces and Absolutely Convex Modules

It is well-known (see Semadeni, Queen Pap. Pure Appl. Math., 33:1–98, 1973 and Pumplün and Röhrl, Commun. Algebra, 12(8):953–1019, 1984, 1985) that the embedding of vector spaces into the category of absolutely convex modules is reflective. As we will show, under a separatedness condition on these modules it is at the same time coreflective. This is a peculiar situation, see Kannan, Math. Ann., 195:168–174, (1972) and Hu $\textrm {\u{s}}It is well-known (see Semadeni, Queen Pap. Pure Appl. Math., 33:1–98, 1973 and Pumplün and R?hrl, Commun. Algebra, 12(8):953–1019, 1984, 1985) that the embedding of vector spaces into the category of absolutely convex modules is reflective. As we will show, under a separatedness condition on these modules it is at the same time coreflective. This is a peculiar situation, see Kannan, Math. Ann., 195:168–174, (1972) and Huek, Reflexive and coreflexive subcategories of unif and top, Seminar Uniform Spaces, Prague, 113–126, (1973), but we do find it also in the embedding (Lowen, Approach Spaces: The Missing Link in the Topology-Uniformity-Metric Triad. Oxford Mathematical Monographs, Oxford University Press, London, UK, 1997) and, by extension, in the embedding (see Lowen and Verwulgen, Houst. J. Math, 30(4):1127–1142, 2004, and Sioen and Verwulgen, Appl. Gen. Topol., 4(2):263–279, 2003. We demonstrate that, in this setting, by duality arguments, absolutely convex modules are indeed the numerical counterpart of vector spaces. All these, at first sight unrelated facts, are comprised in the commutative scheme below with natural dualisation functors and their left adjoints.