The modified method of refined bounds for polyhedral approximation of convex polytopes. (Russian, English) Zbl 1164.90425

Lotov, A. V.; Pospelov, A. I.

Zh. Vychisl. Mat. Mat. Fiz. 48, No. 6, 990-998 (2008); translation in Comput. Math. Math. Phys. 48, No. 6, 933-941 (2008).

Summary: The modified method of refined bounds is proposed and experimentally studied. This method is designed to iteratively approximate convex multidimensional polytopes with a large number of vertices. Approximation is realized by a sequence of convex polytopes with a relatively small but gradually increasing number of vertices. The results of an experimental comparison between the modified and the original methods of refined bounds are presented. The latter was designed for the polyhedral approximation of multidimensional convex compact bodies of general type.

MSC:

90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

polyhedral approximation; convex polytopes; convex polyhedra; iteration; convergence rate