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

被引：0
作者：
G. K. Kamenev
机构：
[1] Russian Academy of Sciences,Dorodnicyn Computing Center
来源：
Computational Mathematics and Mathematical Physics | 2008年 / 48卷
关键词：
convex body; polyhedral approximation; algorithm; approximation method; optimal methods; complexity bound; duality;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：376 / 394
页数：18
相关论文
共 31 条
[1]  
Minkowski H.(1903)Volumen und Oberfläche Math. Ann. 57 447-496
[2]  
Kamenev G. K.(1992)On a Class of Adaptive Algorithms for Polyhedral Approximation of Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 32 136-152
[3]  
Kamenev G. K.(2002)Conjugate Adaptive Algorithms for Polyhedral Approximation of Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 42 1351-1367
[4]  
Kamenev G. K.(1993)On the Efficiency of Hausdorff Algorithms for Polyhedral Approximation of Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 33 796-805
[5]  
Kamenev G. K.(1999)Efficient Algorithms for Approximation of Nonsmooth Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 39 446-450
[6]  
Kamenev G. K.(2000)On the Approximation Properties of Nonsmooth Convex Disks Zh. Vychisl. Mat. Mat. Fiz. 40 1464-1474
[7]  
Efremov R. V.(2002)A priori Estimate for Asymptotic Efficiency of One Class of Algorithms for Polyhedral Approximation of Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 42 23-32
[8]  
Kamenev G. K.(2003)A Polyhedral Approximation Method for Convex Bodies That is Optimal with Respect to the Order of the Number of Support and Distance Function Evaluations Dokl. Akad. Nauk 388 309-311
[9]  
Kamenev G. K.(2003)Self-Dual Adaptive Algorithms for Polyhedral Approximation of Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 43 1127-1137
[10]  
Kamenev G. K.(2003)A Priori Estimate for the Efficiency of Adaptive Algorithms for Polyhedral Approximation of Convex Bodies Zh. Vychisl. Mat. Mat. Fiz. 43 149-160
1234