2
$\begingroup$

Let $f: \mathbb R^n \to [0 , +\infty] $ be a lower semicontinuous, convex, and positively homogenous degree-$2$ function. Prove that for all $x \in \mbox{dom} f$, we have $$ \partial f(x) \neq \emptyset $$

Note, that the latter is equivalent to saying that there exists a $\kappa > 0$ and a neighborhood $U$ of $x$ such that, for all $y \in U$ we have $$- \kappa \| y - x\| \leq f(y) - f(x)$$

I was able to prove that $\partial f(0) \neq \emptyset$, but I couldn't prove that for nonzero vectors. Actually It may not be true for those.

P.S : Positively homogenous of degree 2 means for all $t \geq 0 $ we have $f(tx)= t^2 f(x).$

$\endgroup$
  • 1
    $\begingroup$ In finite dimensions, all convex functions have subgradients at points in the core (or algebraic interior, substitute with "interior" if you want) of the domain. Given the positively homogeneous of degree $2$ condition, it appears that the domain has to be a subspace, and so if you restrict $f$ to this subspace, you should be able to find a subgradient for the restriction of $f$. You can then extend this subgradient in any way you like to the full space to obtain an element of the subgradient in the full space. I'm writing a comment because I feel like I've missed something in your question... $\endgroup$ – Theo Bendit Mar 14 at 2:36
  • $\begingroup$ @TheoBendit Thanks for your comment . The domain is just cone not necessary subspace, otherwise problem would become trivial as any convex function $f$ has subgradient on the relative interior of it's domain . (in finite dimension) $\endgroup$ – Red shoes Mar 14 at 2:49
  • $\begingroup$ Ah yes, there it is: I've missed the condition that $t \ge 0$. Still though, the standard argument will show that subgradients exist on the relative interior. You just need to worry about the relative boundary. Basically, this will fail when the subgradients are unbounded in the neighbourhood of the relative boundary point, which I'm fairly confident can happen. That is, I'm pretty sure that this is false, though I don't have time to write up a counterexample at the moment. $\endgroup$ – Theo Bendit Mar 14 at 2:59
  • $\begingroup$ @TheoBendit I doubt that. The restriction of function over half line (with starting point zero) is quadratic so it is nice. $\endgroup$ – Red shoes Mar 14 at 3:49
  • $\begingroup$ @TheoBendit I posted a similar question, in math.stackexchange.com/q/3151905/219176 I thought you might be interested to this one. I want to get a deep inside of those kind of function. Any help would be appreciated. $\endgroup$ – Red shoes Mar 17 at 18:46
2
$\begingroup$

Ok, let's construct a counterexample, since I can't express my thoughts via comments.

Start by considering the semicircle function over $\Bbb{R}$, defined by $$x \mapsto \begin{cases}1-\sqrt{1 - x^2} & \text{if } |x| \le 1 \\ \infty & \text{if } |x| > 1 \end{cases}.$$ This is an example of an lsc which fails to admit subgradients at each point in the domain, as there is no subgradient at $x = \pm 1$. We can see this visually by observing that the points $(\pm 1, 1)$ are supported only by vertical lines.

Now, we embed this function in $\Bbb{R}^2$, then extend it to a cone. Let $C$ be the cone generated by $[-1, 1] \times \{1\}$, which is defined by the inequality $y \ge |x|$. We form a function $g$ over $C$ by defining its graph to be the (non-convex) cone generated by the graph of the semicircle function over the domain $[-1, 1] \times \{1\}$. More explicitly, $$g(x, y) = \begin{cases}y -\sqrt{y^2 - x^2} & \text{if }(x, y) \in C \\ \infty & \text{otherwise} \end{cases}.$$ This function is scalar positive-homogeneous (only degree $1$; we shall square it soon enough!).

I also claim that $g$ is lsc and convex. I think the most intuitive way to see this is to express $\operatorname{epi} g$ as the closure of the cone generated by our semicircle defined over $[-1, 1]$. In particular, $$\operatorname{epi} g = \overline{\operatorname{cone}} S$$ where $$S = \left\{(x, 1, z) : |x| \le 1 \text{ and } z \ge 1 - \sqrt{1 - x^2}\right\}.$$ So, suppose $(a, b, c) \in \operatorname{cone} S$. We may therefore find $x, z, \lambda$, the latter non-negative, such that $(a, b, c) = \lambda(x, 1, z)$, $|x| \le 1$, and $z \ge 1 - \sqrt{1 - x^2}$. Clearly, $\lambda = b$. If $b = 0$, then $(a, b, c) = (0, 0, 0) \in \operatorname{epi} g$, so we may assume $b > 0$.

We also have $\left|\frac{a}{b}\right| = |x| \le 1 \implies |a| \le |b| = b$, so $(a, b, c) \in C$. Given the condition that $z \ge 1 - \sqrt{1 - x^2}$, we get $$\frac{c}{b} \ge 1 - \sqrt{1 - \left(\frac{a}{b}\right)^2} \implies c \ge b - \sqrt{b^2 - a^2} = g(a, b) \implies (a, b, c) \in \operatorname{epi} g.$$

On the other hand, if $(a, b, c) \in \operatorname{epi g}$, then $(a, b) \in C$, hence $b \ge |a|$. Suppose for the moment that $b > 0$, and consider the point $$(x, 1, z) = \left(\frac{a}{b}, 1, \frac{c}{b}\right).$$ We see that $b(x, 1, z) = (a, b, c)$, and by reverse engineering the above calculation, we get that $(x, 1, z) \in S$. Hence $(a, b, c) \in \operatorname{cone} S$.

On the other hand, suppose $b = 0$. Note that this implies $a = 0$ too, by definition of $C$. We know that $c \ge 0$.

Fix $\varepsilon > 0$. Consider the point $(0, \varepsilon, c)$. We have $$c \ge 0 = g(0, \varepsilon),$$ hence this point lies in $\operatorname{epi} g$, and by the above argument, $\operatorname{cone} S$. Since this point is $\varepsilon$-close to $(a, b, c)$, it follows $(a, b, c) \in \overline{\operatorname{cone}} S$.

To finally complete the proof that $g$ is lsc and convex, note that $g$ is continuous when restricted to $C$, hence its epigraph is closed, and thus is equal to the closed convex set $\overline{\operatorname{cone}} S$.

Now, we may define $f : \Bbb{R}^2 \to [0, \infty]$ by $f(x) = g(x)^2$, where $\infty^2 = \infty$. As we are applying a monotone increasing real convex function over the positive reals to $g$, the resulting function is convex. The nice continuity properties of the squaring map also ensures that $f$ is lsc. We finally have $$f(\lambda (x, y)) = g(\lambda (x, y))^2 = \lambda^2 g(x, y)^2 = \lambda^2 f(x, y),$$ as required. We have now completely constructed our counterexample!


The only thing left to do is prove it is a counterexample. None of the points of the form $(\pm x, x)$ will have subgradients, but let's just pick on $(1, 1)$.

Suppose $(a, b) \in \partial f(1, 1)$. Consider points along the ray $(1, 1) + t(-1, 1)$ for $t \ge 0$. Note that this ray is contained in $C$, and we have, by definition of the subgradient, $$(a, b) \cdot (-1, 1) \le \frac{f(1 - t, 1 + t) - 1}{t}.$$ Expanding, \begin{align*} f(1 - t, 1 + t) &= \left(1 + t - \sqrt{(1 + t)^2 - (1 - t)^2}\right)^2 \\ &= \left(1 + t - 2\sqrt{t}\right)^2 = (1 - \sqrt{t})^4. \end{align*} However, $$\lim_{t \to 0^+} \frac{(1 - \sqrt{t})^4 - 1}{t} = -\infty,$$ so for sufficiently small $t$, we have $$\frac{f(1 - t, 1 + t) - 1}{t} < (a, b) \cdot (-1, 1)$$ against assumption. That is, $\partial f(1, 1) = \emptyset$ (finally).

$\endgroup$
  • $\begingroup$ (I have no doubt that I've left errors lying about the place. Please let me know if you find some.) $\endgroup$ – Theo Bendit Mar 14 at 5:22
  • 1
    $\begingroup$ Awesome . Thank you $\endgroup$ – Red shoes Mar 14 at 7:15

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.