How can I decompose the $\max$ of a product of functions?

Question

In this video, the author states that if $f(x) \geq 0$ for every $x$ and $g(x,y) \geq 0$ for every $x$ and $y$, then $$ \max_{x,y} f(x)g(x,y) = \max_x \left[f(x) \cdot \max_y g(x,y)\right] $$ I tried to prove this equality using $\log$'s as follows. \begin{align} \log\left(\max_{x,y} f(x)g(x,y)\right) &= \max_{x,y} \log f(x) + \log g(x,y) \\ &= \max_{x} \log f(x) + \max_{x,y} \log g(x,y) \tag{1} \\ &= \max_x \left[\log f(x) + \max_y \log g(x,y)\right] \tag{2} \end{align} I would then compute the $\exp$ of both sides of this equation to get the result. However, I think going from $(1)$ to $(2)$ is incorrect, but not exactly sure why.

Answer 1

Fundamentally, the following general rule is being used: $$\sup_{x, y} h(x, y) = \sup_x \sup_y h(x, y),$$ This is not difficult to see. Note that $$\sup_x \sup_y h(x, y) \ge \sup_y h(x_0, y) \ge h(x_0, y_0)$$ for all $x_0, y_0$, so $$\sup_{x, y} h(x, y) \le \sup_x \sup_y h(x, y).$$ On the other hand, $\sup_{x, y} h(x, y) \ge h(x_0, y_0)$ for any particular $x_0, y_0$, so if we take the supremum of both sides with respect to $y_0$ (bearing in mind that the left hand side is a constant with respect to $y_0$, we obtain $$\sup_{x, y} h(x, y) \ge \sup_{y_0} h(x_0, y_0) = \sup_y h(x_0, y),$$ for all $x_0$. Taking now the supremum of both sides with respect to $x_0$, $$\sup_{x, y} h(x, y) \ge \sup_{x_0} \sup_y h(x_0, y) = \sup_x \sup_y h(x, y),$$ completing the proof.

---

If the suprema are achieved on the right hand side, then all the suprema (including on the left hand side) are maxima instead. This means we can conclude: $$\max_{x, y} f(x)g(x, y) = \max_x \max_y f(x)g(x, y).$$ The only ingredient missing is that, if $\alpha \ge 0$, then $\sup_x \alpha h(x) = \alpha \sup_x h(x)$. This is essentially true by the fact that multiplication by $\alpha > 0$ preserves strict inequality, and a special case argument for $\alpha = 0$. Since $f(x) \ge 0$ is a constant with respect to $y$, we get $$\max_y f(x) g(x, y) = f(x) \max_y g(x, y).$$ Taking the maximum over $x$ of both sides completes the proof.

Answer 2

For convenience, here is another version of @TheoBendit's proof that has a bit more commentary (the second part of @TheoBendit's answer that discusses $\max_{x, y} f(x)g(x, y)$ is not discussed here) and shows that $$\min_{x,y} h(x,y) = \min_{x} \left[ \min_{y} h(x,y) \right]$$ To prove this, we want to show that $$\min_{x,y} h(x,y) \geq \min_{x} \left[ \min_{y} h(x,y) \right]$$ and $$\min_{x,y} h(x,y) \leq \min_{x} \left[ \min_{y} h(x,y) \right]$$ First, we show that $$\min_{x,y} h(x,y) \geq \min_{x} \left[ \min_{y} h(x,y) \right]$$ Note that \begin{align} \min_{x} \left[ \min_{y} h(x,y) \right] &\leq \min_y h(x_0,y) \\ &\leq h(x_0,y_0) \end{align} for every pair $(x_0,y_0)$, including the pair $(\bar x, \bar y)$ that minimizes $h(x,y)$. That is, if $h(\bar x,\bar y) = \min_{x,y} h(x,y)$, then we can write, \begin{align} \min_{x} \left[ \min_{y} h(x,y) \right] &\leq h(\bar x,\bar y) \\ &= \min_{x,y} h(x,y) \end{align} and so we have shown that $$\min_{x,y} h(x,y) \geq \min_{x} \left[ \min_{y} h(x,y) \right]$$ Next, we show that $$\min_{x,y} h(x,y) \leq \min_{x} \left[ \min_{y} h(x,y) \right]$$ Note that $$\min_{x,y} h(x,y) \leq h(x_0,y_0)$$ for every pair $(x_0,y_0)$. Then, we can apply $\min_{y_0}[\cdot]$ followed by $\min_{x_0}[\cdot]$ to both sides of this inequality to get \begin{align} \min_{x,y} h(x,y) &\leq h(x_0,y_0) \\ \min_{x_0} \left[ \min_{y_0} \left[ \min_{x,y} h(x,y) \right] \right] &\leq \min_{x_0} \left[ \min_{y_0} h(x_0,y_0) \right] \end{align} Because $\min_{x,y} h(x,y)$ on the left-hand side of this inequality is a constant, then this inequality becomes \begin{align} \min_{x,y} h(x,y) &\leq \min_{x_0} \left[ \min_{y_0} h(x_0,y_0) \right] \end{align} By changing the variables $x_0$ to $x$ and $y_0$ to $y$ on the right-hand side of this inequality, it becomes $$\min_{x,y} h(x,y) \leq \min_{x} \left[ \min_{y} h(x,y) \right]$$ which completes the proof.