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 [ edit ]
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 [ edit ]
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 [ edit ]
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 [ edit ]
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 program [1]
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 [ edit ]
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}}}
References [ edit ]
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 .