Charnes-Cooper transformation Created 2026-09-24 Updated 2026-11-05
For linear-fractional programming with objective and positive denominator, set
Then 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.
Linear-fractional programming Created 2026-09-24 Updated 2026-11-05
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]
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.
Let be feasible for . Since and , the vector is nonzero. Every entry of is strictly positive and , so every component of is strictly positive. The relation
therefore forces .
Set . Then
so is feasible for , and
Thus every feasible value of is a feasible value of the linear-fractional program . Together with part (i), this proves