max-min optimization problem

I'm curious if there is any nice way to approach solving the following kind of optimization problem. Given a $n \times m$ matrix $A = (a_{ij})$, I want to solve \begin{align*} & \max_{c}\min_{1 \leq i \leq n} \left|\sum_{j=1}^{m}c_{j}a_{ij}\right|\\ & \textrm{ s.t. } \sum_{j=1}^{m}c_{j} = 1, \quad c_{j} \geq 0. \end{align*}

On a related note, if instead we have a vector of smooth scalar functions $\mathbf{f}(x) = [f_{1}(x), \ldots, f_{m}(x)]$ with each defined on some compact set $X \subset \mathbb{R}^{d}$, is there a nice way to solve \begin{align*} & \max_{c} \min_{x \in X} \left|\sum_{j=1}^{m}c_{j}f_{j}(x) \right|\\ & \textrm{ s.t. } \sum_{j=1}^{m}c_{j} = 1, \quad c_{j} \geq 0. \end{align*}

1 Answer

Introduce a slack variable t, as mentioned in Convex Optimization by Stephen Boyd
\begin{align*} & \max_{R} t \\ & \textrm{ s.t. } \left|\sum_{j=1}^{m}c_{j}a_{ij}\right| \geq t \forall i\\ & \sum_{j=1}^{m}c_{j} = 1, \quad c_{j} \geq 0 \end{align*}

Its a reduced linear programming problem. Geometrically, interpret it as maximizing the lower bound