1
Q
Lemma
A symmetric 2x2 matrix A is…
5 points
A
- positive definite iff |A| > 0 and a > 0
- positive semidefinite, not definite iff |A| = 0 and a + c ≥ 0
- negative definite iff |A| > 0 and a < 0
- negative semidefinite, not definite iff |A| = 0 and a + c ≤ 0
- indefinite iff |A| = 0
2
Q
Lemma
If g: ℝ → ℝ is a stricly increasing function, then
Optimization Tricks
A
arg min f(x) = arg min g(f(x)) for x ∈ F
3
Q
Lemma
If g: ℝ → ℝ is a 1-1 function, then
Optimization Tricks
A
arg min f(x) = g(arg min f(g(x))) for x ∈ F
4
Q
Knowledge
Midpoint Rule
2 points
A
- Approximate f: [a, b] → ℝ by 0ᵗʰ-order Taylor polynomial at m
- M₁[f, a, b] = (b - a)f(m)
5
Q
Knowledge
Bounds for err(M₁)[f, a, b]
2 points
A
- Lower bound: -((b - a)³/24)D̅₂
- Upper bound: -((b - a)³/24)D̲₂
6
Q
Knowledge
Trapezium Rule
2 points
A
- Approximate f: [a, b] → ℝ by its linear interpolation
- T₁[f, a, b] = ((b - a)/2)(f(a) + f(b))
7
Q
Knowledge
Bounds for err(T₁)[f, a, b]
2 points
A
- Lower bound: ((b - a)³/12)D̲₂
- Upper bound: ((b - a)³/12)D̅₂
8
Q
Knowledge
Simpson’s Rule
2 points
A
- Approximate f: [a, b] → ℝ by quadratic interpolation
- S₂[f, a, b] = ((b - a)/6)(f(a) + 4f(m) + f(b))
9
Q
Knowledge
Bounds for err(S₂)[f, a, b]
2 points
A
- Lower bound: ((b - a)⁵/2880)D̲₄
- Upper bound: ((b - a)⁵/2880)D̅₄
10
Q
Formula
Composite Midpoint Rule
A
Mₙ[f, a, b] = ((b - a)/n)(f((x₀ + x₁)/2) + … + f((xₙ₋₁ + xₙ)/2))
11
Q
Knowledge
Composite Midpoint Rule Error Bounds
2 points
A
- O(n⁻²)
- Depends on -f’’
12
Q
Formula
Composite Simpson’s Rule
A
Sₙ[f, a, b] = ((b - a)/(3n))(f(x₀) + 4f(x₁) + 2f(x₂) + 4f(x₃) + … + 4f(xₙ₋₁) + f(xₙ))
13
Q
Knowledge
Composite Simpson’s Rule Error Bounds
2 points
A
- O(n⁻⁴)
- Depends on f’’’’
14
Q
Knowledge
d-dimensional Midpoint Rule Error Bounds
2 points
A
- N = nᵈ
- O(N^(-2/d))
15
Q
Knowledge
d-dimensional Simpson’s Rule Error Bounds
2 points
A
- N = nᵈ
- O(N^(-4/d))
16
Q
Knowledge
Monte Carlo Integration
4 points
A
- MCₙ[f, R] = A(R)(1/n)∑ᵢ f(Xᵢ)
- A(R) is the area or volume of R
- Xᵢ are indpenedently uniformly random on R
- Pdf is p(x) = 1/A(R) if x ∈ R otherwise p(x) = 0
17
Q
Lemma
MCₙ[f, r] is unbiased
A
E[MCₙ[f, r]] = ∫ᵣ f(x̲) dx̲
18
Q
Lemma
Var[MCₙ[f, R]] = …
2 points
A
- V / n for a constant V
- V can be estimated by ∑ᵢ f(Xᵢ) + ∑ᵢ f²(Xᵢ)
19
Q
Lemma
MCₙ[f, R] is consistent
A
P[|err(MCₙ)[f, R]| ≥ ε] → 0 as n → ∞ for any ε > 0
20
Q
Lemma
For large n err(MCₙ)[f, R] approaches
A
N(0, V/n)
21
Q
Knowledge
IEEE 754 Single Precision Standard
4 points
A
- 23 bits for m
- 8 bits for e
- 1 bit for sign
- ε = 2⁻²⁴ ≈ 6⋅10⁻⁸
22
Q
Knowledge
IEEE 254 Double Precision Standard
4 points
A
- 52 bits for m
- 11 bits for e
- 1 bit for sign
- ε = 2⁻⁵³ ≈ 10⁻¹⁶
23
Q
Knowledge
Truncation Error
A
Approximating an infinite process by a finite one
24
Q
Knowledge
Roundoff Error
A
Approximating a real number for example in floating point format
25
# Definition
Linear Convergence
| 2 points
* εₙ → 0
* |εₙ₊₁|/|εₙ| → a for 0 < a < 1
26
# Definition
Sublinear Convergence
| 2 points
* εₙ → 0
* |εₙ₊₁|/|εₙ| → 1
27
# Definition
Logarithmic Convergence
| 3 points
* εₙ → 0
* xₙ converges sublinearly
* |εₙ₊₂ - εₙ₊₁|/|εₙ₊₁ - εₙ| → 1
28
# Definition
Superlinear Convergence
| 2 points
* εₙ → 0
* |εₙ₊₁|/|εₙ| → 0
29
# Definition
Order-k Convergence
| 2 points
* εₙ → 0
* |εₙ₊₁|/|εₙ|ᵏ → a for a > 0, k > 1
30
# Lemma
If xₙ converges with order q, then ...
x₂ₙ converges with order q²
31
# Knowledge
Interval Bisection
| 4 points
* Let xₙ = (aₙ + bₙ)/2
* If f(aₙ)f(xₙ) < 0 then (aₙ, xₙ) is a bracket
* If f(aₙ)f(xₙ) > 0 then (xₙ, bₙ) is a bracket
* If f(xₙ) = 0 then we have found a root
32
# Knowledge
Interval Bisection Error Analysis
| 2 points
* |εₙ| < (b₀ - a₀)/2ⁿ⁺¹
* Linear convergence
33
# Knowledge
Newton's Method (1 dimension)
| 2 points
* Approximate f by its first-order Taylor polynomial
* xₙ₊₁ = xₙ - f(xₙ)/f'(xₙ)
34
# Lemma
Error Analysis for Newton's Method (1 dimension)
| 1st Lemma; 2 points
Assume f has two continuous derivatives and f(x\*) = 0
Let A(c) = max|f''(β)|/min|f'(α)| where α, β ∈ I = (x\* - c, x\* + c)
1. If xₙ ∈ I then |εₙ₊₁| ≤ (A(c)/2)εₙ²
2. If x₀ ∈ I and c A(c)/2 < 1 then xₙ → x\* at least quadratically
35
# Proof
Assume f has two continuous derivatives and f(x\*) = 0
Let A(c) = max|f''(β)|/min|f'(α)| where α, β ∈ I = (x\* - c, x\* + c)
1. If xₙ ∈ I then |εₙ₊₁| ≤ (A(c)/2)εₙ²
2. If x₀ ∈ I and c A(c)/2 < 1 then xₙ → x\* at least quadratically
| 4 points
* Use definition of Newton's method
* Use 2nd order Taylor's remainder term
* Show |εₙ| ≤ ρⁿ|ε₀| where ρ = c A(c)/2 by induction
* Apply 1 to inductive hypothesis
36
# Lemma
Error Analysis for Newton's Method (1 dimension)
| 2nd Lemma; 2 points
Assume f has two continuous derivatives and f(x\*) = 0
Let B(c) = max|f''(β)|/min|f'(α)| where I = (x₀ - 2c, x₀ + 2c)
1. If x\* ∈ (x₀ - c, x₀ + c) and c B(c)/2 < 1 then xₙ → x\* at least quadratically
2. Such an I exists if f'(x\*) ≠ 0
37
# Proof
Assume f has two continuous derivatives and f(x\*) = 0
Let B(c) = max|f''(β)|/min|f'(α)| where I = (x₀ - 2c, x₀ + 2c)
1. If x\* ∈ (x₀ - c, x₀ + c) and c B(c)/2 < 1 then xₙ → x\* at least quadratically
2. Such an I exists if f'(x\*) ≠ 0
| 5 points
* Deduce |ε₁| < ρc
* xₙ ∈ (x₀ - 2c, x₀ + 2c)
* Use induction to show |εₙ| ≤ ρⁿ|ε₀|
* A(c) → |f''(x\*)/f'(x\*)| as c → 0
* c A(c)/2 < 1 for sufficiently small c
38
# Knowledge
Secant Method (1 dimension)
| 2 points
* Approximate f by its linear interpolation
* xₙ₊₁ = xₙ - f(xₙ)(xₙ - xₙ₋₁)/(f(xₙ) - f(xₙ₋₁))
39
# Knowledge
Secant Method Error Analysis (1 dimension)
| 2 points
* Converges under same conditions as Newton's method
* Order ~1.62 convergence
40
# Knowledge
Halley's Method
| 4 points
* Second-order Taylor approximation
* Cubic convergence under certain conditions
* Second-order polynomial may have zero or two roots
* Solving second-order polynomials requires the slow square-root function
41
# Knowledge
Muller's Method
| 5 points
* Tracks three points on the function, interpolating them by a parabola
* Second-order polynomial may have zero or two roots
* Solving second-order polynomials requires the slow square-root function
* Allows complex roots so may converge to a complex number
* Order of convergence ~1.84
42
# Knowledge
Inverse Quadratic Interpolation
| 3 points
* Fit x = ay² + by + c
* Always has exactly one real solution to y = 0
* Order of convergence ~1.84
43
# Knowledge
Brent's Method
| 3 points
* Global convergence
* Linear convergence for badly-behaved functions and order ~1.84 for well-behaved
* Keeps track of three values, using IQI, but then Secant method if IQI tries to go outside the bracket and then interval bisection if neither provide sufficient reduction in the bracket size
44
# Knowledge
Newton's Method (d dimensions)
| 4 points
* Approximate each component of **f**(**x**) by its first-order Taylor polynomial
* **xₙ₊₁** = **xₙ** - (**J**(**f**)(**xₙ**))⁻¹**f**(**xₙ**)
* Solve **J**(**f**)(**xₙ**) **∆x** = -**f**(**xₙ**) then set **xₙ₊₁** = **xₙ** + **∆x**
* Computational cost of evaluating the Jacobian is O(d²) and solving the system is O(d³)
45
# Knowledge
Broyden's Method
| 6 points
* Track the Jacobian by an approximation
* **xₙ₊₁** = **xₙ** + **∆x**, **ĵₙ∆x** = -**f**(**xₙ**)
* Computational cost of solving the system is O(d³)
* Can track **ĵₙ⁻¹** for O(d²) computation
* Converges if started close to an isolated root slower than Newton's method
* Limited memory methods reduce space requirement to O(d)
46
# Knowledge
f(x) and f(x\*) may be indistinguishable when...
|x - x\*|/|x\*| < O(√ε)
47
# Knowledge
Golden Section Search
| 4 points
* A bracket is an interval (a, b, c) with f(b) < f(a) ∧ f(b) < f(c)
* If cₙ - bₙ > bₙ - aₙ then z = cₙ - ((√5 - 1)/2)(cₙ - bₙ)
* If f(b) < f(z) then aₙ₊₁ = aₙ, bₙ₊₁ = bₙ, cₙ₊₁ = z
* Symmetric for other cases
48
# Knowledge
Golden Section Search Error Analysis
| 2 points
* |εₙ| < Φⁿ⁺¹|c₀ - a₀|
* Linear convergence
49
# Knowledge
Line Search Methods
| 4 points
* **xₙ₊₁** = **xₙ** + αₙ **dₙ**
* **dₙ** should be a descent direction d(**xₙ** + α **dₙ**)/dα (0) = **dₙ**ᵀ **gₙ** < 0
* **dₙ**, **dₙ₋₁**, **dₙ₋₂** should not veer wildly in different directions
* αₙ should loosely minimize f(**xₙ** + α **dₙ**)
50
# Knowledge
Backtracking
| 3 points
* Start with αₙ = α'
* Repeatedly multiply through by a factor of 0 < ρ < 1 (usually ρ = 1/2) until the step length obeys the Armijo Rule
* Choose α' = αₙ₋₁ (**gₙ₋₁**ᵀ**dₙ₋₁**)/(**gₙ**ᵀ**dₙ**)
51
# Knowledge
Armijo Rule
| 2 points
* f(**xₙ** + αₙ**dₙ**) < f(**xₙ**) + σαₙ**gₙ**ᵀ**dₙ**
* σ in the range 10⁻⁴ to 10⁻¹
52
# Knowledge
Coordinate Gradient Descent
**dₙ** = ±**eᵢ**
53
# Knowledge
Gradient Descent
| 3 points
* **dₙ** = -**gₙ**
* O(d) computation for 1 evaluation of df/d**x**
* Global, linear convergence
54
# Knowledge
Newton's Method
| 3 points
## Footnote
Gradient Descent
* Approximate f by its second-order Taylor polynomial
* d̲ₙ = -H̲(f)(x̲ₙ)⁻¹ g̲ₙ
* αₙ = 1
55
# Knowledge
Newton's Method Error Analysis
| 2 points
## Footnote
Gradient Descent
* O(d²) derivatives in **H**(f) and O(d³) computation
* Convergence not always guaranteed and only quadratic when **H**(f)(**xₙ**) is positive definite near the minimum
56
# Knowledge
BFGS Method
| 3 points
* Update an approximate Hessian **Ĥₙ**
* **dₙ** = -**Ĥₙ**⁻¹ **gₙ**
* Shermar-Morrison formula updates an approximate inverse Hessian **Ĥₙ**⁻¹
57
# Knowledge
BFGS Method Error Analysis
| 2 points
* O(d³) computation or O(d²) using Shermar-Morrison formula
* Global, superlinear convergence for well-behaved f
