Why It Matters
What is Optimization
Critical Points
First Derivative Test
Second Derivative Test
Global vs Local Extrema
Optimization Process
Worked Examples
Example 1: Maximum Volume of a Box
Example 2: Shortest Distance
Example 3: Minimum Surface Area
Constrained Optimization
Python Implementation
Univariate Optimization with SciPy
import numpy as np
from scipy.optimize import minimize_scalar
# Minimize f(x) = x^4 - 4x^3 + 6x^2 - 4x + 1
f = lambda x: x**4 - 4*x**3 + 6*x**2 - 4*x + 1
# Bounded search
result = minimize_scalar(f, bounds=(-10, 10), method='bounded')
print(f"Minimum at x = {result.x:.6f}")
print(f"Minimum value = {result.fun:.6f}")
# With derivative information for faster convergence
def f_and_grad(x):
val = x**4 - 4*x**3 + 6*x**2 - 4*x + 1
grad = 4*x**3 - 12*x**2 + 12*x - 4
return val, grad
from scipy.optimize import minimize
result = minimize(lambda x: f_and_grad(x)[0], x0=0.5,
jac=lambda x: f_and_grad(x)[1], method='BFGS')
print(f"Optimum at x = {result.x[0]:.6f}")
Multivariate Optimization
import numpy as np
from scipy.optimize import minimize
# Rosenbrock function: f(x,y) = (1-x)^2 + 100(y-x^2)^2
def rosenbrock(x):
return (1 - x[0])**2 + 100*(x[1] - x[0]**2)**2
def rosenbrock_grad(x):
dx = -2*(1 - x[0]) - 400*x[0]*(x[1] - x[0]**2)
dy = 200*(x[1] - x[0]**2)
return np.array([dx, dy])
# Minimize with gradient
result = minimize(rosenbrock, x0=[-1, 1], jac/rosenbrock_grad, method='L-BFGS-B')
print(f"Optimum: {result.x}, Value: {result.fun:.2e}")
# Without gradient (numerical approximation)
result = minimize(rosenbrock, x0=[-1, 1], method='Nelder-Mead')
print(f"Optimum: {result.x}, Value: {result.fun:.2e}")
Constrained Optimization
import numpy as np
from scipy.optimize import minimize
# Minimize f(x,y) = x^2 + y^2 subject to x + y = 1
def objective(x):
return x[0]**2 + x[1]**2
def constraint_eq(x):
return x[0] + x[1] - 1 # Must equal 0
from scipy.optimize import LinearConstraint, NonlinearConstraint
# Method 1: SLSQP with constraint dict
constraints = {'type': 'eq', 'fun': constraint_eq}
result = minimize(objective, x0=[0.5, 0.5], method='SLSQP', constraints=constraints)
print(f"Optimum: {result.x}, Value: {result.fun:.4f}")
# Expected: [0.5, 0.5] with value 0.5
# Method 2: Lagrange multiplier verification
from scipy.optimize import minimize
def lagrangian(x, lam):
return x[0]**2 + x[1]**2 + lam * (x[0] + x[1] - 1)
# Solve the KKT system analytically
# x* = y* = 0.5, lambda* = -1
print(f"Verification: f(0.5, 0.5) = {0.5**2 + 0.5**2}")
Gradient Descent Implementation
import numpy as np
def gradient_descent(f, grad_f, x0, lr=0.01, n_iters=1000, tol=1e-8):
"""Basic gradient descent with convergence check."""
x = np.array(x0, dtype=float)
history = [x.copy()]
for i in range(n_iters):
g = grad_f(x)
x_new = x - lr * g
history.append(x_new.copy())
if np.linalg.norm(x_new - x) < tol:
print(f"Converged at iteration {i}")
break
x = x_new
return x, np.array(history)
# Minimize f(x,y) = x^2 + 4y^2
f = lambda x: x[0]**2 + 4*x[1]**2
grad = lambda x: np.array([2*x[0], 8*x[1]])
x_opt, hist = gradient_descent(f, grad, [5.0, 5.0], lr=0.1)
print(f"Optimum: {x_opt}") # Should be near [0, 0]
Applications in AI/ML
Loss Minimization
Gradient Descent in Neural Networks
Hyperparameter Tuning as Optimization
Common Mistakes
| Mistake | Incorrect | Correct | Why It Matters |
|---|---|---|---|
| Assuming critical point is extremum | min or max | Must test with 1st or 2nd derivative test | Inflection points also have |
| Forgetting endpoints on bounded domains | Only check critical points | Also check and | Global extremum may be at boundary |
| Confusing local and global extrema | Local min = global min | Local min is only optimal in a neighborhood | ML training often gets stuck in local minima |
| Wrong second derivative test | minimum | Test is inconclusive; use 1st derivative test | has but is a minimum |
| Ignoring domain constraints | Optimize over all | Respect physical/logical constraints | Negative lengths, probabilities are invalid |
| Not checking convergence | Run gradient descent for fixed iterations | Monitor gradient norm or loss change | May stop before reaching optimum |
| Using wrong learning rate | for all problems | Tune per problem (typically to ) | Too large diverges, too small is slow |
| Ignoring saddle points in high dimensions | All critical points are extrema | Saddle points are common in high dimensions | Neural network loss landscapes have many saddle points |
Interview Questions
Q1: What is the difference between a local and global minimum?
Q2: Explain the second derivative test. When does it fail?
Q3: Why is non-convex optimization hard for neural networks?
Q4: How does the learning rate affect gradient descent convergence?
Q5: What are KKT conditions and when are they used?
Q6: Explain the vanishing gradient problem and its connection to optimization.
Practice Problems
Problem 1: Find and Classify Critical Points
Problem 2: Optimization Word Problem
Problem 3: Prove Convexity Implies Global Minimum
Problem 4: Multivariable Optimization
Quick Reference
Cross-References
- Derivatives: Foundation for computing gradients needed in optimization -> Derivatives and Differentiation
- Chain Rule: Essential for backpropagation and computing gradients of composite functions -> Chain Rule
- Partial Derivatives: Gradients in multivariable optimization -> Partial Derivatives
- Taylor Series: Quadratic approximation used in Newton's method -> Taylor Series
- Lagrange Multipliers: Deep dive into constrained optimization -> Lagrange Multipliers
- Multivariable Calculus: Gradients, Jacobians, and Hessians for higher dimensions -> Multivariable Calculus
- Convex Optimization: Properties that make optimization tractable -> Convex Optimization
- Gradient Descent Algorithms: SGD, Adam, and advanced optimizers -> Gradient Descent
- Newton's Method: Second-order optimization using Hessians -> Newton's Method
- Constrained Optimization: Linear programming, quadratic programming -> Constrained Optimization
- Hyperparameter Tuning: Bayesian optimization and search strategies -> Hyperparameter Optimization