In mathematical optimization, fractional programming is a generalization of linear-fractional programming. The objective function in a fractional program is a ratio of two functions that are in general nonlinear. The ratio to be optimized often describes some kind of efficiency of a system.

Definition

Let ${\displaystyle f,g,h_{j},j=1,\ldots ,m}$ be real-valued functions defined on a set ${\displaystyle \mathbf {S} _{0}\subset \mathbb {R} ^{n))$. Let ${\displaystyle \mathbf {S} =\((\boldsymbol {x))\in \mathbf {S} _{0}:h_{j}({\boldsymbol {x)))\leq 0,j=1,\ldots ,m\))$. The nonlinear program

${\displaystyle {\underset ((\boldsymbol {x))\in \mathbf {S} }{\text{maximize))}\quad {\frac {f({\boldsymbol {x)))}{g({\boldsymbol {x))))),}$

where ${\displaystyle g({\boldsymbol {x)))>0}$ on ${\displaystyle \mathbf {S} }$, is called a fractional program.

Concave fractional programs

A fractional program in which f is nonnegative and concave, g is positive and convex, and S is a convex set is called a concave fractional program. If g is affine, f does not have to be restricted in sign. The linear fractional program is a special case of a concave fractional program where all functions ${\displaystyle f,g,h_{j},j=1,\ldots ,m}$ are affine.

Properties

The function ${\displaystyle q({\boldsymbol {x)))=f({\boldsymbol {x)))/g({\boldsymbol {x)))}$ is semistrictly quasiconcave on S. If f and g are differentiable, then q is pseudoconcave. In a linear fractional program, the objective function is pseudolinear.

Transformation to a concave program

By the transformation ${\displaystyle {\boldsymbol {y))={\frac {\boldsymbol {x)){g({\boldsymbol {x)))));t={\frac {1}{g({\boldsymbol {x)))))}$, any concave fractional program can be transformed to the equivalent parameter-free concave program^[1]

${\displaystyle {\begin{aligned}{\underset ((\frac {\boldsymbol {y)){t))\in \mathbf {S} _{0)){\text{maximize))}\quad &tf\left({\frac {\boldsymbol {y)){t))\right)\\{\text{subject to))\quad &tg\left({\frac {\boldsymbol {y)){t))\right)\leq 1,\\&t\geq 0.\end{aligned))}$

If g is affine, the first constraint is changed to ${\displaystyle tg({\frac {\boldsymbol {y)){t)))=1}$ and the assumption that g is positive may be dropped. Also, it simplifies to ${\displaystyle g({\boldsymbol {y)))=1}$.

Duality

The Lagrangian dual of the equivalent concave program is

${\displaystyle {\begin{aligned}{\underset {\boldsymbol {u)){\text{minimize))}\quad &{\underset ((\boldsymbol {x))\in \mathbf {S} _{0)){\operatorname {sup} )){\frac {f({\boldsymbol {x)))-{\boldsymbol {u))^{T}{\boldsymbol {h))({\boldsymbol {x)))}{g({\boldsymbol {x)))))\\{\text{subject to))\quad &u_{i}\geq 0,\quad i=1,\dots ,m.\end{aligned))}$