Finitely convergent cutting planes for concave minimization

In 1964 Tuy introduced a new type of cutting plane, the concavity cut, in the context of concave minimization. These cutting planes, which are also known as convexity cuts, intersection cuts and Tuy cuts, have found application in several algorithms, e.g., branch and bound algorithm, conical algorithm and cutting plane algorithm, and also in algorithms for other optimization problems, e.g., reverse convex programming, bilinear programming and Lipschitzian optimization. Up to now, however, it has not been possible to either prove or disprove the finite convergence of a pure cutting plane algorithm for concave minimization based solely on these cutting planes. In the present paper a modification of the concavity cut is proposed that yields deeper cutting planes and ensures the finite convergence of a pure cutting plane algorithm based on these cuts.