Extreme 2-homogeneous polynomials on Hilbert spaces

Let H be a (real or complex) Hilbert space. We characterize the extreme points of the unit ball of the space of 2-homogeneous polynomials on H. We find the exact value of the λ-function for P(² H) and thus we show that its unit ball is the norm closed convex hull of its extreme points. We also describe topological properties of the set of extreme points, making connections between the set of extreme points and Grassmanian manifolds.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

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.     

AnR danalogue of Valentine’s theorem on 3-convex sets

This paper deals with anR ^danalogue of a theorem of Valentine which states that a closed 3-convex setS in the plane is decomposable into 3 or fewer closed convex sets. In Valentine’s proof, the points of local nonconvexity ofS are treated as vertices of a polygonP contained in the kernel ofS, yielding a decomposition ofS into 2 or 3 convex sets, depending on whetherP has an even or odd number of edges. Thus the decomposition actually depends onc(P′), the chromatic number of the polytopeP′ dual toP. A natural analogue of this result is the following theorem: LetS be a closed subset ofR ^d, and letQ denote the set of points of local nonconvexity ofS. We require thatQ be contained in the kernel ofS and thatQ coincide with the set of points in the union of all the (d − 2)-dimensional faces of somed-dimensional polytopeP. ThenS is decomposable intoc(P′) closed convex sets.     

Extreme points for convex mappings ofB n

We exhibit a collection of extreme points of the family of normalized convex mappings of the open unit ball of ℂ ⁿ forn≥2. These extreme points are defined in terms of the extreme points of a closed ball in the Banach space of homogeneous polynomials of degree 2 in ℂ ⁿ⁻¹, which are fully classified. Two examples are given to show that there are more convex mappings than those contained in the closed convex hull of the set of extreme points here exhibited.     

Unique representation in convex sets by extraction of marked components

After introducing the basic concepts of extraction and marking for convex sets, the following marked representation theorem is established: Let C be a lineally closed convex set without lines, the face lattice of which satisfies some descending chain condition, and let μ be some marking on C. Then every point of C can be represented in unique way as a convex (nonnegative) linear combination of points (directions) of C which are μ-independent, and this representation can be determined by an algorithm of successive extractions. In particular, if C is a finite dimensional closed convex set without lines and μ marks extreme points (directions) only, then the marked representation theorem contains some well-known results of convex analysis as special cases, and it yields in the case where C is a polyhedral triangulation which extends available results on polytopes to the unbounded case. The triangulation of unbounded polyhedra then is applied to a certain class of parametric linear programs.     

On the range sets of variational inequalities

This paper investigates the closedness and convexity of the range sets of the variational inequality (VI) problem defined by an affine mappingM and a nonempty closed convex setK. It is proved that the range set is closed ifK is the union of a polyhedron and a compact convex set. Counterexamples are given such that the range set is not closed even ifK is a simple geometrical figure such as a circular cone or a circular cylinder in a three-dimensional space. Several sufficient conditions for closedness and convexity of the range set are presented. Characterization for the convex hull of the range set is established in the case whereK is a cone, while characterization for the closure of the convex hull of the range set is established in general. Finally, some applications to stability of VI problems are derived.This work was supported by the Australian Research Council.We are grateful to Professors M. Seetharama Gowda, Olvi Mangasarian, Jong-Shi Pang, and Steve Robinson for references. We are thankful to Professor Jim Burke for discussions on Theorem 2.1 and Counterexample 3.5.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

A counterexample to the Bishop-Phelps Theorem in complex spaces

The Bishop-Phelps Theorem asserts that the set of functionals which attain the maximum value on a closed bounded convex subsetS of a real Banach spaceX is norm dense inX ^*. We show that this statement cannot be extended to general complex Banach spaces by constructing a closed bounded convex set with no support points.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

The mixing-MIR set with divisible capacities

We study the set , where , j =  1, ..., n, and B ₁ | ... | B _n . The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Günlük and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about S remain unanswered, including the tractability of optimization over S and how to efficiently find a most violated cutting plane valid for P =  conv (S). We address these questions by analyzing the extreme points and extreme rays of P. We give all extreme points and extreme rays of P. In the worst case, the number of extreme points grows exponentially with n. However, we show that, in some interesting cases, it is bounded by a polynomial of n. In such cases, it is possible to derive strong cutting planes for P efficiently. Finally, we use our results on the extreme points of P to give a polynomial-time algorithm for solving optimization over S.      

Depth-Optimized Convexity Cuts

This paper presents a general, self-contained treatment of convexity or intersection cuts. It describes two equivalent ways of generating a cut—via a convex set or a concave function—and a partial-order notion of cut strength. We then characterize the structure of the sets and functions that generate cuts that are strongest with respect to the partial order. Next, we specialize this analytical framework to the case of mixed-integer linear programming (MIP). For this case, we formulate two kinds of the deepest cut generation problem, via sets or via functions, and subsequently consider some special cases which are amenable to efficient computation. We conclude with computational tests of one of these procedures on a large set of MIPLIB problems.     

Continuity at the extreme points

We prove that a bounded convex lower semicontinuous function defined on a convex compact set K is continuous at a dense subset of extreme points. If there is a bounded strictly convex lower semicontinuous function on K, then the set of extreme points contains a dense completely metrizable subset.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

A decomposition theorem form-convex sets

LetS be a closedm-convex subset of the plane,m≧2,Q the set of points of local nonconvexity ofS, with convQ ⊆S. If there is some pointp in [(bdryS) ∩ (kerS)] ∼Q, thenS is a union ofm−1 closed convex sets. The result is best possible for everym.     

The Dirichlet problem for Baire-one functions

Let X be a compact convex set and let ext X stand for the set of all extreme points of X. We characterize those bounded function defined on ext X which can be extended to an affine Baire-one function on the whole set X.     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

The facialQ-topology for compact convex sets

The structure of the set of closed two-sided ideals in aC*-algebraU with identity is described by means of a topology on the set _e K of extreme points of the state spaceK ofU. Recent results of Alfsen, Andersen, Combes, Perdrizet, Wils, and others have shown that such a topology can be defined on the set _e K of extreme points of an arbitrary compact convex subset of a locally convex Hausdorff topological vector space.The structure of the set of closed left ideals in aC*-algebraU with identity can also be described by means of a set of subsets of the set _e K of extreme points of its state spaceK. Akemann, Giles, and Kummer showed that this formed a more general structure than a topology which was called aq-topology. In this paper it is shown that for a reasonably wide class of compact convex subsetsK of locally convex Hausdorff topological vector spaces such aq-topology can also be defined on _e K and that it shares many of the properties of theq-topology defined forC*-algebras. The methods used depend strongly upon recent results of Alfsen and Shultz on the spectral theory of affine functions on compact convex sets.     

Width of convex bodies in spaces of constant curvature

We consider the measure of points, the measure of lines and the measure of planes intersecting a given convex body K in a space form. We obtain some integral formulas involving the width of K and the curvature of its boundary ∂K. Also we study the special case of constant width. Moreover we obtain a generalisation of the Heintze–Karcher inequality to space forms. Work partially supported by grant number ACI2003-44 Joint action Catalonia–Baden-Württemberg and by FEDER/MEC grant number MTM2006-04353. The third author was also supported by the program Ramón y Cajal, MEC.     

Polynomial hulls and H￥H^\infty control for a hypoconvex constraint

We say that a subset of is hypoconvex if its complement is the union of complex hyperplanes. Let be the closed unit disk in , . We prove two conjectures of Helton and Marshall. Let be a smooth function on whose sublevel sets have compact hypoconvex fibers over . Then, with some restrictions on , if Y is the set where is less than or equal to 1, the polynomial convex hull of Y is the union of graphs of analytic vector valued functions with boundary in Y. Furthermore, we show that the infimum is attained by a unique bounded analytic f which in fact is also smooth on . We also prove that if varies smoothly with respect to a parameter, so does the unique f just found. Received: 18 December 1998 / Published online: 28 June 2000