The Empty Hexagon Theorem

Let P be a finite set of points in general position in the plane. Let C(P) be the convex hull of P and let Cⁱ_P be the ith convex layer of P. A minimal convex set S of P is a convex subset of P such that every convex set of P ∩ C(S) different from S has cardinality strictly less than |S|. Our main theorem states that P contains an empty convex hexagon if C¹_P is minimal and C⁴_P is not empty. Combined with the Erdos-Szekeres theorem, this result implies that every set P with sufficiently many points contains an empty convex hexagon, giving an affirmative answer to a question posed by Erdos in 1977.     

On Two-sided Locally Convex H*-algebras

We introduce (left, right, two-sided) locally convex H*-algebras, and we give conditions under which an one-sided locally convex H*-algebra turns to be a two-sided one (actually, a locally convex H*-algebra). We also give an example of a proper right locally convex H*-algebra with a (right) involution, which is not a left involution and an example of a proper two-sided locally convex H*-algebra, which is not a locally convex H*-algebra. Moreover, we connect (via an Arens-Michael decomposition) a two-sided locally m-convex H*-algebra with the classical (Banach) two-sided H*-algebras. Further, we present conditions so that the left, right involutions be continuous, and we see when a twosided locally convex H*-algebra is a dual one. Finally, we present some properties of invariant ideals which play an important rôle in structure theory of two-sided locally convex H*-algebras.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs

We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer’s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.

     

Empty Convex Hexagons in Planar Point Sets

Erdős asked whether every sufficiently large set of points in general position in the plane contains six points that form a convex hexagon without any points from the set in its interior. Such a configuration is called an empty convex hexagon. In this paper, we answer the question in the affirmative. We show that every set that contains the vertex set of a convex 9-gon also contains an empty convex hexagon.     

Convex approximations to sparse PCA via Lagrangian duality

We derive a convex relaxation for cardinality constrained Principal Component Analysis (PCA) by using a simple representation of the L₁ unit ball and standard Lagrangian duality. The resulting convex dual bound is an unconstrained minimization of the sum of two nonsmooth convex functions. Applying a partial smoothing technique reduces the objective to the sum of a smooth and nonsmooth convex function for which an efficient first order algorithm can be applied. Numerical experiments demonstrate its potential.     

New affine measures of symmetry for convex bodies

Grünbaum introduced measures of symmetry for convex bodies that measure how far a given convex body is from a centrally symmetric one. Here, we introduce new measures of symmetry that measure how far a given convex body is from one with “enough symmetries”.To define these new measures of symmetry, we use affine covariant points. We give examples of convex bodies whose affine covariant points are “far apart”. In particular, we give an example of a convex body whose centroid and Santaló point are “far apart”.     

Banach–Zaretsky theorem for compactly absolutely continuous mappings

For mappings of an interval into locally convex spaces, convex and compact convex analogs of absolute continuity, bounded variation, and the Luzin N-property are introduced and studied. We prove that, in the general case, a convex analog of the Banach–Zaretsky criteria can be “split” into sufficient and necessary conditions. However, in the Fréchet-space case, we have an exact compact analog of the criteria.     

A Krasnosel’skii-type result for planar sets starshaped via orthogonally convex paths

A Krasnosel’skii-type theorem for compact sets that are starshaped via staircase paths may be extended to compact sets that are starshaped via orthogonally convex paths: Let S be a nonempty compact planar set having connected complement. If every two points of S are visible via orthogonally convex paths from a common point of S, then S is starshaped via orthogonally convex paths. Moreover, the associated kernel Ker S has the expected property that every two of its points are joined in Ker S by an orthogonally convex path. If S is an arbitrary nonempty planar set that is starshaped via orthogonally convex paths, then for each component C of Ker S, every two of points of C are joined in C by an orthogonally convex path. Communicated by Imre Bárány     

ON THE PRODUCT OF GATEAUX DIFFERENTIABILITY LOCALLY CONVEX SPACES

A locally convex space is said to be a Gâteaux differentiability space (GDS) provided every continuous convex function defined on a nonempty convex open subset D of the space is densely Gâteaux differentiable in D. This paper shows that the product of a GDS and a family of separable Fréchet spaces is a GDS, and that the product of a GDS and an arbitrary locally convex space endowed with the weak topology is a GDS.     

A Plasticity Principle of Convex Quadrilaterals on a Convex Surface of Bounded Specific Curvature

We derive the plasticity equations for convex quadrilaterals on a complete convex surface with bounded specific curvature and prove a plasticity principle which states that: Given four shortest arcs which meet at the weighted Fermat-Torricelli point their endpoints form a convex quadrilateral and the weighted Fermat-Torricelli point belongs to the interior of this convex quadrilateral, an increase of the weight corresponding to a shortest arc causes a decrease of the two weights that correspond to the two neighboring shortest arcs and an increase of the weight corresponding to the opposite shortest arc by solving the inverse weighted Fermat-Torricelli problem for quadrilaterals on a convex surface of bounded specific curvature. The invariance of the weighted Fermat-Torricelli point(geometric plasticity principle) and the plasticity principle of quadrilaterals characterize the evolution of quadrilaterals on a complete convex surface. Furthermore, we show a connection between the plasticity of convex quadrilaterals on a complete convex surface with bounded specific curvature with the plasticity of some generalized convex quadrilaterals on a manifold which is certainly composed by triangles. We also study some cases of symmetrization of weighted convex quadrilaterals by introducing a new symmetrization technique which transforms some classes of weighted geodesic convex quadrilaterals on a convex surface to parallelograms in the tangent plane at the weighted Fermat-Torricelli point of the corresponding quadrilateral. This geometric method provides some pattern for the variable weights with respect to the 4-inverse weighted Fermat-Torricelli problem such that the weighted Fermat-Torricelli point remains invariant. By introducing the notion of superplasticity, we derive as an application of plasticity the connection between the Fermat-Torricelli point for some weighted kites with the fundamental equation of P. de Fermat for real exponents in the two dimensional Euclidean space. By using as an initial condition to the 3 body problem the solution of the 3-inverse weighted Fermat-Torricelli problem we give some future perspectives in plasticity, in order to derive new periodic solutions (chronotrees). We conclude with some philosophical ideas regarding Leibniz geometric monad in the sense of Euclid which use as an internal principle the plasticity of quadrilaterals.     

Representation of convex geometries by circles on the plane

Convex geometries are closure systems satisfying the anti-exchange axiom. Every finite convex geometry can be embedded into a convex geometry of finitely many points in an $n$-dimensional space equipped with a convex hull operator, by the result of Kashiwabara et al. (2005). Allowing circles rather than points, as was suggested by Czédli (2014), may presumably reduce the dimension for representation. This paper introduces a property, the Weak 2 × 3-Carousel rule, which is satisfied by all convex geometries of circles on the plane, and we show that it does not hold in all finite convex geometries. This raises a number of representation problems for convex geometries, which may allow us to better understand the properties of Euclidean space related to its dimension.     

Order Types of Convex Bodies

We prove a Hadwiger transversal-type result, characterizing convex position on a family of non-crossing convex bodies in the plane. This theorem suggests a definition for the order type of a family of convex bodies, generalizing the usual definition of order type for point sets. This order type turns out to be an oriented matroid. We also give new upper bounds on the Erdős–Szekeres theorem in the context of convex bodies.     

Global error bounds for piecewise convex polynomials

In this paper, by examining the recession properties of convex polynomials, we provide a necessary and sufficient condition for a piecewise convex polynomial to have a Hölder-type global error bound with an explicit Hölder exponent. Our result extends the corresponding results of Li (SIAM J Control Optim 33(5):1510–1529, 1995) from piecewise convex quadratic functions to piecewise convex polynomials.     

Convex analysis treated by linear programming

The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham).     

Inequalities for Convex Hulls of Random Points

 We prove an estimate for the probability that the convex hull of j independent random points is disjoint from the convex hull of k further independent random points chosen in a plane convex body.     

Polyominoes Determined by Permutations: Enumeration via Bijections

A permutominide is a set of cells in the plane satisfying special connectivity constraints and uniquely defined by a pair of permutations. It naturally generalizes the concept of permutomino, recently investigated by several authors and from different points of view [1, 2, 4, 6, 7]. In this paper, using bijective methods, we determine the enumeration of various classes of convex permutominides, including, parallelogram, directed convex, convex, and row convex permutominides. As a corollary we have a bijective proof for the number of convex permutominoes, which was still an open problem.     

Evaluating inclusion functionals for random convex hulls

Summary The inclusion functional of a random convex set, evaluated at a fixed convex set K, measures the probability that the random convex set contains K. This functional is an analogue of the complement of the distribution function of an ordinary random variable. A methodology is described for evaluating the inclusion functional for the case where the random convex set is generated as the convex hull of n i.i.d. points from a distribution function F in the plane. For general K and F, the inclusion probability is difficult to compute in closed form. The case where K is a straight line segment is examined in detail and, in this situation, a simple answer is given for an interesting class of distributions F.     

Second-order global optimality conditions for convex composite optimization

In recent years second-order sufficient conditions of an isolated local minimizer for convex composite optimization problems have been established. In this paper, second-order optimality conditions are obtained of aglobal minimizer for convex composite problems with a non-finite valued convex function and a twice strictly differentiable function by introducing a generalized representation condition. This result is applied to a minimization problem with a closed convex set constraint which is shown to satisfy the basic constraint qualification. In particular, second-order necessary and sufficient conditions of a solution for a variational inequality problem with convex composite inequality constraints are obtained. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Obstacle Numbers of Graphs

An obstacle representation of a graph G is a drawing of G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of G is the smallest number of obstacles (convex obstacles) in any obstacle representation of G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex k-gon if and only if it is a circular arc graph with clique covering number at most k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with a single segment obstacle if and only if it is the complement of an interval bigraph.