Minimization of Concave Functions Subject to Linear Constraints.

摘要

A cutting plane method for minimizing a concave function subject to linear constraints is developed. It consists of three steps: Finding an absolute local minimum;Building a cut that excludes the previous point;Computing a lower bound. The cutting planes are defined by the solution of a linear program. They satisfy a maximality criterion. The lower bounds are computed using a set that encloses the feasible region. The algorithm depends mainly on the dimension of the feasible set. (Author)