0

Let $x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]$ where $\alpha$ is a fixed angle $\in(0,\pi/2)$.

The goal For a fixed $(A_{ij})_{1\leq i\leq 4,5\leq j\leq n}\in\{-1,+1\}$, verify whether it holds that \begin{equation}\label{1} \begin{aligned} G\big((A_{ij})_{1\leq i\leq 4,5\leq j\leq n}\big):=\min_{x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]}\max\big\{&\sum_{k=5}^n-A_{1k}\sin x_k+A_{2k}\sin(x_k-\alpha),\\ &\sum_{k=5}^nA_{3k}\sin x_k-A_{4k}\sin(x_k-\alpha),\\ &\sum_{k=5}^nA_{3k}\sin x_k+A_{2k}\sin(x_k-\alpha),\\ &\sum_{k=5}^n-A_{1k}\sin x_k-A_{4k}\sin(x_k-\alpha)\big\}>0 \end{aligned} \end{equation}

The motivation for this problem The original motivation for solving this problem comes from my research problem, where $G>0$ is the condition for a region to be reverse positive invariant in a dynamical system. Since to prove why it is the condition for positive invariant would require a lengthy content, I omit it here.

Perhaps this is the Difficulty: To evalue $G$ involves evaluating maximum between four $n-4$ dimensional functions, which is hard in general. Moreover, this maximum takes different values under different configurations of $(A_{ij})_{1\leq i\leq 4,5\leq j\leq n}\in\{-1,+1\}$ (in fact, there are $2^{4(n-4)}$ configurations), and tt is not possible to compute $G$ for each configuration, since the dimension $n$ is general (I don't fix it as any number).

What I tried on its upper bound I was not able to derive a good lower bound, but it seems dealing its upper bound is easier. I think this might be relevant so I wrote it below.

The max function $F(x_k;A_{ik})$ is upper bounded by \begin{equation} \begin{aligned} F(x_k;A_{ik})\leq \sum_{k=5}^n\max\big\{&-A_{1k}\sin x_k+A_{2k} \sin(x_k-\alpha) ,\\ &A_{3k}\sin x_k-A_{4k}\sin(x_k-\alpha),\\ &A_{3k}\sin x_k+A_{2k}\sin(x_k-\alpha),\\ &-A_{1k}\sin x_k-A_{4k}\sin(x_k-\alpha)\big\} \end{aligned} \end{equation} according to the fact that $\max\{a+c,b+d\}\leq\max\{a,b\}+\max\{c+d\}$ for $a,b,c,d\in\mathbb{R}$, see here.

Thus we have \begin{equation} \begin{aligned} G\leq\min_{x_5,\cdots,x_n\in[0,\alpha]\cap[-\pi,\alpha-\pi]}\sum_{k=5}^n\max\big\{&-A_{1k}\sin x_k+A_{2k} \sin(x_k-\alpha) ,\\ &A_{3k}\sin x_k-A_{4k}\sin(x_k-\alpha),\\ &A_{3k}\sin x_k+A_{2k}\sin(x_k-\alpha),\\ &-A_{1k}\sin x_k-A_{4k}\sin(x_k-\alpha)\big\} \end{aligned} \end{equation} Now we have decoupled the $n-4$ variables, and the summation can be take out:

\begin{equation} \begin{aligned} G\leq\sum_{k=5}^n\min_{x_k\in[0,\alpha]\cap[-\pi,\alpha-\pi]}\max\big\{&-A_{1k}\sin x_k+A_{2k} \sin(x_k-\alpha) ,\\ &A_{3k}\sin x_k-A_{4k}\sin(x_k-\alpha),\\ &A_{3k}\sin x_k+A_{2k}\sin(x_k-\alpha),\\ &-A_{1k}\sin x_k-A_{4k}\sin(x_k-\alpha)\big\} \end{aligned} \end{equation}

This is easier to deal with, because each term in the summation, we can discussion all senarios where $A_{1k},A_{2k},A_{3k},A_{4k}$ take different values (thus there are 16 senarios in total), and compute the term $\min_{x_k\in[0,\alpha]\cap[-\pi,\alpha-\pi]}\max\{\cdots\}$ exactly.

What I tried on its lower bound I obtained a un-meaningful lower bound by using Minmax inequality as follows. \begin{equation}\label{} \begin{aligned} \min_{x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]}\max_{B_1+B_2+B_3+B_4=1,B_i\in\{0,1\}}&B_1\sum_{k=5}^n-A_{1k}\sin x_k+A_{2k}\sin(x_k-\alpha)\\ +&B_2\sum_{k=5}^nA_{3k}\sin x_k-A_{4k}\sin(x_k-\alpha)\\ +&B_3\sum_{k=5}^nA_{3k}\sin x_k+A_{2k}\sin(x_k-\alpha)\\ +&B_4\sum_{k=5}^n-A_{1k}\sin x_k-A_{4k}\sin(x_k-\alpha) \end{aligned} \end{equation}

According to minmax inequality

$$\min_{x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]}\max_{B_1+B_2+B_3+B_4=1,B_i\in\{0,1\}}\geq \max_{B_1+B_2+B_3+B_4=1,B_i\in\{0,1\}}\min_{x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]}$$

Then we can swap $\min$ and $\max$, and by simple analysis we obtain the lower bound \begin{equation}\label{} \begin{aligned} \max_{B_1+B_2+B_3+B_4=1,B_i\in\{0,1\}}\min_{x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]}&B_1\sum_{k=5}^n-A_{1k}\sin x_k+A_{2k}\sin(x_k-\alpha)\\ +&B_2\sum_{k=5}^nA_{3k}\sin x_k-A_{4k}\sin(x_k-\alpha)\\ +&B_3\sum_{k=5}^nA_{3k}\sin x_k+A_{2k}\sin(x_k-\alpha)\\ +&B_4\sum_{k=5}^n-A_{1k}\sin x_k-A_{4k}\sin(x_k-\alpha)\\ \geq &-2\sin\frac{\alpha}{2}(N_{+}^{12}+N_{-}^{34}+N_{+-}^{14}+N_{-}^{12}+N_{+}^{34}+N_{-+}^{14})-\sin\alpha(N_{+}^{12}+N_{+-}^{34}+N_{-}^{14}+N_{+-}^{12}+N_{-+}^{34}+N_{+}^{14}) \end{aligned} \end{equation} which is obviously not larger than zero.

Note that for example, $N_{+}^{12}$ denotes the number of $k$ such that $A_{1k}=1$ and $A_{2k}=1$.

My Question

(1) Is the upper bounding correct? and how much we lost in this step?

(2) Would it be possible to derive a lower bound of $G$ which is easier to compute?

(3) If analytical method would not work, is it possible to come up with a reformulation of the problem such that there exists a good algorithm to verify $G>0$?

M.K
  • 541
  • Hi. I've re-edited my question post, and please review it and perhaps withdraw your decision on "Close" if you find it becomes more clear. Thank you! – M.K Feb 04 '24 at 14:49
  • Your "Find condition on $A$ such that for any $A_{1k},A_{2k},A_{3k},A_{4k}\in{+1,-1},k\in{5,\cdots,n}$ it holds that $G>0$" is unclear. Don't you rather mean "find for which $A_{1k},A_{2k},A_{3k},A_{4k}\in{+1,-1},k\in{5,\cdots,n}$ it holds that $G>0$"? (or better phrased: "find for which $(A_{i,k})\in{+1,-1}^{{1,\dots,4}\times{5,\cdots,n}}$ it holds that $G>0$). – Anne Bauval Feb 04 '24 at 15:18
  • @AnneBauval Hi. Actually it is what I wrote in the post, i.e. find the condition on matrix instead of configuration: find a matrix $A$ such that for its elements $A_{1k},A_{2k},A_{3k},A_{4k}$ $k\in{5,\cdots,n}$ such that $G>0$ holds. So it is not, find configuration $A_{1k},A_{2k},A_{3k},A_{4k}$, $k\in{5,\cdots,n}$ such that $G>0$ holds. – M.K Feb 04 '24 at 15:23
  • Sorry but both means the same (except that there is one excess "such that for its elements A1k,A2k,A3k,A4k $k\in{5,\cdots,n}$" in your first formulation), and they are not what you wrote in the post. This is the reason for my previous comment. Can you please suppress your confusing "for any" in the post? – Anne Bauval Feb 04 '24 at 15:28
  • What you call the converse is the negation. 2) The negation of $G>0$ is not $G<0$ but $G\le0$. 3) Your matrix $A$ is irrelevant here and obscures your post. Better stay with $(A_{i,j}){1\le i\le 4,5\le j\le n}$. 4) Your minus signs in front of $A{1,k}$ and $A_{4,k}$ are also useless distractions. I will drop them in the next point. 5) Let $A_i:=\sum_{j=5}^nA_{i,j}\sin x_j$ if $i\in{1,3}$ and $\sum_{j=5}^nA_{i,j}\sin(x_j-\alpha)$ if $i\in{2,4}$. Note that $\max(A_1+A_2,A_3+A_4,A_3+A_2,A_1+A_4)=\max(A_1,A_3)+\max(A_2,A_4)$.
    • – Anne Bauval Feb 04 '24 at 15:30
  • @AnneBauval Thank you! I re-edited the post according to your comment, except for the last one, since I need to think about it. Could you check whether it is still confusing concerning "for any"? – M.K Feb 04 '24 at 15:44
  • Thank you! it is not confusing any longer. What about dropping the reference to a matrix and the minus signs? (points 3 and 4 of my comment). 6) There are not $2^{n-4}$ configurations but $(2^{n-4})^4$, i.e. $2^{4(n-4)}$, i.e. $|{+1,-1}^{{1,\dots,4}\times{5,\cdots,n}}|$. – Anne Bauval Feb 04 '24 at 15:58
  • $[0,\alpha]\cap[-\pi,\alpha-\pi]=[0,\alpha-\pi]$.
    • – Anne Bauval Feb 04 '24 at 16:14
  • 1
    @AnneBauval yes I dropped the matrix, and instead referring to $(A_{ij})_{1\leq i\leq 4, 5\leq j\leq n}$. About sign, maybe I could keep it because it has physical meaning in my original problem and seem it does not distract too much to the post. About (7), sorry, it should be $\cup$ instead of $\cap$. And Thank you for all your comments! – M.K Feb 04 '24 at 16:59