Convex Optimization - Weierstrass Theorem


Advertisements

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

Proof

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

$\alpha =Inf\left \{ f\left ( x \right ):x \in S \right \}$

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

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 \right \}$ for $j=1,2,...$

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

Since $\alpha \leq f\left ( y_i \right )\leq \alpha+\delta^k, \alpha=\displaystyle\lim_{k\rightarrow \infty}f\left ( y_i \right )=f\left ( \hat{x} \right )$

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 f\left ( x \right )=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 $f\left ( x \right )=\frac{1}{x}$ in the domain \left ( 0,1 \right ).

    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.

Advertisements