5
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Commented Jun 30, 2020 at 6:43
  • $\begingroup$ Did you check the mentioned post? I tried to follow the McCormick envelopes method given in the answers. $\endgroup$
    – tcokyasar
    Commented Jun 30, 2020 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$
    – tcokyasar
    Commented Jun 30, 2020 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
    Commented Jun 30, 2020 at 15:29
  • $\begingroup$ Oops! I thought It was going to hold the original. Is there any alternative solution? $\endgroup$
    – tcokyasar
    Commented Jun 30, 2020 at 15:39

1 Answer 1

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Johan, do you know if Gurobi supports this? If yes, can you please provide a link to an example? Thanks! $\endgroup$
    – tcokyasar
    Commented Jun 30, 2020 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$ Commented Jun 30, 2020 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$
    – tcokyasar
    Commented Jun 30, 2020 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$ Commented Jul 1, 2020 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$
    – tcokyasar
    Commented Jul 2, 2020 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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