iterative method
Last edited: February 2, 2026constituents
requirements
Iterative methods require a starting point \(x^{(0)}\) such that:
- \(x^{(0)} \in \text{dom } f\)
- sublevel set \(S = \qty {x \mid f\qty(x) \leq f\qty(x^{(0)})}\) is closed
additional information
strong convexity
\(f\) is strongly convex on \(S\) if there exists \(m > 0\) such that:
\begin{align} \nabla^{2}f\qty(x) \succeq mI, \forall x \in S \end{align}
if \(f\) is strongly convex for \(x, y \in S\), we have:
\begin{align} f\qty(y) \geq f\qty(x) + \nabla f\qty(x)^{T} \qty(y-x) + \frac{m}{2} \norm{x-y}_{2}^{2} \end{align}
Newton's Method
Last edited: February 2, 2026constituents
requirements
A Newton step is:
\begin{align} \Delta x_{nt} = -\nabla^{2}f\qty(x)^{-1}\nabla f\qty(x) \end{align}
additional information
Newton’s method is affine invariant!
convergence
Then number of steps until convergence for Newton’s method relates to the third derivative because its step changes as a function of how the second derivative changes.
Number of iterations until \(f\qty(x) - p^{*} \leq \epsilon\) is bounded above by:
\begin{align} \frac{f\qty(x^{(0)}) - p^{*}}{\gamma} + \log \log \qty(\frac{\epsilon_{0}}{\epsilon}) \end{align}
Numerical Linear Algebra
Last edited: February 2, 2026FLOP
A FLOP is a “floating-point operations”. One addition, subtraction, multiplication, or division of two floating-point numbers.
Basic Linear Algebra Subroutines
BLAS Level 1
Vector-Vector operations
- inner product \(x^{T}y\) which is \(2n-1\) flops
- sum \(x+y\) and scale \(\alpha x\) which is \(n\) flops
BLAS Level 2
Matrix-vector product
\(y = Ax\) with \(A \in \mathbb{R}^{m \times n}\)
- standard multiply \(m\qty(2n - 1)\)
- \(2N\) if \(A\) is sparse with \(N\) non-zero elements
- \(2p\qty(n+m)\) if \(A\) is given as \(A = UV^{T}\), where \(U \in \mathbb{R}^{m \times p}\) and \(V \in \mathbb{R}^{n \times p}\), which is called a “banded” matrix (sparse everywhere except for a strip nexht to diagonal)
BLAS Level 3
Matrix-matrix operations