# zbMATH — the first resource for mathematics

On the existence of polyhedral convex envelopes. (English) Zbl 1176.90473
Floudas, Christodoulos A. (ed.) et al., Frontiers in global optimization. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7699-1/hbk). Nonconvex Optim. Appl. 74, 563-573 (2004).
Summary: We address the problem of identifying those functions whose convex envelope on a polyhedron $$P$$ coincides with the convex envelope of their restrictions to the vertices of $$P$$. When this property holds we say that the function has a vertex polyhedral convex envelope.
The interest for identifying this property is due to the fact that if a function has a vertex polyhedral convex envelope on $$P$$, then such a convex envelope can be computed exactly in finite time and it can be expressed as the maximum of a finite family of affine functions. This implies that the minimum of the convex envelope on $$P$$ can be obtained by means of a linear program.
The main results of this paper are the facts that a function $$f$$ has a vertex polyhedral convex envelope on $$P$$ if and only if for every affine function $$g$$, the modified function $$f(x)+g(x)$$ attains its minimum at a vertex of $$P$$ and that this property holds if $$f$$ is edge concave on $$P$$, i.e., concave along all directions parallel to an edge of $$P$$.
We also show that edge concavity of $$f$$ on $$P$$ holds for all classes of functions previously known to admit a vertex polyhedral convex envelope and we describe some new classes of functions for which the existence of a vertex polyhedral convex envelope is guaranteed.
For the entire collection see [Zbl 1031.90001].

##### MSC:
 90C26 Nonconvex programming, global optimization 90C46 Optimality conditions and duality in mathematical programming