Skip to Main content Skip to Navigation
Journal articles

Inscribed ball and enclosing box methods for the convex maximization problem

Abstract : Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.
Document type :
Journal articles
Complete list of metadatas
Contributor : Équipe Hal Uvsq <>
Submitted on : Wednesday, June 26, 2019 - 5:15:50 PM
Last modification on : Friday, January 10, 2020 - 3:42:22 PM



Guillaume Guerard, Ider Tseveendorj. Inscribed ball and enclosing box methods for the convex maximization problem. Optimization Letters, Springer Verlag, 2016, 10 (2), pp.417-432. ⟨10.1007/s11590-015-0981-5⟩. ⟨hal-02166374⟩



Record views