📖 Fundamentals of optimization#
⏱ | words
WARNING
This section of the lecture notes is still under construction. It will be ready before the lecture.
starting from univariate examples
maximizers and minimizers of a function
stationary points, FOCs
global vs local extrema
shape conditions, uniqueness
(skip necessary and sufficient SOCs)
examples of failure of existence of extrema Need general theory
switch multivariate functions and multidimensional spaces
bounded and unbounded sets
closed/open sets, compactness
switching to \(\mathbb{R}\) to talk about range of functions
suprema and infima in \(\mathbb{R}\)
boundedness of functions
Weierstrass boundedness theorem
Weierstrass extreme value theorem
sketch of proof
examples, examples, examples
Bounded sets#
Definition
A set \(A \subset \mathbb{R}^N\) called bounded if
Fig. 20 Bounded set in \(\mathbb{R}^2\)#
Example
Every finite subset \(A\) of \(\mathbb{R}\) is bounded
Indeed, set \(M := \max \{ |a| : a \in A \}\). Then \(A\) is bounded by definition
Example
The set \(\{(x,y)\in\mathbb{R}^2\colon xy \leqslant 1 \}\) is unbounded
Proof:
For any \(M \in \mathbb{R}\) consider the point whit coordinates \(x=1/M\) and \(y=M\). This point belongs to the set because it satisfies \(xy=1\), yet
Therefore, for any candidate bound \(M\) we can find points in the set that are further away from the origin than \(M\).
Example
\((a, b)\) is bounded for any \(a, b \in \mathbb{R}\)
Proof:
Let \(M := \max\{ |a|, |b| \}\). We have to show that each \(x \in (a, b)\) satisfies \(|x| \leq M\)
Cases:
\(0 \le a \le b \implies x > 0, x = |x| < |b| = b = \max\{|a|,|b|\}\)
\(a \le b \le 0 \implies a < x < 0, |x|= -x < -a = |a| = \max\{|a|,|b|\}\)
\(a \le 0 \le b \implies\)
Fact
If \(A\) and \(B\) are bounded sets then so is \(A \cup B\)
Proof
Let \(A\) and \(B\) be bounded sets and let \(C := A \cup B\)
By definition, \(\exists \, M_A\) and \(M_B\) with
Let \(M_C := \max\{M_A , M_B\}\) and fix any \(x \in C\)
Open and closed sets#
Definition
Let \(G \subset \mathbb{R}^N\). We call \(x \in G\) interior to \(G\) if \(\exists \; \epsilon > 0\) with \(B_\epsilon(x) \subset G\)
Fig. 21 Loosely speaking, interior means “not on the boundary”#
Example
Example
If \(G = (a, b)\) for some \(a < b\), then any \(x \in (a, b)\) is interior
Proof:
Fix any \(a < b\) and any \(x \in (a, b)\)
Let \(\epsilon := \min\{x - a, b - x\}\)
If \(y \in B_\epsilon(x)\) then \(y < b\) because
Exercise: Show \(y \in B_\epsilon(x) \implies y > a\)
Example
If \(G = [-1, 1]\), then \(1\) is not interior
Proof:
Intuitively, any \(\epsilon\)-ball centered on \(1\) will contain points \(> 1\)
More formally, pick any \(\epsilon > 0\) and consider \(B_\epsilon(1)\)
There exists a \(y \in B_\epsilon(1)\) such that \(y \notin [-1, 1]\)
For example, consider the point \(y := 1 + \epsilon/2\)
Exercise: Check this point: lies in \(B_\epsilon(1)\) but not in \([-1, 1]\)
Definition
A set \(G\subset \mathbb{R}^N\) is called open if all of its points are interior
Example
Open sets:
any open interval \((a,b) \subset \mathbb{R}\), since we showed all points are interior
any open ball \(B_\epsilon(a) = x \in \mathbb{R}^N : \|x - a \| < \epsilon\)
\(\mathbb{R}^N\) itself satisfies the defintion of open set
Sets that are not open
\((a,b]\) because \(b\) is not interior
\([a,b)\) because \(a\) is not interior
Closed Sets#
Definition
A set \(F \subset \mathbb{R}^N\) is called closed if every convergent sequence in \(F\) converges to a point in \(F\)
Rephrased: If \(\{x_n\} \subset F\) and \(x_n \to x\) for some \(x \in \mathbb{R}^N\), then \(x \in F\)
Example
All of \(\mathbb{R}^N\) is closed \(\Leftarrow\) every sequence converging to a point in \(\mathbb{R}^N\) converges to a point in \(\mathbb{R}^N\)!
Example
If \((-1, 1) \subset \mathbb{R}\) is not closed
Proof:
True because
\(x_n := 1-1/n\) is a sequence in \((-1, 1)\) converging to \(1\),
and yet \(1 \notin (-1, 1)\)
Example
If \(F = [a, b] \subset \mathbb{R}\) then \(F\) is closed in \(\mathbb{R}\)
Proof:
Take any sequence \(\{x_n\}\) such that
\(x_n \in F\) for all \(n\)
\(x_n \to x\) for some \(x \in \mathbb{R}\)
We claim that \(x \in F\)
Recall that (weak) inequalities are preserved under limits:
\(x_n \leq b\) for all \(n\) and \(x_n \to x\), so \(x \leq b\)
\(x_n \geq a\) for all \(n\) and \(x_n \to x\), so \(x \geq a\)
therefore \(x \in [a, b] =: F\)
Properties of Open and Closed Sets#
Fact
\(G \subset \mathbb{R}^N\) is open \(\iff \; G^c\) is closed
Proof
\(\implies\)
First prove necessity
Pick any \(G\) and let \(F := G^c\)
Suppose to the contrary that \(G\) is open but \(F\) is not closed, so
\(\exists\) a sequence \(\{x_n\} \subset F\) with limit \(x \notin F\)
Then \(x \in G\), and since \(G\) open, \(\exists \, \epsilon > 0\) such that \(B_\epsilon(x) \subset G\)
Since \(x_n \to x\) we can choose an \(N \in \mathbb{N}\) with \(x_N \in B_\epsilon(x)\)
This contradicts \(x_n \in F\) for all \(n\)
\(\Longleftarrow\)
Next prove sufficiency
Pick any closed \(F\) and let \(G := F^c\), need to prove that \(G\) is open
Suppose to the contrary that \(G\) is not open
Then exists some non-interior \(x \in G\), that is no \(\epsilon\)-ball around \(x\) lies entirely in \(G\)
Then it is possible to find a sequence \(\{x_n\}\) which converges to \(x \in G\), but every element of which lies in the \(B_{1/n}(x) \cap F\)
This contradicts the fact that \(F\) is closed
Fact
Any singleton \(\{ x \} \subset \mathbb{R}^N\) is closed
Proof
Let’s prove this by showing that \(\{x\}^c\) is open
Pick any \(y \in \{x\}^c\)
We claim that \(y\) is interior to \(\{x\}^c\)
Since \(y \in \{x\}^c\) it must be that \(y \ne x\)
Therefore, exists \(\epsilon > 0\) such that \(B_\epsilon(y) \cap B_\epsilon(x) = \varnothing\)
In particular, \(x \notin B_\epsilon(y)\), and hence \(B_\epsilon(y) \subset \{x\}^c\)
Therefore \(y\) is interior as claimed
Since \(y\) was arbitrary it follows that \(\{x\}^c\) is open and \(\{x\}\) is closed
Fact
Any finite union of open sets is open
Any finite intersection of closed sets is closed
Proof
Proof of first fact:
Let \(G := \cup_{\lambda \in \Lambda} G_\lambda\), where each \(G_\lambda\) is open
We claim that any given \(x \in G\) is interior to \(G\)
Pick any \(x \in G\)
By definition, \(x \in G_\lambda\) for some \(\lambda\)
Since \(G_\lambda\) is open, \(\exists \, \epsilon > 0\) such that \(B_\epsilon(x) \subset G_\lambda\)
But \(G_\lambda \subset G\), so \(B_\epsilon(x) \subset G\) also holds
In other words, \(x\) is interior to \(G\)
But be careful:
An infinite intersection of open sets is not necessarily open
An infinite union of closed sets is not necessarily closed
For example, if \(G_n := (-1/n, 1/n)\), then \(\cap_{n \in \mathbb{N}} G_n = \{0\} \)
Definition
Set \(X\) is called compact if it is both closed and bounded.
XXX
Weierstrass boundedness theorem#
Putting together all the above material to formulate a fundamental result which is essential for establishing the existence of maxima and minima of functions in the next section.
Definition
A function \(f\) is called bounded if its range is a bounded set.
Fact
Consider a continuous function \(f: X \subset \mathbb{R}^N \to \mathbb{R}\).
If \(X\) is compact, then \(f\) is bounded on \(X\).
Proof
Sketch of the proof:
Suppose that range of \(f\) denoted \(f(X)\) is not a bounded set
Then we can find a sequence \(\{x_n\}\) in \(X\) such \(\forall n\in\mathbb{N}\) there exists \(f(x_n)\) such that \(|f(n)|>n\).
Sequence \(\{x_n\}\) is bounded, so by Bolzano-Weierstrass theorem it has a convergent subsequence \(\{x_{n_k}\}\), where \(n_k\) is a subset of \(\mathbb{N}\) index by \(k\), and thus \(k \leqslant n_k\) for all \(k\)
Denote by \(L\) the limit of this subsequence, \(L = \lim_{k \to \infty} \{x_{n_k}\}\)
\(L \in X\) because \(X\) is a compact and thus is a closed set
By continuity of \(f\) at \(L\) we have that \(f(x_{n_k}) \to f(L)\)
Then the sequence \(\{f(x_{n_k})\}\) is bounded due to the properties of the limit (see above)
This contradicts that by our construction \(|f(x_n)| > n \geqslant k\) where \(k\) can be arbitrary large
Also see the discussion here