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.     

Existence and sum decomposition of vertex polyhedral convex envelopes

Convex envelopes are a very useful tool in global optimization. However finding the exact convex envelope of a function is a difficult task in general. This task becomes considerably simpler in the case where the domain is a polyhedron and the convex envelope is vertex polyhedral, i.e., has a polyhedral epigraph whose vertices correspond to the vertices of the domain. A further simplification is possible when the convex envelope is sum decomposable, i.e., the convex envelope of a sum of functions coincides with the sum of the convex envelopes of the summands. In this paper we provide characterizations and sufficient conditions for the existence of a vertex polyhedral convex envelope. Our results extend and unify several results previously obtained for special cases of this problem. We then characterize sum decomposability of vertex polyhedral convex envelopes, and we show, among else, that the vertex polyhedral convex envelope of a sum of functions coincides with the sum of the vertex polyhedral convex envelopes of the summands if and only if the latter sum is vertex polyhedral.     

Convex envelopes for edge-concave functions

Deterministic global optimization algorithms frequently rely on the convex underestimation of nonconvex functions. In this paper we describe the structure of the polyhedral convex envelopes of edge-concave functions over polyhedral domains using geometric arguments. An algorithm for computing the facets of the convex envelope over hyperrectangles in ³ is described. Sufficient conditions are described under which the convex envelope of a sum of edge-concave functions may be shown to be equivalent to the sum of the convex envelopes of these functions.Author to whom all correspondence should be addressed.     

Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques

In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f(x,y) over a hypercube under the assumption that f is concave in x and convex in y.     

A Convex Envelope Formula for Multilinear Functions

Convex envelopes of multilinear functions on a unit hypercube arepolyhedral. This well-known fact makes the convex envelopeapproximation very useful in the linearization of non-linear 0–1programming problems and in global bilinear optimization. This paperpresents necessary and sufficient conditions for a convex envelope to be apolyhedral function and illustrates how these conditions may be used inconstructing of convex envelopes. The main result of the paper is a simpleanalytical formula, which defines some faces of the convex envelope of amultilinear function. This formula proves to be a generalization of the wellknown convex envelope formula for multilinear monomial functions.     

Convex envelopes of separable functions over regions defined by separable functions of the same type

In this paper we derive the convex envelope of separable functions obtained as a linear combination of strictly convex coercive one-dimensional functions over compact regions defined by linear combinations of the same one-dimensional functions. As a corollary of the main result, we are able to derive the convex envelope of any quadratic function (not necessarily separable) over any ellipsoid, and the convex envelope of some quadratic functions over a convex region defined by two quadratic constraints.     

On convex envelopes for bivariate functions over polytopes

In this paper we discuss convex envelopes for bivariate functions, satisfying suitable assumptions, over polytopes. We first propose a technique to compute the value and a supporting hyperplane of the convex envelope over a general two-dimensional polytope through the solution of a three-dimensional convex subproblem with continuously differentiable constraint functions. Then, for quadratic functions as well as for some polynomial and rational ones, again satisfying suitable assumptions, we show how the same computations can be carried out through the solution of a single semidefinite problem.     

Tight convex underestimators for {{\mathcal C}^2}-continuous problems: I. univariate functions

A novel method for the convex underestimation of univariate functions is presented in this paper. The method is based on a piecewise application of the well-known αBB underestimator, which produces an overall underestimator that is piecewise convex. Subsequently, two algorithms are used to identify the linear segments needed for the construction of its -continuous convex envelope, which is itself a valid convex underestimator of the original function. The resulting convex underestimators are very tight, and their tightness benefits from finer partitioning of the initial domain. It is theoretically proven that there is always some finite level of partitioning for which the method yields the convex envelope of the function of interest. The method was applied on a set of univariate test functions previously presented in the literature, and the results indicate that the method produces convex underestimators of high quality in terms of both lower bound and tightness over the whole domain under consideration.     

PTIME Parametric Verification of Safety Properties for Reasonable Linear Hybrid Automata

This paper identifies an industrially relevant class of linear hybrid automata (LHA) called reasonable LHA for which parametric verification of convex safety properties with exhaustive entry states can be verified in polynomial time and time-bounded reachability can be decided in nondeterministic polynomial time for non-parametric verification and in exponential time for parametric verification. Properties with exhaustive entry states are restricted to runs originating in a (specified) inner envelope of some mode-invariant. Deciding whether an LHA is reasonable is shown to be decidable in polynomial time.     

Finite Order Rank-One Convex Envelopes and Computation of Microstructures with Laminates in Laminates

Finite order rank-one convex envelopes are introduced and it is shown that the i-th order laminated microstructures, or laminates in laminates, can be solved by any of the k-th order rank-one convex envelopes with k i. It is also shown that in finite element approximations of microstructures, replacing the non-quasiconvex potential energy density by its k-th order rank-one convex envelope, one can generally obtain sharper numerical results. Especially, for crystalline microstructures with laminates in laminates of order no greater than k + 1, numerical results with up to the computer precision can be obtained. Numerical examples on the first and second order rank-one convex envelopes for the Ericksen-James two-dimensional model for elastic crystals are given. A numerical example on finite element approximations of a crystalline microstructure by using the first order rank-one convex envelope and the periodic relaxation method is also presented. The methods turn out to be very successful for microstructures with laminates in laminates.     

Corrigendum to “The envelope theorem for multiobjective convex programming via contingent derivatives” [J. Math. Anal. Appl. 372 (1) (2010) 197–207]

The aim of this note is to formulate an envelope theorem for vector convex programs. This version corrects an earlier work, “The envelope theorem for multiobjective convex programming via contingent derivatives” by Jiménez Guerra et al. (2010) [3]. We first propose a necessary and sufficient condition allowing to restate the main result proved in the alluded paper. Second, we introduce a new Lagrange multiplier in order to obtain an envelope theorem avoiding the aforementioned error.     

GENERAL INFORMATION

We characterize the convex envelope of a given function f as the unique solution of a convex programming problem. It allows us to build a sequence of convex and polygonal function ^un that converges uniformly to the convex envelope of f.     

Supports and convex envelopes

The construct of anL ₁-Support is extended to the environment of a lower semicontinuous function over a solid, finite union of polytopes by utilizing the convex envelope of the function. The existence of and a characterization for theL ₁-Support of the convex envelope are established. The characterization is solely dependent upon the original function’s characteristics and thus the need to calculate the functional form of the convex envelope explicity is eliminated.     

A convex sets in general position

The notion of convex cones in general position has turned out to be useful in convex programming theory. In this paper we extend the notion to convex sets and give some characterizations which yield a better insight into this concept. We also consider the case of convex sets in S-general position.     

The Moreau envelope function and proximal mapping in the sense of the Bregman distance

In this paper, we explore some properties of the Moreau envelope function e_λf(x) of f and the associated proximal mapping P_λf(x) in the sense of the Bregman distance induced by a convex function g. Precisely, we study the continuity, differentiability, and Clarke regularity of the Moreau envelope function and the upper semicontinuity and single-valuedness of the proximal mapping as well as its relation to the convexity of λf+g, where λ is a positive parameter.     

Integration formulas via the Fenchel subdifferential of nonconvex functions

Starting from explicit expressions for the subdifferential of the conjugate function, we establish in the Banach space setting some integration results for the so-called epi-pointed functions. These results use the ε-subdifferential and the Fenchel subdifferential of an appropriate weak lower semicontinuous (lsc) envelope of the initial function. We apply these integration results to the construction of the lsc convex envelope either in terms of the ε-subdifferential of the nominal function or of the subdifferential of its weak lsc envelope.     

A Lower Bound for the Translative Kissing Numbers of Simplices

H (K) of a d-dimensional convex body K is the maximum number of mutually non-overlapping translates of K that can be arranged so that all touch K. In this paper we show that holds for any d-dimensional simplex (). We also prove similar inequalities for some, more general classes of convex bodies. Received May 18, 1998