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.

Bibliographie

[1] Pschenichnyi B. N., Convex Analysis and Extremal Problems, Nauka, M., 1980, 320 pp. (in Russian) | MR

[2] Demyanov V. F., Vasiliev L. V., Nondifferentiable Optimization, Springer-Optimization Software, New York, 1986, 452 pp. | MR | MR

[3] Demyanov V. F., Rubinov A. V., Elements of nonsmooth analysis and quasidifferential calculus, Nauka, M., 1990, 431 pp. (in Russian)

[4] Clarke F. H., Optimization and Nonsmooth Analysis, SIAM, 1990, 308 pp. | MR | Zbl

[5] Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L., “A survey of optimization techniques for integrated-circuit design”, Proceedings of the IEEE, 69:10 (1981), 1334–1362 | DOI

[6] Dudov S. I., Meshchanov V. P., “Parametric optimization of the designed devices according to the criteria of cost and quality”, Reviews on Electronics. Ser. 1. Electronics Microwave, 1 (1512), TsNII “Electronika”, M., 1990, 40 pp. (in Russian)

[7] Ioffe A. D., Tikhomirov V. M., Theory of extremal problems, Nord Holland PC, Amsterdam, 1979, 460 pp. | MR | Zbl

[8] Polovinkin E. S., Balashov M. V., Elements of convex and strongly convex analysis, Fizmatlit, M., 2004, 240 pp. (in Russian)

[9] Rockafellar R. T., Convex Analysis, Princeton Univ. Press, Princeton, 1970, 472 pp. | MR | Zbl

[10] Zukhovitski S. I., Avdeeva L. I., Linear and Convex Programming, Fizmatlit, M., 1967, 460 pp. (in Russian)

[11] Ivanov G. E., Weakly convex sets and functions, Fizmatlit, M., 2004, 352 pp. (in Russian)

[12] Poliak B. T., Introduction to optimization, Optimization Software, New York, 1987, 460 pp. | MR | MR

[13] Vial J.-P., “Strong and weak convexity of set and funtions”, Math. Ops. Res., 8:2 (1983), 231–259 | DOI | MR | Zbl

[14] Vasiliev F. P., Optimization methods, MTsNMO, M., 2011, 433 pp. (in Russian)

[15] Bronstein E. M., “Approximation of convex sets by polytopes”, Journal of Mathematical Sciences, 153:6 (2008), 727–762 | DOI | MR | Zbl