Technical Note—Construction of Difficult Linearly Constrained Concave Minimization Problems

Given a polytope and an arbitrary subset of its vertices, we show how to construct a differentiable concave function that assumes any arbitrary value (within a specified ε-tolerance) at each vertex of the subset, with each vertex in the subset a strong local constrained minimum. We also show how this construction method can be used to generate test problems for linearly constrained concave minimization algorithms.