Linear-fractional programming: Difference between revisions

Revision as of 17:11, 16 April 2023

Revision as of 17:20, 16 April 2023

Line 1:

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 one1.

==Relation to linear programming==

Line 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-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>.)

Under the assumption that the feasible region is non-empty and bounded, the Charnes-Cooper transformation<ref name="CC"/>

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

:<math>\mathbf{y} = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta} \cdot \mathbf{x}\;;\;\; t = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta}</math>

translates the linear-fractional program above to the equivalent linear program:

:<math>

Line 28 ⟶ 26:

& t \geq 0.

\end{align}

</math>A solution <math>\mathbf{x}</math> to the original linear-fractional program can be translated to a solution of the transformed program via the equalities

</math>

:<math>\mathbf{y} = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta} \cdot \mathbf{x}\;;quad \;text{and} \;quad t = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta}.</math>

ThenConversely, thea solution for <math>\mathbf{y}</math> and <math>t </math> yieldsof the transformed program can be translated to a solution of the original problem asvia

:<math>\mathbf{x}=\frac{1}{t}\mathbf{y}.</math>