Duality theory of optimal adaptive methods for polyhedral approximation of convex bodies

G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 3, pp. 397-417

Résumé

A duality theory is developed to describe iterative methods for polyhedral approximation of convex bodies. The various types of approximation problems requiring the application of the duality theory are considered. Based on the theory, approximation methods can be designed for bodies with a dual description (in terms of the support/distance function) and methods can be developed that are optimal in terms of dual complexity characteristics of approximating polytopes (vertices/facets). New optimal methods based on the theory are formulated.

Bibliographie

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

[2] Gruber P. M., “Aspects of approximation of convex bodies”, Handbook of convex geometry, v. A, B, North-Holland, Amsterdam, 1993, 319–345 | MR | Zbl

[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 coals 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 vnutrennei 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] Bronshtein E. M., Ivanov L. D., “O priblizhenii vypuklykh mnozhestv mnogogrannikami”, Sibirskii matem. zhurnal, 26:5 (1975), 1110–1112

[24] Dudley R., “Metric entropy of some classes of sets with differentiable boundaries”, J. Approximat. Theory, 10 (1974), 227–236 ; Corr., ibid 26 (1979), 192–193 | DOI | MR | Zbl | DOI | MR | Zbl

[25] Schneider R., Wieacker J. A., “Approximation of convex bodies by polytopes”, Bull. London Math. Soc., 13 (1981), 149–156 | DOI | MR | Zbl

[26] Brusnikina N. B., Kamenev G. K., “O slozhnosti i metodakh poliedralnoi approksimatsii vypuklykh tel s chastichno gladkoi granitsei”, Zh. vychisl. matem. i matem. fiz., 45:9 (2005), 1555–1565 | MR | Zbl

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

[28] Rokafellar R., Vypuklyi analiz, Mir, M., 1973

[29] Schneider R., Convex bodies: the Brunn–Minkowski theory, Cambridge, 1993 | MR

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

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

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

[33] 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

[34] Efremov P. V., Kamenev G. K., Lotov A. B., “Postroenie ekonomnogo opisaniya mnogogrannika na osnove teorii dvoistvennosti vypuklykh mnozhestv”, Dokl. RAN, 399:5 (2004), 594–596 | MR