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.
Contents
Definition
Let be real-valued functions defined on a set . Let . The nonlinear program
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \underset{\boldsymbol{x} \in \mathbf{S}}{\text{maximize}} \quad \frac{f(\boldsymbol{x})}{g(\boldsymbol{x})},
where on , 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 are affine.
Properties
The function 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 , any concave fractional program can be transformed to the equivalent parameter-free concave program [1]
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \begin{align} \underset{\frac{\boldsymbol{y}}{t} \in \mathbf{S}_0}{\text{maximize}} \quad & t f(\frac{\boldsymbol{y}}{t}) \\ \text{subject to} \quad & t g(\frac{\boldsymbol{y}}{t}) \leq 1, \\ & t \geq 0. \end{align}
If g is affine, the first constraint is changed to and the assumption that f is nonnegative may be dropped.
Duality
The Lagrangean dual of the equivalent concave program is
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \begin{align} \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{align}
Notes
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
References
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.