← back

Classify Critical Points Using Hessian Eigenvalues

#311 · Machine Learning · Medium

⊣ Solve on deep-ml.com

Problem

Classify critical points of a multivariable function using the eigenvalues of the Hessian matrix. A critical point is a local minimum if all eigenvalues are positive, a local maximum if all are negative, and a saddle point if eigenvalues have mixed signs.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import numpy as np

def compute_hessian(f, x: np.ndarray, h: float = 1e-5) -> np.ndarray:
    n = len(x)
    hessian = np.zeros((n, n))

    for i in range(n):
        for j in range(n):
            x_pp = x.copy(); x_pp[i] += h; x_pp[j] += h
            x_pm = x.copy(); x_pm[i] += h; x_pm[j] -= h
            x_mp = x.copy(); x_mp[i] -= h; x_mp[j] += h
            x_mm = x.copy(); x_mm[i] -= h; x_mm[j] -= h
            hessian[i, j] = (f(x_pp) - f(x_pm) - f(x_mp) + f(x_mm)) / (4 * h * h)

    return hessian

def classify_critical_point(f, x: np.ndarray) -> dict:
    hessian = compute_hessian(f, x)
    eigenvalues = np.linalg.eigvalsh(hessian)

    if np.all(eigenvalues > 0):
        classification = "local minimum"
    elif np.all(eigenvalues < 0):
        classification = "local maximum"
    elif np.any(eigenvalues > 0) and np.any(eigenvalues < 0):
        classification = "saddle point"
    else:
        classification = "inconclusive"

    return {
        "hessian": hessian,
        "eigenvalues": eigenvalues.tolist(),
        "classification": classification,
    }

Explanation

  1. Hessian matrix contains all second-order partial derivatives: H[i,j] = d^2f / (dx_i dx_j). Computed using the central difference formula for mixed partials.
  2. Eigenvalues of the Hessian determine the curvature in each principal direction.
  3. All positive eigenvalues mean the function curves upward in every direction (local minimum). All negative means it curves downward (local maximum). Mixed signs indicate a saddle point.
  4. If any eigenvalue is zero, the second-order test is inconclusive.

Complexity

  • Time: O(n^2) function evaluations for the Hessian plus O(n^3) for eigenvalue decomposition
  • Space: O(n^2) for the Hessian matrix
← #310#312 →