A finite method for globally minimizing a concave function over an unbounded polyhedral convex set and its applications (Q1112727)

We present a finite algorithm for globally minimizing a concave function over an arbitrary polyhedral convex set. This algorithm uses a practical and relatively simple technique for determining the vertices and the extreme directions of a polyhedral convex set that is obtained by adding a new linear constraint to a polyhedral convex set with known vertices and extreme directions. We also discuss several particular features of applications of the algorithm to bilinear programming, linear complementarity problems and concave minimization problems with special structure. Some preliminary computational experience is reported.