linear-fractional programming
   HOME

TheInfoList



OR:

In
mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, linear-fractional programming (LFP) is a generalization of
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
(LP). Whereas the objective function in a linear program is a
linear function In mathematics, the term linear function refers to two distinct but related notions: * In calculus and related areas, a linear function is a function (mathematics), function whose graph of a function, graph is a straight line, that is, a polynomia ...
, the objective function in a linear-fractional program is a ratio of two linear functions. A linear program can be regarded as a special case of a linear-fractional program in which the denominator is the constant function one.


Relation to linear programming

Both linear programming and linear-fractional programming represent optimization problems using linear equations and linear inequalities, which for each problem-instance define a
feasible set In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...
. Fractional linear programs have a richer set of objective functions. Informally, linear programming computes a policy delivering the best outcome, such as maximum profit or lowest cost. In contrast, a linear-fractional programming is used to achieve the highest ''ratio'' of outcome to cost, the ratio representing the highest efficiency. For example, in the context of LP we maximize the objective function profit = income − cost and might obtain maximum profit of $100 (= $1100 of income − $1000 of cost). Thus, in LP we have an efficiency of $100/$1000 = 0.1. Using LFP we might obtain an efficiency of $10/$50 = 0.2 with a profit of only $10, but only requiring $50 of investment.


Definition

Formally, a linear-fractional program is defined as the problem of maximizing (or minimizing) a ratio of
affine function In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generally, ...
s over a
polyhedron In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on th ...
, : \begin \text \quad & \frac \\ \text \quad & A\mathbf \leq \mathbf, \end where \mathbf \in \mathbb^n represents the vector of variables to be determined, \mathbf, \mathbf \in \mathbb^n and \mathbf \in \mathbb^m are vectors of (known) coefficients, A \in \mathbb^ is a (known) matrix of coefficients and \alpha, \beta \in \mathbb are constants. The constraints have to restrict the
feasible region In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...
to \, i.e. the region on which the denominator is positive. Alternatively, the denominator of the objective function has to be strictly negative in the entire feasible region.


Transformation to a linear program

Under the assumption that the feasible region is non-empty and bounded, the Charnes-Cooper transformation :\mathbf = \frac \cdot \mathbf\;;\;\; t = \frac translates the linear-fractional program above to the equivalent linear program: : \begin \text \quad & \mathbf^T \mathbf + \alpha t \\ \text \quad & A\mathbf \leq \mathbf t \\ & \mathbf^T \mathbf + \beta t = 1 \\ & t \geq 0. \end Then the solution for \mathbf and t yields the solution of the original problem as :\mathbf=\frac\mathbf.


Duality

Let the dual variables associated with the constraints A\mathbf - \mathbf t \leq \mathbf and \mathbf^T \mathbf + \beta t - 1 = 0 be denoted by \mathbf and \lambda, respectively. Then the dual of the LFP above is : \begin \text \quad & \lambda \\ \text \quad & A^T\mathbf + \lambda \mathbf = \mathbf \\ & -\mathbf^T \mathbf + \lambda \beta \geq \alpha \\ & \mathbf \in \mathbb_+^m, \lambda \in \mathbb, \end which is an LP and which coincides with the dual of the equivalent linear program resulting from the Charnes-Cooper transformation.


Properties and algorithms

The objective function in a linear-fractional problem is both quasiconcave and
quasiconvex In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form (-\infty,a) is a convex set. For a function of a single ...
(hence quasilinear) with a
monotone Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony. Monotone or monotonicity may also refer to: In economics *Monotone preferences, a property of a consumer's preference ordering. *Monotonic ...
property,
pseudoconvexity In mathematics, more precisely in the theory of functions of several complex variables, a pseudoconvex set is a special type of open set in the ''n''-dimensional complex space C''n''. Pseudoconvex sets are important, as they allow for classificatio ...
, which is a stronger property than quasiconvexity. A linear-fractional objective function is both pseudoconvex and pseudoconcave, hence pseudolinear. Since an LFP can be transformed to an LP, it can be solved using any LP solution method, such as the
simplex algorithm In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
(of
George B. Dantzig George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics. Dantzig is known for his ...
), the
criss-cross algorithm In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective ...
, or
interior-point method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...
s.


Notes


References

* * * * *


Further reading

* * * * *


Software


WinGULF
– educational interactive linear and linear-fractional programming solver with a lot of special options (pivoting, pricing, branching variables, etc.) *JOptimizer – Java convex optimization library (open source) {{DEFAULTSORT:Linear-Fractional Programming Optimization algorithms and methods Linear programming Generalized convexity