Linear Algebra for Optimization

Introduction and Context

Optimization is the mathematical process of selecting parameters that minimize or maximize an objective. It is central to artificial intelligence and machine learning: model training minimizes a loss function, regularization controls model complexity, and constrained optimization incorporates resource, safety, or fairness requirements.

Linear algebra provides the language for describing optimization in many variables. Vectors represent parameters and gradients; matrices represent curvature, interactions among variables, covariance, and constraints. Understanding these objects helps practitioners choose algorithms, diagnose convergence, and recognize when an optimization problem is well behaved or ill conditioned.

This chapter develops the connections among gradients, Hessians, convexity, positive semidefiniteness, constrained optimization, Lagrange multipliers, and regularization.

Learning Objectives

By the end of this chapter, you should be able to:

1. Interpret gradients and Hessians geometrically and computationally.

2. Classify stationary points using first- and second-order information.

3. Explain convexity and the role of positive semidefinite Hessians.

4. Apply gradient descent and analyze its basic convergence behavior.

5. Formulate equality-constrained problems using Lagrange multipliers.

6. Explain how regularization changes optimization geometry and generalization.

7. Diagnose scaling, conditioning, step-size, and curvature problems in AI systems.

1. Optimization Notation and the Geometry of Learning

Let the parameter vector be

\[

\theta=(\theta_1,\ldots,\theta_d)^T\in\mathbb{R}^d,

\]

and let the differentiable objective be \(f:\mathbb{R}^d\to\mathbb{R}\). In supervised learning, \(f\) may be an empirical loss such as mean squared error or cross-entropy.

A point \(\theta^*\) is a global minimizer if

\[

f(\theta^*)\leq f(\theta)\quad\text{for every }\theta.

\]

It is a local minimizer if the inequality holds only in some neighborhood of \(\theta^\). A stationary point satisfies \(\nabla f(\theta^)=0\), but stationarity alone does not guarantee a minimum.

Directional change

For a small displacement \(p\), Taylor expansion gives

\[

f(\theta+p)=f(\theta)+\nabla f(\theta)^Tp+\frac12p^TH(\theta)p+o(\|p\|^2),

\]

where \(H(\theta)\) is the Hessian. The gradient determines first-order change, while the Hessian determines second-order curvature.

The directional derivative in direction \(p\) is

\[

D_pf(\theta)=\nabla f(\theta)^Tp.

\]

Among unit directions, the greatest increase occurs in the direction of the gradient, and the greatest decrease occurs in the direction \(-\nabla f(\theta)\). This fact motivates gradient descent.

2. Gradients, Jacobians, and Hessians

For a scalar function, the gradient is the column vector

\[

\nabla f(\theta)=

\begin{bmatrix}

\partial f/\partial\theta_1\\

\vdots\\

\partial f/\partial\theta_d

\end{bmatrix}.

\]

Its entries measure local sensitivity to individual parameters. The gradient has the same output units as \(f\) divided by the units of the corresponding parameter.

For a vector-valued function \(g:\mathbb{R}^d\to\mathbb{R}^m\), the Jacobian is the \(m\times d\) matrix

\[

J_g(\theta)_{ij}=\frac{\partial g_i}{\partial\theta_j}.

\]

The gradient is a special case of a Jacobian when the output is scalar.

The Hessian is the matrix of second derivatives:

\[

H_f(\theta)_{ij}=\frac{\partial^2 f}{\partial\theta_i\partial\theta_j}.

\]

If the second partial derivatives are continuous near the point, the Hessian is symmetric. Its eigenvectors represent principal curvature directions, and its eigenvalues represent curvature in those directions.

For a quadratic objective,

\[

f(\theta)=\frac12\theta^TA\theta-b^T\theta+c,

\]

where \(A\) is symmetric, \(b\) is a vector, and \(c\) is a scalar,

\[

\nabla f(\theta)=A\theta-b,\qquad H_f(\theta)=A.

\]

If \(A\) is positive definite, the unique minimizer satisfies \(A\theta^*=b\).

Worked Example 1: Gradient and Hessian

Consider

\[

f(x,y)=x^2+4xy+5y^2-2x+6.

\]

The gradient is

\[

\nabla f(x,y)=

\begin{bmatrix}

2x+4y-2\\4x+10y

\end{bmatrix},

\]

and the Hessian is

\[

H=

\begin{bmatrix}

2&4\\4&10

\end{bmatrix}.

\]

The stationary point solves

\[

2x+4y-2=0,\qquad4x+10y=0.

\]

The second equation gives \(x=-2.5y\). Substitution into the first gives \(-y-2=0\), so \(y=-2\) and \(x=5\).

The Hessian is positive definite because its leading principal minors are \(2>0\) and \(2(10)-4^2=4>0\). Therefore, \((5,-2)\) is the unique global minimizer.

3. Positive Definiteness, Semidefiniteness, and Curvature

A symmetric matrix \(A\) is:

• Positive definite (PD) if \(z^TAz>0\) for every nonzero vector \(z\).
• Positive semidefinite (PSD) if \(z^TAz\geq0\) for every vector \(z\).
• Negative definite if \(z^TAz<0\) for every nonzero \(z\).
• Indefinite if the quadratic form is positive for some vectors and negative for others.

For a symmetric matrix, these conditions are equivalent to eigenvalue conditions. PD means all eigenvalues are positive; PSD means all are nonnegative. A PSD matrix may have zero eigenvalues and therefore flat directions.

For a twice-differentiable function, the second-order conditions at a stationary point \(\theta^*\) are:

• If \(H(\theta^)\) is positive definite, \(\theta^\) is a strict local minimum.
• If \(H(\theta^)\) is negative definite, \(\theta^\) is a strict local maximum.
• If the Hessian is indefinite, \(\theta^*\) is a saddle point.
• If the Hessian is merely PSD or has zero eigenvalues, the test is inconclusive; higher-order terms may be needed.

These results assume twice differentiability near the stationary point. They do not apply directly at nonsmooth points such as the absolute-value penalty at zero.

4. Convexity and Why It Matters

A function is convex on a convex domain if, for all \(x,y\) in the domain and \(t\in[0,1]\),

\[

f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).

\]

Geometrically, the line segment joining two points on the graph lies above the graph.

For a twice-differentiable function on a convex open domain, a sufficient and necessary condition for convexity is

\[

H_f(\theta)\succeq0

\]

throughout the domain. Strong convexity with parameter \(\mu>0\) requires

\[

f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{\mu}{2}\|y-x\|_2^2.

\]

For twice-differentiable functions, this corresponds to \(H_f(\theta)\succeq\mu I\).

Every local minimum of a convex function is global. If the function is strictly convex, the minimizer is unique when it exists. If it is strongly convex, it has a unique minimizer and better conditioning of the optimization landscape, although the numerical condition number may still be large.

Nonconvex objectives, common in deep learning, can contain multiple local minima, saddle points, flat regions, and barriers. A PSD Hessian at one point does not prove that a globally nonconvex function is convex; convexity requires the condition throughout the domain.

5. Gradient Descent

The basic gradient-descent update is

\[

\theta_{k+1}=\theta_k-\alpha_k\nabla f(\theta_k),

\]

where \(\alpha_k>0\) is the learning rate or step size. The method uses the locally steepest descent direction under the Euclidean norm.

For a quadratic function with Hessian eigenvalues between \(\mu\) and \(L\), where \(0<\mu\leq L\), a constant step size satisfying

\[

0<\alpha<\frac{2}{L}

\]

produces convergence for the exact quadratic iteration. A common theoretically motivated choice for strongly convex smooth functions is \(\alpha\leq1/L\). The condition number \(\kappa=L/\mu\) indicates difficulty: large \(\kappa\) produces elongated contours and slow zig-zagging.

Worked Example 2: One Gradient Step

Let

\[

f(x,y)=\frac12(3x^2+y^2),

\]

so \(\nabla f(x,y)=(3x,y)^T\). Starting at \((2,1)\) with \(\alpha=0.1\),

\[

\nabla f(2,1)=(6,1)^T,

\]

therefore

\[

(x_1,y_1)=(2,1)-0.1(6,1)=(1.4,0.9).

\]

The objective decreases from \(f(2,1)=6.5\) to

\[

f(1.4,0.9)=\tfrac12(3(1.4)^2+0.9^2)=3.225.

\]

The decrease is not guaranteed for every arbitrary step size; an excessively large step can overshoot.

Variants used in machine learning

In empirical risk minimization, the objective is often an average over many examples. Batch gradient descent uses the exact gradient, whereas stochastic gradient descent uses an unbiased or approximately unbiased estimate from a mini-batch. Momentum accumulates a moving direction, and adaptive methods rescale coordinates using estimates of past gradient magnitudes. These methods can improve practical training but change the dynamics and may complicate convergence analysis.

Automatic differentiation computes derivatives through the computational graph. It is generally more reliable than manually coding derivatives, but gradients should still be checked using small numerical tests, especially when implementing custom operations.

6. Constrained Optimization and Lagrange Multipliers

Many real problems require constraints:

\[

\min_\theta f(\theta)\quad\text{subject to}\quad g_i(\theta)=0,

\]

where \(g_i\) are equality constraints. Define the Lagrangian

\[

\mathcal{L}(\theta,\lambda)=f(\theta)+\lambda^Tg(\theta),

\]

where \(\lambda\) is the vector of Lagrange multipliers. Under suitable differentiability and constraint-qualification assumptions, a candidate solution satisfies the first-order conditions

\[

\nabla_\theta\mathcal{L}(\theta,\lambda)=0,

\qquad g(\theta)=0.

\]

The multiplier measures sensitivity of the optimal value to a small change in the corresponding constraint, subject to sign and convention choices. It is often interpreted as a shadow price, but that interpretation requires a well-defined perturbation and regularity conditions.

Worked Example 3: Closest Point on a Line

Find the point closest to \((1,2)\) subject to \(x+y=4\). Minimize squared distance,

\[

f(x,y)=(x-1)^2+(y-2)^2,

\]

with constraint \(g(x,y)=x+y-4=0\). The Lagrangian is

\[

\mathcal L=(x-1)^2+(y-2)^2+\lambda(x+y-4).

\]

Stationarity gives

\[

2(x-1)+\lambda=0,\qquad2(y-2)+\lambda=0.

\]

Thus \(x=y-1\). Combining with \(x+y=4\) gives \(2y-1=4\), so \(y=2.5\) and \(x=1.5\). The closest point is \((1.5,2.5)\), whose squared distance is \(0.5\).

Inequality constraints and KKT conditions

For a problem

\[

\min f(\theta)\quad\text{subject to }g_i(\theta)\leq0,

\]

the Karush–Kuhn–Tucker conditions include primal feasibility \(g_i(\theta)\leq0\), dual feasibility \(\lambda_i\geq0\), stationarity, and complementary slackness:

\[

\lambda_i g_i(\theta)=0.

\]

Complementary slackness says an inactive constraint has zero multiplier, while an active constraint may have a nonzero multiplier. For convex problems with appropriate constraint qualifications, KKT conditions are also sufficient for global optimality.

7. Regularization as Geometry and Prior Structure

Regularization adds a penalty to the training objective:

\[

\min_\theta \; f(\theta)+\lambda R(\theta),

\qquad \lambda\geq0.

\]

The parameter \(\lambda\) controls the trade-off between data fit and model complexity. It must normally be selected using validation data or a principled model-selection procedure, not by evaluating repeatedly on the final test set.

L2 regularization

The L2-regularized objective is

\[

f_\lambda(\theta)=f(\theta)+\frac{\lambda}{2}\|\theta\|_2^2.

\]

Its gradient and Hessian are

\[

\nabla f_\lambda(\theta)=\nabla f(\theta)+\lambda\theta,

\qquad H_{f_\lambda}=H_f+\lambda I.

\]

Thus L2 regularization shifts every Hessian eigenvalue upward by \(\lambda\). It can improve conditioning, discourage large parameters, and remove flat directions when \(\lambda>0\), provided the remaining objective has suitable smoothness.

For linear regression with design matrix \(X\) and target vector \(y\), the objective

\[

\frac12\|X\theta-y\|_2^2+\frac{\lambda}{2}\|\theta\|_2^2

\]

has solution

\[

\hat\theta=(X^TX+\lambda I)^{-1}X^Ty,

\]

when \(\lambda>0\). This formula assumes the variables are consistently scaled and the regularization applies to all displayed parameters. In many neural networks, biases are excluded from weight decay.

L1 regularization

L1 regularization uses \(R(\theta)=\|\theta\|_1=\sum_j|\theta_j|\). It promotes sparsity but is not differentiable when any coordinate is zero. Optimization therefore uses subgradients or specialized proximal methods. The proximal operator for \(\lambda\alpha\|\theta\|_1\) is soft thresholding:

\[

\operatorname{prox}(v)_j=\operatorname{sign}(v_j)\max(|v_j|-\lambda\alpha,0).

\]

L1 and L2 penalties encode different preferences: L1 tends to set coordinates exactly to zero, whereas L2 usually shrinks them continuously.

Regularization is not a substitute for data governance. It does not automatically remove bias, prevent data leakage, or guarantee fairness, robustness, or privacy.

8. Conditioning and Optimization Diagnostics

A problem is ill-conditioned when small changes in inputs or parameters produce relatively large changes in the solution or when curvature varies greatly across directions. For a positive-definite Hessian, the local condition number is approximately

\[

\kappa(H)=\frac{\lambda_{\max}(H)}{\lambda_{\min}(H)}.

\]

A large condition number can cause slow convergence, numerical instability, and sensitivity to learning-rate choices.

Useful diagnostics include:

• Plotting training and validation objectives to identify overfitting or divergence.
• Monitoring gradient norms, parameter norms, and update-to-parameter ratios.
• Checking for NaNs, exploding gradients, and vanishing gradients.
• Inspecting feature scales and standardizing variables when appropriate.
• Estimating curvature or Hessian-vector products rather than forming a huge Hessian explicitly.
• Comparing objective decrease with the predicted first-order decrease.
• Testing sensitivity to learning rate, regularization strength, initialization, and random seed.

A small gradient does not always mean successful optimization: the point may be a saddle, a flat region, or a poorly scaled solution. Conversely, a large gradient may occur near a valid solution if parameters or objective units are badly scaled.

9. Applied Case: Regularized Classification Under a Stability Constraint

The following is an illustrative case. A university deploys a binary classifier to prioritize student-support outreach. The model uses a parameter vector \(\theta\), logistic loss \(\ell(\theta)\), and L2 regularization. The team also requires a constraint that the average score difference between two monitored groups remain below a specified tolerance.

Background and problem

An unconstrained model achieves good validation accuracy but produces unstable coefficients: small changes in the training sample lead to large changes in some weights. In addition, the institution has a governance requirement concerning group-level score differences.

Analysis

Feature inspection reveals strongly correlated predictors, making the empirical Hessian ill-conditioned. The smallest eigenvalues correspond to directions that trade off correlated features with little change in loss. The largest eigenvalues correspond to highly sensitive directions, forcing a small learning rate for stable gradient descent.

Approach

The team standardizes continuous inputs using training-set statistics, adds an L2 penalty, and formulates the governance requirement as an explicit constraint. They solve the resulting constrained problem using a primal-dual method and monitor KKT residuals: stationarity, feasibility, and complementary slackness where relevant. They select the regularization coefficient using validation data, while reserving a separate test set for final reporting.

The team also examines calibration, subgroup error rates, missing-data patterns, and whether the constraint itself is an adequate representation of institutional fairness. These checks are essential because a mathematically feasible model can still be socially harmful or operationally unreliable.

Outcome

The regularized model has more stable coefficients and improved numerical conditioning. The constraint is satisfied on the validation data, but its performance is reported with uncertainty intervals and monitored after deployment. The institution documents the objective, constraint definitions, data lineage, model limitations, and a human review process for high-impact decisions.

Learning points

1. Curvature diagnostics can reveal why optimization is unstable.

2. Regularization can improve both generalization and numerical conditioning.

3. A constraint must be explicitly defined, measured, and audited.

4. Optimization success does not establish fairness or ethical acceptability.

5. Deployment requires monitoring for distribution shift and constraint violation.

10. Limitations, Governance, and Best Practices

Optimization models rely on assumptions about differentiability, data quality, scaling, and the relationship between the objective and the real-world goal. Convex analysis gives strong guarantees only when the stated convexity and regularity assumptions hold. Deep neural-network training is generally nonconvex, and practical success often depends on architecture, initialization, stochasticity, and implicit regularization.

Important governance concerns include:

• Objective specification: optimizing a proxy can create unwanted incentives.
• Fairness: constraints and penalties represent particular definitions and may conflict.
• Transparency: users should understand material limitations and trade-offs.
• Privacy and security: gradients and parameters can leak information in some settings.
• Accountability: high-impact decisions need human oversight and appeal mechanisms.
• Reproducibility: record data versions, preprocessing, random seeds, software, and hyperparameters.

Best practice is to define the objective and units clearly, verify derivatives, scale data appropriately, use validation rather than test data for tuning, inspect curvature and residuals, compare multiple optimization methods, and evaluate both numerical performance and real-world consequences.

Contemporary Developments

Modern large-scale optimization increasingly uses matrix-free methods, which compute Hessian-vector products without storing the full Hessian. Quasi-Newton methods approximate curvature from successive gradients. Distributed and federated learning introduce communication constraints and privacy considerations. Adaptive optimizers, sharpness measures, and implicit bias remain active research topics, especially because training loss, parameter norm, flatness, and generalization do not have a universally simple relationship.

The lasting principle is that linear algebra is not merely computational machinery. Eigenvalues, norms, projections, and quadratic forms provide diagnostic interpretations of what an optimization algorithm is doing and whether its solution is trustworthy.

Chapter Summary

Optimization in AI represents learning as the minimization of an objective over parameter vectors. The gradient identifies first-order sensitivity and supplies the steepest local descent direction. The Hessian describes second-order curvature; its eigenvalues distinguish steep, flat, positive, negative, and saddle-like directions. Positive definiteness supports strict local minima, while positive semidefiniteness characterizes convexity when it holds throughout a convex domain.

Gradient descent updates parameters opposite the gradient, but its behavior depends strongly on step size and conditioning. Convexity provides global guarantees that are generally unavailable for nonconvex deep-learning objectives. Lagrange multipliers and KKT conditions incorporate equality and inequality constraints, while regularization modifies the objective, geometry, and often generalization behavior. L2 adds \(\lambda I\) to the Hessian; L1 encourages sparsity but requires nonsmooth optimization methods.

Professional optimization requires more than reaching a low loss. Practitioners must inspect conditioning, gradient behavior, constraint residuals, validation performance, scaling, reproducibility, fairness, privacy, and deployment risks.

Key Terms

Gradient: Vector of first partial derivatives of a scalar function.

Directional derivative: Rate of change of a function in a specified direction.

Jacobian: Matrix of first derivatives of a vector-valued function.

Hessian: Matrix of second partial derivatives of a scalar function.

Stationary point: Point where the gradient is zero, when the gradient exists.

Positive definite: Symmetric matrix with strictly positive quadratic form for every nonzero vector.

Positive semidefinite: Symmetric matrix with nonnegative quadratic form for every vector.

Eigenvalue: Scalar describing scaling of an eigenvector under a matrix transformation.

Convex function: Function whose graph lies below every chord between two points.

Strong convexity: Convexity with a uniform positive quadratic lower bound.

Condition number: Ratio of largest to smallest relevant singular value or eigenvalue.

Gradient descent: Iterative method that moves opposite the gradient.

Learning rate: Positive step size used in an optimization update.

Lagrangian: Objective augmented with weighted constraints.

KKT conditions: First-order feasibility, stationarity, dual, and complementary-slackness conditions.

Regularization: Penalty or constraint used to control complexity or stabilize estimation.

L2 regularization: Penalty proportional to the squared Euclidean norm.

L1 regularization: Penalty proportional to the absolute-value norm.

Proximal operator: Mapping used to handle certain nonsmooth penalties.

Hessian-vector product: Product of a Hessian and vector computed without explicitly storing the Hessian.

Review Questions

Short Answer Questions

1. What information does the gradient provide about a differentiable objective?

2. State the difference between positive definite and positive semidefinite matrices.

3. Why can a stationary point fail to be a local minimum?

4. What is the purpose of a Lagrange multiplier?

5. How do L1 and L2 regularization differ in their typical effect on parameters?

Long Answer Questions

1. Explain how the Hessian, eigenvalues, and condition number influence gradient-descent behavior.

2. Derive the gradient and Hessian of a general quadratic objective and explain the role of positive definiteness.

3. Explain convexity and why a local minimum of a convex function is global.

4. Describe the KKT conditions for inequality-constrained optimization and interpret complementary slackness.

5. Discuss how regularization affects optimization, generalization, and model governance.

Analytical / Application Questions

1. For \(f(x,y)=\frac12(4x^2+y^2)\), starting at \((1,2)\) with learning rate \(0.2\), compute one gradient-descent update and the objective before and after the update.

2. Solve the problem of minimizing \((x-2)^2+(y+1)^2\) subject to \(x+y=0\) using a Lagrangian, and interpret the result geometrically.

3. A model has a Hessian with eigenvalues \(0.01\) and \(100\). Explain the numerical consequences and recommend at least three diagnostic or remedial actions.

Multiple Choice Questions with Answers

Question 1

Which statement about a positive semidefinite symmetric matrix is correct?

A. All its eigenvalues are strictly positive.

B. Its quadratic form is nonnegative for every vector.

C. Its quadratic form is negative for every nonzero vector.

D. It must be nonsymmetric.

Correct Answer: B. Its quadratic form is nonnegative for every vector.

Question 2

For f(θ)=1/2 θᵀAθ−bᵀθ+c with symmetric A, what is the gradient?

A. Aθ+b

B. Aᵀθ−b

C. Aθ−b

D. θ−Ab

Correct Answer: C. Aθ−b

Question 3

For a twice-differentiable function, which condition guarantees a strict local minimum at a stationary point?

A. The Hessian is positive definite.

B. The gradient is nonzero.

C. The Hessian is indefinite.

D. The Hessian has at least one negative eigenvalue.

Correct Answer: A. The Hessian is positive definite.

Question 4

If the largest Hessian eigenvalue for a strongly convex quadratic is L, which constant step-size condition guarantees convergence of exact gradient descent?

A. α>2/L

B. α=0

C. α<−1/L

D. 0<α<2/L

Correct Answer: D. 0<α<2/L

Question 5

What does the L2 penalty λ/2 ||θ||² add to the Hessian?

A. λI

B. λθ

C. I/λ

D. λ²I

Correct Answer: A. λI

Question 6

Which KKT condition states that λᵢgᵢ(θ)=0 for an inequality constraint?

A. Primal feasibility

B. Dual feasibility

C. Complementary slackness

D. Stationarity

Correct Answer: C. Complementary slackness

Question 7

For the constraint x+y=4, what is the closest point on the line to (1,2)?

A. (1,3)

B. (1.5,2.5)

C. (2,2)

D. (2.5,1.5)

Correct Answer: B. (1.5,2.5)

Question 8

What is a typical effect of L1 regularization?

A. It shifts every Hessian eigenvalue upward by the same amount.

B. It guarantees a dense parameter vector.

C. It promotes exact zeros in some parameters.

D. It removes all nonsmoothness from the objective.

Correct Answer: C. It promotes exact zeros in some parameters.

Question 9

A large condition number generally indicates that an optimization landscape is:

A. Equally curved in every direction.

B. Ill-conditioned, with substantially different curvature scales.

C. Guaranteed to be nonconvex.

D. Guaranteed to have no stationary points.

Correct Answer: B. Ill-conditioned, with substantially different curvature scales.

Question 10

Which statement about a small gradient norm is most accurate?

A. It always proves the point is a global minimum.

B. It proves the Hessian is positive definite.

C. It may occur at a saddle point or flat region.

D. It means the objective is convex everywhere.

Correct Answer: C. It may occur at a saddle point or flat region.