# Maximizing a sum of minimums → maximizing a single minimum

Let $$\Delta_n$$ be the standard simplex. Does there exist a function

$$f : \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n} \rightarrow \mathbb{R}^{m \times n}$$

such that

$$\operatorname*{argmax}_{x \in \Delta_n} \left(\min_{y \in \Delta_m} A \cdot x \cdot y + \min_{y \in \Delta_m} B \cdot x \cdot y\right) = \operatorname*{argmax}_{x \in \Delta_n} \min_{y \in \Delta_m} f(A, B) \cdot x \cdot y$$

for all $$A,B \in \mathbb{R}^{m \times n}$$? Note that this is equivalent to

$$\operatorname*{argmax}_{x \in \Delta_n} \left(\min_{i \in [m]} (A \cdot x)_i + \min_{i \in [m]} (B \cdot x)_i\right) = \operatorname*{argmax}_{x \in \Delta_n} \min_{i \in [m]} (f(A, B) \cdot x)_i$$

• Such a function certainly exists: For any given $A,B$, the left-hand side of your equation is just some vector $x^*\in\Delta_n$. So you can define $f(A,B)$ to be any matrix $C$ such that $\min_i (C\cdot x)_i$ attains its minimum at $x^*$. Or are you looking for an explicit formula for $C$ in terms of $A,B$ that does not require solving the former minimization? – Rahul Oct 10 '19 at 12:44
• @Rahul The latter, yes. I wasn’t sure how to formalize what you just said but it’s exactly what I’m looking for. – user76284 Oct 10 '19 at 13:22