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$$

  • $\begingroup$ 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? $\endgroup$ – Rahul Oct 10 '19 at 12:44
  • $\begingroup$ @Rahul The latter, yes. I wasn’t sure how to formalize what you just said but it’s exactly what I’m looking for. $\endgroup$ – user76284 Oct 10 '19 at 13:22

Your Answer

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

Browse other questions tagged or ask your own question.