The Supporting Hyperplane Method for Unimodal Programming

This paper proposes an algorithm for maximizing a linear (unimodal) function over a compact convex set X in n-dimensional Euclidian space. The algorithm is a variant of the cutting-plane method of Cheney and Goldstein and of Kelley. In their method one maximizes the original linear (unimodal) function over successively refined approximations to X. Each approximation is the intersection of finitely many closed half spaces containing X. Any limit point of the sequence of solutions to the approximating problems solves the original problem. The principal new feature of our method is that each successive half space is defined by a hyperplane that supports X at a boundary point (Zoutendijk's MFD method also has this property). The particular boundary point is chosen as the point where the line drawn from a fixed interior point of X to the solution (exterior to X) to the most recent approximating problem pierces the boundary of X. Our method is applicable where X is described as the set on which finitely many unimodal functions are nonnegative. The cutting-plane method is applicable only under the more restrictive assumption that the above functions are concave. Our method is formulated so as to be applicable also to unimodal integer programs.