Is there a notion of 'pre-convex' sets?

Question

A set $A$ in $\mathbb{R}^n$ is convex if for any two points $p,q \in A$ and real $\lambda \in [0,1]$, the point $\lambda p + (1-\lambda)q$ is also in $A$. There are many beautiful theorems about convex sets, perhaps the most important of which is: Let $f$ be a linear function on $\mathbb{R}^n$ (or more generally, take $f$ convex) and $A$ a compact, convex set. Then $f$ attains its maximum on the boundary of $A$.

Another nice property is that any local maximum of $f$ (still linear/convex) restricted to $A$ is in fact a global maximum.

What I would like to know is if there is a notion for non-convex sets which still satisfy this local maximum property.

For example, the sphere is not convex, but clearly any local maximum of a linear function is a global maximum. Of course, the sphere is the boundary of the ball, which is convex.

My hunch is that if a set $N$ is the boundary of its convex hull then any local max is in fact a global max, but there seem to be weaker sets which also have this property. All the obvious examples to me (such as the 1-skeleton of a convex polyhedra, the sphere) are what I would want to call 'pre-convex,' but I am not sure exactly what that should mean.

Your conjecture is true for linear functions $f$, and that's not too hard to show; any linear function is of the form $\vec{a}\cdot\vec{x}+b$ and so by a rotation and possible translation you can take your linear function to just be $f(\vec{x}) = x_0$, (i.e., the first coordinate of $\vec{x}$); then the 'local maximum is global maximum' is just the convexity property. — Steven Stadnicki, Feb 22 '14 at 20:58
A sphere is by definition the boundary of a ball, which is convex but the sphere is not. — Sebastian Bechtel, Apr 03 '17 at 07:26

score 0 · Answer 1 · answered Feb 19 '24 at 21:07

This notion of pre-convex depends a bit on our notion of local maximum: is it a point which is not exceeded in a neighborhood, or a point which strictly exceeds every other point in some neighborhood? (E.g., is $(1,0.5)$ a local maximum of $f(x,y)=x$ on the unit square $[0,1]\times [0,1]$?)

I'm going to use the latter, stricter sense of local maximum in what follows.

Suppose that a set $A$ has the property that for all linear $f$, if $P$ is a strict local maximum of $f$ on $A$ then there is no $Q\in A$ with $f(Q)\ge f(P)$.

This is actually a little

By considering the possible gradients of such an $f$, this is equivalent to:

For all $P\in A$ and vectors $v$, if $A$ is locally on one side of the half-space orthogonal to $v$ (and no other points lie on the half-space), then $A$ has no other points on the other side of that half-space or its boundary.

From this perspective, it's pretty clear that the boundary of any convex set is convex. However, so are many other strange things, like $[-2,2]\times [-2,2]$ minus the open unit disc, or minus any number of disjoint closed convex sets, or the union of the diagonals of any convex polygon (even omitting the side lengths). In general as long as we have something like a convex exterior and "room to maneuver" around anything on the interior, we'll maintain this property.

score 0 · Answer 2 · answered Feb 22 '14 at 20:38

0

Your conjecture is false. Define the function $f$ on the unit circle by $$ f(x,y) = x^2 + 3 y^2 $$ The unit circle is the boundary of a convex region given by $ x^2+y^2 \le 1$, you can chect that on the unit circle $f$ has a local maximum for $x=1, y=0$, but that is not a global maximum (the global maximum has the value 3).

answered Feb 22 '14 at 20:38

kjetil b halvorsen

6,625

4

(1) This $f$ is convex but not linear; (2) isn't it in fact a local minimum at $x=1$? On the circle the function is $3-2x^2$... – Steven Stadnicki Feb 22 '14 at 20:55

Is there a notion of 'pre-convex' sets?

2 Answers2