Reinterpret maximin as LP I have the following problem
For $L,T \in \mathbb{R}^n$ and $G \in \mathbb{R}^{n\times n}$
$$\mathsf{max}_L \;\mathsf{min}_T \sum_{j = 1}^n T_j$$
Subject to
\begin{align*}\forall i,j &&T_j \geq L_i G_{ij}\\ &&\sum_{i = 1}^n L_i = 1\end{align*}
I'm not sure how to approach nested max min problems like this. I've seen some techniques on this site regarding introducing slack variables and such, but it doesn't seem to simplify this problem the way I'm applying it.
The above formulation is equivalent to
\begin{align*}
\mathsf{max}_L \sum_{j=1}^n \max_i L_iG_{ij}
\end{align*}
Subject to
\begin{align*}
\sum_{j=1}^n L_i = 1
\end{align*}
If there are any other nice ways to reinterpret this is a LP or QP please let me know!
 A: For maximizing a convex function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ over some domain $Conv(X)$, where $X\subseteq \mathbb{R}^n$ and $Conv(X)$ is the convex hull of set $X$, you can search for an optimal point in $X$.
Proof:  For any $x \in Conv(X)$ we have $x = \sum_{i=1}^m p_i x_i$ for some positive integer $m$ and some points $x_1, \ldots, x_m \in X$ and some values $p_i\geq 0$ such that $\sum_{i=1}^m p_i=1$. Then
$$f(x) = f\left(\sum_{i=1}^m p_i x_i\right) \overset{(a)}{\leq} \sum_{i=1}^m p_i f(x_i) \leq \sum_{i=1}^m p_i\left(\max_{i\in \{1, ..., m\}} f(x_i)\right) = \max_{i \in \{1, ..., m\}} f(x_i)$$
where (a) holds by convexity of $f$. So for any $x \in Conv(X)$, there is another point $x_i \in X$ such that $f(x_i)\geq f(x)$. $\Box$
In your problem you have the convex function
$$ f(L_1, ..., L_n) = \sum_{j=1}^n \max_{i \in \{1, ..., n\}}\{G_{ij}L_i\}$$
If your domain $Y$ is a simplex then $Y=Conv(X)$ where $X$ is the set of $n$ vectors:
$$(1,0,...,0), (0,1,0, ..., 0), ..., (0,0,...,0,1)$$
and you just search over that set of size $n$ for the best vector. If you add the constraints $0\leq L_i\leq 1/k$ for all $i$, for some positive integer $k \in \{1, ..., n\}$, then I believe $Y=Conv(X)$ where $X$ is the set of all $n$-dimensional vectors with entries $1/k$ in $k$ places and $0$ in the other places.  So you could search over all ${n \choose k}$ possibilities.
