Mathematical Optimization

Optimization is the selection of a best element (with regard to some criterion) from some set of available alternatives. In its simplest form, this means finding the values that maximize or minimize a function.

Unconstrained Optimization

For a differentiable function $f(x)$, local extrema occur at points where $f'(x) = 0$. The Second Derivative Test determines if a point is a maximum ($f'' < 0$) or a minimum ($f'' > 0$).

import numpy as np

def f(x):
  return x**4 - 4*x**2 + 3

def df(x):
  return 4*x**3 - 8*x

def ddf(x):
  return 12*x**2 - 8

# Roots of df(x) are 0, sqrt(2), -sqrt(2)
critical_points = [0, np.sqrt(2), -np.sqrt(2)]

for p in critical_points:
  second_der = ddf(p)
  kind = "Min" if second_der > 0 else "Max"
  print(f"Point x={p:.2f} is a {kind} (f''={second_der:.2f})")

Gradient Descent

In higher dimensions, we often use iterative methods like Gradient Descent to find a local minimum: $\mathbf{x}_{n+1} = \mathbf{x}_n - \gamma \nabla f(\mathbf{x}_n)$ where $\gamma$ is the learning rate.

def f(x, y):
  return x**2 + y**2 + 10

def grad_f(x, y):
  return np.array([2*x, 2*y])

point = np.array([5.0, 5.0])
gamma = 0.1

for _ in range(10):
  point = point - gamma * grad_f(*point)
  print(f"Current point: {point}")

Constrained Optimization: Lagrange Multipliers

To optimize $f(x, y)$ subject to $g(x, y) = c$, we look for points where the gradients are parallel: $\nabla f = \lambda \nabla g$