Finiteness of conical algorithms with omega-subdivisions
In this paper the problem of finding the global optimum of a concave function over a polytope is considered. A well-known class of algorithms for this problem is the class of conical algorithms. In particular, the conical algorithm based on the so called omega-subdivision strategy is considered. It is proved that, for any given accuracy epsilon > 0, this algorithm stops in a finite time by returning an epsilon-optimal solution for the problem, while it is convergent for epsilon = 0.
conical algorithms omega-subdivisions concave optimization