On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm
- Recently, Kronqvist et al. (J Global Optim 64(2):249–272, 2016) rediscovered the supporting hyperplane algorithm of Veinott (Oper Res 15(1):147–152, 1967) and demonstrated its computational benefits for solving convex mixed integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm (J Soc Ind Appl Math 8(4):703–712, 1960) applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by a class of general, not necessarily convex nor differentiable, functions.
| Author: | Felipe SerranoORCiD, Robert SchwarzORCiD, Ambros GleixnerORCiD |
|---|---|
| Document Type: | Article |
| Parent Title (English): | Journal of Global Optimization |
| Volume: | 78 |
| First Page: | 161 |
| Last Page: | 179 |
| Year of first publication: | 2020 |
| Preprint: | urn:nbn:de:0297-zib-73253 |
| DOI: | https://doi.org/10.1007/s10898-020-00906-y |
