Premium
Maximizing the ratio of two convex functions over a convex set
Author(s) -
Benson Harold P.
Publication year - 2006
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20143
Subject(s) - subderivative , mathematical optimization , proper convex function , convex analysis , convex set , mathematics , regular polygon , convex optimization , convex combination , convex hull , linear programming , set (abstract data type) , differentiable function , convex function , computer science , mathematical analysis , geometry , programming language
The purpose of this article is to present an algorithm for globally maximizing the ratio of two convex functions f and g over a convex set X . To our knowledge, this is the first algorithm to be proposed for globally solving this problem. The algorithm uses a branch and bound search to guarantee that a global optimal solution is found. While it does not require the functions f and g to be differentiable, it does require that subgradients of g can be calculated efficiently. The main computational effort of the algorithm involves solving a sequence of subproblems that can be solved by convex programming methods. When X is polyhedral, these subproblems can be solved by linear programming procedures. Because of these properties, the algorithm offers a potentially attractive means for globally maximizing ratios of convex functions over convex sets. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006