Optimization Online


On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley's Cutting Plane Algorithm

Felipe Serrano(serrano***at***zib.de)
Robert Schwarz(schwarz***at***zib.de)
Ambros Gleixner(gleixner***at***zib.de)

Abstract: Recently, Kronqvist et al.rediscovered the supporting hyperplane algorithm of Veinott 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 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 general, not necessarily convex, differentiable functions that satisfy a mild condition.

Keywords: Convex MINLP, Cutting plane algorithms, Supporting hyperplane algorithm

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: ZIB Report 19-18, Zuse Institute Berlin

Download: [PDF]

Entry Submitted: 05/20/2019
Entry Accepted: 05/20/2019
Entry Last Modified: 05/20/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society