# For a convex function, can subgradients be formed from finite convex combinations of gradients?

Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ a convex function. Since convex functions are locally Lipschitz, they are differentiable almost everywhere. Let $\delta f(x)$ be the set of subgradients to $f$ at $x$. Suppose that $f$ is not differentiable at $x_0$ and we are interested in a certain subgradient at this point, $v_0 \in \mathbb{R}^n$ where $f(x) \geq f(x_0)+v_0 \cdot (x-x_0)$.

Let $\mathcal{B}_{x_0}$ be some open ball around $x_0$ and define $\mathcal{S}=\{ v \in \mathbb{R}^n : \exists x \in \mathcal{B}_{x_0} \mbox{ s.t. } \delta f(x)= \{v \} \}$, that is $\mathcal{S}$ is the set of all gradients in the ball.

My question is this: Does there exist $\hat{\mathcal{S}} \subset \mathcal{S}$ such that $|\hat{\mathcal{S}}|< \infty$ and $\sum_{v \in \hat{\mathcal{S}}}v a_v= v_0$, where $a_v>0$ and $\sum_{v \in \hat{\mathcal{S}}}a_v = 1$. That is, can $v_0$ always be formed as a finite convex combination of nearby gradients of $f$?

I know that the problem is related to the concept of a Clarke subdifferential, but any other references are greatly appreciated.

• I don't think you can get by without a limit here (as in Clarke's gradient formula), unless you assume more structure for $f$. – Christian Clason Aug 6 '16 at 1:44

Consider the function $$f(x,y)=\sqrt{x^2+y^2}+|y|$$ Note that $v_0=(1,0)$ is a subgradient at $(0,0)$. The gradient of $f$ is defined if $y\ne0$ and at all these points its first coordinate is strictly less than 1. Hence the statement follows.
• I wonder if there is also an example where all $x$ within the unit ball are defined for the function. I feel that this example only works (it is a valid counterexample) because there are undefined points in the ball. – Austin Bren Aug 6 '16 at 22:11
• @TravisHartford, in this case it is true. In fact if the gradient is defined at all points of a small sphere then any subgradient inside is a convex combination of at most $n+1$ of gradients on the sphere. – Anton Petrunin Aug 6 '16 at 22:32
• @AntonPetrunin: If I understand this example correctly, the subgradient (1,0) can be approximated arbitrarily well by a convex combination of gradients in a ball around (0,0)... so we might as well call it a subgradient, right? If so, it seems a bit like telling someone that $\max x : x < 1$ doesn't exist... which is true, but not all that interesting. Are there any interesting counterexamples, or are they all correct if we're willing to take reasonable limits as needed? – user541686 Mar 13 '17 at 5:56