0

I have four variables $a,b,c,d$ and I want to know either $a=c$ and $b=d$ holds or $a=d$ and $b=c$ holds or both do not hold. I want to set $t=1$ if either condition holds. Else I want $t=0$.

Is there any way to check which condition holds in convex program by introducing new variables and using only real variables?

I know I can do this by checking $\max(a,b)=\max(c,d)$ and $\min(a,b)=\min(c,d)$. If both hold then I know $a=c$ and $b=d$ or $a=d$ and $b=c$ holds. However there is no natural way to take max or min operation in linear programming. Is there a way around?

Is there a way to modify the following optimization and make it work?

$n_1\leq a,b\leq m_1$ and $n_2\leq c,d\leq m_2$ and minimize $(m_1+m_2)-(n_1+n_2)$ ?

Turbo
  • 6,221
  • Checking if one real number is equal to another real number is dicey. Usually your programming environment has what's called a "machine epsilon", which I'll denote $\varepsilon$. The best way to test if two real variables $x_1$ and $x_2$ are equal is to evaluate $|x_1-x_2|<\varepsilon$. That should do it. – Adrian Keister Apr 30 '18 at 19:14
  • 1
    The condition itself is not convex $(1,0,1,0)$ and $(2,0,0,2)$ satisfy it, but the average $(1.5, 0, 0.5, 1)$ does not. You therefore cannot find a convex representation. – LinAlg Apr 30 '18 at 19:31
  • @LinAlg Thank you that clears it. I am struggling with a related problem. I have a $0/1$ matrix. I want to check if it is rank $1$. Is this possible to do this in convex quadratic program? This seems a possible counter example $A=\begin{bmatrix}0&1\0&0\end{bmatrix}$ and $B=\begin{bmatrix}0&0\1&0\end{bmatrix}$ have rank $1$ while their average is $\begin{bmatrix}0&0.5\0.5&0\end{bmatrix}$ which is of rank $2$ and so there cannot be a convex quadratic program. This example looks sensible. Will this argument suffice? – Turbo Apr 30 '18 at 22:31
  • @LinAlg Also updated problem. Is it not possible for this version also? – Turbo Apr 30 '18 at 23:04
  • I see a few different questions. Minimizing a convex quadratic function under linear constraints is of course convex. A rank-1 constraint is not convex. – LinAlg Apr 30 '18 at 23:15
  • @LinAlg So $n_1\leq a,b\leq m_1$, $n_2\leq c,d\leq m_2$ and minimize $(m_1-m_2)^2+(n_1-n_2)^2$ can be minimized but even if $(m_1-m_2)^2+(n_1-n_2)^2=0$ there is no guarantee the pairs match within the program correct? and so in essence it boils down to saying the cross-checking $a,b$ pair matches $c,d$ pair is not possible with convex quadratic programming. correct? – Turbo May 01 '18 at 00:07
  • Why do you use two different kinds of commas? Are you tricking me? :) – LinAlg May 01 '18 at 00:19
  • @LinAlg Oops I updated in post that removes ambiguous commas. – Turbo May 01 '18 at 00:24
  • You also removed the squares from your question. I do not see how this is related to your original question. – LinAlg May 01 '18 at 01:02
  • @LinAlg if we minimize $m_1+m_2$ we are making $m_1$ and $m_2$ as close as possible to $\max(a,b)$ and $\max(c,d)$ respectively correct? – Turbo May 01 '18 at 01:06
  • right, but there is no guarantee that you will get $m_1=m_2$ – LinAlg May 01 '18 at 13:33

0 Answers0