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.

Let ${\displaystyle f,g,h_j,j=1,\dots ,m}$ be real-valued functions defined on a set ${\displaystyle {\mathbf{𝐒}}_0\subset {\mathbb{ℝ}}^n}$. Let ${\displaystyle \mathbf{𝐒}=\{\mathit{x}\in {\mathbf{𝐒}}_0:h_j(\mathit{x})\le 0,j=1,\dots ,m\}}$. The nonlinear program

${\displaystyle \underset{\mathit{x}\in \mathbf{𝐒}}{\text{maximize}}\frac{f(\mathit{x})}{g(\mathit{x})},}$

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

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,\dots ,m}$ are affine.

The function ${\displaystyle q(\mathit{x})=f(\mathit{x})/g(\mathit{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.

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

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

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

The Lagrangian dual of the equivalent concave program is

${\displaystyle \begin{array}{rl}\underset{\mathit{u}}{\text{minimize}}& \underset{\mathit{x}\in {\mathbf{𝐒}}_0}{\sup }\frac{f(\mathit{x})-{\mathit{u}}^T\mathit{h}(\mathit{x})}{g(\mathit{x})}\\ \text{subject to}& u_i\ge 0,i=1,\dots ,m.\end{array}}$

• Avriel, Mordecai; Diewert, Walter E.; Schaible, Siegfried; Zang, Israel (1988). Generalized Concavity. Plenum Press. 
• Schaible, Siegfried (1983). "Fractional programming". Zeitschrift für Operations Research 27: 39–54. doi:10.1007/bf01916898. 

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Fractional programming. Read more