O. V. Khamisov. Approximation of the measure of a convex compact set ... P. 272-279.

We consider an approach to constructing upper and lower bounds for the measure of a convex compact set. The approach is based on extremal inscribed and circumscribed parallelepipeds. It is assumed that the measure of a parallelepiped can be easily calculated. It is shown that the problem of constructing an inscribed parallelepiped of maximum volume is reduced to a convex programming problem with exponential number of constraints. In some particular important cases the exponential number of constraints can be avoided. We suggest an algorithm for the iterative inner and outer approximation of a convex compact set by parallelepipeds. The complexity of the algorithm is estimated. The results of a preliminary numerical experiment are given. The possibility of constructing parallelepipeds that are extremal with respect to measure is discussed. Some advantages of the proposed approach are specified in the conclusion.

Keywords: measure, convex compact set, extremal parallelepiped, inner and outer approximation.

The paper was received by the Editorial Office on May, 12, 2017.

Oleg Valer’evich Khamisov, Dr. Phys.-Math. Sci., Melentiev Energy Systems Institute, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: khamisov@isem.irk.ru


1.   Kolmogorov A.N., Fomin S.V. Elements of the theory of functions and functional analysis. (Two volumes in one, translated from the first Russian edition 1957–1961). Martino Fine Books, United States, 2012, 280 p. ISBN: 1614273049 . The 4th edition of Russian text published in Elementy teorii funktsii i funktsional’nogo analiza. Moscow, Nauka Publ., 1976, 544 p.

2.   Shilov G.E., Gurevich B.L. Integral, measure and derivative: A unified approach. (Translated from the first Russian edition 1964). N.J.: Prentice-Hall, Inc., Englewood Cliffs, 1966, 233 p. ISBN: 0486635198 . The 2nd edition of Russian text published inIntegral, mera i proizvodnaya. Moscow, Nauka Publ. 1967, 220 p.

3.   Mikhailov G.A., Voytishek A.V. Chislennoe statisticheskoe modelirovanie. Metody Monte-Karlo. [Numerical Statistical Simulation. Monte Carlo methods]. Moscow: Publ. Center Academy, 2006, 368 p. ISBN: 5-7695-2739-0 .

4.   LovДasz L., Simonovits M. Random walks in a convex body and an improved volume algorithm. Random structures & algorithms, 1993, vol. 4, no. 4, pp. 359–412. doi: 10.1002/rsa.3240040402 .

5.   Bronshtein E.M. Approximation of Convex Sets by Polytopes. J. Math. Sci., 2008, vol. 153, no. 6, pp. 727–762. doi: 10.1007/s10958-008-9144-x .

6.   PrДekopa A. Stochastic Programming. Dordrecht, Boston, Kluwer Acad. Publ., 1995, 599 p.
ISBN: 0792334825 .

7.   Norkin V.I., Roenko, N.V. α-concave functions and measures and their applications. Cybern. Syst. Anal., 1991, vol. 27, no. 6, pp. 860–869. doi: 10.1007/BF01246517 .

8.   Ashchepkov L.T. Construction of the maximum cube inscribed in a given domain. U.S.S.R. Comput. Math. Math. Phys., 1980, vol. 20, no. 2, pp. 245–249. doi: 10.1016/0041-5553(80)90039-7 .

9.   Khachiyan L.G. The problem of calculating the volume of a polyhedron is enumerably hard. Russian Math. Surveys, 1989, vol. 44, no. 3, pp. 199–200. doi: 10.1070/RM1989v044n03ABEH002136 .

10.   Tuy H., Al-Khayyal F., Thach P.T. Monotonic optimization: Branch and cut methods. In: Essays and Surveys in Global Optimization, C. Audet, P. Hansen, G. Savard (eds.), Berlin: Springer, 2005, pp. 39–78. doi: 10.1007/0-387-25570-2_2 .