# Linearizing a constraint with square root of a variable

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $$A,C,D,T\in\mathbb{R}^+$$. The set $$\mathcal{J}$$ is polynomially-sized.

\begin{alignat}2\min &\quad \sum_{j\in\mathcal{J}}\left(Cb_j+D\lambda_j\right)\tag1\\ \text{s.t.}&\quad b_j\geq T\lambda_j+A\sqrt{T\lambda_j}\qquad j\in\mathcal{J}\tag2\\ &\quad \lambda_j,b_j\in \mathbb{R}^+.\end{alignat}

Seeing this post and the McCormick Envelope, I tried to implement it but did not seem to work as expected. Can you please help me debug where I am doing wrong? First, I re-write (2) as $$b_j\geq T\lambda_j+Ae_j$$, where $$e_j=\sqrt{T\lambda_j}$$. Then, squaring both sides, I get $$f_j=T\lambda_j$$, where $$f_j=e_j^2$$. Under these conditions and assuming $$-M_j\leq e_j \leq M_j$$, I replace (2) with the following set of constraints.

\begin{alignat}2 &\quad b_j\geq T\lambda_j+Ae_j\qquad j\in\mathcal{J}\tag3\\ &\quad M_je_j\geq f_j\qquad j\in\mathcal{J}\tag4\\ &\quad f_j\geq T\lambda_j\qquad j\in\mathcal{J}\tag5\\ &\quad M_j^2\geq f_j\qquad j\in\mathcal{J}\tag6\\ &\quad f_j\geq 2M_je_j-M_j^2\qquad j\in\mathcal{J}\tag7\\ &\quad e_j\leq M_j\qquad j\in\mathcal{J}\tag8\\ \end{alignat}

Although I defined $$M_j$$, I cannot define a strict big number for a specific index $$j\in\mathcal{J}$$. So, I assume $$M=M_j$$. Moreover, I use Gurobi to solve this problem and I am open to a quadratic constraint. Indeed, I also tried defining $$e_j e_j \geq T\lambda_j$$ in Gurobi and it also did not work. I assume I made a mistake in that definition.

• First, why have you relaxed the equality $f_j = T\lambda_j$ to an inequality? And exactly what do you mean with "did not seem to work as expected"? Jun 30, 2020 at 6:43
• Did you check the mentioned post? I tried to follow the McCormick envelopes method given in the answers. Jun 30, 2020 at 11:57
• With “did not seem to work expected” I mean $b_j$, $e_j$, and $f_j$ do not get expected values. Specifically, $e_j =\sqrt{f_j}$ does not hold. Jun 30, 2020 at 13:19
• The McCormick envelope provides only a relaxation, so I don't think you should expect the original constraints to hold. Jun 30, 2020 at 15:29
• Oops! I thought It was going to hold the original. Is there any alternative solution? Jun 30, 2020 at 15:39

## 1 Answer

Define $$\mu_i = \sqrt{\lambda_i}$$ and the problem is a convex quadratically constrained problem in $$(b,\mu)$$

• Johan, do you know if Gurobi supports this? If yes, can you please provide a link to an example? Thanks! Jun 30, 2020 at 18:04
• Convex quadratic constraint? Of course. So does Mosek and Cplex. If you use a modelling language (such as YALMIP in MATLAB, disclaimer: developed by me) you simply write b>=T*mu.^2 + Asqrt(T)*mu or similar and you are done Jun 30, 2020 at 18:13
• I guess we do not need a lot of linearization procedures after all. I was using Gurobi 8 and just realized that Gurobi 9.0 does not mind about PSD anymore. Jun 30, 2020 at 21:13
• If you can solve it as a convex problem, you should do so. Keeping the nonconvex model can cause it to go from seconds to days in terms of solution time Jul 1, 2020 at 6:06
• Well, I tried the McCormick envelope and it doesn’t provide the exact solution. So, I had to go with MIQCP formulation and as you said, the solution time for some instances skyrocketed. Jul 2, 2020 at 2:19