Chapter 1: Mathematical Background

This chapter establishes all mathematical preliminaries needed throughout the course, from basic linear algebra and calculus to foundational optimization concepts.

---

1.1 What Is Optimization?

Optimization is the process of finding the best decision among a set of alternatives, subject to restrictions.

The Optimization Model

The standard formulation of an optimization problem is:

$$\begin{array}{rl}\mathrm{minimize}& f(x)\\ \mathrm{subject}\mathrm{to}& x\in X\end{array}$$

where:

Decision variable(s) $x$: represents some action or choice we control.

Objective function $f(\cdot )$: represents total cost, risk, or negative profit (the quantity we wish to minimize or maximize).

Constraint set $X$: puts restrictions on the permissible choices of $x$.

Why Optimization Matters

Optimization appears across virtually every domain:

• Applied science, engineering, economics, finance, medicine, statistics, business
• General decision and policy making
• Image inpainting (filling missing regions)
• Recommendation systems (predicting user preferences)
• Linear and logistic regression (predictive modeling)
• Neural networks (deep learning)
• Portfolio design, logistics, diet planning

As Maupertuis (1698–1759) proclaimed:

"...nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear."

Key Conceptual Distinctions

Global vs. local optimum: A global optimum is the best among all feasible points; a local optimum is best only within a neighborhood.

Feasible vs. infeasible point: A feasible point satisfies all constraints; an infeasible point violates at least one constraint.

Constrained vs. unconstrained optimization: A constrained problem has $X⊊{\mathbb{R}}^n$; an unconstrained problem has $X={\mathbb{R}}^n$.

Linear vs. nonlinear optimization: A linear problem has a linear objective and linear constraints; a nonlinear problem has at least one nonlinear function.

Convex vs. nonconvex optimization: A convex problem has a convex objective minimized over a convex feasible set; nonconvex problems may have multiple local optima.

---

1.2 Inner Products

Inner Product of Vectors

Definition: For vectors $x,y\in {\mathbb{R}}^n$, the inner product (dot product) is

$$⟨x,y⟩=x^{\mathrm{\top }}y=\sum _{i=1}^n{x}_i{y}_i$$

Geometric Interpretation

The angle $\theta$ between $x$ and $y$ is defined by

$$\cos \theta =\frac{⟨x,y⟩}{\parallel x\parallel \parallel y\parallel },\parallel x\parallel =\sqrt{⟨x,x⟩}$$

• $\theta =0^{\circ }\Rightarrow$ vectors point in the same direction
• $\theta ={90}^{\circ }\Rightarrow$ vectors are orthogonal (perpendicular)
• $\theta ={180}^{\circ }\Rightarrow$ vectors point in opposite directions

Example:

$$x=\left[\begin{array}{c}1\\ 2\end{array}\right],y=\left[\begin{array}{c}3\\ 1\end{array}\right]⟹⟨x,y⟩=1\cdot 3+2\cdot 1=5,\theta ={\cos }^{-1}\left(\frac{5}{\sqrt{5}\sqrt{10}}\right)$$

Frobenius Inner Product of Matrices

Definition: For matrices $A,B\in {\mathbb{R}}^{m\times n}$, the Frobenius inner product is

$$⟨A,B{⟩}_F=\sum _{i=1}^m\sum _{j=1}^n{A}_{ij}{B}_{ij}=\mathrm{trace}(A^{\mathrm{\top }}B)$$

The angle between matrices is defined analogously:

$$\cos \theta =\frac{⟨A,B{⟩}_F}{\parallel A{\parallel }_F\parallel B{\parallel }_F}$$

Example:

$$A=\left[\begin{array}{cc}1& 2\\ 0& 3\end{array}\right],B=\left[\begin{array}{cc}2& 1\\ 1& 0\end{array}\right]⟹⟨A,B{⟩}_F=1\cdot 2+2\cdot 1+0\cdot 1+3\cdot 0=4$$

---

1.3 Norms

A norm $\parallel \cdot \parallel$ measures the length or magnitude of a vector (or matrix). It satisfies:

1. $\parallel x\parallel \ge 0$, and $\parallel x\parallel =0⟺x=0$
2. $\parallel \alpha x\parallel =|\alpha |\parallel x\parallel$ (homogeneity)
3. $\parallel x+y\parallel \le \parallel x\parallel +\parallel y\parallel$ (triangle inequality)

Common Vector Norms

Euclidean Norm (${\ell }_2$ norm)

$$\parallel x{\parallel }_2=\sqrt{\sum _{i=1}^n{x}_i^2}$$

The most familiar norm, corresponding to geometric length.

${\ell }_1$ Norm

$$\parallel x{\parallel }_1=\sum _{i=1}^n|x_i|$$

Sum of absolute values. Promotes sparsity in optimization (e.g., LASSO, basis pursuit).

Chebyshev Norm (${\ell }_{\mathrm{\infty }}$ norm)

$$\parallel x{\parallel }_{\mathrm{\infty }}=\underset{i}{max}|x_i|$$

Maximum absolute component. Used in worst-case analysis.

${\ell }_p$ Norm (general, $p\ge 1$)

$$\parallel x{\parallel }_p={(\sum _{i=1}^n|x_i{|}^p)}^{1/p}$$

Recovers ${\ell }_1$ when $p=1$, ${\ell }_2$ when $p=2$, and approaches ${\ell }_{\mathrm{\infty }}$ as $p\to \mathrm{\infty }$.

Frobenius Norm (Matrix Norm)

$$\parallel A{\parallel }_F=\sqrt{⟨A,A{⟩}_F}=\sqrt{\sum _{i,j}{A}_{ij}^2}$$

The Frobenius norm treats a matrix as a vector in ${\mathbb{R}}^{mn}$; it is the ${\ell }_2$ norm of the vectorized matrix.

---

1.4 Symmetric Matrices

Definition: A square matrix $A\in {\mathbb{R}}^{n\times n}$ is symmetric if

$$A=A^{\mathrm{\top }}\text{or equivalently}{A}_{ij}=A_{ji}\text{ for all }i,j$$

Key Properties

• All eigenvalues are real. This is a consequence of symmetry and guarantees that eigenvalue-based analysis is well-defined.
• Eigenvectors corresponding to distinct eigenvalues are orthogonal.
• Symmetric matrices are diagonalizable by an orthogonal matrix. There exists $Q$ with $Q^{\mathrm{\top }}Q=I$ and a diagonal $\mathrm{\Lambda }$ such that $A=Q\mathrm{\Lambda }{Q}^{\mathrm{\top }}$.

Eigenvalue Decomposition

If $A$ is symmetric, it admits the decomposition

$$A=Q\mathrm{\Lambda }{Q}^{\mathrm{\top }}=\sum _{i=1}^n{\lambda }_i{q}_i{q}_i^{\mathrm{\top }}$$

where:

• $Q=[q_1{q}_2\dots q_n]$ is orthonormal: $Q^{\mathrm{\top }}Q=I$
• $\mathrm{\Lambda }=\mathrm{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$ with ${\lambda }_i\in \mathbb{R}$
• Each term ${\lambda }_i{q}_i{q}_i^{\mathrm{\top }}$ is a rank-1 symmetric matrix

---

1.5 Positive Semidefinite (PSD) Matrices

Definition: A symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ is positive semidefinite (PSD), denoted $A⪰0$, if

$$x^{\mathrm{\top }}Ax\ge 0\mathrm{\forall }x\in {\mathbb{R}}^n$$

Key Properties

• Eigenvalue characterization: All eigenvalues of $A$ are nonnegative: ${\lambda }_i\ge 0$.
• PSD matrices are symmetric, hence diagonalizable by orthogonal matrices.
• Cholesky factorization: If $A⪰0$, then $A=B{B}^{\mathrm{\top }}$ for some $B\in {\mathbb{R}}^{n\times n}$ (matrix square root).
• The set of PSD matrices forms a convex cone. That is, if $A,B⪰0$ and $\alpha ,\beta \ge 0$, then $\alpha A+\beta B⪰0$.

PSD Cone

Denote:

• ${\mathbb{S}}^n=\{X\in {\mathbb{R}}^{n\times n}:X^{\mathrm{\top }}=X\}$ — the set of $n\times n$ symmetric matrices
• ${\mathbb{S}}_{+}^n=\{X\in {\mathbb{S}}^n:X⪰0\}$ — the positive semidefinite cone
• ${\mathbb{S}}_{++}^n=\{X\in {\mathbb{S}}^n:X\succ 0\}$ — the positive definite cone (strict inequality, all eigenvalues $>0$)

---

1.6 Gradient and Hessian

For a multivariate function $f:{\mathbb{R}}^n\to \mathbb{R}$:

Gradient (First-Order Information)

Gradient: The gradient points in the direction of steepest increase:

$$\mathrm{\nabla }f(x)=\left[\begin{array}{c}\frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\\ ⋮\\ \frac{\partial f}{\partial x_n}\end{array}\right]\in {\mathbb{R}}^n$$

Hessian (Second-Order Information)

Hessian: The matrix of second-order partial derivatives describing local curvature:

$${\mathrm{\nabla }}^{2}f(x)=\left[\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}\\ \frac{{\partial }^{2}f}{\partial x_2\partial x_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right]\in {\mathbb{R}}^{n\times n}$$

The Hessian is symmetric when $f$ is twice continuously differentiable (by Clairaut's theorem).

Quadratic Form Example

Let $f(x)=x^{\mathrm{\top }}Ax+b^{\mathrm{\top }}x+c$, with $A\in {\mathbb{R}}^{n\times n}$ symmetric, $b\in {\mathbb{R}}^n$, $c\in \mathbb{R}$. Then:

$$\mathrm{\nabla }f(x)=2Ax+b,{\mathrm{\nabla }}^{2}f(x)=2A$$

---

1.7 Lines, Line Segments, and Rays

Given two points $x,y\in {\mathbb{R}}^n$, define the direction vector $d:=y-x$.

Parametric Representations

Line through $x$ and $y$:

$${\ell }_{x,y}=\{x+\theta d\mid \theta \in \mathbb{R}\}$$

Line segment from $x$ to $y$:

$$[x,y]=\{x+\theta d\mid \theta \in [0,1]\}=\{(1-\theta )x+\theta y\mid \theta \in [0,1]\}$$

Ray starting at $x$ going through $y$:

$$\overrightarrow{xy}=\{x+\theta d\mid \theta \ge 0\}$$

Geometric Intuition

• The line extends infinitely in both directions.
• The line segment is the convex combination of $x$ and $y$, bounded between them.
• The ray extends infinitely in the direction from $x$ toward $y$.

These primitive sets are the building blocks of convex geometry. The line segment representation

$$z=(1-\theta )x+\theta y,\theta \in [0,1]$$

is called a convex combination of $x$ and $y$, and it is the central operation in the definition of convex sets.

---

1.8 Summary of Mathematical Preliminaries

Concept	Key Formula / Property
Inner product (vectors)	$⟨x,y⟩=x^{\mathrm{\top }}y=\sum x_i{y}_i$
Frobenius inner product	$⟨A,B{⟩}_F=\mathrm{trace}(A^{\mathrm{\top }}B)$
Orthogonality	$⟨x,y⟩=0\iff \theta ={90}^{\circ }$
${\ell }_2$ norm	$|x{|}_2=\sqrt{\sum x_i^2}$
${\ell }_1$ norm	$|x{|}_1=\sum |x_i|$
${\ell }_{\mathrm{\infty }}$ norm	$|x{|}_{\mathrm{\infty }}=\underset{i}{max}|x_i|$
${\ell }_p$ norm	$|x{|}_p=(\sum |x_i{|}^p{)}^{1/p}$
Frobenius norm	$|A{|}_F=\sqrt{\sum A_{ij}^2}$
Symmetric matrix	$A=A^{\mathrm{\top }}$, eigenvalues real
Eigenvalue decomposition	$A=Q\mathrm{\Lambda }{Q}^{\mathrm{\top }}$
PSD matrix	$x^{\mathrm{\top }}Ax\ge 0\mathrm{\forall }x$, ${\lambda }_i\ge 0$
PSD convex cone	$\alpha A+\beta B⪰0$ for $\alpha ,\beta \ge 0$
Gradient	$\mathrm{\nabla }f(x)\in {\mathbb{R}}^n$, direction of steepest increase
Hessian	${\mathrm{\nabla }}^{2}f(x)\in {\mathbb{R}}^{n\times n}$, local curvature
Line through $x,y$	$\{x+\theta (y-x)\mid \theta \in \mathbb{R}\}$
Line segment $[x,y]$	$\{(1-\theta )x+\theta y\mid \theta \in [0,1]\}$
Ray $\overrightarrow{xy}$	$\{x+\theta (y-x)\mid \theta \ge 0\}$

These mathematical tools form the foundation for the study of convex sets, convex functions, and optimization algorithms in the chapters that follow.