Let $m$ be an even integer greater than $8$. Is there any software I can use to determine for some small $m$ whether the following constraints on $t_0,\ldots,t_{m-1}$ and $w$ have solutions?

$-\pi\leq t_r\leq\pi,\ r=0,\ldots,m-1,$

$0\leq w\leq\frac{1}{m},$

$\sum\limits_{j=1}^{2r-1}\cos(t_j+t_{2r-j})+\sum\limits_{j=2r+1}^{m-1}\cos(t_j+t_{2r+m-j})=2w\cos t_{2r},\ r=1,\ldots,\frac{m}{2}-1,$

$\sum\limits_{j=1}^{2r-1}\sin(t_j+t_{2r-j})+\sum\limits_{j=2r+1}^{m-1}\sin(t_j+t_{2r+m-j})=2w\sin t_{2r},\ r=1,\ldots,\frac{m}{2}-1,$

$t_r+t_{m-r}=0,\ r=1,\ldots,\frac{m}{2},$

$\cos(t_r+t_{\frac{m}{2}+r})=\cos(t_{2r}+rt_0),\ r=1,\ldots,\frac{m}{2}-1,$

$\sin(t_r+t_{\frac{m}{2}+r})=\sin(t_{2r}+rt_0),\ r=1,\ldots,\frac{m}{2}-1,$


  • $\begingroup$ The constraint on $w$ seems to be crucial, otherwise we'd immediately get the trivial solution $w=2$, $t_r=0$ for all $r$. $\endgroup$ – Suvrit Jul 21 '12 at 13:46
  • $\begingroup$ Yes, actually I'm considering how small can $w$ be. $\endgroup$ – Binzhou Xia Jul 22 '12 at 8:45

It seems to me that methods based on interval analysis are very efficient for solving hard constraints satisfaction problems. In particular, SIVIA (Set Inversion Via Interval Analysis) is an algorithm which can approximate using small "boxes" a subset of $\mathbb{R}^n$ satisfying a given set of constraints. It's a branch and bound algorithm, with quite a big complexity, but if the set is actually empty it can answer rather quickly. To be precise, it find an "inner" and an "outer" approximation of this set: if the outer approximation is empty, then your set is guaranteed to be empty, if the inner approximation is non empty then your set is guaranteed to be non empty, otherwise you can't tell and have to try with a higher precision, which increase the computing time and memory usage exponentially.

Unfortunately I'm not aware of an easy to use implementation of this algorithm. There are some links on Luc Jaulin's home page, and I know that there exists various interval libraries for most of programming language and numerical softwares.

  • $\begingroup$ Is the algorithm guaranteed to be convenrgent in theory? I mean does there exist some case such that the algorithm can not tell no matter what precision I make? $\endgroup$ – Binzhou Xia Jul 22 '12 at 13:55
  • 1
    $\begingroup$ Yes, it is theoretically convergent. The point is that if $f$ is an elementary function/operation, then $f$ applied to an interval is not generally an interval. So it's replaced by an "interval valued" function which satisfy some conditions which guarantee that you recover the true function when the size of the interval is small enough. Then the precision of the algorithm is roughly related to the size of boxes you allows at the boundary, i.e. between the inner and outer approximation. $\endgroup$ – Adrien Jul 22 '12 at 15:26
  • 1
    $\begingroup$ As the name suggest, the general goal of SIVIA is to approximate the inverse image of some subset of $\mathbb{R}^k$ by some function, and when the precision goes to 0, the abovementionned conditions implies that bot the inner and the outer approximation goes to the exact set you're looking for. $\endgroup$ – Adrien Jul 22 '12 at 15:28

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.