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 ${\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}}}$

Solution methods

One of the most widely used algorithms for solving concave fractional programs is Dinkelbach's method, introduced by Werner Dinkelbach in 1967. ^[2] It is an iterative approach that transforms the fractional objective into a sequence of simpler parametric programs.

The method defines for a parameter ${\displaystyle \lambda }$ the auxiliary function

${\displaystyle \phi (\lambda )={\underset {{\boldsymbol {x}}\in \mathbf {S} }{\max }}\;{\big (}f({\boldsymbol {x}})-\lambda g({\boldsymbol {x}}){\big )}.}$

The optimal value ${\displaystyle \lambda ^{*}}$ of the fractional program is the unique value such that ${\displaystyle \phi (\lambda ^{*})=0}$. Dinkelbach's algorithm proceeds iteratively:

1. Start with an initial ${\displaystyle \lambda ^{(0)}}$.
2. At iteration ${\displaystyle k}$, solve

${\displaystyle {\boldsymbol {x}}^{(k)}=\arg \max _{{\boldsymbol {x}}\in \mathbf {S} }{\big (}f({\boldsymbol {x}})-\lambda ^{(k)}g({\boldsymbol {x}}){\big )}.}$

1. Update

${\displaystyle \lambda ^{(k+1)}={\tfrac {f({\boldsymbol {x}}^{(k)})}{g({\boldsymbol {x}}^{(k)})}}.}$

The sequence ${\displaystyle (\lambda ^{(k)})}$ converges superlinearly to the optimal ratio. ^[3]

Notes

1. Schaible, Siegfried (1974). "Parameter-free Convex Equivalent and Dual Programs". Zeitschrift für Operations Research. 18 (5): 187–196. doi:10.1007/BF02026600. MR   0351464. S2CID   28885670.
2. Dinkelbach, W. (1967). "On nonlinear fractional programming". Management Science. 13 (7). INFORMS: 492–498. doi:10.1287/mnsc.13.7.492. JSTOR   2627691.
3. Schaible, Siegfried (1995). "Fractional Programming". In Horst, R. and Pardalos, P. M. (ed.). Handbook of Global Optimization. Springer. pp. 495–608. doi:10.1007/978-1-4757-4847-7_14. ISBN   978-1-4757-4849-1.{{cite book}}: Check |isbn= value: checksum (help)

References

• 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. S2CID   28766871.