how to prove the affine composition of the subdifferential?

Question

I'm reading the subdifferential definition, which is the set of all subgradients of a function at point $x.$

I have some difficulty in proving this exercise: if $g(x) = f(Ax+b)$ then subdifferential of $g(x)$ equals to $A'\partial f(Ax+b)$

(which is from 7.4.1 of http://www.stat.cmu.edu/~ryantibs/convexopt-S15/scribes/06-subgradients-scribed.pdf )

What I don't understand is that by definition:

$\partial g(x)=\{p: f(Ay+b) \geq f(Ax+b)+p'(y-x)\}$

and also by definition

$\partial f(Ax+b) = \{q: f(Ay+b) \geq f(Ax+b)+q'(y-x)\}$

Then why $p \neq q$

Can someone show me how to work it out ? thanks

Answer 1

Suppose that $g(x) := f(Ax+b)$. Then

$A^*\partial f(Ax+b) \subseteq \partial g(x)$.

Proof:
Let $u\in\partial f(Ax+b)$.
Then $(\forall y)$ $\langle u,(Ay+b)-(Ax+b)\rangle + f(Ax+b)\leq f(Ay+b)$.
Hence $(\forall y)$ $\langle u,A(y-x)\rangle + g(x)\leq g(y)$,
i.e., $(\forall y)$ $\langle A^*u,y-x\rangle + g(x)\leq g(y)$,
which means $A^*u\in\partial g(x)$. QED

This is the "easy direction".

The opposite inclusion, namely,

$A^*\partial f(Ax+b) \supseteq \partial g(x)$

is generally false; however, it is true
when (i) the range of $A$ contains a point of the relative interior of $\mathrm{dom}\, f$;
or when (ii) $f$ is polyhedra and the range of $A$ contains a point of $\mathrm{dom}\, f$.
This inclusion is nontrivial; see, e.g., Rockafellar's Convex Analysis, Theorem 23.9 for details.