The initial convergence rate of adaptive methods for polyhedral approximation of convex bodies

G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 763-778

Résumé

The convergence rate at the initial stage is analyzed for a previously proposed class of asymptotically optimal adaptive methods for polyhedral approximation of convex bodies. Based on the results, the initial convergence rate of these methods can be evaluated for arbitrary bodies (including the case of polyhedral approximation of polytopes) and the resources sufficient for achieving optimal asymptotic properties can be estimated.

Bibliographie

[1] Minkowski H., “Volumen und Oberfläche”, Math. Ann., 57 (1903), 447–496 | DOI | MR

[2] Gruber P. M., “Aspects of approximation of convex bodies”, Handbook of Convex Geometry, Ch. 1.10, Elsevier Sci. Publs, 1993, 321–345 | MR

[3] Pontryagin L. S., Boltyanskii V. G., Gamkrelidze R. V., Mischenko E. F., Matematicheskaya teoriya optimalnykh protsessov, Nauka, M., 1969

[4] Lotov A. B., Bushenkov V. A., Kamenev G. K., Chernykh O. L., Kompyuter i poisk kompromissa. Metod dostizhimykh tselei, Nauka, M., 1997

[5] Lotov A. V., Bushenkov V. A., Kamenev G. K., Feasible goals method search for smart decisions, VTs PAH, M., 2001

[6] Lotov A. V., Bushenkov V. A., Kamenev G. K., Interactive decision maps, Approximation and Visualization of Pareto Frontier. Appl. Optimizat., 89, Kluwer Acad. Publs, Boston etc., 2004 | MR | Zbl

[7] Kamenev G. K., “Ob odnom klasse adaptivnykh skhem approksimatsii vypuklykh tel mnogogrannikami”, Matem. modelirovanie i diskretnaya optimizatsiya, VTs AN SSSR, M., 1988, 3–9 | MR

[8] Kamenev G. K., “Ob odnom klasse adaptivnykh algoritmov approksimatsii vypuklykh tel mnogogrannikami”, Zh. vychisl. matem. i matem. fiz., 32:1 (1992), 136–152 | MR

[9] Kamenev G. K., “Sopryazhennye adaptivnye algoritmy poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 42:9 (2002), 1351–1367 | MR | Zbl

[10] Kamenev G. K., “Ob effektivnosti khausdorfovykh algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 33:5 (1993), 796–805 | MR | Zbl

[11] Kamenev G. K., “Effektivnye algoritmy approksimatsii negladkikh vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 39:3 (1999), 446–450 | MR | Zbl

[12] Kamenev G. K., “Ob approksimatsionnykh svoistvakh negladkikh vypuklykh diskov”, Zh. vychisl. matem. i matem. fiz., 40:10 (2000), 1464–1474 | MR | Zbl

[13] Efremov R. V., Kamenev G. K., “Apriornaya otsenka asimptoticheskoi effektivnosti odnogo klassa algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 42:1 (2002), 23–32 | MR | Zbl

[14] Kamenev G. K., “Metod poliedralnoi approksimatsii vypuklykh tel, optimalnyi po poryadku chisla raschetov opornoi i distantsionnoi funktsii”, Dokl. RAN, 388:3 (2003), 309–311 | MR

[15] Kamenev G. K., “Samodvoistvennye adaptivnye algoritmy poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 43:8 (2003), 1123–1137 | MR | Zbl

[16] Efremov R. V., “Apriornaya otsenka effektivnosti adaptivnykh algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 43:1 (2003), 149–160 | MR

[17] Kamenev G. K., Issledovanie iteratsionnykh metodov approksimatsii vypuklykh mnozhestv mnogogrannikami, VTs AN SSSR, M., 1986

[18] Dzholdybaeva S. M., Kamenev G. K., “Chislennoe issledovanie effektivnosti algoritma approksimatsii vypuklykh tel mnogogrannikami”, Zh. vychisl. matem. i matem. fiz., 32:6 (1992), 857–866 | MR | Zbl

[19] Burmistrova L. V., “Eksperimentalnyi analiz novogo adaptivnogo metoda poliedralnoi approksimatsii mnogomernykh vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 43:3 (2003), 328–346 | MR | Zbl

[20] Leikhtveis K., Vypuklye mnozhestva, Nauka, M., 1985 | MR

[21] Kamenev G. K., Metody approksimatsii vypuklykh tel mnogogrannikami i ikh primenenie dlya postroeniya i analiza obobschennykh mnozhestv dostizhimosti, Dis. $\dots$ kand. fiz.-matem. nauk, MFTI, M., 1986, 219 pp.

[22] Button L., Wilker J.-B., “Cutting exponents for polyhedral approximations to convex bodies”, Geometriac Dedicata, 7:4 (1978), 417–430 | MR

[23] Kamenev G. K., “Issledovanie odnogo algoritma approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 34:4 (1994), 608–616 | MR | Zbl

[24] Blyashke V., Krug i shar, Nauka, M., 1967 | MR

[25] Koutroufiotis D., “On Blaschke's rolling theorems”, Arch. Math., 23 (1972), 655–660 | DOI | MR | Zbl

[26] Schneider R., “Closed convex hypersurfaces with curvature restrictions”, Proc. Amer. Math. Soc., 103 (1988), 1201–1204 | DOI | MR | Zbl

[27] Brooks I. N., Strantzen J. B., Blaschke's rolling theorem in $R^n$, Mem. Amer. Math. Soc., 80, no. 405, Providence, 1989, 2–5 pp. | MR

[28] Leichtweiß K., “Convexity and differential geometry”, Handbook of Convex Geometry, Ch. 4.1, Elsevier, Amsterdam, 1993, 1045–1080 | MR