Top Qs
Timeline
Chat
Perspective

Fractional programming

From Wikipedia, the free encyclopedia

Remove ads

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 be real-valued functions defined on a set . Let . The nonlinear program

where on , is called a fractional program.

Remove ads

Concave fractional programs

Summarize
Perspective

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]

If g is affine, the first constraint is changed to and the assumption that g is positive may be dropped. Also, it simplifies to .

Duality

The Lagrangian dual of the equivalent concave program is

Solution methods

One of the most widely used algorithms for solving concave fractional programs is Dinkelbach's method, introduced by Werner Dinkelbach in 1967.[2] It is an iterative approach that transforms the fractional objective into a sequence of simpler parametric programs.

The method defines for a parameter the auxiliary function

The optimal value of the fractional program is the unique value such that . Dinkelbach's algorithm proceeds iteratively:

  1. Start with an initial .
  2. At iteration , solve
  1. Update

The sequence converges superlinearly to the optimal ratio.[3]


Remove ads

Notes

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads