Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10346217 | Computers & Operations Research | 2013 | 13 Pages |
Abstract
This paper considers the problem of minimizing the ordered weighted average (or ordered median) function of finitely many rational functions over compact semi-algebraic sets. Ordered weighted averages of rational functions are, in general, neither rational functions nor the supremum of rational functions so current results available for the minimization of rational functions cannot be applied to handle these problems. We prove that the problem can be transformed into a new problem embedded in a higher dimensional space where it admits a convenient polynomial optimization representation. This reformulation allows a hierarchy of SDP relaxations that approximates, up to any degree of accuracy, the optimal value of those problems. We apply this general framework to a broad family of continuous location problems showing that some difficult problems (convex and non-convex) that up to date could only be solved on the plane and with Euclidean distance can be reasonably solved with different âp-norms in finite dimensional spaces. We illustrate this methodology with some extensive computational results on constrained and unconstrained location problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
VÃctor Blanco, Safae El Haj Ben Ali, Justo Puerto,