Checking inequality

82 Views Asked by At

Let $\pi$ be a given permutation of the integers $\{1,\ldots,n\}$ and let $$\mathcal{X}=\{x\in\mathbb{R}_{+}^{n} \mid x_{\pi(1)}\geq\cdots\geq x_{\pi(n)},\mathbb{1}^\top x\geq \alpha\},$$ for some $\alpha>0$. Let $a\in\mathbb{R}$, $b\in\mathbb{R}^{n}$ and $Q\in\mathbb{R}^{n\times n}$ symmetric. Is there a way to check if \begin{align*} a+b^{\top}x+x^{\top}Qx<0,\quad \forall x\in\mathcal{X}, \end{align*} in general? For example, if $Q$ is negative semidefinite, then we can use convex quadratic programming to solve the problem. However, can we do something in the general case? Perhaps the eigendecomposition of $Q$ and the structure of $\mathcal{X}$ might be used.