A technique to derive the analytical form of convex envelopes for some bivariate functions

In the recent paper (Locatelli and Schoen in Math Program, 2013) it is shown that the value of the convex envelope of some bivariate functions over polytopes can be computed by solving a continuously differentiable convex problem. In this paper we show how this result can be exploited to derive in some cases the analytical form of the envelope. The technique is illustrated through two examples.     

Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes

This paper is about the minimization of Lipschitz-continuous and strongly convex functions over integer points in polytopes. Our results are related to the rate of convergence of a black-box algorithm that iteratively solves special quadratic integer problems with a constant approximation factor. Despite the generality of the underlying problem, we prove that we can find efficiently, with respect to our assumptions regarding the encoding of the problem, a feasible solution whose objective function value is close to the optimal value. We also show that this proximity result is the best possible up to a factor polynomial in the encoding length of the problem.     

An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes

In this paper, we constructively derive an explicit characterization of the convex envelope of a bilinear function over a special type of polytope in ². Our motivation stems from the use of such functions for deriving strengthened lower bounds within the context of a branch-and-bound algorithm for solving bilinear programming problems. For the case of polytopes with no edges having finite positive slopes, that is polytopes with downward sloping edges (which we call D-polytopes), we obtain a direct, explicit characterization of the convex envelope. This case subsumes the analysis of Al-Khayyal and Falk (1983) for constructing the convex envelope of a bilinear function over a rectangle in ². For non-D-polytopes, the analysis is more complex. We propose three strategies for this case based on (i) encasing the region in a D-polytope, (ii) employing a discretization technique, and (iii) providing an explicit characterization over a triangle along with a triangular decomposition approach. The analysis is illustrated using numerical examples.     

On empty convex polytopes

Letn andd be integers,n>d 2. We examine the smallest integerg(n,d) such that any setS of at leastg(n,d) points, in general position in E^d, containsn points which are the vertices of an empty convexd-polytopeP, that is, SintP = 0. In particular we show thatg(d+k, d) = d+2k–1 for 1 k iLd/2rL+1.     

Exponential sums and integrals over convex polytopes

Sechenov Institute of Evolutional Physiology and Biochemistry of RAN. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 26, No. 2, pp. 64–66, April–June, 1992.     

On ray shooting in convex polytopes

LetP be a convex polytope withn facets in the Euclidean space of a (small) fixed dimensiond. We consider themembership problem forP (given a query point, decide whether it lies inP) and theray shooting problem inP (given a query ray originating insideP, determine the first facet ofP hit by it). It was shown in [AM2] that a data structure for the membership problem satisfying certain mild assumptions can also be used for the ray shooting problem, with a logarithmic overhead in query time. Here we show that some specific data structures for the membership problem can be used for ray shooting in a more direct way, reducing the overhead in the query time and eliminating the use of parametric search. We also describe an improved static solution for the membership problem, approaching the conjectured lower bounds more tightly.     

On a class of convex polytopes

Let ℘ denote the class of convex polytopesP having the following property: IfQ ₁ andQ ₂ are any subpolytopes ofP with no vertex in common, thenQ ₁ ∩Q ₂ is either empty or a single point. A characterization of ℘ is given which implies the characterization of strongly positively independent sets due to McKinney, Hansen and Klee.     

On perimeters of sections of convex polytopes

In his book “Geometric Tomography” Richard Gardner asks the following question. Let P and Q be origin-symmetric convex bodies in R³ whose sections by any plane through the origin have equal perimeters. Is it true that P=Q? We show that the answer is “Yes” in the class of origin-symmetric convex polytopes. The problem is treated in the general case of Rn.     

Indecomposable convex polytopes

Shephard has given a criterion for the indecomposability (in the sense of Minkowski addition) of a convex polytope, in terms of strong chains of indecomposable faces joining pairs of vertices. Here, this criterion is weakened, to one involving strongly connected sets of indecomposable faces meeting every facet.     

Barycentric coordinates for convex polytopes

An extension of the standard barycentric coordinate functions for simplices to arbitrary convex polytopes is described. The key to this extension is the construction, for a given convex polytope, of a unique polynomial associated with that polytope. This polynomial, theadjoint of the polytope, generalizes a previous two-dimensional construction described by Wachspress. The barycentric coordinate functions for the polytope are rational combinations of adjoints of various dual cones associated with the polytope.     

Convex envelopes of bivariate functions through the solution of KKT systems

In this paper we exploit a slight variant of a result previously proved in Locatelli and Schoen (Math Program 144:65–91, 2014) to define a procedure which delivers the convex envelope of some bivariate functions over polytopes. The procedure is based on the solution of a KKT system and simplifies the derivation of the convex envelope with respect to previously proposed techniques. The procedure is applied to derive the convex envelope of the bilinear function xy over any polytope, and the convex envelope of functions \(x^n y^m\) over boxes.     

Computing the conjugate of convex piecewise linear-quadratic bivariate functions

We present a new algorithm to compute the Legendre–Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case complexity. We present the algorithm, and illustrate it with numerical examples. We proceed to build a toolbox for convex bivariate PLQ functions by implementing the addition, and scalar multiplication operations. Finally, we compose these operators to compute classical convex analysis operators such as the Moreau envelope, and the proximal average.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

Convex envelopes of products of convex and component-wise concave functions

In this paper, we consider functions of the form f(x,y)=f(x)g(y){\phi(x,y)=f(x)g(y)} over a box, where f(x), x ? \mathbb R{f(x), x\in {\mathbb R}} is a nonnegative monotone convex function with a power or an exponential form, and g(y), y ? \mathbb Rⁿ{g(y), y\in {\mathbb R}^n} is a component-wise concave function which changes sign over the vertices of its domain. We derive closed-form expressions for convex envelopes of various functions in this category. We demonstrate via numerical examples that the proposed envelopes are significantly tighter than popular factorable programming relaxations.