Modules invariant under automorphisms of their covers and envelopes

In this paper we develop a general theory of modules which are invariant under automorphisms of their covers and envelopes. When applied to specific cases like injective envelopes, pure-injective envelopes, cotorsion envelopes, projective covers, or flat covers, these results extend and provide a much more succinct and clear proofs for various results existing in the literature. Our results are based on several key observations on the additive unit structure of von Neumann regular rings.     

Explicit convex and concave envelopes through polyhedral subdivisions

In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of concave-extendable supermodular functions and the convex envelopes of disjunctive convex functions.     

On the Construction of Convex and Concave Envelope Formulas for Bilinear and Fractional Functions on Quadrilaterals

Convex and concave envelopes play important roles in various types of optimization problems. In this article, we present a result that gives general guidelines for constructing convex and concave envelopes of functions of two variables on bounded quadrilaterals. We show how one can use this result to construct convex and concave envelopes of bilinear and fractional functions on rectangles, parallelograms and trapezoids. Applications of these results to global optimization are indicated.     

Some results on the strength of relaxations of multilinear functions

We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yields the convex and concave envelopes if the bounds on all variables are symmetric around zero. We then review and extend some results on conditions when the concave envelope of a multilinear function can be written as a sum of concave envelopes of its individual terms. Finally, for bilinear functions we prove that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is always within a constant of the difference between the concave and convex envelopes. These results, along with numerical examples we provide, give insight into how to construct strong relaxations of multilinear functions.     

Convex envelopes generated from finitely many compact convex sets

We consider the problem of constructing the convex envelope of a lower semi-continuous function defined over a compact convex set. We formulate the envelope representation problem as a convex optimization problem for functions whose generating sets consist of finitely many compact convex sets. In particular, we consider nonnegative functions that are products of convex and component-wise concave functions and derive closed-form expressions for the convex envelopes of a wide class of such functions. Several examples demonstrate that these envelopes reduce significantly the relaxation gaps of widely used factorable relaxation techniques.     

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.     

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.     

Prox-regular functions in Hilbert spaces

This paper studies the prox-regularity concept for functions in the general context of Hilbert space. In particular, a subdifferential characterization is established as well as several other properties. It is also shown that the Moreau envelopes of such functions are continuously differentiable.     

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.     

Convex underestimation for posynomial functions of positive variables

The approximation of the convex envelope of nonconvex functions is an essential part in deterministic global optimization techniques (Floudas in Deterministic Global Optimization: Theory, Methods and Application, 2000). Current convex underestimation algorithms for multilinear terms, based on arithmetic intervals or recursive arithmetic intervals (Hamed in Calculation of bounds on variables and underestimating convex functions for nonconvex functions, 1991; Maranas and Floudas in J Global Optim 7:143–182, (1995); Ryoo and Sahinidis in J Global Optim 19:403–424, (2001)), introduce a large number of linear cuts. Meyer and Floudas (Trilinear monomials with positive or negative domains: Facets of convex and concave envelopes, pp. 327–352, (2003); J Global Optim 29:125–155, (2004)), introduced the complete set of explicit facets for the convex and concave envelopes of trilinear monomials with general bounds. This study proposes a novel method to underestimate posynomial functions of strictly positive variables.     

Weakly tight functions, their Jordan type decomposition and total variation in effect algebras

In the present paper, we have studied envelopes of a function m defined on a subfamily E (containing 0 and 1) of an effect algebra L. The notion of a weakly tight function is introduced and its relation to tight functions is investigated; examples and counterexamples are constructed for illustration. A Jordan type decomposition theorem for a locally bounded real-valued weakly tight function m defined on E is established. The notions of total variation |m| on the subfamily E and m-atoms on a sub-effect algebra E (along with a few examples of m-atoms for null-additive as well as non null-additive functions) are introduced and studied. Finally, it is proved for a real-valued additive function m on a sub-effect algebra E that, m is non-atomic if and only if its total variation |m| is non-atomic.     

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.     

Subdifferential characterization of s-lower regular functions

As for Moreau envelopes of primal lower nice as well as prox-regular functions, Moreau s-envelopes of s-lower regular functions have been proved recently to have several remarkable differential properties and to have many important applications. Here, we provide a subdifferential characterization of extended real-valued s-lower regular functions on Banach spaces in terms of a hypomonotonicity-like property of the subdifferential.     

Approximation of the steepest descent direction for the O-D matrix adjustment problem

In this paper, a method to approximate the directions of Clarke's generalized gradient of the upper level function for the demand adjustment problem on traffic networks is presented. Its consistency is analyzed in detail. The theoretical background on which this method relies is the known property of proximal subgradients of approximating subgradients of proximal bounded and lower semicountinuous functions using the Moreau envelopes. A double penalty approach is employed to approximate the proximal subgradients provided by these envelopes. An algorithm based on partial linearization is used to solve the resulting nonconvex problem that approximates the Moreau envelopes, and a method to verify the accuracy of the approximation to the steepest descent direction at points of differentiability is developed, so it may be used as a suitable stopping criterion. Finally, a set of experiments with test problems are presented, illustrating the approximation of the solutions to a steepest descent direction evaluated numerically. Research supported under Spanish CICYT project TRA99-1156-C02-02.     

Banach envelopes of vector valued H spaces

In the paper we describe the Banach envelopes of Hardy spaces of analytic functions of several variables on polydiscs taking values in quasi-Banach spaces.     

DISTRIBUTION OF MULTIPLICATIVE FUNCTIONS DEFINED ON SEMIGROUPS

Abstract

The value distribution problem for real-valued multiplicative functions defined on an additive arithmetical semigroup is examined. We prove that, in contrast to the classical theory of number-theoretic functions defined on the semigroup of natural numbers, this problem is equivalent to that for additive functions only under some extra condition. In this way, applying the known results for additive functions we derive general sufficient conditions for the existence of a limit law for appropriately normalized multiplicative functions.     

A remark on polyconvex envelopes of radially symmetric functions in dimension 2 × 2

We study polyconvex envelopes of a class of functions related to the function of Kohn and Strang introduced in [4]. We present an example of a function of this class for which the polyconvex envelope may be computed explicitly and we also point out some general features of the problem.     

RELAXATION OF FUNCTIONALS INVOLVING HOMOGENEOUS FUNCTIONS AND INVARIANCE OF ENVELOPES

51. IntroductionWe denote by Mm. the space of real m x n matrices. Let U' bc a function defined onM.., with values in R and n be a bounded domain in Wt. The basic problenl of the Calculusof Variations consists in minirnizing such energy functionals asI(u) = f I+'(vu(x))dx, (1.l)jt, I+'(vu(x))ax, (1.l)where u is a mapping from t1 into R"' belonging to some subset of a Sobolcv space. Inthis context, 7u designates the gradicnt of u, i.e., the m x 1l matrix witll components(7u)ij = % l where …