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 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.