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.

Achieving maximum ee in multi relay ofdma cellular networks a fractional programming approach

Definition

Let f , g , h j , j = 1 , … , m be real-valued functions defined on a set S 0 ⊂ R n . Let S = { x ∈ S 0 : h j ( x ) ≤ 0 , j = 1 , … , m } . The nonlinear program

maximize x ∈ S f ( x ) g ( x ) ,

where g ( 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 , … , m are affine.

Properties

The function q ( x ) = f ( x ) / g ( 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 ) , any concave fractional program can be transformed to the equivalent parameter-free concave program

maximize y t ∈ S 0 t f ( y t ) subject to t g ( y t ) ≤ 1 , t ≥ 0.

If g is affine, the first constraint is changed to t g ( y t ) = 1 and the assumption that f is nonnegative may be dropped.

Duality

The Lagrangean 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 .

References

Fractional programming Wikipedia

(Text) CC BY-SA