03. Linear Algebra for Optimization — Directions, Curvature, and Linear Systems

// BACKGROUND 3/6 — vector, matrix, inner product, linear independence, eigenvalue, positive definiteness, linear systems

Optimization algorithms almost always move through a vector space. Linear algebra is the language for discussing direction, distance, orthogonality, curvature, and computational tractability in that space.

Vectors and matrices

A vector $x\in\mathbb{R}^n$ is one candidate solution. A matrix $A\in\mathbb{R}^{m\times n}$ is a linear transformation that maps a vector to another vector:

$$y=Ax.$$

The constraint $Ax\le b$ means that "$x$ must satisfy several linear inequalities simultaneously." An example of a least-squares problem is

$$\min_x \|Ax-b\|_2^2.$$

Inner product

The inner product measures how much two vectors point in the same direction:

$$\langle x,y\rangle=x^\top y.$$

If $x^\top y$ is positive, they point in similar directions; if negative, in opposite directions; and if zero, they are orthogonal. Choosing $p=-\nabla f(x)$ in gradient descent gives

$$\nabla f(x)^\top p=-\|\nabla f(x)\|_2^2<0,$$

so it is a descent direction.

Linear independence

Vectors are linearly independent when they provide directions that do not duplicate one another. This matters when solving linear systems or checking the independence of constraints.

If constraint gradients are independent, the constraints can be viewed as "not merely repeating the same statement." This condition is needed to handle Lagrange multipliers and KKT conditions stably.

Eigenvalues

If a matrix $A$ changes only the magnitude of some direction $v$ while preserving its direction,

$$Av=\lambda v,$$

then $\lambda$ is called an eigenvalue. The eigenvalues of the Hessian show the function's curvature in each direction.

Hessian eigenvalues	Meaning
All positive	Curves upward in every direction
All negative	Curves downward in every direction
Mixed positive and negative	Possible saddle point

Positive definiteness

A symmetric matrix $H$ is positive definite if, for every $p\ne 0$,

$$p^\top H p>0.$$

In optimization, a positive-definite Hessian means the region around that point is bowl-shaped, and a strict local minimum can be expected.

Linear systems

At each iteration, Newton's method solves the linear system

$$\nabla^2 f(x_k)p_k=-\nabla f(x_k).$$

The Newton step is therefore not a problem of explicitly calculating the Hessian's inverse, but of stably solving a linear system. Real implementations do not construct the inverse; they use a factorization or iterative solver.

Connections to remember

• The inner product describes whether directions agree.
• Eigenvalues describe the strength of curvature by direction.
• Positive definiteness describes a "bowl that rises in every direction."
• Linear systems are the computational center of Newton, quasi-Newton, and conjugate-gradient methods.

Next: Numerical Analysis for Optimization