5

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.

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

1 Answers1

3

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

Johan Löfberg
  • 1,702
  • 5
  • 9
  • Johan, do you know if Gurobi supports this? If yes, can you please provide a link to an example? Thanks! – tcokyasar Jun 30 '20 at 18:04
  • 2
    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>=Tmu.^2 + Asqrt(T)mu or similar and you are done – Johan Löfberg Jun 30 '20 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. – tcokyasar Jun 30 '20 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 – Johan Löfberg Jul 01 '20 at 06: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. – tcokyasar Jul 02 '20 at 02:19
  • McCormick envelope would almost never give a solution to the original problem. That's why it is called a relaxation, and normally is used iteratively as a core step in a global solver. If you solve the convex model I described here, it should not skyrocket as an SOCP is solved in roughly the same order of magnitude as an LP. – Johan Löfberg Jul 02 '20 at 07:03