Constrained vs Unconstrained optimization

62 Views Asked by At

Let us assume that $$ \max_{f \in \mathcal{F}} \min_{x \in \mathbb{R}^n} f(x)$$ exists and is finite. Here $\mathcal{F}$ is class of continuous differentiable functions.

Can we then claim $$ \max_{f \in \mathcal{F}} \min_{x \in \mathcal{X}} f(x)$$ exists where $\mathcal{X}$ is a compact set in $\mathbb{R}^n$.

My hunch is yes because for every continuous function with compact domain has extremal points well defined.

Of course $\mathcal{F}$ contains the domain $\mathcal{X}$. Thanks

1

There are 1 best solutions below

3
On BEST ANSWER

Here is a counterexample. Take $n = 1$, and consider $\mathcal{X}$ to be the point $1 \in \mathbb{R}$. Now, consider the family of quadratic functions $$\mathcal{F} = \{ax^2 : 0 < a < 1\}$$ It's easy to see that for any $f \in \mathcal{F}$, $\min_{x \in \mathbb{R}} f(x) = 0$, so in particular, $\max_{f \in \mathcal{F}} \min_{x \in \mathbb{R}} f(x) = 0$. On the other hand, it is easy to see that for any $y < 1$, there is some $f \in \mathcal{F}$ so that $f(1) = y$, but there is no $f \in \mathcal{F}$ so that $f(1) = 1$. So, there is no $f \in \mathcal{F}$ so that $\min_{x \in \mathcal{X}}f(x) = \sup_{g \in \mathcal{F}} \min_{x \in \mathcal{X}}g(x)$.

Now, of course, if you replace $\max$ with $\sup$ in the above question, the answer is yes, because of the least upper bound property for real numbers. Another, more subtle way to make this true is to assume that $\mathcal{F}$ is compact under some topology so that the function $f\mapsto \min_{x\in \mathcal{X}} f(x)$ is continuous.