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

https://hal.uvsq.fr/hal-02166374
Contributor : Équipe Hal Uvsq <>
Submitted on : Wednesday, June 26, 2019 - 5:15:50 PM
Last modification on : Friday, July 19, 2019 - 1:31:36 AM

Identifiers

Citation

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⟩

Share

Metrics

Record views

25