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].

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