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.

  • $\begingroup$ 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"? $\endgroup$ – Johan Löfberg Jun 30 '20 at 6:43
  • $\begingroup$ Did you check the mentioned post? I tried to follow the McCormick envelopes method given in the answers. $\endgroup$ – Taner Cokyasar Jun 30 '20 at 11:57
  • $\begingroup$ 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. $\endgroup$ – Taner Cokyasar Jun 30 '20 at 13:19
  • $\begingroup$ The McCormick envelope provides only a relaxation, so I don't think you should expect the original constraints to hold. $\endgroup$ – RobPratt Jun 30 '20 at 15:29
  • $\begingroup$ Oops! I thought It was going to hold the original. Is there any alternative solution? $\endgroup$ – Taner Cokyasar Jun 30 '20 at 15:39

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

  • $\begingroup$ Johan, do you know if Gurobi supports this? If yes, can you please provide a link to an example? Thanks! $\endgroup$ – Taner Cokyasar Jun 30 '20 at 18:04
  • 2
    $\begingroup$ 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 $\endgroup$ – Johan Löfberg Jun 30 '20 at 18:13
  • $\begingroup$ 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. $\endgroup$ – Taner Cokyasar Jun 30 '20 at 21:13
  • $\begingroup$ 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 $\endgroup$ – Johan Löfberg Jul 1 '20 at 6:06
  • $\begingroup$ 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. $\endgroup$ – Taner Cokyasar Jul 2 '20 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.