Convexification techniques for fractional programs.
Saved in:
| Title: | Convexification techniques for fractional programs. |
|---|---|
| Authors: | He, Taotao1 (AUTHOR) hetaotao@sjtu.edu.cn, Liu, Siyue2 (AUTHOR) siyueliu@andrew.cmu.edu, Tawarmalani, Mohit3 (AUTHOR) mtawarma@purdue.edu |
| Source: | Mathematical Programming. Sep2025, Vol. 213 Issue 1/2, p107-149. 43p. |
| Subjects: | Fractional programming, Mathematical optimization, Convex sets, Combinatorial optimization, Mathematical simplification, Mathematical transformations, Polynomials |
| Abstract: | This paper develops a correspondence relating convex hulls of fractional functions with those of polynomial functions over the same domain. Using this result, we develop a number of new reformulations and relaxations for fractional programming problems. First, we relate 0 - 1 problems involving a ratio of affine functions with the boolean quadric polytope, and use inequalities for the latter to develop tighter formulations for the former. Second, we derive a new formulation to optimize a ratio of quadratic functions over a polytope using copositive programming. Third, we show that univariate fractional functions can be convexified using moment hulls. Fourth, we develop a new hierarchy of relaxations that converges finitely to the simultaneous convex hull of a collection of ratios of affine functions of 0 - 1 variables. Finally, we demonstrate theoretically and computationally that our techniques close a significant gap relative to state-of-the-art relaxations, require much less computational effort, and can solve larger problem instances. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | This paper develops a correspondence relating convex hulls of fractional functions with those of polynomial functions over the same domain. Using this result, we develop a number of new reformulations and relaxations for fractional programming problems. First, we relate 0 - 1 problems involving a ratio of affine functions with the boolean quadric polytope, and use inequalities for the latter to develop tighter formulations for the former. Second, we derive a new formulation to optimize a ratio of quadratic functions over a polytope using copositive programming. Third, we show that univariate fractional functions can be convexified using moment hulls. Fourth, we develop a new hierarchy of relaxations that converges finitely to the simultaneous convex hull of a collection of ratios of affine functions of 0 - 1 variables. Finally, we demonstrate theoretically and computationally that our techniques close a significant gap relative to state-of-the-art relaxations, require much less computational effort, and can solve larger problem instances. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 00255610 |
| DOI: | 10.1007/s10107-024-02131-x |
