Modified Dinkelbach-type algorithm for generalized fractional programs with infinitely many ratios

J. Y. Lin, Ruey-Lin Sheu

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

In this paper, we extend the Dinkelbach-type algorithm of Crouzeix, Ferland, and Schaible to solve minmax fractional programs with infinitely many ratios. Parallel to the case with finitely many ratios, the task is to solve a sequence of continuous minmax problems, P(αk)=min x∈X(maxt∈T[ft(x)- αkgt(x)]), until {αk} converges to the root of P(α)=0. The solution of P(α k ) is used to generate α k+1. However, calculating the exact optimal solution of P(αk ) requires an extraordinary amount of work. To improve, we apply an entropic regularization method which allows us to solve each problem P(α k ) incompletely, generating an approximate sequence {α̃k}, while retaining the linear convergence rate under mild assumptions. We present also numerical test results on the algorithm which indicate that the new algorithm is robust and promising.

Original languageEnglish
Pages (from-to)323-343
Number of pages21
JournalJournal of Optimization Theory and Applications
Volume126
Issue number2
DOIs
Publication statusPublished - 2005 Aug 1

Fingerprint

Fractional
Min-max Problem
Linear Convergence
Regularization Method
Min-max
Convergence Rate
Optimal Solution
Roots
Converge
Regularization
Optimal solution
Convergence rate

All Science Journal Classification (ASJC) codes

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

Cite this

@article{9af1e0e9334049a7abfb049a65182afa,
title = "Modified Dinkelbach-type algorithm for generalized fractional programs with infinitely many ratios",
abstract = "In this paper, we extend the Dinkelbach-type algorithm of Crouzeix, Ferland, and Schaible to solve minmax fractional programs with infinitely many ratios. Parallel to the case with finitely many ratios, the task is to solve a sequence of continuous minmax problems, P(αk)=min x∈X(maxt∈T[ft(x)- αkgt(x)]), until {αk} converges to the root of P(α)=0. The solution of P(α k ) is used to generate α k+1. However, calculating the exact optimal solution of P(αk ) requires an extraordinary amount of work. To improve, we apply an entropic regularization method which allows us to solve each problem P(α k ) incompletely, generating an approximate sequence {α̃k}, while retaining the linear convergence rate under mild assumptions. We present also numerical test results on the algorithm which indicate that the new algorithm is robust and promising.",
author = "Lin, {J. Y.} and Ruey-Lin Sheu",
year = "2005",
month = "8",
day = "1",
doi = "10.1007/s10957-005-4717-z",
language = "English",
volume = "126",
pages = "323--343",
journal = "Journal of Optimization Theory and Applications",
issn = "0022-3239",
publisher = "Springer New York",
number = "2",

}

Modified Dinkelbach-type algorithm for generalized fractional programs with infinitely many ratios. / Lin, J. Y.; Sheu, Ruey-Lin.

In: Journal of Optimization Theory and Applications, Vol. 126, No. 2, 01.08.2005, p. 323-343.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Modified Dinkelbach-type algorithm for generalized fractional programs with infinitely many ratios

AU - Lin, J. Y.

AU - Sheu, Ruey-Lin

PY - 2005/8/1

Y1 - 2005/8/1

N2 - In this paper, we extend the Dinkelbach-type algorithm of Crouzeix, Ferland, and Schaible to solve minmax fractional programs with infinitely many ratios. Parallel to the case with finitely many ratios, the task is to solve a sequence of continuous minmax problems, P(αk)=min x∈X(maxt∈T[ft(x)- αkgt(x)]), until {αk} converges to the root of P(α)=0. The solution of P(α k ) is used to generate α k+1. However, calculating the exact optimal solution of P(αk ) requires an extraordinary amount of work. To improve, we apply an entropic regularization method which allows us to solve each problem P(α k ) incompletely, generating an approximate sequence {α̃k}, while retaining the linear convergence rate under mild assumptions. We present also numerical test results on the algorithm which indicate that the new algorithm is robust and promising.

AB - In this paper, we extend the Dinkelbach-type algorithm of Crouzeix, Ferland, and Schaible to solve minmax fractional programs with infinitely many ratios. Parallel to the case with finitely many ratios, the task is to solve a sequence of continuous minmax problems, P(αk)=min x∈X(maxt∈T[ft(x)- αkgt(x)]), until {αk} converges to the root of P(α)=0. The solution of P(α k ) is used to generate α k+1. However, calculating the exact optimal solution of P(αk ) requires an extraordinary amount of work. To improve, we apply an entropic regularization method which allows us to solve each problem P(α k ) incompletely, generating an approximate sequence {α̃k}, while retaining the linear convergence rate under mild assumptions. We present also numerical test results on the algorithm which indicate that the new algorithm is robust and promising.

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

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

U2 - 10.1007/s10957-005-4717-z

DO - 10.1007/s10957-005-4717-z

M3 - Article

VL - 126

SP - 323

EP - 343

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

IS - 2

ER -