08. Mathematical Foundations — Gradient, Convexity, Norm, and Decomposition

// CORE 2/7 — gradient/Jacobian/Hessian, Taylor approximation, convexity, norm, inner product, orthogonality, matrix decomposition

This page gathers in one place the mathematical tools that recur when reading optimization algorithms. If Background Parts 1–4 provide the grammar, this page shows how that grammar is used inside algorithms.

Gradient / Jacobian / Hessian

For a scalar objective $f:\mathbb{R}^n\to\mathbb{R}$, the gradient gives first-order information:

$$\nabla f(x).$$

For a vector-valued function $F:\mathbb{R}^n\to\mathbb{R}^m$, the Jacobian gives first-order information:

$$J_F(x)=\frac{\partial F}{\partial x}.$$

The Hessian gives second-order information about a scalar objective:

$$\nabla^2 f(x).$$

Constrained optimization considers not only the gradient of the objective, but also the gradients or Jacobian of the constraints.

Taylor approximation

Optimization algorithms turn a complex problem into an easy problem near the current point:

$$f(x+p)\approx f(x)+\nabla f(x)^\top p+\frac{1}{2}p^\top \nabla^2 f(x)p.$$

Gradient descent looks only at the linear term to choose a descending direction. Newton's method obtains its step by minimizing the quadratic model.

Convexity

A convex function has values below the chord along the line segment between any two points:

$$f(\theta x+(1-\theta)y)\le \theta f(x)+(1-\theta)f(y),\quad 0\le\theta\le 1.$$

Convex optimization matters because a local minimum is a global minimum. Non-convex problems require distinguishing saddle points from local minima, while optimality conditions become much stronger for convex problems.

Norm / inner product

A norm describes magnitude, while an inner product describes directional alignment:

$$\|x\|_2=\sqrt{x^\top x},\qquad \langle x,y\rangle=x^\top y.$$

A descent direction $p$ usually satisfies

$$\nabla f(x)^\top p<0.$$

In other words, it has a component opposite the gradient.

Orthogonality

Two vectors are orthogonal when their inner product is zero:

$$x^\top y=0.$$

Conjugate gradient uses $A$-orthogonality, a stronger condition than ordinary orthogonality:

$$p_i^\top A p_j=0\quad (i\ne j).$$

Thanks to this condition, the method proceeds in a new direction without undoing what was already optimized in previous directions.

Matrix decomposition

Matrix decomposition makes large linear-algebra calculations stable and fast.

Decomposition	Use
LU	Solve general linear systems
Cholesky	Solve symmetric positive-definite systems
QR	Least squares and orthogonalization
Eigen decomposition	Analyze curvature and positive definiteness
SVD	Rank, ill-conditioning, and pseudoinverses

When the Hessian is positive definite in Newton's method, Cholesky factorization obtains the step stably. QR or SVD is safer for ill-conditioned least-squares problems.

Connection map

• Gradient: where to descend
• Hessian: how much it curves
• Convexity: whether a local solution is global
• Norm: magnitude and stopping criteria
• Orthogonality: structure that avoids reusing directions
• Decomposition: tool that makes real calculation possible

Next: Optimality Conditions