Linear-fractional programming minimizes or maximizes a ratio of affine functions over a linear polyhedron, with the denominator required to be positive:For a threshold , the sublevel condition is equivalent to the linear inequality . Its sublevel sets are therefore convex, although the ratio need not be a convex function. The positivity restriction makes this multiplication preserve the inequality direction.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §4.3.2, linear-fractional programs and their linear transformation
The Charnes-Cooper transformation rescales by the denominator and introduces one extra variable to produce a linear program. Positive transformed scale gives an actual original feasible point; zero scale can encode a recession limit and must be interpreted separately when discussing attainment.
For linear-fractional programming with objective and positive denominator, setThen and the objective becomes . An equality becomes , and an inequality becomes . Nonnegativity of becomes nonnegativity of .
For the substitution is reversible, with , and preserves the objective exactly. The usual closed linear program allows . If the original feasible set is nonempty, a feasible transformed point is a recession direction: for any original feasible , the points are feasible for , and their ratios tend to . Thus the closed transformed program preserves the infimum, but a zero-scale optimizer need not produce a finite original optimizer.[ref]
For example, minimize on . The transformed constraints are , , and the objective is . Its minimum occurs at , whereas the original infimum zero is approached only as . If the original polyhedron is nonempty and bounded, a nonzero recession direction is impossible, excluding this zero-scale case.
Articles by others on the same topic
Linear-fractional programming (LFP) is a type of mathematical optimization problem where the objective function is a ratio of linear functions.