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

* 1 Definition
* 2 Concave fractional programs
* 2.1 Properties
* 2.2 Transformation to a concave program
* 2.3 Duality
* 3 Notes
* 4 References

## Definition

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

maximizex∈𝐒f(x)g(x),

where g(x)>0 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 f,g,hj,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=xg(x);t=1g(x), any concave fractional program can be transformed to the equivalent parameter-free concave program[1]

maximizeyt∈𝐒0tf(yt)subject totg(yt)≤1,t≥0.

If g is affine, the first constraint is changed to tg(yt)=1 and the assumption that g is positive may be dropped. Also, it simplifies to g(y)=1.

### Duality

The Lagrangian dual of the equivalent concave program is

minimizeusupx∈𝐒0f(x)−uTh(x)g(x)subject toui≥0,i=1,…,m.

## 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.

## 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.

* v
* t
* e

Major subfields of optimization

* Convex programming
* Integer programming
* Quadratic programming
* Nonlinear programming
* Stochastic programming
* Robust optimization
* Combinatorial optimization
* Infinite-dimensional optimization
* Metaheuristics
* Constraint satisfaction
* Multiobjective optimization

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Fractional programming. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Fractional_programming&oldid=248705"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template