Basicness of Semialgebraic Sets

This paper is concerned with the problem of deciding whether a semialgebraic set S of an algebraic variety X over R is basic. Furthermore, in such a case, we decide what is the sharp number of inequalities defining S. For that, it suffices to desingularize X, as well as the boundary of S, and then ask the same question for the trace of S on its boundary. In this way, after a finite number of blowing-ups, we lower the dimension of the data and by induction we get a finite decision procedure to solve this problem. Decidability of other known criteria is also analyzed.     

Computing an Integer Point of a Class of Convex Sets

A simplicial algorithm is proposed for computing an integer point of a convex set ^CRn satisfying

Betti Numbers of Semialgebraic and Sub-Pfaffian Sets

Let X be a subset in [–1,1]^n₀R^n₀ defined by the formula X={x₀|Q₁x₁Q₂x₂...Qx ((x₀,x₁,...x)X)}, where Q_i{ }, Q_i Q_i+1, x_i [–1, 1]^n_i, and X may be eitheran open or a closed set in [–1,1]^n₀+...+n, being the differencebetween a finite CW-complex and its subcomplex. An upper boundon each Betti number of X is expressed via a sum of Betti numbersof some sets defined by quantifier-free formulae involving X. In important particular cases of semialgebraic and semi-Pfaffiansets defined by quantifier-free formulae with polynomials andPfaffian functions respectively, upper bounds on Betti numbersof X are well known. The results allow to extend the boundsto sets defined with quantifiers, in particular to sub-Pfaffiansets.     

SOS-Convex Semialgebraic Programs and its Applications to Robust Optimization: A Tractable Class of Nonsmooth Convex Optimization

In this paper, we introduce a new class of nonsmooth convex functions called SOS-convex semialgebraic functions extending the recently proposed notion of SOS-convex polynomials. This class of nonsmooth convex functions covers many common nonsmooth functions arising in the applications such as the Euclidean norm, the maximum eigenvalue function and the least squares functions with ? ₁-regularization or elastic net regularization used in statistics and compressed sensing. We show that, under commonly used strict feasibility conditions, the optimal value and an optimal solution of SOS-convex semialgebraic programs can be found by solving a single semidefinite programming problem (SDP). We achieve the results by using tools from semialgebraic geometry, convex-concave minimax theorem and a recently established Jensen inequality type result for SOS-convex polynomials. As an application, we show that robust SOS-convex optimization proble ms under restricted spectrahedron data uncertainty enjoy exact SDP relaxations. This extends the existing exact SDP relaxation result for restricted ellipsoidal data uncertainty and answers an open question in the literature on how to recover a robust solution of uncertain SOS-convex polynomial programs from its semidefinite programming relaxation in this broader setting.     

Betti Numbers of Semialgebraic Sets Defined by Quantifier-Free Formulae

Let X be a semialgebraic set in Rⁿ defined by a Boolean combination of atomic formulae of the kind h * 0 where * \in { >, \ge, = }, deg(h) < d, and the number of distinct polynomials h is k. We prove that the sum of Betti numbers of X is less than O(k²d)ⁿ.     

Constructible Convex Sets

We investigate when closed convex sets can be written as countable intersections of closed half-spaces in Banach spaces. It is reasonable to consider this class to comprise the constructible convex sets since such sets are precisely those that can be defined by a countable number of linear inequalities, hence are accessible to techniques of semi-infinite convex programming. We also explore some model theoretic implications. Applications to set convergence are given as limiting examples.     

Finding Convex Sets in Convex Position

Let F{\cal{F}} denote a family of pairwise disjoint convex sets in the plane. F{\cal{F}} is said to be in convex position, if none of its members is contained in the convex hull of the union of the others. For any fixed k 3 5k\ge5, we give a linear upper bound on P_k(n)P_k(n), the maximum size of a family F{\cal{F}} with the property that any k members of F{\cal{F}} are in convex position, but no n are.     

Translating Finite Sets into Convex Sets

Let X be a reflexive Banach space, and let C X be a closed,convex and bounded set with empty interior. Then, for every > 0, there is a nonempty finite set F X with an arbitrarilysmall diameter, such that C contains at most .|F| points ofany translation of F. As a corollary, a separable Banach spaceX is reflexive if and only if every closed convex subset ofX with empty interior is Haar null. 2000 Mathematics SubjectClassification 46B20 (primary), 28C20 (secondary).     

The Randomized Integer Convex Hull

Let K R^d be a sufficiently round convex body (the ratio of the circumscribed ball to the inscribed ball is bounded by a constant) of a sufficiently large volume. We investigate the randomized integer convex hull I_L(K) = conv (K L), where L is a randomly translated and rotated copy of the integer lattice Z^d. We estimate the expected number of vertices of I_L(K), whose behaviour is similar to the expected number of vertices of the convex hull of Vol K random points in K. In the planar case we also describe the expectation of the missed area Vol (K \ I_L(K)). Surprisingly, for K a polygon, the behaviour in this case is different from the convex hull of random points.     

Extremal Convex Planar Sets

Each convex planar set K has a perimeter C, a minimum width E, an area A, and a diameter D. The set of points (E,C, A^1/2, D) corresponding to all such sets is shown to occupy a cone in the non-negative orthant of R⁴with its vertex at the origin. Its three-dimensional cross section S in the plane D = 1 is investigated. S lies in a rectangular parallelepiped in R³. Results of Lebesgue, Kubota, Fukasawa, Sholander, and Hemmi are used to determine some of the boundary surfaces of S, and new results are given for the other boundary surfaces. From knowledge of S, all inequalities among E, C ,A, and D can be found.     

Computing the Homology of Semialgebraic Sets. II: General Formulas

Foundations of Computational Mathematics - We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean...     

Valuations on Convex Sets of Oriented Hyperplanes

We discuss valuations on convex sets of oriented hyperplanes in ^d. For d = 2, we prove an analogue of Hadwigers characterization theorem for continuous, rigid motion invariant valuations.     

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.     

Pebble Sets in Convex Polygons

Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane. We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points.     

Noncommutative Polynomials Describing Convex Sets

Foundations of Computational Mathematics - The free closed semialgebraic set $${mathcal {D}}_f$$ determined by a hermitian noncommutative polynomial $$fin {text {M}}_{{delta }}({mathbb...     

Intersecting Convex Sets by Rays

What is the smallest number τ=τ(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most τ sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following:Given any collection \({\mathcal{C}}\) of n pairwise disjoint compact convex sets in d-dimensional Euclidean space, there exists a point p such that any ray emanating from p meets at most \(\frac{dn+1}{d+1}\) members of \({\mathcal{C}}\).There exist collections of n pairwise disjoint (i) equal-length segments or (ii) disks in the Euclidean plane such that from any point there is a ray that meets at least \(\frac{2n}{3}-2\) of them.We also determine the asymptotic behavior of τ(n) when the convex bodies are fat and of roughly equal size.     

New Combinations of Convex Sets

The family of convex sets in a (finite dimensional) real vector space admits several unary and binary operations – dilatation, intersection, convex hull, vector sum – which preserve convexity. These generalize to convex functions, where there are in fact further operations of this kind. Some of the latter may be regarded as combinations of two such operations, acting on complementary subspaces. In this paper, a general theory of such mixed operations is introduced, and some of its consequences developed.     

Canonical Theorems for Convex Sets

Let F be a family of pairwise disjoint compact convex sets in the plane such that none of them is contained in the convex hull of two others, and let r be a positive integer. We show that F has r disjoint ⌊ c _r n⌋ -membered subfamilies F _i (1 ≤ i ≤ r) such that no matter how we pick one element F _i from each F _i , they are in convex position, i.e., every F _i appears on the boundary of the convex hull of ⋃ _i=1 ^r F _i . (Here c _r is a positive constant depending only on r .) This generalizes and sharpens some results of Erdős and Szekeres, Bisztriczky and Fejes Tóth, Bárány and Valtr, and others. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p427.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received April 30, 1997, and in revised form August 5, 1997.