Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Abramova V. V., Dudov S. I., Osipcev M. A. The External Estimate of the Compact Set by Lebesgue Set of the Convex Function. Izv. Sarat. Univ. Math. Mech. Inform., 2020, vol. 20, iss. 2, pp. 142-153. DOI: 10.18500/1816-9791-2020-20-2-142-153

Published online: 
Full text:
(downloads: 45)
Article type: 

The External Estimate of the Compact Set by Lebesgue Set of the Convex Function

Abramova Veronika V., Saratov State University
Dudov Sergey Ivanovitch, Saratov State University
Osipcev Mikhail Anatolievich, Saratov State University

The finite-dimensional problem of embedding a given compact D ⊂ R p into the lower Lebesgue set G(α) = {y ∈ R p : f(y) 6 α} of the convex function f(·) with the smallest value of α due to the offset of D is considered. Its mathematical formalization leads to the problem of minimizing the function φ(x) = max y∈D f(y − x) on R p . The properties of the function φ(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(·) 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 xi to obtain xi+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 Mi = G(ai), where ai = f(xi). The rationale for the convergence for a sequence of approximations to the problem solution is given.

  1. Pschenichnyi B. N. Vypuklyi analiz i ekstremal’nye zadachi [Convex Analysis and Extremal Problems]. Moscow, Nauka, 1980. 320 p. (in Russian).
  2. Demyanov V. F., Vasiliev L. V. Nondifferentiable Optimization. New York, SpringerOptimization Software, 1986. 452 p. (Russ. ed.: Moscow, Nauka, 1981. 384 p.).
  3. Demyanov V. F., Rubinov A. V. Osnovy negladkogo analiza i kvazidifferentsial’noe ischislenie [Elements of nonsmooth analysis and quasidifferential calculus]. Мoscow, Nauka, 1990. 431 p. (in Russian).
  4. Clarke F. H. Optimization and Nonsmooth Analysis. SIAM, 1990. 308 p. (Russ. ed.: Moscow, Nauka, 1988. 280 p.).
  5. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. A survey of optimization techniques for integrated-circuit design. Proceedings of the IEEE, 1981, vol. 69, iss. 10, pp. 1334–1362.
  6. Dudov S. I., Meshchanov V. P. Parametric optimization of the designed devices according to the criteria of cost and quality. Obzory po elektronike. Ser. 1. Elektronika SVCh [Reviews on Electronics. Ser. 1. Electronics Microwave]. Moscow, TsNII “Electronika”, 1990, iss. 1 (1512). 40 p. (in Russian).
  7. Ioffe A. D., Tikhomirov V. M. Theory of extremal problems. Amsterdam, Nord Holland PC, 1979. 460 p. (Russ. ed.: Moscow, Nauka, 1974. 481 p.).
  8. Polovinkin E. S., Balashov M. V. Elementy vypuklogo i sil’no vypuklogo analiza [Elements of convex and strongly convex analysis]. Moscow, Fizmatlit, 2004. 240 p. (in Russian).
  9. Rockafellar R. T. Convex Analysis. Princeton, Princeton Univ. Press, 1970. 472 p. (Russ. ed.: Moscow, Mir, 1973. 340 p.).
  10. Zukhovitski S. I., Avdeeva L. I. Linejnoe i vypukloe programmirovanie [Linear and Convex Programming]. Moscow, Fizmatlit, 1967. 460 p. (in Russian).
  11. Ivanov G. E. Slabo vypuklye funktsii i mnozhestva [Weakly convex sets and functions]. Moscow, Fizmatlit, 2004. 352 p. (in Russian).
  12. Poliak B. T. Introduction to optimization. New York, Optimization Software, 1987. 460 p. (Russ. ed.: Moscow, Nauka, 1983. 384 p.).
  13. Vial J.-P. Strong and weak convexity of set and funtions. Math. Ops. Res., 1983, vol. 8, no. 2, pp. 231–259.
  14. Vasiliev F. P. Metody optimizatsii [Optimization methods]. Moscow, MTsNMO, 2011. 433 p. (in Russian).
  15.  Bronstein E. M. Approximation of convex sets by polytopes. Journal of Mathematical Sciences, 2008, vol. 153, iss. 6, pp. 727–762.