Gradient of $\max_yf(x,y)$

Question

Given $p(\textbf{x})$=$\max_{y}f(\textbf{x},y)$, do we have $\nabla p(\textbf{x})=\max_{y}(\nabla_{\textbf{x}}f(\textbf{x},y))$?

Answer 1

No, but there's a different formula that you might want to know.

Notice that $p(x) = f(x,y^\star(x))$, where $y^\star(x) = \arg\max_y f(x,y)$. Assuming that $y^\star$ is a differentiable function, the chain rule tells us that \begin{align} p'(x) &= \frac{\partial f(x,y^\star(x))}{\partial x} + \underbrace{\frac{\partial f(x,y^\star(x))}{\partial y}}_0 \,\, (y^\star)' (x) = \frac{\partial f(x,y^\star(x))}{\partial x}. \end{align} In the above calculation, we used the fact that $\frac{\partial f(x,y^\star(x))}{\partial y} = 0$, which is true because $y^\star(x)$ is a maximizer for the function $y \mapsto f(x,y)$.

Answer 2

No.

For example, take $f\colon\mathbb{R}^2\to\mathbb{R}$ to be $f(x,y)=-(x+y)^2$, so $p(x)=0$ for all $x$. But $$ \max_y\frac{\partial f(x,y)}{\partial x}=\max_y-2(x+y)=+\infty. $$

Furthermore, there is no reason why $p$ is differentiable even if $f$ is. For example, it is easy to come up with a smooth function $\phi\colon\mathbb{R}\to[-1,1]$ such that $\operatorname{sign}\phi(x)=\operatorname{sign} x$, $\phi(y)=1$ for all $y\geq 1$, and $\phi(y)=-1$ for all $y\neq -1$. Then $f(x,y)=\phi(y)x$ gives $p(x)=\lvert x\rvert$ not differentiable at $0$.