# A binary min-max optimization problem

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!

• 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. – megas Dec 11 '14 at 6:54
• 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. – user2008790 Dec 11 '14 at 6:57
• 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)$? – mathmandan Dec 11 '14 at 7:05
• Yes exactly! We have used exhaustive search to find the answer unto n=16. But we need to find an analytical solution. – user2008790 Dec 11 '14 at 7:15
• @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! – mathmandan Dec 11 '14 at 16:08

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.

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