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? \begin{cases} &-\pi\leq t_r\leq\pi,\ r=0,\ldots,m-1,\\ &0<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})=w\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})=w\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. \end{cases}
- $\begingroup$ Invariably, more information lead to a better solution... $\endgroup$copper.hat– copper.hat2012-07-20 17:26:39 +00:00Commented Jul 20, 2012 at 17:26
1 Answer
The suggestions certainly will depend on the form of the problems.
If your constraints are linear inequalities then there are simple methods (linear programming) which will check feasibility. If they are polynomial (in)equalities, there are general methods for quantifier elimination like cylindrical algebraic decomposition, but these methods are usually only tractable for very small problems. For certain intermediate cases you may be able to cast your problem as a semidefinite program. For more complicated problems, like inequalities that involve polynomials but also the sine function, the problem quickly becomes provably undecidable without additional structure.
If your problem is one of the former types, a google search of the mentioned methods will find you free software to solve it.
- $\begingroup$ My cases are the "more complicated problems". They contain linear and quadratic inequalities/equalities but also sine and cosine functions $\endgroup$Binzhou Xia– Binzhou Xia2012-07-20 15:20:52 +00:00Commented Jul 20, 2012 at 15:20
- $\begingroup$ Ok, then it really will depend on the precise structure. I'd suggest adding to your post as much information as you have about the exact form of the functions. $\endgroup$Noah Stein– Noah Stein2012-07-20 16:55:10 +00:00Commented Jul 20, 2012 at 16:55
- $\begingroup$ Thank you for your suggestion. I have added to my post the precise structure, where I use a lot of sine and cosine functions. If replacing $\cos t_r$ and $\sin t_r$ by $x_r$ and $y_r$ respectively, the corresponding constraints will become polynomials, but the form will also become longer. $\endgroup$Binzhou Xia– Binzhou Xia2012-07-21 02:59:23 +00:00Commented Jul 21, 2012 at 2:59