9 The Subdifferential Chain Rule

Lemma 9.1 Let B:\mathbb{R}^n\to\mathbb{R}^p be an affine mapping given by B(x):=Ax+b, where A is a p\times n matrix and b\in\mathbb{R}^p. Then for any (\bar x,\bar y)\in{\rm gph}(B) we have

N\big((\bar x,\bar y);{\rm gph}(B)\big)=\big\{(u,v)\in\mathbb{R}^n\times\mathbb{R}^p\;\big|\;u=-A^\top v\big\}.

Proof It is clear that {\rm gph}(B) is convex and (u,v)\in N((\bar x,\bar y)\;{\rm gph}(B)) if and only if

\langle u,x-\bar x\rangle +\langle v,B(x)-B(\bar x)\rangle\le 0\;\text{ for all }x\in\mathbb{R}^n.

It follows directly from the definitions that

\langle u,x-\bar x\rangle +\langle v,B(x)-B(\bar x)\rangle=\langle u,x-\bar x\rangle +\langle v,A(x)-A(\bar x)\rangle

=\langle u,x-\bar x\rangle +\langle A^\top v,x-\bar x\rangle =\langle u+A^\top v,x-\bar x\rangle.

This implies that (u,v)\in N\big((\bar x,\bar y);{\rm gph}(B)\big) is equivalent to \langle u+A^\top v,x-\bar x\rangle\le 0 for all x\in \mathbb{R}^n, and so we have u=-A^\top v.  \square

Proposition 9.2 Let f\colon\mathbb{R}^p\to(-\infty, \infty] be a convex function, and let B:\mathbb{R}^n\to\mathbb{R}^p be given by B(x):=Ax+b, where A is a p\times n matrix and b\in\mathbb{R}^p . Fix \bar x\in\mathbb{R}^n such that B(\bar x)\in{\rm dom}(f). Denote \bar y:=B(\bar x). Then we have that

\partial(f\circ B)(\bar x)\supset A^\top\big(\partial f(\bar y)\big)=\big\{A^\top v\;\big|\;v\in\partial f(\bar y)\big\}.

Proof Fix u\in A^\top \partial f(\bar y). By definition we have that there exists a v\in\partial f(\bar y) such that u=A^\top v.  Then we have that

\langle u,x-\bar x\rangle =\langle A^\top v,x-\bar x\rangle

=\langle v,Ax-A\bar x\rangle =\langle v,B(x)-B(\bar x)\rangle,

and because v\in\partial f(\bar y) and \bar y=B(\bar x) then we have that

\langle u,x-\bar x\rangle\le f\big(B(x)\big)-f\big(B(\bar x)\big)=(f\circ B)(x)-(f\circ B)(\bar x).  

Thus we have that u\in\partial (f\circ B)(\bar x).  \square

We will now prove the main result of this section.

Theorem 9.3 Let f\colon\mathbb{R}^p\to(-\infty, \infty] be a convex function, and let B:\mathbb{R}^n\to\mathbb{R}^p be given by B(x):=Ax+b, where A is a p\times n matrix and b\in\mathbb{R}^p. Fix \bar x\in\mathbb{R}^n such that B(\bar x)\in{\rm dom}(f). Denote \bar y:=B(\bar x) and assume that the range of B contains a point of \mbox{\rm ri(dom}(f)). Then we have that

\partial(f\circ B)(\bar x) = A^\top\big(\partial f(\bar y)\big)=\big\{A^\top v\;\big|\;v\in\partial f(\bar y)\big\}.

Proof The first inclusion was proved in Proposition 9.2, so we only need to prove that

\partial(f\circ B)(\bar x)\subset A^\top\big(\partial f(\bar y)\big).

Fix v\in\partial(f\circ B)(\bar x) and form the subsets of \mathbb{R}^n\times\mathbb{R}^p\times\mathbb{R} by

\Omega_1:={\rm gph}(B)\times\mathbb{R}\;\mbox{ and }\;\Omega_2:=\mathbb{R}^n\times{\rm epi}(f).

Then we clearly get the relationships

\mbox{\rm ri}(\Omega_1)=\Omega_1={\rm gph}(B)\times\mathbb{R},

\mbox{\rm ri}(\Omega_2)=\{(x,y,\lambda)\;|\;x\in\mathbb{R}^n,\;y\in\mbox{\rm ri(dom}(f)),\;\lambda>f(y)\},

and thus the assumption of the theorem tells us that \mbox{\rm ri}(\Omega_1)\cap \mbox{\rm ri}(\Omega_2)\neq\emptyset.

Further, it follows from the definitions of the subdifferential and of the normal cone that (v,0,-1)\in N((\bar x,\bar y,\bar z);\Omega_1\cap\Omega_2), where \bar z:=f(\bar y). Indeed, for any (x,y,\lambda)\in\Omega_1\cap\Omega_2 we have y=B(x) and \lambda\ge f(y), and so \lambda\ge f(B(x)). Thus

\langle v,x-\bar x\rangle +0(y-\bar y)+(-1)(\lambda-\bar z)\le\langle v, x-\bar x\rangle -[f(B(x))-f(B(\bar x))]\le 0.

Employing the intersection rule of Theorem 6.3 to the above sets gives us

(v,0,-1)\in N\big((\bar x,\bar y,\bar z);\Omega_1\big)+N\big((\bar x,\bar y,\bar z);\Omega_2\big),

which tells us that (v,0,-1)=(v,-w,0)+(0,w,-1) with (v,-w)\in N((\bar x,\bar y);{\rm gph}(B)) and (w,-1)\in N((\bar y,\bar z);{\rm epi}(f)). Then we get

v=A^\top w\;\mbox{ and }\;w\in\partial f(\bar y),

which implies that v\in A^\top(\partial f(\bar y)) and hence verifies the inclusion “\subset“.   \square

Proceed to the next section