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

J. Y. Lin, Ruey-Lin Sheu

研究成果: Article

8 引文 (Scopus)

摘要

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.

原文English
頁(從 - 到)323-343
頁數21
期刊Journal of Optimization Theory and Applications
126
發行號2
DOIs
出版狀態Published - 2005 八月 1

指紋

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

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

引用此文

@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",

}

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

AN - SCOPUS:23844477256

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 -