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!
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.