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.

  • $\begingroup$ 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$. $\endgroup$ – Christian Clason Aug 6 '16 at 1:44

The answer is "no".

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Austin Bren Aug 6 '16 at 22:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Anton Petrunin Aug 6 '16 at 22:32
  • $\begingroup$ Thanks for the responses. Does this fact go for when we have gradients almost everywhere on the ball (and subgradients on the non-differentiable points)? Also, any citations or literature to go with this? $\endgroup$ – Austin Bren Aug 6 '16 at 23:38
  • $\begingroup$ @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? $\endgroup$ – user541686 Mar 13 '17 at 5:56
  • $\begingroup$ @Mehrdad, no, there are no interesting examples; this is easy to check. $\endgroup$ – Anton Petrunin Mar 13 '17 at 16:36

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.