5
$\begingroup$

Let $B_d$ the unit ball in $\mathbb{R}^d$, and let $F_d$ be the set of convex functions with Lipschitz constant at most 1 from $B_d$ to $\mathbb{R}$.

When $d=1$ (so the domain is the just the interval $[-1,1]$), we can write every function $f\in F_1$ as a convex combination of very "simple" functions of the form $g_y(x) = |y-x|$ (up to an additive constant). That is, there is a distribution $P$ on $[-1,1]$ and a $c\in\mathbb{R}$ such that, for all $x$, we have $f(x) = E_{y\sim P} (g_y(x))+c$. The absolute value functions $g_y$ are thus the extremal points of $F_1$. (One can get rid of the constant $c$ by restricting $F_1$ to functions such that $f(0)=0$ and adjusting the $g_y$'s accordingly.)

My question is: what are the extremal points of $F_d$? Is there a simple collection of such functions whose convex hull is (dense in) the whole space? Is that set unique? I have a feeling this is well known, but could not figure out where to look for the result.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ $F_d$ has no extremal points --- every Lipschitz convex function $f$ can be written as $f = .5((f + 1) + (f-1))$. Unless you mean something else by "extremal". Can you make the question more precise? $\endgroup$
    – Nik Weaver
    Commented Apr 27, 2016 at 21:50
  • $\begingroup$ You are right that the functions are extremal only if we somehow ignore additive constant functions. One way to do this is to define equivalence classes of functions (with two functions equivalent if they differ by a constant), or more simply by insisting that f(0)=0 for all the functions we work with. A similar issue arises if we try to characterize convex functions in terms of their subgradients. I edited the question to clarify this, though I am not sure I chose the cleanest way. $\endgroup$
    – Adam Smith
    Commented Apr 28, 2016 at 2:42
  • $\begingroup$ For some examples of functions in higher dimensions that are probably extremal, we could look at "distance functions": for a closed convex set C, define a function $f_C(x)$ as the Euclidean distance to the nearest point in C. Such a function is always Lipschitz. $\endgroup$
    – Adam Smith
    Commented Apr 28, 2016 at 2:46
  • 1
    $\begingroup$ You mean Lipschitz-$1$, i.e. $|f(x) - f(y)| \le \|x-y\|$? $\endgroup$
    – Robert Israel
    Commented Apr 28, 2016 at 3:00
  • 1
    $\begingroup$ E.g. $|x| = .5(1.5|x| + .5|x|)$, so the absolute value function still is not extreme. Do you mean to require Lipschitz constant at most 1, as Robert suggests? $\endgroup$
    – Nik Weaver
    Commented Apr 28, 2016 at 3:28

1 Answer 1

Reset to default
4
$\begingroup$

A bit is known about the extreme points of the set $\{f: B_d \to \mathbb{R}\, |\, f(0) = 0$ and $L(f) \leq 1\}$ where $L(f)$ denotes the Lipschitz number of $f$. But you are asking for the extreme points of the family of convex functions in this set. I don't know of any previous work on this.

One thing we can say is that any function satisfying $|\nabla f| = 1$ almost everywhere is an extreme point of the first set. (And such functions can be fairly complicated.) So if it is also convex then it must be an extreme point of the second, smaller set. This would cover your shifted absolute value functions in the $d = 1$ case, for example. An obvious higher-dimensional analog would be the shifts of the functions $f(x) = |x - y|$ for $y \in B_d$.

Some notation: for any function $f$, let $\tilde{f} = f - f(0)$ be the shifted function which satisfies $\tilde{f}(0) = 0$. Then it seems to me that in the $d = 2$ case, if $L \subset B_2$ is a line segment and $f(x) = \rho(x,L)$ where $\rho$ is euclidean distance, then $|\nabla f| = 1$ almost everywhere and $f$ is convex, so $\tilde{f}$ is a function of your type. I guess this generalizes for arbitrary $d$ to the functions $f(x) = \rho(x,L)$ where $L \subset B_d$ is a $\leq d-1$-dimensional convex subset.

I think it's a good conjecture that the convex hull of these functions is dense in the whole set, but I don't know this.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I agree that these functions are natural to consider (I called them $f_C$ in my earlier comment). They are definitely extremal when the set $L$ has measure 0, but I don't think such functions generate the whole space. $\endgroup$
    – Adam Smith
    Commented Apr 29, 2016 at 13:59
  • $\begingroup$ Consider, for example, what happens when $d=2$ (so that $B_2$ is the unit-radius circle) and $C$ is a smaller disc also centered at the origin. Can we approximate $f_C$ as a convex combination of functions $\tilde f_L$ where $L$ is convex and has measure 0? In order for the gradient to have norm 1 outside of $C$, I think that the convex combination has to be supported on sets $L$ that are rotationally symmetric about the origin. The only such convex set of measure 0 is the singleton {(0,0)}, and $f_{(0,0)}$ is not a good approximation to $f_C$. $\endgroup$
    – Adam Smith
    Commented Apr 29, 2016 at 14:06
  • $\begingroup$ If the argument I outlined is correct, then we have to enlarge the set of extremal functions somehow (perhaps by including all functions $\tilde f_C$, where $C$ may have nonzero measure?) in order to generate all of $F_2$. $\endgroup$
    – Adam Smith
    Commented Apr 29, 2016 at 14:07
  • $\begingroup$ @AdamSmith: Hmm, you are right. If $L$ is any closed convex subset of the interior of $B_d$ then $\tilde{f}_L$ should be extreme. If $\tilde{f}_L = .5(g + h)$ then $\nabla \tilde{f}_L = .5(\nabla g + \nabla h)$, so that $\nabla g = \nabla h = \nabla f$ outside $L$. I think this implies that $f$, $g$, and $h$ differ by an additive constant outside $L$, and then inside $L$ convexity forces equality. $\endgroup$
    – Nik Weaver
    Commented Apr 29, 2016 at 14:26
  • $\begingroup$ On the other hand, the $d = 1$ case already shows that $\tilde{f}_L$ might not be extreme when $L$ is an interval that disconnects $B_1$. $\endgroup$
    – Nik Weaver
    Commented Apr 29, 2016 at 14:27

You must log in to answer this question.

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