0
$\begingroup$

I encountered a very special optimization problem for a practical application.

We have a variable $$\mathbf{s}=(s_1,s_2,s_3, s_4)^T$$, where $s_i$ can only take $1$ or $-1$, and we also have a constant $$\mathbf{p}=(p_1,p_2,p_3,p_4)^T=(1,-1,1,-1)^T$$. The correlation variables $c_k$'s are defined by

$$c_1=\mathbf{s} \cdot \mathbf{p}$$ $$c_2=\mathbf{s} \cdot (p_2,p_3,p_4,s_1)$$ $$c_3=\mathbf{s} \cdot (p_3,p_4,s_1,s_2)$$ $$c_4=\mathbf{s} \cdot (p_4,s_1,s_2,s_3)$$ where $\cdot$ is the inner product.

Our target is to find the variable $\mathbf{s}$ such that $$ \max(c_1,c_2,c_3,c_4)$$ is minimized.

How can we do this?

Moreover, what if we have the constraint that the numbers of $1$ and $-1$ are same in $\mathbf{s}$?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Are you interested in similar problems, or this exact one? Because simply exhaustive enumeration/comparison of all binary candidate solutions would work in this case. Same with the additional constraint. $\endgroup$ – megas Dec 11 '14 at 6:54
  • $\begingroup$ Yes, we are interested in similar problems. I want to find a closed form/analytical solution. This problem can be done by searching, but as the dimension of the vector increases to a few hundreds, the closed form/analytical solution is meaningful to us. $\endgroup$ – user2008790 Dec 11 '14 at 6:57
  • $\begingroup$ So, the question really is about ${\bf{s}} = \langle s_1, s_2, \ldots s_n \rangle$, with $s_i = \pm 1$? Meanwhile, the entries of ${\bf{p}}$ are alternating between $1$ and $-1$, starting at 1? (Note: does $n$ have to be even?) And then there's $c_1, c_2, \ldots c_n$, where $c_i = {\bf{s}} \cdot \langle p_i, \ldots, p_n, s_1, s_2, \ldots, s_{i-1} \rangle$? And we want to minimize ${\bf{max}}(c_1, \ldots c_n)$? $\endgroup$ – mathmandan Dec 11 '14 at 7:05
  • $\begingroup$ Yes exactly! We have used exhaustive search to find the answer unto n=16. But we need to find an analytical solution. $\endgroup$ – user2008790 Dec 11 '14 at 7:15
  • 1
    $\begingroup$ @Michael I imagine the OP didn't mean "analytical" in any technical sense. However, I definitely agree with your edit removing the "convex" tag. Thanks! $\endgroup$ – mathmandan Dec 11 '14 at 16:08
0
$\begingroup$

I guess I don't have a proof of an optimal $S$, but I do have some suggestions. Let's write $+$ and $-$ for $+1$ and $-1$, respectively.

1) You don't want $S$ to have all $+$'s, since then $S$ will correlate strongly with $DS$, the shift of $S$ down by one place, in which case your $c_{n}$ will be large.

2) You don't want $S = (+++++-----)$ for the same reason. In general you don't want a lot of long uninterrupted strings of $+$'s or $-$'s, or else $c_{n}$ will be large.

3) On the other hand, you don't want $S = (+-+-...+-+-)$ or $(-+-+...-+-+)$. These configurations are undesirable partly because they make $c_1$ or $c_2$ large, but also because an $S$ of either of these forms will correlate strongly with $D^2S$ (the shift of $S$ down by two spots), which would make $c_{n-1}$ large. This suggests that maybe we really don't have to worry too much about $P$, and just concentrate on killing correlations between $S$ and shifts of itself.

4) We don't really want any periodicity at all in $S$, since if $S$ is periodic with period $m$, then $S$ will correlate strongly with $D^mS$, and $c_{n+1-m}$ will be large.

5) The best would be a random $S$, since that would mean that the digits would be uncorrelated, meaning that all the $c_i$'s should be reasonably close to $0$. The more random, the better--that's really what you're looking for!

6) OK, but what's "the most random $S$"? Use your favorite random number generator! Alternatively, here's a suggestion:

Expand $\pi$ in binary notation, and use $+$ for every $0$ and $-$ for every $1$. Here is a reference listing the first binary digits of $\pi$:

http://www.befria.nu/elias/pi/binpi.html

This sequence of $0$'s and $1$'s is guaranteed not to have any persistent periodicity, due to the irrationality of $\pi$.

Apparently the above link was listed among the "ten most useless sites on the Internet", so I am glad to have found a use for it.

$\endgroup$
  • $\begingroup$ Very interesting! We will think about it! $\endgroup$ – user2008790 Dec 13 '14 at 2:08

Your Answer

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

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