Linearizing $x^2/(1-x)$ by partitioning the interval $0<x\le X$

Question

We have two decision variables \begin{align} & 0<x\le X,\\ & 0<y\le Y, \end{align} where both $X$ and $Y$ are two sensible upper bounds on our decision variables.

We also have a constraint

$$y=\frac{x^2}{1-x}.$$

We discretize the interval $(0,X]$ and denote each piece by $r_i$ where $i=1,\ldots,n$ and $n$ is a finite number.

By defining a binary decision variable say $z_i\in\{0,1\}$ where $z_i=1$ if and only if $x\in(r_{i},r_{i+1}]$ and $z_i=0$, otherwise, we linearize this constraint as

$$y=\sum_{i=1}^{n}\left(\frac{r_i^2}{1-r_i}\right)z_i.$$

Now the question is how to determine $n$?

I am also aware that there are other techniques of linearization we would like to focus on this method for the moment.

I'm also sure this method has been used before but I could not find any reference on it, mainly because I don't know if it has a name or where to even look!

Could someone help please?

Answer 1

I assume $X\le1$, since the formulation is infeasible for $x > 1$.

What you are doing is a form of piecewise linear approximation of the function $f(x) = x^2/(1-x)$. Choosing $n$ is a matter of trial and error. Obviously, the larger $n$ is the more accurate the approximation is. Also obvious is that larger $n$ means longer solution time (and more memory usage).

There are a couple of things worth noting. One is that you might (or might not) get a more accurate approximation using $(r_i + r_{i+1})/2$ rather than $r_i$ as the point in interval $i$ where you evaluate $f(x)$. Another is that it is often a good idea to concentrate evaluation points where the function has greatest curvature. So you would shrink the spacing between points as $x$ progressed from 0 to 1.

Addendum: If solution times are fairly brief, one other thing that might be worth trying is to discretize, solve, add break points near the optimal solution (to get a better approximation there) and maybe remove a few breakpoints away from the optimum (to conserve model size), solve again, and repeat until satisfied (or bored).

Answer 2

Have you tried solving the problem directly? This is simply a quadratic non-convex constraint:

$$ y = \frac{x^2}{1-x}\implies y - yx = x^2 $$

So e.g. using Gurobi and Python, you can write:

import gurobipy as gp


m = gp.Model()
x = m.addVar(0, x_ub)
y = m.addVar(0, y_ub)
m.addConstr(y - y*x == x*x)