Linear-fractional programming: Difference between revisions

Revision as of 10:00, 24 October 2023

Latest revision as of 11:52, 20 August 2025

(5 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Concept in mathematical optimization}}

In [[mathematical optimization]], '''linear-fractional programming''' ('''LFP''') is a generalization of [[linear programming]] (LP). Whereas the objective function in a linear program is a [[linear functional|linear function]], the objective function in a linear-fractional program is a ratio of two linear functions. A linear program can be regarded as a special case of a linear-fractional program in which the denominator is the constant function 1.

Line 14 ⟶ 15:

==Transformation to a linear program==

Any linear-fractional program can be transformed into a linear program, assuming that the feasible region is non-empty and bounded, using the '''Charnes-CooperCharnes–Cooper transformation'''.<ref name="CC" /> The main idea is to introduce a new non-negative variable <math>t </math> to the program which will be used to rescale the constants involved in the program (<math>\alpha, \beta, \mathbf{b}</math>). This allows us to require that the denominator of the objective function (<math>\mathbf{d}^T \mathbf{x} + \beta</math>) equals 1. (To understand the transformation, it is instructive to consider the simpler special case with <math>\alpha = \beta = 0</math>.)

Formally, the linear program obtained via the Charnes-CooperCharnes–Cooper transformation uses the transformed variables <math>\mathbf{y} \in \mathbb{R}^n</math> and <math>t \ge 0 </math>:

:<math>

Line 44 ⟶ 45:

\end{align}

</math>

which is an LP and which coincides with the dual of the equivalent linear program resulting from the Charnes-CooperCharnes–Cooper transformation.

==Properties and algorithms==

The objective function in a linear-fractional problem is both quasiconcave and [[quasiconvex function|quasiconvex]] (hence quasilinear) with a [[monotonicity|monotone]] property, [[pseudoconvex function|pseudoconvexity]], which is a stronger property than [[quasiconvex function|quasiconvexity]]. A linear-fractional objective function is both pseudoconvex and pseudoconcave, hence [[pseudolinear function|pseudolinear]]. Since an LFP can be transformed to an LP, it can be solved using any LP solution method, such as the [[simplex algorithm]] (of [[George B. Dantzig]]),<ref>

Chapter five: {{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-5 |mr=949209}}</ref><ref>{{cite journal| last1=Kruk | first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming |journal=[[SIAM Review]]|volume=41 |year=1999 |issue=4 |pages=795–805 |mr=1723002|jstor=2653207|doi=10.1137/S0036144598335259| bibcode=1999SIAMR..41..795K|citeseerx=10.1.1.53.7355}}

</ref><ref>{{cite journal | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |journal=[[SIAM Review]]|volume=37 |year=1995 |issue=2 |pages=230–234|mr=1343214|jstor=2132826|doi=10.1137/1037046|s2cid=120626738 }}

</ref><ref>{{harvtxt|Murty|1983|loc=Chapter&nbsp;3.20 (pp.&nbsp;160–164) and pp.&nbsp;168 and&nbsp;179}}</ref> the [[criss-cross algorithm]],<ref>{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|issue=1|

Line 68 ⟶ 69:

*{{cite book | last=Stancu-Minasian | first=I. M.| title=Fractional programming: Theory, methods and applications | others=Translated by Victor Giurgiutiu from the 1992 Romanian | series=Mathematics and its applications|volume=409|publisher=Kluwer Academic Publishers Group | ___location=Dordrecht | year=1997 | pages=viii+418 | isbn=978-0-7923-4580-0 | mr=1472981 }}

==Software==

*[http://zeus.nyf.hu/~bajalinov/WinGulf/wingulf.html WinGULF] – educational interactive linear and linear-fractional programming solver with a lot of special options (pivoting, pricing, branching variables, etc.) (dead link)

*JOptimizer – Java convex optimization library (open source)

{{DEFAULTSORT:Linear-Fractional Programming}}