# π Fundamentals of optimization#

β± | words

The goal is

Weierstrass extreme value theoremwhich establishes the existence of max and min for continuous functions over compact setsTalk about sets in \(\mathbb{R}\) first \(\rightarrow\) then transitions to functions

In the introductory lecture we have seen a few simple examples of optimization problems:

a solution exists

the solution is unique and not hard to find

However, for the *majority* of problems such properties arenβt guaranteed

`We need some idea of how to check whether a solution to an optimization problems even exists!`

Consider the problem of finding the βmaximumβ or βminimumβ of a function

A first issue is that such values might not be well defined

Recall that the set of maximizers/minimizers can be

empty

a singleton (contains one element)

infinite (contains infinitely many elements)

## Show code cell content

```
from myst_nb import glue
import matplotlib.pyplot as plt
import numpy as np
def subplots():
"Custom subplots with axes through the origin"
fig, ax = plt.subplots()
# Set the axes through the origin
for spine in ['left', 'bottom']:
ax.spines[spine].set_position('zero')
for spine in ['right', 'top']:
ax.spines[spine].set_color('none')
return fig, ax
xmin, xmax = 0, 1
xgrid1 = np.linspace(xmin, xmax, 100)
xgrid2 = np.linspace(xmax, 2, 10)
fig, ax = subplots()
ax.set_ylim(0, 1.1)
ax.set_xlim(-0.0, 2)
func_string = r'$f(x) = x^2$ if $x < 1$ else $f(x) = 0.5$'
ax.plot(xgrid1, xgrid1**2, 'b-', lw=3, label=func_string)
ax.plot(xgrid2, -0.25 * xgrid2 + 0.5, 'b-', lw=3)
ax.plot(xgrid1[-1], xgrid1[-1]**2, marker='o', markerfacecolor='white', markeredgewidth=2, markersize=6, color='b')
ax.plot(xgrid2[0], -0.25 * xgrid2[0] + 0.5, marker='.', markerfacecolor='b', markeredgewidth=2, markersize=10, color='b')
glue("fig_none", fig, display=False)
```

Example: no maximizers

The following function has no maximizers on \([0, 2]\)

## Suprema and Infima (\(\mathrm{sup}\) + \(\mathrm{inf}\))#

Always well defined

Agree with max and min when the latter exist

Definition

Let \(A \subset \mathbb{R}\) (we restrict attention to subsets of real line for now)

A number \(u \in \mathbb{R}\) is called an **upper bound** of \(A\) if

Example

If \(A = (0, 1)\) then 10 is an upper bound of \(A\) β indeed, every element of \((0, 1)\) is \(\leqslant 10\)

If \(A = (0, 1)\) then 1 is an upper bound of \(A\) β indeed, every element of \((0, 1)\) is \(\leqslant 1\)

If \(A = (0, 1)\) then \(0.75\) is **not** an upper bound of \(A\)

Definition

Let \(U(A)\) denote **set of all upper bounds** of \(A\).

A set \(A \subset \mathbb{R}\) is called **bounded above** if \(U(A)\) is not empty

Examples

If \(A = [0, 1]\), then \(U(A) = [1, \infty)\)

If \(A = (0, 1)\), then \(U(A) = [1, \infty)\)

If \(A = (0, 1) \cup (2, 3)\), then \(U(A) = [3, \infty)\)

If \(A = \mathbb{N}\), then \(U(A) = \varnothing\)

Definition

The *least upper bound* \(s\) of \(A\) is called **supremum** of \(A\), denoted \(s=\sup A\), i.e.

Example

If \(A = (0, 1]\), then \(U(A) = [1, \infty)\), so \(\sup A = 1\)

If \(A = (0, 1)\), then \(U(A) = [1, \infty)\), so \(\sup A = 1\)

Definition

A **lower bound** of \(A \subset \mathbb{R}\) is any \(\ell \in \mathbb{R}\) such that \(\ell \leqslant a\) for all \(a \in A\).

Let \(L(A)\) denote **set of all lower bounds** of \(A\).

A set \(A \subset \mathbb{R}\) is called **bounded below** if \(L(A)\) is not empty.

The highest of the lower bounds \(p\) is called the **infimum** of \(A\), denoted \(p=\inf A\), i.e.

Example

If \(A = [0, 1]\), then \(\inf A = 0\)

If \(A = (0, 1)\), then \(\inf A = 0\)

### Some useful facts#

Fact

Boundedness of a subset of the set of real numbers is equivalent to it being bounded above and below.

Proof

The proof follows trivially from the definitions

Fact

Every nonempty subset of \(\mathbb{R}\) bounded above has a supremum in \(\mathbb{R}\)

Every nonempty subset of \(\mathbb{R}\) bounded below has an infimum in \(\mathbb{R}\)

Proof

Similar to the proof that all Cauchy sequences converge, follows from the density property of \(\mathbb{R}\)

Some textbooks allow all sets to have a supremum and infimum, even if they are not bounded. This is achieved by extending the set of real numbers with \(\{-\infty,\infty\}\)

Then, if \(A\) is unbounded above then \(\sup A = \infty\), and if \(A\) is unbounded below then \(\inf A = -\infty\).

Note

Aside: Conventions for dealing with symbols β\(\infty\)ββ and β\(-\infty\)β If \(a \in \mathbb{R}\), then

\(a + \infty = \infty\)

\(a - \infty = -\infty\)

\(a \times \infty = \infty\) if \(a \ne 0\), \(0 \times \infty = 0\)

\(-\infty < a < \infty\)

\(\infty + \infty = \infty\)

\(-\infty - \infty = -\infty\) But \(\infty - \infty\) is not defined

Fact

Let \(A\) be any set bounded above and let \(s = \sup A\). There exists a sequence \(\{x_n\}\) in \(A\) with \(x_n \to s\).

Analogously, if \(A\) is bounded below and \(p = \inf A\), then there exists a sequence \(\{x_n\}\) in \(A\) with \(x_n \to p\).

Proof

Note that

(Otherwise \(s\) is not a sup, because \(s-\frac{1}{n}\) is a smaller upper bound)

The sequence \(\{x_n\}\) lies in \(A\) and converges to \(s\).

The proof for the infimum is analogous.

## Maxima and Minima (\(\max\) + \(\min\))#

Definition

We call \(a^*\) the **maximum** of \(A \subset \mathbb{R}\), denoted \(a^* = \max A\), if

We call \(a^*\) the **minimum** of \(A \subset \mathbb{R}\) and write \(a^* = \min A\) if

Example

For \(A = [0, 1]\) \(\max A = 1\) and \(\min A = 0\)

### Relationship between max/min and sup/inf#

Fact

Let \(A\) be any subset of \(\mathbb{R}\)

If \(\sup A \in A\), then \(\max A\) exists and \(\max A = \sup A\)

If \(\inf A \in A\), then \(\min A\) exists and \(\min A = \inf A\)

In other words, when max and min exist they agree with sup and inf

Proof

Proof of case 1: Let \(a^* = \sup A\) and suppose \(a^* \in A\)

We want to show that \(\max A = a^*\)

Since \(a^* \in A\), we need only show that \(a \leqslant a^*\) for all \(a \in A\)

This follows from \(a^* = \sup A\), which implies \(a^* \in U(A)\)

Fact

If \(F \subset \mathbb{R}\) is a closed and bounded, then \(\max F\) and \(\min F\) both exist

Proof

Proof for the max case:

Since \(F\) is bounded,

\(\sup F\) exists

\(\exists\) a sequence \(\{x_n\} \subset F\) with \(x_n \to \sup F\)

Since \(F\) is closed, this implies that \(\sup F \in F\)

Hence \(\max F\) exists and \(\max F = \sup F\)

## Segway to functions#

Of course, in optimization we are mainly interested in maximizing and minimizing functions

Will apply the notions of supremum and infimum, minimum and maximum to the **range of a function**

Equivalently, we may consider the **image of a set** \(X \subset \mathbb{R}^N\) under a function \(f\)

Definition

Let \(f \colon A \to \mathbb{R}\), where \(A\) is any set

The **supremum of \(f\) on \(A\)** is defined as

The **infimum of \(f\) on \(A\)** is defined as

Definition

Let \(f \colon A \to \mathbb{R}\) where \(A\) is any set

The **maximum** of \(f\) on \(A\) is defined as

The **minimum** of \(f\) on \(A\) is defined as

$$

Definition

A **maximizer** of \(f\) on \(A\) is a point \(a^* \in A\) such that

The set of all maximizers is typically denoted by

Definition

A **minimizer** of \(f\) on \(A\) is a point \(a^* \in A\) such that

The set of all minimizers is typically denoted by

## Weierstrass extreme value theorem#

`Fundamental result on existence of maxima and minima of functions!`

Fact (Weierstrass extreme value theorem)

If \(f: A \subset \mathbb{R}^N \to \mathbb{R}\)
is continuous and \(A\) is closed and bounded,

then \(f\) has both a maximizer and a minimizer on \(A\).

Proof

Sketch of the proof:

If \(f\) is continuous and \(A\) is compact, then \(f(A)\) is bounded, see relevant fact

Because \(f(A)\) is bounded \(\sup f(A)\) and \(\inf f(A)\) exist, see relevant fact

There is a sequence \(\{y_n\} \in f(A)\) converging to sup/inf, see relevant fact

Consider the corresponding sequence of \(x\) such that \(y=f(x)\)

It may not be convergent, but is bounded (belongs to compact), therefore contains a convergent subsequence (by Bolzano-Weierstrass theorem), see relevant fact

Let \(c\) be the limit of a convergent subsequence

Then by definition of continuity \(f(c)\) is the limit of the sequence \(f(x_n)\)

\(f(c)\) must then be the same as the limit of the sequence \(y_n\) = sup/inf due to the fact that any sequence can have at most one limit, see relevant fact

Therefore sup/inf is attained at \(x=c\)

Example

Consider the problem

where

\(r=\) interest rate, \(w=\) wealth, \(\beta=\) discount factor

all parameters \(> 0\)

Let \(B\) be all \((c_1, c_2)\) satisfying the constraint

**Exercise:** Show that the budget set \(B\) is a closed, bounded subset of \(\mathbb{R}^2\)

**Exercise:** Show that \(U\) is continuous on \(B\)

We conclude that a maximizer exists

## References and further reading#

## References

Simon & Blume: 12.2, 12.3, 12.4, 12.5, 13.4, 29.2, 30.1

Sundaram: 1.2.6, 1.2.7, 1.2.8, 1.2.9, 1.2.10, 1.4.1, section 3