Fractional programming

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 $f,g,h_j,j=1,\dots ,m$ be real-valued functions defined on a set ${𝐒}_0\subset {ℝ}^n$. Let $𝐒=\{𝒙\in {𝐒}_0:h_j(𝒙)\le 0,j=1,\dots ,m\}$. The nonlinear program

$\underset{𝒙\in 𝐒}{\text{maximize}}\frac{f(𝒙)}{g(𝒙)},$

where $g(𝒙)>0$ on $𝐒$, 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 $f,g,h_j,j=1,\dots ,m$ are affine.

Properties

The function $q(𝒙)=f(𝒙)/g(𝒙)$ 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 $𝒚=\frac{𝒙}{g(𝒙)};t=\frac{1}{g(𝒙)}$, any concave fractional program can be transformed to the equivalent parameter-free concave program

$\begin{array}{cc}\underset{\frac{𝒚}{t}\in {𝐒}_0}{\text{maximize}}& tf\left(\frac{𝒚}{t}\right)\\ \text{subject to}& tg\left(\frac{𝒚}{t}\right)\le 1,\\ & t\ge 0.\end{array}$

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

Duality

The Lagrangian dual of the equivalent concave program is

$\begin{array}{cc}\underset{𝒖}{\text{minimize}}& \underset{𝒙\in {𝐒}_0}{\sup }\frac{f(𝒙)-{𝒖}^T𝒉(𝒙)}{g(𝒙)}\\ \text{subject to}& u_i\ge 0,i=1,\dots ,m.\end{array}$

References

• Template:Cite book
• Template:Cite journal