3
$\begingroup$

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,$

$\cos(\frac{mt_0}{2})=1.$

$\endgroup$
2
  • $\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, 2012 at 13:46
  • $\begingroup$ Yes, actually I'm considering how small can $w$ be. $\endgroup$ Jul 22, 2012 at 8:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Jul 22, 2012 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, 2012 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, 2012 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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