1
$\begingroup$

I have difficulties converting a constraint to a SOC constraint. Here is the full problem:

\begin{align} \text{minimize} &\quad \alpha \nonumber\\ \text{subject to} &\quad \sum_{P_j \in \Pi_i} x_{ij} = 1 & (1)\\ &\quad y_{ik} = \sum_{P_j \in \Pi_i} x_{ij} \mathbf{I}_{L_k \in P_j} & (2)\\ &\quad \sum_{L_k \in P_j} \varepsilon_k \le \epsilon & (3)\\ &\quad \big( 2 \ln\frac{1}{\varepsilon_k} \big) \sum_{F_i} \sigma^2_i y^2_{ik} \le \Big( \alpha C_k - \sum_{F_i} \mu_i y_{ik} \Big)^2 & (4)\\ &\quad 0 \le x_{ij} \le 1 \\ &\quad 0 \le y_{ik} \le 1 \\ &\quad 0 \le \varepsilon_k \le 1 \end{align}

Problem is Constraint (4), which can be stated as below: \begin{equation} \theta \sum_{i} y_i^2 \le u^2, \end{equation} where $0 \le y_i \le 1$, $\theta \ge 0$, and $u \ge 0$ are optimization variables. If $\theta$ was not present, the constraint would be a standard SOC constraint.

I have the following, \begin{align} \theta y_i^2 \le z_i^2 \Rightarrow \sum_{i} z_i^2 \le u^2 \end{align} which is now a SOC constraint, if the following is correct: \begin{align} &\theta y_i^2 \le z_i^2 \\ &\equiv y_i^2 \le \frac{1}{\theta} z_i^2 \\ &\equiv \begin{cases} y_i^2 \le t z_i^2\\ \frac{1}{\theta} \le t \end{cases} \qquad(1)\\ &\equiv \begin{cases} y_i^2 \le t w_i\\ z_i^2 \le w_i\\ 1 \le \theta t \end{cases} \qquad(2) \end{align}

The final system of inequalities can be easily converted to standard cone constraints \begin{equation} \equiv \begin{cases} 4 y_i^2 + (t - w_i)^2 \le (t + w_i)^2\\ 4 z_i^2 + (1 - w_i)^2 \le (1+w_i)^2\\ 4 + (\theta - t)^2 \le (\theta + t)^2 \end{cases} \end{equation}

Question: Are the inequalities in steps (1) and (2) equivalent to the original constraint? Any comment is appreciated.

$\endgroup$
  • $\begingroup$ It seems that $w$ in (2) is not bounded. You want $w_i \leq z_i^2$. I deleted my original answer because it does not apply to your current question. I do not think your constraint is representable. If you show your entire problem, maybe there it can be reformulated. $\endgroup$ – LinAlg Apr 8 '18 at 20:37
  • $\begingroup$ Thanks! Yes, It should be $w_i \le z_i^2$. The rest of the program has only linear constraints. I have updated my question to show the whole program. As you can see, problem is Constraint (4), which is what I have been trying to convert to a SOC constraint. $\endgroup$ – Agha Lub Apr 9 '18 at 3:43
  • $\begingroup$ If $\theta, y, z$ are all variables then $\theta y^2\leq z^2$ is not SOCP representable. If it was, then in conjunction with $z^2\leq y$ you could model $\theta y\leq 1$ which obviously you can't. Your last transformation does not work because the inequality $\frac{1}{\theta}\leq t$ needs to be written the other way around. $\endgroup$ – Michal Adamaszek Apr 9 '18 at 21:01

Your Answer

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

Browse other questions tagged or ask your own question.