Note this question is similar to my previous question, but it here I have added some constraints to avoid a trivial outcome.
Define the following function:
$$\Delta(p,y) = \sum_{i = 1}^n p_i y^T M_i^T M_i y - \frac{1}{n} \sum_{j = 1}^n y^T M_j^T M_j y$$ $$\Delta(p,y) = y^T \left(\sum_{i = 1}^n p_i M_i^T M_i - \frac{1}{n} \sum_{j = 1}^n M_j^T M_j\right) y$$
where $p$ lives on the $n$-simplex ($p_i > 0, \sum_i p_i = 1$). The matrix $M_i^T M_i$ is symmetric, thus has non-negative eigenvalues, and is of size $d \times d$. $y$ is a real-valued vector of size $d$, furthermore, we may assume that $|| y ||_2 \leq \Lambda$. Furthermore, to avoid trivially that everything becomes zero, consider the two constraints:
- $y \neq 0$.
- $||y|| = \Lambda$.
Is it then possible to compute, approximate or bound
$$\max_{y} \min_{p} \Delta(p,y)$$
I was thinking to apply a minimax theorem (such as this one), however, the maximization with respect to $y$ is generally not concave, since if we subtract the matrices the resulting matrix might become indefinite, and therefore it seems I cannot apply the theorem (the minimization in $p$ is convex though).
In order to use a minimax theorem I think it might be useful to consider mixed strategy for the max-player as well, so perhaps it is more tractable to compute:
$$\max_{p_y} \min_{p} \int p_y(y) \Delta(p,y) dy$$
In this case I think it will be possible to use a minimax theorem such as Parthasarathy's theorem
I'm particularly interested under which conditions $\max_{y} \min_{p} \Delta(p,y) < 0$ and $\max_{p_y} \min_{p} \int p_y(y) \Delta(p,y) dy < 0$.
Any help would be greatly appreciated!
The inner problem is the minimization of an affine function over the simplex. By the maximum principle, there is always a corner point of the simplex where the minimum value is attained. So, your problem simplifies to $$\forall y : ||y||=\Lambda, \; \exists i : y^T \left(M_i^T M_i - \frac{1}{n} \sum_{j = 1}^n M_j^T M_j\right) y <0?$$ To answer this question, you can precompute the eigenspaces of $M_i^T M_i - \frac{1}{n} \sum_{j = 1}^n M_j^T M_j$ corresponding to negative eigenvalues, and see if they span $\mathbb{R}^d$.