Let $f : \mathbb{R}^n \longrightarrow \mathbb{R}^m$ be the affine function defined by $f(x) = Mx + b$ where $M$ is an $m \times n$ matrix and $b$ is a vector in $\mathbb{R}^m$. Prove that for $(x_0,y_0) \in \text{gph}(f)$: $$ N_{\text{gph}(f)}(x_0,y_0)=\big\{ (u,v)\in\mathbb{R}^n \times \mathbb{R}^m:u+M^Tv=0 \big\}. $$


Normal Cone
The normal cone of a nonempty, closed, and convex set $K$ at a point $x_0 \in K$ is: $$ N_K(x_0)=\big\{ z:\langle z, \;x-x_0 \rangle \leq 0,\; \forall x \in K\big\} $$


By applying the above definitions I was able to reach $$ \langle u + M^Tv , \; x - x_0\rangle \leq 0 $$

I am not sure how to prove that $u + M^Tv = 0$.

One thing that might help: the subdifferential of $f$ is $\partial f = \{ \nabla f \} = \{ M^T \}$.

Any help is greatly appreciated.


You are on a good way towards proving $u+M^\top v=0$.

If you have $$ \langle u+M^\top v,\;x-x_0\rangle \leq 0 $$ for all $x\in\mathbb R^n$, then (by substituting $x$ with $x+x_0$) it follows that $$ \langle u+M^\top v,\;x\rangle \leq 0 $$ for all $x\in\mathbb R^n$. By substituting $x$ with $-x$, we get $$ \langle u+M^\top v,\;x\rangle =0 $$ for all $x\in\mathbb R^n$. This implies (by linear algebra) that $u+M^\top v=0$.

This would complete the "$\subset$" part of the proof.

The other "$\supset$" part is easier in my opinion, so you should give it a try.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.