On convex envelopes for bivariate functions over polytopes (Q2452372)

The concept of convex envelope of a lower semi-continuous function at a point \(x \in P\), where \(P\) is a given polytope in \(\mathbb{R}^n\) is introduced. The paper studies the convex envelope of bi-variate functions over polytopes in \(\mathbb{R}^2\). It is assumed that the Hessian of the functions is indefinite in the interior of \(P\) and the restriction of the functions along each edge of \(P\) is either concave or strictly convex. A method for the computation of the value of the convex envelope over a general two-dimensional polytope at a given point \(x\) is proposed. Further it is shown that the same results can be obtained for quadratic, some polynomial and some rational functions. It is shown that the computations can be carried out by solving a single semi-definite problem. The results can be directly applied to some advanced Branch-and-Bound techniques. The theoretical results are demonstrated on a small numerical example in the Appendix.