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.     

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.     

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.     

A Shape Optimization Algorithm for Interface Identification Allowing Topological Changes

In this paper, we provide sufficient and necessary conditions for the minimax equality for extended real-valued abstract convex–concave functions. As an application, we get sufficient and necessary conditions for the minimax equality for extended real-valued convex–concave functions.     

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.     

Analysis of Bounds for Multilinear Functions

We analyze four bounding schemes for multilinear functions and theoretically compare their tightness. We prove that one of the four schemes provides the convex envelope and that two schemes provide the concave envelope for the product of p variables over .     

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.     

Solving large-scale minimax problems with the primal—dual steepest descent algorithm

This paper shows that the primal-dual steepest descent algorithm developed by Zhu and Rockafellar for large-scale extended linear—quadratic programming can be used in solving constrained minimax problems related to a generalC ² saddle function. It is proved that the algorithm converges linearly from the very beginning of the iteration if the related saddle function is strongly convex—concave uniformly and the cross elements between the convex part and the concave part of the variables in its Hessian are bounded on the feasible region. Better bounds for the asymptotic rates of convergence are also obtained. The minimax problems where the saddle function has linear cross terms between the convex part and the concave part of the variables are discussed specifically as a generalization of the extended linear—quadratic programming. Some fundamental features of these problems are laid out and analyzed.This work was supported by Eliezer Naddor Postdoctoral Fellowship in Mathematical Sciences at the Department of Mathematical Sciences, the Johns Hopkins University during the year 1991–92.     

Unconstrained 0–1 nonlinear programming: A nondifferentiable approach

The purpose of this paper is to give new formulations for the unconstrained 0–1 nonlinear problem. The unconstrained 0–1 nonlinear problem is reduced to nonlinear continuous problems where the objective functions are piecewise linear. In the first formulation, the objective function is a difference of two convex functions while the other formulations lead to concave problems. It is shown that the concave problems we obtain have fewer integer local minima than has the classical concave formulation of the 0–1 unconstrained 0–1 nonlinear problem.     

On a class of modified Wasserstein distances induced by concave mobility functions defined on bounded intervals

We study a new class of distances between Radon measures similar to those studied in Dolbeault et al. (Calc Var Partial Differ Equ 34:193–231, 2009). These distances (more correctly pseudo-distances because can assume the value +∞) are defined generalizing the dynamical formulation of the Wasserstein distance by means of a concave mobility function. We are mainly interested in the physical interesting case (not considered in Dolbeault et al. (Calc Var Partial Differ Equ 34:193–231, 2009)) of a concave mobility function defined in a bounded interval. We state the basic properties of the space of measures endowed with this pseudo-distance. Finally, we study in detail two cases: the set of measures defined in ${\mathbb{R}^{d}}$ with finite moments and the set of measures defined in a bounded convex set. In the two cases we give sufficient conditions for the convergence of sequences with respect to the distance and we prove a property of boundedness.     

Trilinear Monomials with Mixed Sign Domains: Facets of the Convex and Concave Envelopes

Convex underestimators of nonconvex functions, frequently used in deterministic global optimization algorithms, strongly influence their rate of convergence and computational efficiency. A good convex underestimator is as tight as possible and introduces a minimal number of new variables and constraints. Multilinear monomials over a coordinate aligned hyper-rectangular domain are known to have polyhedral convex envelopes which may be represented by a finite number of facet inducing inequalities. This paper describes explicit expressions defining the facets of the convex and concave envelopes of trilinear monomials over a box domain with bounds of opposite signs for at least one variable. It is shown that the previously used approximations based on the recursive use of the bilinear construction rarely yield the convex envelope itself.     

Embedding optimal transports in statistical manifolds

We consider Monge-Kantorovich optimal transport problems on ? ^d , d ≥ 1, with a convex cost function given by the cumulant generating function of a probability measure. Examples include theWasserstein-2 transport whose cost function is the square of the Euclidean distance and corresponds to the cumulant generating function of the multivariate standard normal distribution. The optimal coupling is usually described via an extended notion of convex/concave functions and their gradient maps. These extended notions are nonintuitive and do not satisfy useful inequalities such as Jensen’s inequality. Under mild regularity conditions, we show that all such extended gradient maps can be recovered as the usual supergradients of a nonnegative concave function on the space of probability distributions. This embedding provides a universal geometry for all such optimal transports and an unexpected connection with information geometry of exponential families of distributions.     

Fuchsian convex bodies: basics of Brunn–Minkowski theory

The hyperbolic space ${\mathbb{H}^d}$ can be defined as a pseudo-sphere in the (d + 1) Minkowski space-time. In this paper, a Fuchsian group Γ is a group of linear isometries of the Minkowski space such that ${\mathbb{H}^d/\Gamma}$ is a compact manifold. We introduce Fuchsian convex bodies, which are closed convex sets in Minkowski space, globally invariant for the action of a Fuchsian group. A volume can be associated to each Fuchsian convex body, and, if the group is fixed, Minkowski addition behaves well. Then Fuchsian convex bodies can be studied in the same manner as convex bodies of Euclidean space in the classical Brunn–Minkowski theory. For example, support functions can be defined, as functions on a compact hyperbolic manifold instead of the sphere. The main result is the convexity of the associated volume (it is log concave in the classical setting). This implies analogs of Alexandrov–Fenchel and Brunn–Minkowski inequalities. Here the inequalities are reversed.     

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.     

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.     

Extended formulations in mixed integer conic quadratic programming

In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.     

A mixed finite element method for thin film epitaxy

We present a mixed finite element method for the thin film epitaxy problem. Comparing to the primal formulation which requires $C^2$ elements in the discretization, the mixed formulation only needs to use $C^1$ elements, by introducing proper dual variables. The dual variable in our method is defined naturally from the nonlinear term in the equation, and its accurate approximation will be essential for understanding the long-time effect of the nonlinear term. For time-discretization, we use a backward-Euler semi-implicit scheme, which involves a convex–concave decomposition of the nonlinear term. The scheme is proved to be unconditionally stable and its convergence rate is analyzed.     

Minimal convex majorants of functions and Demyanov–Rubinov exhaustive super(sub)differentials

ABSTRACT

The primary goal of the paper is to establish characteristic properties of (extended) real-valued functions defined on normed vector spaces that admit the representation as the lower envelope (the pointwise infimum) of their minimal (with respect of the pointwise ordering) convex majorants. The results presented in the paper generalize and extend the well-known Demyanov-Rubinov characterization of upper semicontinuous positively homogeneous functions as the lower envelope of exhaustive families of continuous sublinear functions to larger classes of (not necessarily positively homogeneous) functions defined on arbitrary normed spaces. As applications of the above results, we introduce, for nonsmooth functions, a new notion of the Demyanov-Rubinov exhaustive subdifferential at a given point, and show that it generalizes a number of known notions of subdifferentiability, in particular, the Fenchel-Moreau subdifferential of convex functions, the Dini-Hadamard (directional) subdifferential of directionally differentiable functions, and the Φ-subdifferential in the sense of the abstract convexity theory. Some applications of Demyanov-Rubinov exhaustive subdifferentials to extremal problems are considered.