Finitely convergent cutting planes for concave minimization (Q5954662)

The paper concerns the finite convergence of a modified algorithm for the minimization of a concave function \(f:\mathbb{R}^n\to \mathbb{R}\) over a polyhedron \(P\subseteq \mathbb{R}^n\). A standard algorithm eliminates a vertex \(x_0\) of \(P\) by a concavity cut \(c^T(x-x_0)\geq1\) with regard to the smallest cone \(C(x_0)\) vertexed at \(x_0\) and containing \(P\). The modified algorithm eliminates the vertex by a concavity cut \(d^T(x-x_0)\geq1\) with regard to a cone obtained from \(C(x_0)\) by pulling its vertex and base in the direction \(-c\).