The external estimate of the compact set by Lebesgue set of the convex function

V. V. Abramova ; S. I. Dudov ; M. A. Osiptsev

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 20 (2020) no. 2, pp. 142-153

Résumé

The finite-dimensional problem of embedding a given compact $D \subset \mathbb{R}^p$ into the lower Lebesgue set $G (\alpha) = \{y \in \mathbb{R}^p: f (y) \leqslant \alpha \}$ of the convex function $f(\cdot)$ with the smallest value of $\alpha$ due to the offset of $D$ is considered. Its mathematical formalization leads to the problem of minimizing the function $\phi (x) = \max\limits_{y \in D} f (y - x)$ on $\mathbb{R}^p$. The properties of the function $\phi(x)$ are researched, necessary and sufficient conditions and conditions for the uniqueness of the problem solution are obtained. As an important case for applications, the case when $f(\cdot)$ is the Minkowski gauge function of some convex body $M$ is singled out. It is shown that if $M$ is a polyhedron, then the problem reduces to a linear programming problem. The approach to get an approximate solution is proposed in which, having known the approximation of $x_i$ to obtain $x_{i+1}$ it is necessary to solve the simpler problem of embedding the compact set $D$ into the Lebesgue set of the gauge function of the set $M_i= G(a_i)$, where $a_i = f(x_i )$. The rationale for the convergence for a sequence of approximations to the problem solution is given.