Critical points and approximation

.title[
# Critical points and approximation
]
.author[
### <a href="https://jmclip.github.io/MACSS_math_camp/">MACS 33000</a> University of Chicago
]

---

# Misc

* Gradescope: grading underway -- should be all OK
* Academic Integrity: 8/29 @ 11:30 am
* No homework tomorrow (!!)

---
# Learning objectives

* Define critical points
* Calculate critical points via analytical methods
* Demonstrate optimization using maximum likelihood estimation
* Identify need for approximation methods for calculating critical points
* Explain and demonstrate root finding procedures using Newton-Raphson hill climber
* Demonstrate comptuational optimization using gradient descent

---

# Rolle's theorem

* Suppose `$f:[a, b] \rightarrow \Re$`
* Suppose `$f$` has a relative maxima or minima on `$(a,b)$` and call that `$c \in (a, b)$`
* Then `$f'(c) = 0$`

]

* Rolle's theorem guarantees that, at some point, `$f^{'}(x) = 0$`
* Intuition from proof - what happens as we approach from the left? 
* Intuition from proof - what happens as we approach from the right?

]

---

# Higher order derivatives
Conceptually, we are thinking about changes (get excited for all the *moments* you're going to have in stats later!). The first derivative tells us about the rate of change of our function.

--
**BUT!** we can also explore how fast the function is changing...that is, the rate of change for our rate of change. Here, we can understand the acceleration of change. We can keep going (provided our function is differentiable).

---

# Higher order derivatives
(in other words:)
* Derivatives of derivatives
* First derivative

`$$f'(x),  ~~ y',  ~~ \frac{d}{dx}f(x), ~~ \frac{dy}{dx}$$`

* Second derivative

`$$f''(x), ~~ y'', ~~ \frac{d^2}{dx^2}f(x), ~~ \frac{d^2y}{dx^2}$$`

* `$n$`th derivative

`$$\frac{d^n}{dx^n}f(x), \quad \frac{d^ny}{dx^n}$$`

---

# Higher order derivatives: example
Suppose we start with a function. `$x^3$` -- let's explore the different derivatives we might take. Try it out!

--
$$
`\begin{aligned}
f(x) &=x^3\\
f^{\prime}(x) &=3x^2\\
f^{\prime\prime}(x) &=6x \\
f^{\prime\prime\prime}(x) &=6\\
f^{\prime\prime\prime\prime}(x) &=0\\
\end{aligned}`
$$

* If `$f(x)$` is differentiable, also continuous
* If `$f'(x)$` is differentiable, then **continuously differentiable**
* Optimization requires differentiation

---

# Inflection point
Inflection points are where we move from being concave down to concave up (or vice versa).

---

# Inflection point

> For a given function `$y = f(x)$`, a point `$(x^∗, y^∗)$` where the second derivative immediately on one side of the point is signed oppositely to the second derivative immediately on the other side

---

# Inflection point

Let's start with a basic plot: here, we have a function: `$\frac{x^3}{15} - x^2 + 4x +2$`. We can see where we might guess there are the concave up / down points and where the inflection point might be.

---

# Inflection point

Let's now consider the same function, but the derivative. We are expecting THE VALUE OF CHANGE (AKA RATE OF CHANGE TO BE ZERO). GREEN: where the derivative (change) is positive or negative. GRAY: point where we don't see any more change (rate of change = 0).

<img src="04-critical-points_files/figure-html/inflect-deriv0-1.png" width="864" style="display: block; margin: auto;" />
--

### Derivative of original function:

<img src="04-critical-points_files/figure-html/inflect-deriv1-1.png" width="864" style="display: block; margin: auto;" />
---

# Inflection point

---

# Concavity

* Concave up (convex)
* Concave down (concave)
* Verification
    * Graphically
    * Analytically

---

# Concavity

* Where a function is twice differentiable and concave over some area, then the function is concave down where `$f''(x) < 0$` and concave up where `$f''(x) > 0$`

What does this mean? 
--

* If it's concave, there must be a critical point `$(f'(x)=0)$`. Let's start there.

* We are then moving away from that point and we're either *increasing* (min - concave up) or *decreasing* (max - concave down). 
 * If we're increasing, the second derivative is positive, `$f''(x) > 0$`. 
 * If we're decreasing, the second derivative is negative, `$f''(x) < 0$`.

---

# Concavity

* Where a function is twice differentiable and concave over some area, then the function is concave down where `$f''(x) < 0$` and concave up where `$f''(x) > 0$`

---

# Exponential function

]

Exploring change:
 
$$
`\begin{aligned}
f(x) & = e^{x} \text{ (what the function is doing?)}\\ 
f^{'}(x) & = e^{x} \text{ rate of change (never zero!)} \\
f^{''}(x) & = e^{x} \text{ rate of change of rate of change} \\
 & \text{ (still never zero!)}
\end{aligned}`
$$

]

---

# Natural logarithm

]

.pull-right[
Exploring change:
 
$$
`\begin{aligned}
f(x) & = \ln(x) \\ \\
f^{'}(x) & = \frac{1}{x} \\
& \text{ rate of change (always positive (above 0)*}\\ \\
f^{''}(x) & = -\frac{1}{x^2} \\
& \text{ rate of change of rate of change}
\end{aligned}`
$$

\* .tiny[note that `$ln(x)$` only defined for `$x > 0$`]

]

---

# Types of extreme values

* Maximum or minimum
* Local or global

--
*You can find these graphically or analytically*
---

# Types of extreme values: Examples

How would we evaluate the extreme values here? 
<img src="04-critical-points_files/figure-html/endpoints-1.png" width="864" style="display: block; margin: auto;" />

* Derivative of the function. `$f'(x) = 1$`
* Set to zero and solve. (n/a)
* Options: 
  * Plug in values to original function to find corresponding f(x). (only evaluate at end points (0 and 5))
  * Find second derivative to see if positive (min) or negative (max)

---

# Types of extreme values: Example

Try with a neighbor: 
<img src="04-critical-points_files/figure-html/max-middle-1.png" width="864" style="display: block; margin: auto;" />

#### `$f'(x) = -2x$`;  zero at `$x=0$`, `$f(x) = 0^2+5=5$`.

But is it a max or min?

Try adjacent point (e.g. -1 or 1). `$(-1^2+5)=4$` OR take second derivative: `$-2$`

Since 4 is less than 5, we know this is a max at x = 0, since `$f(x = 0) > f(x=1)$`. Similarly, the second derivative is negative, so this also indicates that it is a max (decreasing from this point).

---

# Types of extreme values

---

# Types of extreme values

---

# Types of extreme values

<img src="04-critical-points_files/figure-html/inflection-point-1.png" width="864" style="display: block; margin: auto;" />
---

### Function and derivative

<img src="04-critical-points_files/figure-html/inflection-point-2-1.png" width="864" style="display: block; margin: auto;" />
---

# Framework for analytical optimization

1. Find `$f'(x)$`
1. Set `$f'(x)=0$` and solve for `$x$`. Call all `$x_0$` such that `$f'(x_0)=0$` **critical values**
1. Find `$f''(x)$`. Evaluate at each `$x_0$`
 * If `$f''(x) > 0$`, concave up, and therefore a local minimum
 * If `$f''(x) < 0$`, concave down, and therefore a local maximum
 * If it's the global maximum/minimum, it will produce the largest/smallest value for `$f(x)$`
 * On a closed range along the domain, **check the endpoints as well**

---

### Ex: `$f(x) = -x^2$`,  `$x \in [-3, 3]$`

---

### Ex:  `$f(x) = x^3 - 6x-2$`, `$x \in [-3, 3]$`

---
class: center, middle, inverse

# CSS Application of optimization: MLE
You aren't going to have to calculate this,

but you need to understand the big picture

---