0

I want to linearize or convexify this following constraint.

Here $c_t$ is binary integer variables, $p_t$ are continuous variable which are bounded. $\gamma$ is a continuous variable. $h_t$ and $V$ are known parameters

$\sum\limits_{t=1}^Tc_t{\rm{log_2}}(1+p_th_t)\le V\gamma$ or

$\prod\limits_{t=1}^T(1+p_th_t)^{c_t}\le 2^{V\gamma}$ or

$\prod\limits_{t=1}^T(1+c_tp_th_t)\le 2^{V\gamma} $

You are welcome to linearize anyone of these three equivalent constraints..

Note: These two constraints are equivalent (only when $c_t\in\{0,1\}$).

For example, Lets say $T=2$, $h=[10 \hspace{3mm}20]$, $V=1.001$ and $0\le p\le 3$

Dimitrios
  • 125
  • Is $V$ a positive constant? Does $\gamma$ enter in any other constraint? – Johan Löfberg Nov 05 '14 at 10:17
  • @JohanLöfberg, yes V is a positive constant (V=1.001). You can also consider its equivalent one. I have updated my question. – Dimitrios Nov 06 '14 at 00:18
  • OK. I see no way to get this into a structured MISOCP model or something like that. Feels intrinsically non-convex (i.e., it is obviously non-convex in this form, and I see no methods to exploit the mixed-integer property to get something which can be represented mixed-integer convex form) – Johan Löfberg Nov 06 '14 at 14:43
  • @JohanLöfberg, Can piece-wise linear approximation be used to make it a MILP? – Dimitrios Nov 10 '14 at 05:34
  • Yes, in the logarithmic form that would rather straightforward – Johan Löfberg Nov 10 '14 at 07:48

1 Answers1

0

We first define $h_0=1$,$(1+p_0)^{c_0}:=2^{-V\gamma}$ and rewrite the first one as:

$$\prod\limits_{i=0}^N(1+p_i h_i)^{c_i}\le 1\tag{1}$$

Similarly We define $h_0=1$,$(1+c_0 p_0 h_0):=2^{-V\gamma}$ and rewrite the second one as:

$$\prod\limits_{i=0}^N(1+c_i p_i h_i)\le 1\tag{2}$$

Hope this method may work for you.

mike
  • 5,604
  • is there anything missing in (2)? What about the binary integer variables? – Dimitrios Nov 05 '14 at 04:07
  • I think, (1) and (2) are still nonlinear or non-convex constraints because of the multiplications of the optimization variables. I am using convex programming tool CVX to solve my problem. It is not possible to put this constraint there because in discipled convex programming concave<=real constant is an invalid constraint. Can you suggest me a different method so that the constraint becomes a linear one..Thanks – Dimitrios Nov 05 '14 at 04:26
  • sorry, I mistyped my constraint...I did some mistake while logarithmic transformation – Dimitrios Nov 05 '14 at 07:48
  • No problem. I updated my answer as well. – mike Nov 05 '14 at 10:08