0
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Aug 6, 2016 at 1:44

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Aug 6, 2016 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$ Aug 6, 2016 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$ Aug 6, 2016 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, 2017 at 5:56
  • $\begingroup$ @Mehrdad, no, there are no interesting examples; this is easy to check. $\endgroup$ Mar 13, 2017 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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