1
$\begingroup$

Another terminology question:

If a function $f(x)$ is strictly convex at $y$, does this mean, for an already convex function:

a) $f'(y) = 0$, or equally, $y = \arg \min_y f(y)$

b) $f''(x) \geq 0$ and $f''(y) \neq 0$

c) Something else (specify)

Thanks, L

EDIT: Where $f(x)$ is not differentiable at $x$, read $f'(x)$ as the subgradient of $f$ at $x$. i.e. $f'(x)=0$ means that for subgradient [a,b], $a \leq 0$, $b \geq 0$. Similarly for $f''$.

$\endgroup$
3
  • 1
    $\begingroup$ What is the derivative/subgradient of a subgradient? $\endgroup$
    – Did
    Aug 12, 2011 at 8:26
  • $\begingroup$ How about: there is a line $l(x) = ax+b$ such that $l(y)=f(y)$ and $l(x)<f(x)$ for all $x\ne y$. Do not mention derivatives! $\endgroup$
    – GEdgar
    Aug 12, 2011 at 14:34
  • $\begingroup$ @GEdgar: there's however the following problem (see my answer below). A function is convex if the set of subdifferentials is non-empty. You propose that $f$ is strictly convex at $y$ if there is an element in its subdifferentials that is strictly less than $f$ (except at $y$). But one can alternatively propose that the requisite property is that all subdifferentials be strictly less than $f$ except at $y$. $\endgroup$ Aug 12, 2011 at 15:12

2 Answers 2

1
$\begingroup$

Strict convexity is usually a global property; i.e., a function $f$ is (globally) strictly convex if any of the following hold for any $x\neq y$ in the domain of $f$:

  1. For any $\alpha\in (0,1)$, $f(\alpha x + (1-\alpha) y) < \alpha f(x) + (1-\alpha) f(y)$;

  2. The subdifferential set $\partial f(x)$ (the set of sugradients at $x$) is nonempty, and $f(y) > f(x) + \langle g, y-x\rangle$, where $g\in \partial f(x)$ is arbitrary;

  3. $\partial f(x)$ and $\partial f(y)$ are nonempty, and for any $g_x\in \partial f(x)$ and $g_y \in \partial f(y)$, $\langle g_x - g_y,x-y\rangle > 0$.

Usually you want strict convexity at least on a neighborhood of a point. But if you insist on having strict convexity at a single point, you can adjust the above definition to say "$f$ is strictly convex at $x$ if for every $y$..."

You can find more on the above definitions in Hiriart-Urruty & Lemaréchal's beautiful book "Fundamentals of Convex Analysis", where in particular the above equivalence appears as Proposition D.6.1.3.

$\endgroup$
1
  • $\begingroup$ "Usually you want strict convexity at least on a neighborhood of a point, But if you insist on having strict convexity at a single point" - I don't!! This is exactly why I thought it was a bit of an odd thing to say. $\endgroup$
    – Lucas
    Aug 31, 2011 at 0:38
1
$\begingroup$

It is clear that option (a) is non-ideal. Option (b) is also not good, since we would like the function $f(x) = x^4$ to be globally strictly convex. Using definition (b) this would fail at the origin. (BTW, your condition (b) and its suitable weakening to non-differentiable functions is more related to the notion of strong convexity, which is more restrictive than strict convexity.) (You should also consider the analogous problem that it is possible to have a strictly increasing function $g:\mathbb{R}\to\mathbb{R}$ that is continuously differentiable with $g'(0) = 0$.)

Here I propose a slightly different notion.

In the general case, recall that the notion of convexity on a vector space can be summed up by: $\forall t \in [0,1]$, $$(1)\qquad\qquad f(t\vec{v} + (1-t)\vec{w}) \leq tf(\vec{v}) + (1-t)f(\vec{w})$$ Evidently there are three points under consideration: $\vec{v}$, $\vec{w}$, and $t\vec{v} + (1-t)\vec{w}$; in effect by the symmetry in the relation, $\vec{v}$ and $\vec{w}$ can be considered together as the end-point case, while the other the mid-point case.

Let us see what happens in each of the cases.

Suppose we were to define "strictly convex at a point $\vec{y}$" to mean that the convexity relation (1) is a strict inequality for $\vec{v} = \vec{y}$ and all $\vec{w}$. That is

Definition We say that the convex function $f$ over a vector space is strictly convex at an end-point $y$ if $\forall t\in(0,1)$ and $\forall \vec{w}\neq\vec{y}$, we have the strict inequality $$ f(t\vec{y} + (1-t)\vec{w}) < tf(\vec{y}) + (1-t)f(\vec{w}) $$

Similarly we define

Definition we say that the convex function $f$ over a vector space is strictly convex at a mid-point $y$ if $\forall t\in(0,1)$ and $\forall \vec{v},\vec{w}\neq \vec{y}$ such that $\vec{y} = t\vec{v} + (1-t)\vec{w}$, the strict inequality holds $$ f(\vec{y}) < tf(\vec{v}) + (1-t)f(\vec{w}) $$

The two definitions are not equivalent!

Example Let $f:\mathbb{R}\to\mathbb{R}$ be the function $f(x) = |x|$. Then $f$ is strictly convex at the mid-point 0, but no-where is $f$ strictly convex at an end-point.

On the other hand, it is possible to have 0 be the only point at which $f$ has a strictly convex end-point.

Example Define $f$ the following way: let $f(\pm 2^{k}) = 4^k$ for every $k\in\mathbb{Z}$, and let $f$ be linear between $2^k$ and $2^{k+1}$ (similarly between $-2^k$ and $-2^{k+1}$; in the following we'll only do things on the positive half line, since the argument can be reflected to the negative half-line with minimum modification). And set $f(0) = 0$. This $f$ is continuous. It is clearly convex, and it is clearly not strictly convex at any point other than 0, since for any point $x > 0$, $f$ is linear on the segment $2^{k} \leq x < 2^{k+1}$. But from the definition it is clear that

  • if $x > 2^{k}$, then $f(x) > \frac{x}{2^k} f(2^k)$
  • if $x < 2^{k}$, then $f(x) < \frac{x}{2^k} f(2^k)$

which implies that for all $0<t<1$, $f(tx) < tf(x)$. This implies that $f$ is strictly convex at the endpoint 0.

Now, we have the implication that if a convex function $f$ is strictly convex for the endpoint $\vec{y}$, it must also be strictly convex for the midpoint $\vec{y}$.

Proof Let $\vec{v},\vec{w},t$ such that $\vec{y} = t\vec{v} + (1-t)\vec{w}$. Let $s\in (0,1)$, and let $\vec{v}' = s\vec{y} + (1-s)\vec{v}$ and $\vec{w}' = s\vec{y} + (1-s)\vec{w}$. which implies that $\vec{y} = t\vec{v}' +(1-t)\vec{w}'$. By convexity, $$ f(\vec{y}) \leq tf(\vec{v}') + (1-t)f(\vec{w}') $$ by strict convexity of the end point $$ f(\vec{v}') < sf(\vec{y}) + (1-s) f(\vec{v}) $$ so $$ f(\vec{y}) < sf(\vec{y}) + t(1-s) f(\vec{v}) + (1-t)(1-s)f(\vec{w}) $$ which implies that $f$ is strictly convex at the midpoint $y$. q.e.d.

So depending on whether you want a corner point like what was given in the first example to be a point at which the function is strictly convex, you may choose one definition or the other.


To connect to the notion of partial derivatives: if $f$ is convex, it is (locally) Lipschitz continuous, and hence admits directional derivatives $D_{\vec{r}}f$, which is a non-decreasing function along the line $\vec{x} + s\vec{r}$ for any fixed $\vec{x}$. The notion of strictly convex at an endpoint $\vec{y}$ is equivalent to saying that for any $\vec{r}$ and any $s > 0$, the derivative

$$ D_{\vec{r}} f(\vec{y} + s\vec{r}) > D_{\vec{r}}f(\vec{y}) $$

and where the *strictly convex at a midpoint $\vec{y}$ is equivalent (I think; this last part I'm a bit iffy on) to saying that for any $\vec{r}$, and any $s,t > 0$,

$$ D_{\vec{r}} f(\vec{y} + s\vec{r}) > - D_{-\vec{r}} f(\vec{y} - t\vec{r}) $$

The implication of "endpoint strict convex" $\implies$ "midpoint strict convex" then is a consequence of the fact that for convex functions, $D_{\vec{r}}f \geq - D_{-\vec{r}} f$. (If $f$ is differentiable, then the equality is guaranteed.)


To connect to the notion of subgradients: Define the set of subgradients $\partial f(y)$ to be the set of linear functions $l(x)$ satisfying

  • $l(y) = f(y)$
  • $l(x) \leq f(x)$

A function being convex means that the set of subgradients $\partial f(y)$ is nonempty for any $y$.

Let $l\in \partial f(y)$. We say that $l$ is a "strict subgradient" if $l(x) < f(x)$ for every $x \neq y$. Then the two definitions above are equivalent to:

  • $f$ is strictly convex at the endpoint $y$ iff $\forall l\in\partial f(y)$, $l$ is strict.
  • $f$ is strictly convex at the midpoint $y$ iff $\exists l\in\partial f(y)$ such that $l$ is strict. (See also GEdgar's comment above.)
$\endgroup$

You must log in to answer this question.

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