Minimization of Isotonic Functions Composed of Fractions

J. Y. Lin, S. Schaible, Ruey-Lin Sheu

Research output: Contribution to journalArticle

Abstract

In this paper, we introduce a class of minimization problems whose objective function is the composite of an isotonic function and finitely many ratios. Examples of an isotonic function include the max-operator, summation, and many others, so it implies a much wider class than the classical fractional programming containing the minimax fractional program as well as the sum-of-ratios problem. Our intention is to develop a generic "Dinkelbach-like" algorithm suitable for all fractional programs of this type. Such an attempt has never been successful before, including an early effort for the sum-of-ratios problem. The difficulty is now overcome by extending the cutting plane method of Barros and Frenk (in J. Optim. Theory Appl. 87:103-120, 1995). Based on different isotonic operators, various cuts can be created respectively to either render a Dinkelbach-like approach for the sum-of-ratios problem or recover the classical Dinkelbach-type algorithm for the min-max fractional programming.

Original languageEnglish
Pages (from-to)581-601
Number of pages21
JournalJournal of Optimization Theory and Applications
Volume146
Issue number3
DOIs
Publication statusPublished - 2010 May 6

Fingerprint

Fractional Programming
Fractional
Cutting Plane Method
Mathematical operators
Operator
Min-max
Minimax
Summation
Minimization Problem
Objective function
Composite
Composite materials
Imply
Class
Fractional programming
Cutting planes

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Control and Optimization
  • Management Science and Operations Research

Cite this

@article{c85e1d9168654445a632e2de39df9fb5,
title = "Minimization of Isotonic Functions Composed of Fractions",
abstract = "In this paper, we introduce a class of minimization problems whose objective function is the composite of an isotonic function and finitely many ratios. Examples of an isotonic function include the max-operator, summation, and many others, so it implies a much wider class than the classical fractional programming containing the minimax fractional program as well as the sum-of-ratios problem. Our intention is to develop a generic {"}Dinkelbach-like{"} algorithm suitable for all fractional programs of this type. Such an attempt has never been successful before, including an early effort for the sum-of-ratios problem. The difficulty is now overcome by extending the cutting plane method of Barros and Frenk (in J. Optim. Theory Appl. 87:103-120, 1995). Based on different isotonic operators, various cuts can be created respectively to either render a Dinkelbach-like approach for the sum-of-ratios problem or recover the classical Dinkelbach-type algorithm for the min-max fractional programming.",
author = "Lin, {J. Y.} and S. Schaible and Ruey-Lin Sheu",
year = "2010",
month = "5",
day = "6",
doi = "10.1007/s10957-010-9684-3",
language = "English",
volume = "146",
pages = "581--601",
journal = "Journal of Optimization Theory and Applications",
issn = "0022-3239",
publisher = "Springer New York",
number = "3",

}

Minimization of Isotonic Functions Composed of Fractions. / Lin, J. Y.; Schaible, S.; Sheu, Ruey-Lin.

In: Journal of Optimization Theory and Applications, Vol. 146, No. 3, 06.05.2010, p. 581-601.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Minimization of Isotonic Functions Composed of Fractions

AU - Lin, J. Y.

AU - Schaible, S.

AU - Sheu, Ruey-Lin

PY - 2010/5/6

Y1 - 2010/5/6

N2 - In this paper, we introduce a class of minimization problems whose objective function is the composite of an isotonic function and finitely many ratios. Examples of an isotonic function include the max-operator, summation, and many others, so it implies a much wider class than the classical fractional programming containing the minimax fractional program as well as the sum-of-ratios problem. Our intention is to develop a generic "Dinkelbach-like" algorithm suitable for all fractional programs of this type. Such an attempt has never been successful before, including an early effort for the sum-of-ratios problem. The difficulty is now overcome by extending the cutting plane method of Barros and Frenk (in J. Optim. Theory Appl. 87:103-120, 1995). Based on different isotonic operators, various cuts can be created respectively to either render a Dinkelbach-like approach for the sum-of-ratios problem or recover the classical Dinkelbach-type algorithm for the min-max fractional programming.

AB - In this paper, we introduce a class of minimization problems whose objective function is the composite of an isotonic function and finitely many ratios. Examples of an isotonic function include the max-operator, summation, and many others, so it implies a much wider class than the classical fractional programming containing the minimax fractional program as well as the sum-of-ratios problem. Our intention is to develop a generic "Dinkelbach-like" algorithm suitable for all fractional programs of this type. Such an attempt has never been successful before, including an early effort for the sum-of-ratios problem. The difficulty is now overcome by extending the cutting plane method of Barros and Frenk (in J. Optim. Theory Appl. 87:103-120, 1995). Based on different isotonic operators, various cuts can be created respectively to either render a Dinkelbach-like approach for the sum-of-ratios problem or recover the classical Dinkelbach-type algorithm for the min-max fractional programming.

UR - http://www.scopus.com/inward/record.url?scp=77956440367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956440367&partnerID=8YFLogxK

U2 - 10.1007/s10957-010-9684-3

DO - 10.1007/s10957-010-9684-3

M3 - Article

VL - 146

SP - 581

EP - 601

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

IS - 3

ER -