Premium
Minimizing sums and products of linear fractional functions over a polytope
Author(s) -
Konno Hiroshi,
Yamashita Hajime
Publication year - 1999
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/(sici)1520-6750(199908)46:5<583::aid-nav8>3.0.co;2-5
Subject(s) - polytope , multiplicative function , bounding overwatch , linear programming , mathematics , mathematical optimization , maxima and minima , simple (philosophy) , linear fractional programming , transformation (genetics) , fractional programming , function (biology) , product (mathematics) , computer science , nonlinear programming , combinatorics , nonlinear system , philosophy , artificial intelligence , mathematical analysis , chemistry , biology , biochemistry , geometry , epistemology , quantum mechanics , evolutionary biology , physics , gene
In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999