 The Supporting Hyperplane Method for Unimodal ProgrammingArthur F. Veinott
Operations Research, 1967, vol. 15, issue 1, 147-152 Abstract: 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. Date: 1967 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:15:y:1967:i:1:p:147-152 Access Statistics for this article More articles in Operations Research from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.