Critical points, optimization, and matrices

.title[
# Critical points, optimization, and matrices
]
.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: workshop upcoming
* MACSS Orientation 9/23 (expect notices re: scheduling, etc.)
* JCLIP OH in classroom until 4pm Mon-Thurs!

---
# Learning objectives

* Define and calculate critical points and inflection points
* Calculate higher order derivatives
* Demonstrate optimization using maximum likelihood estimation and gradient descent
* Linear vs matrix algebra!!
* Define vector and matrix

---

# Fermat's interior extremum theorem

* Suppose `$f:[a, b] \rightarrow \mathbb{R}$` and is differentiable on c. 
* Suppose `$f$` has a relative maximum or minimum on `$(a,b)$` and call that `$c \in (a, b)$`
* Then `$f'(c) = 0$`

]

* Fermat's theorem guarantees that, at some point, `$f^{'}(c) = 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 derivative 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, then it is also continuous
* If `$f'(x)$` is differentiable, then f is also  **continuously differentiable**
* Note: these run one direction only. 
  * Continuous does not imply differentiable: `$|x|$` at `$x=0$` 
  * Continuously differentiable does not imply `$f'$` is differentiable: `$x|x|$` at  `$x=0$`
* Analytical 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

```
## $ncol
## [1] 1
## 
## $nrow
## list()
## attr(,"class")
## [1] "waiver"
## 
## $byrow
## list()
## attr(,"class")
## [1] "waiver"
## 
## $widths
## list()
## attr(,"class")
## [1] "waiver"
## 
## $heights
## list()
## attr(,"class")
## [1] "waiver"
## 
## $guides
## list()
## attr(,"class")
## [1] "waiver"
## 
## $tag_level
## list()
## attr(,"class")
## [1] "waiver"
## 
## $axes
## list()
## attr(,"class")
## [1] "waiver"
## 
## $axis_titles
## list()
## attr(,"class")
## [1] "waiver"
## 
## $design
## list()
## attr(,"class")
## [1] "waiver"
## 
## attr(,"class")
## [1] "plot_layout"
```

---

# Inflection point: example function

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

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

### Derivative of original function: 
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). `$f'(x)= \frac{x^2}{5}-2x+4$`, `$f''(x)= 0.4x-2$`.

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

# Inflection point

---

# Concavity

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

---

# Concavity

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

What does this mean? 
--

* A critical point when f'(x)=0 has potential for some kind of concavity (sometimes, but not always! (`$x^3$`)).

* 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 through the critical point, the second derivative is positive, `$f''(x) > 0$`. 
 * If we're decreasing through the critical point, 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 where `$f''(x) > 0$` is **concave up**. Recall: `$f(x)=(x^3 - 15 * x^2 + 60 * x + 30) / 15$`.

---

# 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)$` is 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" alt="" width="85%" style="display: block; margin: auto;" />

---
# Types of extreme values: Examples

How would we evaluate the extreme values here? 
<img src="04-critical-points_files/figure-html/endpoints2-1.png" alt="" width="25%" 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) [not informative]

---

# Types of extreme values: Examples

Try with a neighbor: 
<img src="04-critical-points_files/figure-html/max-middle-1.png" alt="" 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). `$f(-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 (concave down 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" alt="" width="85%" style="display: block; margin: auto;" />
---

### Function and derivative

<img src="04-critical-points_files/figure-html/inflection-point-2-1.png" alt="" width="85%" 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$` or `$f'(x_0)$` does not exist **critical points**
1. Find `$f''(x_0)$`. Evaluate at each `$x_0$`
 * If `$f''(x_0) > 0$`, concave up, and therefore a local minimum
 * If `$f''(x_0) < 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]$`

---

# CSS Application of optimization: MLE
### You aren't going to have to calculate this, but you need to understand the big picture

---