Fractional programming explained

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 , \ldots, m be real-valued functions defined on a set S _{0} \subset R ^{n} . Let S = \{\boldsymbol{x} \in S _{0:} h _{j(\boldsymbol{x})} \leq 0 , j =1 , \ldots, m\} . The nonlinear program\underset{\boldsymbol{x} \in S } \quad \frac,

where

g(\boldsymbol{x}) > 0 on 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

f, g, h _{j,} j =1 , \ldots, m are affine.

Properties

The function

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

\boldsymbol{y} = (\boldsymbol{x)/() }; t = \frac, any concave fractional program can be transformed to the equivalent parameter-free concave program^[1] \begin{align} \underset{ (\boldsymbol{y)/() } \in \mathbf_0} \quad & t f\left(\frac\right) \\\text \quad & t g\left(\frac\right) \leq 1, \\& t \geq 0.\end

If g is affine, the first constraint is changed to

t g( (\boldsymbol{y)/() }) = 1 and the assumption that g is positive may be dropped. Also, it simplifies to g(\boldsymbol{y}) = 1 .

Duality

The Lagrangian dual of the equivalent concave program is

\begin{align} \underset{\boldsymbol{u}}{ minimize } \quad & \underset \frac \\\text \quad & u_i \geq 0, \quad i = 1,\dots,m.\end

Notes

1. Schaible . Siegfried . Parameter-free Convex Equivalent and Dual Programs. Zeitschrift für Operations Research . 18 . 1974 . 5 . 187–196. 10.1007/BF02026600. 351464. 28885670 .

References

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