View in EDS HTML Full Text PDF Full Text

Convexification techniques for fractional programs.

Saved in:
Bibliographic Details
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.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 187668699
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Convexification techniques for fractional programs.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22He%2C+Taotao%22">He, Taotao</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> hetaotao@sjtu.edu.cn</i><br /><searchLink fieldCode="AR" term="%22Liu%2C+Siyue%22">Liu, Siyue</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> siyueliu@andrew.cmu.edu</i><br /><searchLink fieldCode="AR" term="%22Tawarmalani%2C+Mohit%22">Tawarmalani, Mohit</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> mtawarma@purdue.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. Sep2025, Vol. 213 Issue 1/2, p107-149. 43p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Fractional+programming%22">Fractional programming</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Convex+sets%22">Convex sets</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+optimization%22">Combinatorial optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+simplification%22">Mathematical simplification</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+transformations%22">Mathematical transformations</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=187668699
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10107-024-02131-x
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 43
        StartPage: 107
    Subjects:
      – SubjectFull: Fractional programming
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Convex sets
        Type: general
      – SubjectFull: Combinatorial optimization
        Type: general
      – SubjectFull: Mathematical simplification
        Type: general
      – SubjectFull: Mathematical transformations
        Type: general
      – SubjectFull: Polynomials
        Type: general
    Titles:
      – TitleFull: Convexification techniques for fractional programs.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: He, Taotao
      – PersonEntity:
          Name:
            NameFull: Liu, Siyue
      – PersonEntity:
          Name:
            NameFull: Tawarmalani, Mohit
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 00255610
          Numbering:
            – Type: volume
              Value: 213
            – Type: issue
              Value: 1/2
          Titles:
            – TitleFull: Mathematical Programming
              Type: main
ResultId 1