# Linearizing power term in objective function

I would like to linearize $$x^2$$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to MIP if possible. Any help is much appreciated.

• What is the motivation to convert to MIP? – RobPratt Jun 24 '20 at 17:57
• Terms similar to $x^2$ are part of a larger MIP problem and I think the part of the objective function with the power terms are slowing down the solution. So I wanted to see if converting them to pure MIP will reduce the computation time. – S_Scouse Jun 24 '20 at 18:04
• OK, it might help to show the full model. – RobPratt Jun 24 '20 at 18:58
• I am not able to share the full model due to some confidentiality reason. If possible, I would appreciate any method to linearize power terms. – S_Scouse Jun 24 '20 at 19:52

There are two possibilities that come to mind, assuming that $$x$$ is a continuous variable. One is to do a piecewise-linear approximation (leading to an answer that is, well, approximate). The other is to replace $$x^2$$ with a new variable $$z$$ and then, on the fly, add constraints of the form $$z \ge x_0^2 + 2x_0(x-x_0)$$ when a solution is obtained containing $$x_0$$ and $$z_0$$ with $$z_0 \lt x_0^2$$. The latter method is potentially useful if the nature of the model precludes the solver choosing $$z \gt x^2$$. With CPLEX, you can add these constraints in a lazy constraint callback. With a solver that lacks the needed callback structure, you would be in a solve - cut - solve cycle until you got an optimal solution needing no further cuts.
• This is interesting, but I can’t understand why the term $2x_0(x-x_0)$? – Kuifje Jun 25 '20 at 21:21
• @Kuifje: Charitably assuming I did my calculus correctly, that should be the formula for the tangent to $f(x)=x^2$ at $x=x_0$. – prubin Jun 25 '20 at 23:53