Let $\mathcal{X} \subset \mathbb{R}^n$ and $c \in \mathbb{R}^n$. Moreover, define $$ f(c) := \max_{x\in\mathcal{X}} \ x^\top c \quad \text{and} \quad \bar{x}_c := \text{arg}\max_{x\in\mathcal{X}} \ x^\top c. $$ In this paper, Proposition 3.1, it is argued that $\bar{x}_\hat{c}$ is a subgradient of $f$ at $\hat{c}$. They prove it using the following argument:
For any $c \in \mathbb{R}^n$, $$ f(c) - f(\hat{c}) = \max_{x\in\mathcal{X}} \ x^\top c - \max_{x\in\mathcal{X}} \ x^\top \hat{c} = \max_{x\in\mathcal{X}} \ x^\top c - \bar{x}_\hat{c}^\top \hat{c} \geq \bar{x}_\hat{c}^\top (c - \hat{c}). $$
My question is twofold:
- In order to show that $\bar{x}_\hat{c}$ is a subgradient of $f$ at $\hat{c}$, is it enough to show that $f(\hat{c}) + \bar{x}_\hat{c}^\top (c - \hat{c})$ lower bounds $f(c)$ for any $c$, as was done in the paper?
- By definition, $f(c) = \bar{x}_c^\top c$. Since $\bar{x}_c$ is a function of $c$, can we derive a (sub)gradient of $f$ w.r.t. $c$ using some kind of chain rule? Moreover, does it yield the same result as shown in the paper?
Yes, that's the definition of the subgradient, $\partial f(x_0) = \{g : f(x) - f(x_0) \ge g' (x-x_0), \quad \forall x \in X\}$.
That's called the envelope theorem. $\nabla f(c) = \bar{x}_c$ means that the solution correspondence is a supporting hyperplane to the choice set, $X$.