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.

Improve this question
$\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$
    – Christian Clason
    Commented Aug 6, 2016 at 1:44

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Austin Bren
    Commented 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$
    – Anton Petrunin
    Commented 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$
    – Austin Bren
    Commented 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
    Commented Mar 13, 2017 at 5:56
  • $\begingroup$ @Mehrdad, no, there are no interesting examples; this is easy to check. $\endgroup$
    – Anton Petrunin
    Commented Mar 13, 2017 at 16:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .