Chapter 134. Numerical Optimization

134.1 Introduction

Numerical optimization studies algorithms for finding minima or maxima of functions using finite computation.

Linear algebra is one of the foundations of numerical optimization. Vectors represent variables, matrices represent constraints and derivatives, and linear systems appear inside nearly every optimization algorithm.

The basic optimization problem is:

\text{minimize } f(x)

subject to

x\in C,

where:

Symbol	Meaning
$x$	Unknown vector
$f(x)$	Objective function
$C$	Feasible set

Optimization problems appear throughout science and engineering:

Area	Optimization task
Machine learning	Loss minimization
Statistics	Maximum likelihood
Control theory	Optimal control
Signal processing	Error minimization
Finance	Portfolio optimization
Physics	Energy minimization
Numerical PDEs	Variational methods

The central challenge is computational: how to efficiently approximate optimal solutions in finite precision arithmetic.

134.2 Optimization Problems

An optimization problem consists of:

Variables,
An objective function,
Constraints.

The objective function assigns a real number to each feasible point:

f:\mathbb{R}^n\to\mathbb{R}.

The feasible set contains all allowed vectors.

For example:

\text{minimize } x_1^2+x_2^2

subject to

x_1+x_2=1.

The objective measures squared distance from the origin. The constraint restricts the solution to a line.

Optimization seeks the feasible point with smallest objective value.

134.3 Linear Optimization

A linear optimization problem has:

Component	Form
Objective	Linear
Constraints	Linear

The standard form of linear programming is:

\text{minimize } c^Tx

subject to

Ax=b,

and

x\ge0.

Here:

Symbol	Meaning
$x$	Decision vector
$c$	Cost vector
$A$	Constraint matrix
$b$	Constraint values

The feasible region is a convex polyhedron.

Linear programming is important because:

Many practical problems are naturally linear,
Nonlinear problems are often approximated linearly,
Efficient algorithms exist.

The geometry of linear programming is fundamentally linear-algebraic.

134.4 Least Squares Problems

One of the simplest optimization problems is least squares.

Given

A\in\mathbb{R}^{m\times n}, \qquad b\in\mathbb{R}^m,

the least squares problem minimizes

\|Ax-b\|^2.

This problem appears when the system

Ax=b

has no exact solution.

The least squares solution satisfies the normal equations:

A^TAx=A^Tb.

A^TAx=A^Tb

The matrix

A^TA

is symmetric and positive semidefinite.

Least squares is central in regression, data fitting, signal reconstruction, and inverse problems.

134.5 Convex Optimization

A convex optimization problem minimizes a convex function over a convex set.

The problem is:

\text{minimize } f(x)

subject to

x\in C,

where:

Property	Meaning
$C$ convex	Feasible region has no holes or bends inward
$f$ convex	Local minima are global

Convex optimization is especially important because it avoids many pathological behaviors of general nonlinear optimization.

If $f$ is differentiable and convex, then:

\nabla f(x)=0

implies $x$ is globally optimal.

Convexity transforms optimization from a potentially difficult global problem into a tractable local one.

134.6 Gradient Descent

Gradient descent is one of the most fundamental optimization algorithms.

Given a differentiable function

f:\mathbb{R}^n\to\mathbb{R},

the gradient vector is

\nabla f(x) = \begin{bmatrix} \frac{\partial f}{\partial x_1}\\ \vdots\\ \frac{\partial f}{\partial x_n} \end{bmatrix}.

The gradient points in the direction of steepest increase.

Therefore:

-\nabla f(x)

points in the direction of steepest decrease.

Gradient descent updates:

x_{k+1} = x_k-\alpha_k\nabla f(x_k),

where:

Symbol	Meaning
$x_k$	Current iterate
$\alpha_k$	Step size
$\nabla f(x_k)$	Gradient

x_{k+1}=x_k-\alpha_k\nabla f(x_k)

The algorithm repeatedly moves downhill.

134.7 Quadratic Optimization

A quadratic optimization problem minimizes a quadratic function:

f(x) = \frac12 x^TQx+c^Tx+d,

where:

Symbol	Meaning
$Q$	Symmetric matrix
$c$	Linear term
$d$	Constant

The gradient is

\nabla f(x)=Qx+c.

Setting the gradient equal to zero gives:

Qx=-c.

Thus quadratic optimization reduces to solving a linear system.

If $Q$ is positive definite, then the problem has a unique minimizer.

Quadratic problems are central because many nonlinear functions are locally approximated by quadratics.

134.8 Hessian Matrices

The Hessian matrix collects second derivatives.

For a twice-differentiable function

f:\mathbb{R}^n\to\mathbb{R},

the Hessian is

H_f(x) = \left( \frac{\partial^2 f}{\partial x_i\partial x_j} \right).

The Hessian measures local curvature.

Important cases:

Hessian	Interpretation
Positive definite	Local minimum
Negative definite	Local maximum
Indefinite	Saddle point

Second-order optimization methods use Hessians to accelerate convergence.

134.9 Newton’s Method

Newton’s method uses second-order information.

The update rule is:

x_{k+1} = x_k - H_f(x_k)^{-1}\nabla f(x_k).

x_{k+1}=x_k-H_f(x_k)^{-1}\nabla f(x_k)

The method approximates the objective locally by a quadratic function and minimizes that quadratic approximation.

Advantages:

Advantage	Reason
Fast local convergence	Uses curvature
Scale adaptation	Hessian rescales directions

Disadvantages:

Disadvantage	Reason
Expensive	Requires solving linear systems
Hessian storage	Large matrices
Possible instability	Hessian may be singular

Large-scale optimization often approximates Newton steps rather than computing them exactly.

134.10 Constrained Optimization

Many optimization problems include constraints.

Equality constraints have the form:

g_i(x)=0.

Inequality constraints have the form:

h_j(x)\le0.

The feasible set becomes:

C = \{x:g_i(x)=0,\ h_j(x)\le0\}.

Constraints change the geometry of optimization.

The optimum may occur on a boundary rather than in the interior.

134.11 Lagrange Multipliers

Lagrange multipliers solve equality-constrained optimization problems.

Suppose we minimize

f(x)

subject to

g(x)=0.

Define the Lagrangian:

L(x,\lambda) = f(x)+\lambda g(x).

Optimality conditions become:

\nabla_x L(x,\lambda)=0,

and

g(x)=0.

This yields:

\nabla f(x) = -\lambda \nabla g(x).

\nabla f(x)=-\lambda \nabla g(x)

Geometrically, the objective gradient becomes parallel to the constraint gradient.

134.12 Karush-Kuhn-Tucker Conditions

The Karush-Kuhn-Tucker conditions generalize Lagrange multipliers to inequality constraints.

For problems with constraints

h_i(x)\le0,

the KKT conditions include:

Condition	Meaning
Stationarity	Gradient balance
Primal feasibility	Constraints satisfied
Dual feasibility	Multipliers nonnegative
Complementary slackness	Active constraints identified

The KKT system forms the basis of many modern optimization algorithms.

134.13 Interior-Point Methods

Interior-point methods solve constrained optimization problems by moving through the interior of the feasible region.

Rather than enforcing constraints exactly at each step, they use barrier functions such as:

-\mu\sum_i \log(-h_i(x)).

The logarithm approaches infinity near the boundary, preventing the iterates from leaving the feasible region.

Interior-point methods are especially important in:

Problem class	Application
Linear programming	Large sparse systems
Quadratic programming	Control and finance
Semidefinite programming	Convex matrix optimization

These methods rely heavily on sparse linear algebra.

134.14 Conjugate Gradient Method

The conjugate gradient method solves large symmetric positive definite systems:

Ax=b.

It may also be viewed as minimizing the quadratic function:

f(x) = \frac12x^TAx-b^Tx.

f(x)=\frac12x^TAx-b^Tx

Conjugate gradient constructs search directions that are mutually $A$ -orthogonal.

Advantages include:

Advantage	Reason
No matrix inversion	Iterative method
Exploits sparsity	Efficient for large systems
Low memory	Matrix-vector products only

Conjugate gradient is one of the central algorithms in numerical optimization.

134.15 Stochastic Gradient Descent

Stochastic gradient descent, or SGD, approximates gradients using random subsets of data.

Instead of computing:

\nabla f(x),

one computes an estimate:

g_k \approx \nabla f(x_k).

The update becomes:

x_{k+1} = x_k-\alpha_k g_k.

SGD is fundamental in machine learning because exact gradients may be too expensive for massive datasets.

Noise in the gradient introduces randomness but greatly reduces computational cost.

134.16 Regularization

Optimization problems may be ill-posed or unstable.

Regularization adds penalty terms to stabilize solutions.

Examples include:

Method	Objective
Ridge regression	$\\|Ax-b\\|^2+\lambda\\|x\\|^2$
Lasso	$\\|Ax-b\\|^2+\lambda\\|x\\|_1$

Ridge regression penalizes large Euclidean norm.

Lasso promotes sparsity.

Regularization changes both the geometry and numerical conditioning of optimization problems.

134.17 Duality

Many optimization problems possess dual formulations.

The primal problem:

\text{minimize } f(x)

may correspond to a dual problem involving multipliers or supporting hyperplanes.

Duality provides:

Benefit	Interpretation
Lower bounds	Optimality certification
Sensitivity analysis	Constraint interpretation
Alternative algorithms	Easier computation

Strong duality occurs when primal and dual optimal values coincide.

Convexity is closely tied to duality theory.

134.18 Numerical Stability

Optimization algorithms operate in finite precision arithmetic.

Important issues include:

Issue	Effect
Roundoff error	Loss of accuracy
Ill-conditioning	Amplified perturbations
Cancellation	Numerical instability
Overflow/underflow	Computational failure

Stable algorithms minimize error growth.

Condition numbers are especially important because they measure sensitivity of solutions to perturbations.

134.19 Sparse Optimization

Many optimization problems involve sparse matrices.

A sparse matrix has mostly zero entries.

Sparse linear algebra allows:

Advantage	Reason
Lower memory usage	Store nonzeros only
Faster computation	Skip zero operations
Scalable algorithms	Large systems feasible

Sparse optimization is fundamental in:

Area	Typical problem
PDE discretization	Sparse linear systems
Network optimization	Graph sparsity
Machine learning	Sparse features
Signal processing	Compressed sensing

134.20 Optimization and Linear Algebra

Nearly every optimization method relies on linear algebra.

Optimization concept	Linear algebra role
Gradient	Vector
Hessian	Matrix
Constraints	Linear systems
Newton step	Solve matrix equation
Least squares	Orthogonal projection
Convexity	Positive semidefinite Hessian
Duality	Linear functionals
Iterative methods	Krylov subspaces

Modern optimization is fundamentally computational linear algebra.

134.21 Summary

Numerical optimization studies computational methods for minimizing or maximizing functions.

The central concepts are:

Concept	Meaning
Objective function	Quantity being optimized
Feasible set	Allowed region
Convexity	Guarantees global optimality
Gradient	First-order change
Hessian	Second-order curvature
Newton method	Quadratic local approximation
Least squares	Error minimization
Conjugate gradient	Iterative quadratic solver
Interior-point method	Barrier-based constrained optimization
Stochastic gradient	Randomized optimization
Duality	Complementary optimization formulation
Regularization	Stabilization through penalties

Numerical optimization combines geometry, calculus, probability, and linear algebra into algorithms for solving large computational problems.