6
$\begingroup$

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*}

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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