Geodesic
Approximation of the measure of a convex compact set
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 272-279 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TIMM_2017_23_3_a24,
     author = {O. V. Khamisov},
     title = {Approximation of the measure of a convex compact set},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {272--279},
     year = {2017},
     volume = {23},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a24/}
}
TY  - JOUR
AU  - O. V. Khamisov
TI  - Approximation of the measure of a convex compact set
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2017
SP  - 272
EP  - 279
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a24/
LA  - ru
ID  - TIMM_2017_23_3_a24
ER  - 
%0 Journal Article
%A O. V. Khamisov
%T Approximation of the measure of a convex compact set
%J Trudy Instituta matematiki i mehaniki
%D 2017
%P 272-279
%V 23
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a24/
%G ru
%F TIMM_2017_23_3_a24
O. V. Khamisov. Approximation of the measure of a convex compact set. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 272-279. http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a24/

[1] Kolmogorov A.N., Fomin S.V., Elementy teorii funktsii i funktsionalnogo analiza, Nauka, M., 1976, 544 pp. | MR

[2] Shilov G.E., Gurevich B.L., Integral, mera i proizvodnaya, Nauka, M., 1967, 220 pp. | MR

[3] Mikhailov G.A., Voitishek A.V., Chislennoe statisticheskoe modelirovanie. Metody Monte-Karlo, Izd. tsentr “Akademiya”, M., 2006, 368 pp.

[4] Lovasz L., Simonovits M., “Random walks in a convex body and an improved volume algorithm”, Random structures algorithms, 1993, no. 4, 359–412 | DOI | MR | Zbl

[5] Bronshtein E.M., “Approksimatsiya vypuklykh mnozhestv mnogogrannikami”, Sovremennaya matematika. Fundamentalnye napravleniya, 22 (2007), 5–37

[6] Prekopa A., Stochastic programming, Kluwer Acad. Publ., Dordrecht, Boston, 1995, 599 pp. | MR

[7] Norkin V.I., Roenko N.V., “$\alpha$-vognutye funktsii i mery i ikh primeneniya”, Kibernetika i sistemnyi analiz, 1991, no. 6, 77–88 | Zbl

[8] Aschepkov L.T., “O postroenii maksimalnogo kuba, vpisannogo v zadannuyu oblast”, Zhurn. vychisl. matematiki i mat. fiziki, 20:2 (1980), 510–513 | MR

[9] Khachiyan L.G., “Zadacha vychisleniya ob'ema mnogogrannika perechislitelno trudna”, Uspekhi mat. nauk, 44:3 (1989), 179–180 | MR

[10] Tuy H., Al-Khayyal F., Thach P.T., “Monotonic optimization: Branch and cut methods”, Essays and Surveys in Global Optimization, eds. eds. C. Audet, P. Hansen, G. Savard, Springer, Berlin, etc., 2005, 39–78 | DOI | MR | Zbl