Transforming nonlinear optimization problem into linear problem

Question

$$\begin{array}{ll} \text{maximize} & \dfrac{2x_1 - 2x_2 - 2}{x_1 + 3x_2 + 4}\\ \text{subject to} & -x_1 + x_2 \leq 4\\ & 2x_1 + x_2 \leq 14\\ & x_2 \leq 6\\ & x_1 \geq 0\\ & x_2 \geq 0\end{array}$$

I want to obtain a linear problem by introducing new variables. Then it will be possible to solve it. Unfortunately, I have no idea how to introduce these variables.

Answer 1

In general, when we have

$min z=\frac{px+a}{qx+d}$

s.t. $Ax<=b $ , $x>=0$

We changed problem by $z=\frac{1}{qx+d}$ and $y=zx$

Then the original problem changed to:

$ min z= py+az$

s.t.$Ay<=bz$

$qy+dz=1$

$y>=0$

$z>=0$

Answer 2

You can introduce new variables together with equations: $$\cases{x_3 = \phantom{2}x_1+3x_2+4\\x_4 = 2x_1-2x_2-2}$$and you will get:

$$\min\left\{\frac{x_4}{x_3}\right\}$$

which will be achieved (by monotonicity of the $\log$ family of functions), when:

$$\min\{\log(x_4)-\log(x_3)\}$$

Which indeed is linear in the new variables $\cases{x_6=\log(x_4)\\x_5=\log(x_3)}$ : $\min\{1\cdot x_6 - 1\cdot x_5\}$

Now what remains is to find a way to represent the logarithmic function linearly of some suitable representation of $x_3,x_4$ and to linearly fuse all the variables and the constraints. That is a separate (but even more important) problem! Especially if we want to be able to linearize more advanced non-linear functions in the future.