(449c) Convex Envelopes of Product-Separable Edge-Concave Functions for Global Optimization

Convex underestimators are utilized by deterministic global optimization algorithms to relax nonconvex functions. The convergence of these algorithms relies heavily on the tightness of underestimators relative to the original nonconvex functions. We focus on a broad class of functions which have a vertex polyhedral convex envelope over a polytope domain and thus have exploitable special structure with a finite generating set [1,2]. A quite general sufficient condition for a function to have a vertex polyhedral convex envelope is for it to be edge-concave, that is, for it to be concave along the edge directions of the domain [3,4]. This class of functions includes many functional forms prevalent in chemical engineering applications, such as the set of all concave functions, the set of all multilinear functions, and many signomial functional forms over a box domain [5,6].

We present the explicit convex envelopes of edge-concave functions over a box which are product-separable, a condition which has been conjectured to apply to all non-concave edge-concave functions [3]. We defined conditions applicable to component univariate functions to qualify and classify product-separable edge-concave functions. The complexity of this diverse class of functions was reduced by grouping functions by the characteristics of their component univariate functions. The facets of the convex envelopes of every group are then determined by using the appropriate triangulation of the domain into simplices [7,8]. This procedure results in the explicit convex envelope represented by facets which are easily utilized in an optimization modeling platform or global optimization algorithm.

References:

1. Falk, J. E., & Hoffman, K. R. (1976). A successive underestimation method for concave minimization problems. Mathematics of operations research, 1(3), 251-259.

2. Rikun, A. D. (1997). A convex envelope formula for multilinear functions. Journal of Global Optimization, 10(4), 425-437.

3. Tardella, F. (2004). On the existence of polyhedral convex envelopes. In Frontiers in Global Optimization(pp. 563-573). Springer US.

4. Tardella, F. (2008). Existence and sum decomposition of vertex polyhedral convex envelopes. Optimization Letters, 2(3), 363-375.

5. Meyer, C. A., & Floudas, C. A. (2005). Convex envelopes for edge-concave functions. Mathematical programming, 103(2), 207-224.

6. Misener, R., & Floudas, C. A. (2012). Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Mathematical programming, 136(1), 155-182.

7. Meyer, C. A., & Floudas, C. A. (2004). Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes. In Frontiers in global optimization(pp. 327-352). Springer US.

8. Meyer, C. A., & Floudas, C. A. (2004). Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes. Journal of Global Optimization, 29(2), 125-155.