= Charnes-Cooper transformation
{c}
{wiki}
For <linear-fractional programming> with objective $(c^Tx+\alpha)/(d^Tx+\beta)$ and positive denominator, set
$$
t=\frac1{d^Tx+\beta},\qquad y=tx.
$$
Then $d^Ty+\beta t=1$ and the objective becomes $c^Ty+\alpha t$. An equality $Ax=b$ becomes $Ay=bt$, and an inequality $Gx\le h$ becomes $Gy\le ht$. Nonnegativity of $x$ becomes nonnegativity of $y$.
For $t>0$ the substitution is reversible, with $x=y/t$, and preserves the objective exactly. The usual closed <linear program> allows $t\ge0$. If the original feasible set is nonempty, a feasible transformed point $(y,0)$ is a recession direction: for any original feasible $x_0$, the points $x_0+sy$ are feasible for $s\ge0$, and their ratios tend to $c^Ty$. Thus the closed transformed program preserves the infimum, but a zero-scale optimizer need not produce a finite original optimizer.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§4.3.2, equations (4.32)–(4.33), including the zero-scale recession argument]{ref}
For example, minimize $1/x$ on $x\ge1$. The transformed constraints are $y=1$, $y\ge t$, $t\ge0$ and the objective is $t$. Its minimum occurs at $t=0$, whereas the original infimum zero is approached only as $x\to\infty$. If the original polyhedron is nonempty and bounded, a nonzero recession direction is impossible, excluding this zero-scale case.
Back to article page