# Transforming nonlinear optimization problem into linear problem

$$\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.

• Can you please give the source of this problem? Thanks! – Matthew Conroy Nov 18 '17 at 3:30
• There exists $\color{blue}{\texttt{no optimal solution}}$. For any valid value of $x_1$ a greater value of $x_1$ is always valid, which makes the value of the objective function larger. – callculus Nov 18 '17 at 16:02
• In general it is a good idea to look at a (mathematical) problem carefully before thinking of an algorithm. – callculus Nov 18 '17 at 16:11
• @callculus lets pretend we treat everything except $x_1$ to be constant, the quotient will then stagnate at 2 as the limit $\displaystyle\lim_{x_1\to \infty}\frac{2x_1+c_1}{x_1+c_2} = 2$, which clearly does not grow unbounded. – mathreadler Nov 19 '17 at 7:37
• @mathreadler But don´t we need $x_1 \in \mathbb R$ for an optimal solution ? – callculus Nov 19 '17 at 10:41

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$

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.