Semidefinite representation of convex sets

Let be a semialgebraic set defined by multivariate polynomials g _i (x). Assume S is convex, compact and has nonempty interior. Let , and ∂ S (resp. ∂ S _i ) be the boundary of S (resp. S _i ). This paper, as does the subject of semidefinite programming (SDP), concerns linear matrix inequalities (LMIs). The set S is said to have an LMI representation if it equals the set of solutions to some LMI and it is known that some convex S may not be LMI representable (Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007). A question arising from Nesterov and Nemirovski (SIAM studies in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994), see Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007 and Nemirovski in Plenary lecture, International Congress of Mathematicians (ICM), Madrid, Spain, 2006, is: given a subset S of , does there exist an LMI representable set Ŝ in some higher dimensional space whose projection down onto equals S. Such S is called semidefinite representable or SDP representable. This paper addresses the SDP representability problem. The following are the main contributions of this paper: (i) assume g _i (x) are all concave on S. If the positive definite Lagrange Hessian condition holds, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function ℓ ^T x on S is positive definite at the minimizer, then S is SDP representable. (ii) If each g _i (x) is either sos-concave ( − ∇² g _i (x) = W(x) ^T W(x) for some possibly nonsquare matrix polynomial W(x)) or strictly quasi-concave on S, then S is SDP representable. (iii) If each S _i is either sos-convex or poscurv-convex (S _i is compact convex, whose boundary has positive curvature and is nonsingular, i.e., ∇g _i (x) ≠ 0 on ∂ S _i ∩ S), then S is SDP representable. This also holds for S _i for which ∂ S _i ∩ S extends smoothly to the boundary of a poscurv-convex set containing S. (iv) We give the complexity of Schmüdgen and Putinar’s matrix Positivstellensatz, which are critical to the proofs of (i)–(iii).      

Minimal representation of convex polyhedral sets

A system of linear inequality and equality constraints determines a convex polyhedral set of feasible solutionsS. We consider the relation of all individual constraints toS, paying special attention to redundancy and implicit equalities. The main theorem derived here states that the total number of constraints together determiningS is minimal if and only if the system contains no redundant constraints and/or implicit equalities. It is shown that the existing theory on the representation of convex polyhedral sets is a special case of the theory developed here.The author is indebted to Dr. A. C. F. Vorst (Erasmus University, Rotterdam, Holland) for stimulating discussions and comments, which led to considerable improvements in many proofs. Most of the material in this paper originally appeared in the author's dissertation (Ref. 1). The present form was prepared with partial support from a NATO Science Fellowship for the Netherlands Organization for the Advancement of Pure Research (ZWO) and a CORE Research Fellowship.     

A representation of convex semilinear sets

If F is an ordered field, a subset of n-space over F is said to be semilinear just in case it is a finite Boolean combination of translates of closed halfspaces, where a closed halfspace is the set of all points obeying a homogeneous weak linear inequality with coefficients from F. Andradas, Rubio, and Vélez have shown that closed (open) convex semilinear sets are finite intersections of translates of closed (open) halfspaces (an open halfspace is defined as before, but with a strict inequality). This paper represents arbitrary convex semilinear sets in a manner analogous to that of Andradas, Rubio, and Vélez.     

Tiling convex sets by translates

LetK be a compact, convex subset ofE ^dwhich can be tiled by a finite number of disjoint (on interiors) translates of some compact setY. Then we may writeK=X+Y, whereX is finite. The possible structures forK, X andY are completely determined under these conditions.     

Dual representation of convex sets of probability measures on totally bounded spaces

Convex sets of probability measures, frequently encountered in probability theory and statistics, can be transparently analyzed by means of dual representations in a function space. This paper introduces totally bounded spaces, whose structure is defined by a set of bounded real-valued functions, as a general framework for studying such representations. The reinterpretation of classical theorems in this framework clarifies the role of compactness and leads to simple existence criteria. Applications include results on the existence of probability measures satisfying given sets of conditions and an equivalence of consistent preferences and families of probability measures. Moreover, countable additivity of probabilities is seen to be a consequence of elementary consistency assumptions.     

Approximation of convex sets by polytopes

The survey contains results related to different aspects of polyhedral approximation of convex bodies and some adjacent problems. __________ Translated from Sovremennaya Matematika. Fundamental’nye Napravleniya (Contemporary Mathematics. Fundamental Directions), Vol. 22, Geometry, 2007.     

Illumination by translates of convex sets

Let S be a compact set in the plane. If every three points of S are illuminated clearly by some translate of the compact convex set T, then there is a translate of T which illumines every point of S. Various analogues hold for translates of flats in R ^das well.Supported in part by NSF grant DMS-8705336.     

Separating convex sets by straight lines

We answer some questions of Tverberg about separability properties of families of convex sets. In particular, we show that there is a family of infinitely many pairwise disjoint closed disks, no two of which can be separated from two others by a straight line. No such construction exists with equal disks. We also prove that every uncountable family of pairwise disjoint convex sets in the plane has two uncountable subfamilies that can be separated by a straight line.     

Empty convex polygons in almost convex sets

A finite set of points, in general position in the plane, is almost convex if every triple determines a triangle with at most one point in its interior. For every ℓ ≥ 3, we determine the maximum size of an almost convex set that does not contain the vertex set of an empty convex ℓ-gon. Partially supported by grants T043631 and NK67867 of the Hungarian NFSR (OTKA).     

Separation of convex sets by extreme hyperplanes

The problem of separation of convex sets by extreme hyperplanes (functionals) in normed linear spaces is examined. The concept of a bar (a closed set of special form) is introduced; it is shown that a bar is characterized by the property that any point not lying in it can be separated from it by an extreme hyperplane. In two-dimensional spaces, in spaces with strictly convex dual, and in the space of continuous functions, any two bars are extremely separated. This property is shown to fail in the space of summable functions. A number of examples and generalizations are given.     

Unique determination of convex polytopes by non-central sections

A question of Barker and Larman asks whether convex bodies that contain a sphere of radius t in their interiors are uniquely determined by the volumes of sections by hyperplanes tangent to the sphere. We affirmatively solve this problem for convex polytopes.     

On space coverings by unbounded convex sets

Let (C_i) be a sequence of closed convex subsets of Euclidean n-space Eⁿ. This paper is concerned with the problem of finding necessary and sufficient conditions that the sets C_i can be rearranged (by the application of rigid motions or translations) so as to cover all or almost all Eⁿ. Particular attention is paid to the problems that arise if the sets C_i are permitted to be unbounded. It is shown that under certain conditions this covering problem can be reduced to the already thoroughly investigated case of compact sets with bounded diameter set{d(C_i)}, and it is also proved that there are two additional covering possibilities if such a reduction is not possible.     

On visibility and covering by convex sets

A setX⊆ℝ ^d isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn ⁶ convex sets. We improve their bound to 18n ³, and show a lower bound of order Ω(n ²). We also show that ifX⊆ℝ² is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n ⁴+n ²λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4). Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623.     

Nonoscillation theorems in convex sets

This paper presents a new and simple technique for a certain class of variational problems which includes many of the important problems of mathematical physics, e.g., the Brachistochrone, geodesies, and minimal surface of revolution problems. The technique uses Caratheodory's equivalent problems approach but combines two equivalent problems at the same time to get the sufficiency and uniqueness results. It does not use any of the classical sufficiency conditions such as the Weierstrass condition. The equations that we are led to by this new approach turn out to be the Hamilton-Jacobi and Euler-Lagrange equations for the problem, but here we have not had to use any of the classical Hamilton-Jacobi theory nor derivations to get its results (e.g., orthogonality of the extremals to the wave fronts) for this class of problems. The cases for one and n dependent variables are presented and illustrated. Implications and generalizations of the method are discussed.