Inscribed ball and enclosing box methods for the convex maximization problem - Université de Versailles Saint-Quentin-en-Yvelines Access content directly
Journal Articles Optimization Letters Year : 2016

Inscribed ball and enclosing box methods for the convex maximization problem

Guillaume Guerard
  • Function : Author
  • PersonId : 1049618

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.
No file

Dates and versions

hal-02166374 , version 1 (26-06-2019)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More