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 , … , m {\displaystyle f,g,h_{j},j=1,\ldots ,m} be real-valued functions defined on a set S 0 ⊂ R n {\displaystyle \mathbf {S} _{0}\subset \mathbb {R} ^{n}} . Let S = { x ∈ S 0 : h j ( x ) ≤ 0 , j = 1 , … , m } {\displaystyle \mathbf {S} =\{{\boldsymbol {x}}\in \mathbf {S} _{0}:h_{j}({\boldsymbol {x}})\leq 0,j=1,\ldots ,m\}} . The nonlinear program
maximize x ∈ S f ( x ) g ( x ) , {\displaystyle {\underset {{\boldsymbol {x}}\in \mathbf {S} }{\text{maximize}}}\quad {\frac {f({\boldsymbol {x}})}{g({\boldsymbol {x}})}},}where g ( x ) > 0 {\displaystyle g({\boldsymbol {x}})>0} on S {\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 f , g , h j , j = 1 , … , m {\displaystyle f,g,h_{j},j=1,\ldots ,m} are affine.
Properties
The function q ( x ) = f ( x ) / g ( x ) {\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 y = x g ( x ) ; t = 1 g ( x ) {\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 program1
maximize y t ∈ S 0 t f ( y t ) subject to t g ( y t ) ≤ 1 , t ≥ 0. {\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 t g ( y t ) = 1 {\displaystyle tg({\frac {\boldsymbol {y}}{t}})=1} and the assumption that g is positive may be dropped. Also, it simplifies to g ( y ) = 1 {\displaystyle g({\boldsymbol {y}})=1} .
Duality
The Lagrangian dual of the equivalent concave program is
minimize u sup x ∈ S 0 f ( x ) − u T h ( x ) g ( x ) subject to u i ≥ 0 , i = 1 , … , m . {\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}}}Notes
- 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.
References
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. /wiki/Doi_(identifier) ↩