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

2019/05/20 by Serrano, Felipe, Schwarz, Robert, Gleixner, Ambros
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1905.08157

Abstract

Recently, Kronqvist et al.~\citeKronqvistLundellWesterlund2016 rediscovered the supporting hyperplane algorithm of Veinott~\citeVeinott1967 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~\citeJ.E.Kelley1960 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.

Related

• Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets
• A Non-Convex Separation Through an Alternative Proof for the Supporting Hyperplane Theorem
• Geometric Random Edge
• The Cutting Plane Method is Polynomial for Perfect Matchings
• An Algorithmic Separating Hyperplane Theorem and Its Applications