constituents

Functions is self-concordant if:

\begin{align} \mid f’’’\qty(x)\mid \leq 2f’’\qty(x)^{\frac{3}{2}}, \forall x \in \text{dom } f \end{align}

and \(f\) is self-concordant if \(g\qty(t) = f\qty(x+tv)\) is self concordant for all \(x \in \text{dom } f\).

requirements

Convergence analysis! There exists \(\eta \in (0, \frac{1}{4}]\), \(\gamma > 0\) such that:

• if \(\lambda \qty(x) > \eta\), then \(f\qty(x^{(k+1)}) - f\qty(x^{(k)}) \leq -y\)
• if \(\lambda \qty(x) \leq \eta\), then \(2\lambda \qty(x^{(k+1)}) \leq \qty(2 \lambda \qty(x^{(k)}))^{2}\)

and \(\eta, \gamma\) depends only on backtracking line search parameters. This gives bounds:

Descent methods are generally of shape:

\begin{align} x^{(k+1)} = x^{(k)} + t^{(k)} \delta x^{(k)} \end{align}

choosing these is a matter of which descent method you choose. The Hessian thus exposes:

\begin{align} \qty {x + v \mid v^{T} \nabla^{2} f\qty(x) v \leq 1} \end{align}

line search

backtracking line search

A first-order Taylor line in \(t\), centered about \(x\):

\begin{align} f\qty(x) + t \nabla f\qty(x)^{T} \Delta x \end{align}

We can degrade this to raise it to be slightly higher:

constituents

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}

constituents

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}

FLOP

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