Convex Optimization - Weierstrass Theorem

Let S be a non empty, closed and bounded set (also called compact set) in $mathbb{R}^n$ and let $f:S ightarrow mathbb{R} $ be a continuous function on S, then the problem min $left { fleft ( x ight ):x in S ight }$ attains its minimum.

Proof

Since S is non-empty and bounded, there exists a lower bound.

$alpha =Infleft { fleft ( x ight ):x in S ight }$

Now let $S_j=left { x in S:alpha leq fleft ( x ight ) leq alpha +delta ^j ight } forall j=1,2,...$ and $delta in left ( 0,1 ight )$

By the definition of infimium, $S_j$ is non-empty, for each $j$.

Choose some $x_j in S_j$ to get a sequence $left { x_j ight }$ for $j=1,2,...$

Since S is bounded, the sequence is also bounded and there is a convergent subsequence $left { y_j ight }$, which converges to $hat{x}$. Hence $hat{x}$ is a pmit point and S is closed, therefore, $hat{x} in S$. Since f is continuous, $fleft ( y_i ight ) ightarrow fleft ( hat{x} ight )$.

Since $alpha leq fleft ( y_i ight )leq alpha+delta^k, alpha=displaystylepm_{k ightarrow infty}fleft ( y_i ight )=fleft ( hat{x} ight )$

Thus, $hat{x}$ is the minimizing solution.

Remarks

There are two important necessary conditions for Weierstrass Theorem to hold. These are as follows −

Step 1 − The set S should be a bounded set.

Consider the function fleft ( x ight )=x$.

It is an unbounded set and it does have a minima at any point in its domain.

Thus, for minima to obtain, S should be bounded.

Step 2 − The set S should be closed.

Consider the function $fleft ( x ight )=frac{1}{x}$ in the domain left ( 0,1 ight ).

This function is not closed in the given domain and its minima also does not exist.

Hence, for minima to obtain, S should be closed.