Membership based on maximum of a function over the set.

Question

Let $S\subset \mathbb{R}^n$ and let $f(x)$ be a continuous function over $\mathbb{R}^n$. Furthermore, define $s_{\text{max}}:= \sup_{x\in S} \{f(x)\}$ and let $f(x)$ attain its minimum for at least one element in $S$.

Under what conditions on $f(x)$ and $S$ does it hold that $f(x_1)\leq s_{\text{max}}$ $\Rightarrow$ $x_1\in S$?

In particular, does this hold if $f(x)$ is a convex function and $S$ is a convex set? If $f(x)$ is convex and $S$ is an arbitrary set?

Unfortunately I am far from my comfort zone here, so any help is much appreciated!

Answer 1

Let $\Sigma_S = \{x | f(x) \leq \sup_{t \in S} f(t) \}$. If $x \in S$, then we have $f(x) \leq \sup_{t \in S} f(t)$, hence $x \in \Sigma_S$, i.e, $S \subset \Sigma_S$. This is true for all $S,f$.

The desired property above is equivalent to $\Sigma_S \subset S$, hence this is true iff $S = \Sigma_S$.

That is, the property you desire is true iff $S$ has the form $\{x | f(x) \leq L \}$ for some $L$ (which may be $\infty$).

For a counterexample, choose the convex function $f(x) = x^2$ on the convex set $[0,1]$. It is easy to see that $s_\max =1$, but $f(-1) \leq 1$ also.

Answer 2

Let's assume that $S$ is a subset of the domain of $f$ which -- for the case of maximisation -- we define as $\operatorname{dom}f=\{x|f(x)>-\infty\}$. Then, the fact that $f(x)\leq s_{max}$ does not imply that $x\in S$ nor that $x\notin S$. You can see this through a simple example. Consider the concave function $f(x)=-x^2$ and the convex set $S=[-1,1]$. Then $s_{max}=\sup_{-1\leq x \leq 1}-x^2=0$ and take $x_0=2\notin S$. Notice that $f(x_0)\leq s_{max}$. You can easily find counter-examples for your statement using convex functions. Take for instance the convex function $f(x)=x^2$ and $S=[1,2]$ and $x_0=0$.

One useful things about convex minimisation over convex sets, is that any local minimum you find is also global. The same holds true for maximisation problems when the function is concave and the set convex.

I can only think of an extremely special case where your statement holds true. $f:\mathbb{R}^n\to\mathbb{R}$ is quadratic, i.e. $f(x)=x'Qx$ for some positive definite matrix $Q$, and $S$ is of the form $S=\{x\in\mathbb{R}^n|x'Px\leq \gamma\}$ for some $\gamma>0$ and $P=P'$ positive definite.

Answer 3

I'll try answering the following question. What kind of set $S \subset \mathbb{R}^n$ can be defined as $\{x|f(x) \leq c\}$ for a continuous $f : \mathbb{R}^n \rightarrow \mathbb{R}$ and constant $c$.

Trivially, the function $f(x) = \inf_{y \in S} d(x, y)$ - distance from $S$ to $x$ defines any closed set $S$. In general the shape of $f$ can vary a lot as long as $f(\partial S) = c$ and $f$ has the right relation to $c$ in the interior and exterior of $S$. Open sets would work if the condition was $f(x) < c$. Now $f$ would measure the (negative of) distance from $x$ to the complement of $S$ instead.

This does not cover all sets though. $\mathbb{Q} \subset \mathbb{R}$, for example is neither closed nor open. It is clear that unless $f(\mathbb{Q}) = c$ the function will not be continuous. Now take any Cauchy sequence $(x_n)$ that does not converge in $\mathbb{Q}$. Due to continuity of $f$ we have that $f(\lim x_n) = \lim f(x_n) = \lim c = c$ - a contradiction.