I'm looking to describe the feasible set of $x_1, \ldots, x_n$ for the following inequality:

$$a_1\cos x_1 + a_2\cos x_2 + \cdots+ a_n\cos x_n \ge 0$$

For variables $x_1, \ldots, x_n$ restricted to domain $-k\pi \le x_i \le k\pi$ , $k \ge 1$ an integer, and $a_i$ are real numbers.

Is this even possible to describe analytically?

EDIT - I should mention that numerical methods would be very welcome as well. For example, if the problem could somehow be split up into finding $x$ satisfying the intersection of a bunch of convex sets that would be fantastic.

  • $\begingroup$ What if you let $w_i = a_i \cos x_i$? Then you have $\Sigma_i w_i \geq 0$, and $|w_i| \leq a_i$ for all $i$. $\endgroup$ – Théophile Feb 11 '15 at 18:11
  • $\begingroup$ What if $a_i \lt 0$? Then the absolute sign constraint can't be met. $\endgroup$ – JDS Feb 11 '15 at 21:45
  • 1
    $\begingroup$ Right, I meant $|w_i| \leq |a_i|$. Then from any solution to this system, you can retrieve values for the $x_i$. $\endgroup$ – Théophile Feb 12 '15 at 16:42
  • $\begingroup$ How does that condition imply the original equation is $\ge 0$? Want to post an answer explaining more in depth how to find $x$? Thanks for the ideas. $\endgroup$ – JDS Feb 12 '15 at 20:38

Not an answer, but to get some intuition on what kind of regions you might get it is useful to take the simplest cases $n=2$ and $n=3$ and just plot the regions.

Below is a plot of the allowed region for two choices of $a = (a_1,a_2)$ for $n=2$ and two choices of $a=(a_1,a_2,a_3)$ for $n=3$. We see that depening on the vector $a$ the regions go from being a tilted chess-board (when $a$ is tilted $45^\circ$ wrt the coordinate axes) to stripes (in the limit of $a$ being aligned with one of the coordinate axes).

The Mathematica code to do this is for $n=2$:

a = {1, -1};

v = {Cos[x], Cos[y]};

f[x_, y_] = If[a.v < 0, -1, 1];

ContourPlot[f[x, y], {x, -10, 10}, {y, -10, 10}, Contours -> {0.0}]

and for $n=3$ use

ContourPlot3D[f[x, y, z], {x, -10, 10}, {y, -10, 10}, {z, -10, 10}, Contours -> {0.0}]

$$(a_1,a_2) = \{1,-1\}$$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

$$(a_1,a_2) = \{1,1/2\}$$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

$$(a_1,a_2,a_3) = \{1,1,-2\}$$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

$$(a_1,a_2,a_3) = \{2,1,1\}$$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here


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.