Prerequisites & Notation

This chapter builds on linear algebra (Chapter 1) and basic probability (Chapter 2). The following topics should feel comfortable before proceeding.

Inner products, norms, and projections in $\mathbb{R}^n$ (Review ch01)
Self-check: Can you project a vector onto a subspace and compute the projection error?
Eigenvalue decomposition and positive (semi)definiteness(Review ch01)
Self-check: Can you determine whether a symmetric matrix is positive definite by inspecting its eigenvalues or attempting a Cholesky factorization?
Matrix calculus: gradients and Hessians(Review ch01)
Self-check: Can you compute $\nabla_{\mathbf{x}} (\mathbf{x}^T \mathbf{A} \mathbf{x})$ for symmetric $\mathbf{A}$ ?
Expectation, variance, and basic probabilistic inequalities(Review ch02)
Self-check: Can you state Jensen's inequality and explain why $\mathbb{E}[\log X] \leq \log \mathbb{E}[X]$ ?
Multivariable calculus: partial derivatives, chain rule, Taylor expansion
Self-check: Can you write the second-order Taylor expansion of $f : \mathbb{R}^n \to \mathbb{R}$ around a point $\mathbf{x}_0$ ?

Symbols introduced in this chapter. See also the NGlobal Notation Table master table in the front matter.

Symbol	Meaning	Introduced
$\mathcal{C}$	A convex set in $\mathbb{R}^n$	s01
$\text{epi}(f)$	Epigraph of a function $f$	s01
$\nabla f(\mathbf{x})$	Gradient of $f$ at $\mathbf{x}$	s01
$\nabla^2 f(\mathbf{x})$	Hessian matrix of $f$ at $\mathbf{x}$	s01
$\mathbf{A} \succeq 0$	$\mathbf{A}$ is positive semidefinite	s01
$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu})$	Lagrangian function	s02
$g(\boldsymbol{\lambda}, \boldsymbol{\nu})$	Lagrangian dual function	s02
$p^\star$	Optimal primal value	s02
$d^\star$	Optimal dual value	s02
$\mu$	Water level in water-filling	s03
$\alpha_k$	Step size (learning rate) at iteration $k$	s04
$\text{prox}_{\alpha g}(\mathbf{x})$	Proximal operator of $g$ with parameter $\alpha$	s04