Unconstrained Optimization

An unconstrained optimization problem is:

$$\min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x})$$

where $f : \mathbb{R}^n \to \mathbb{R}$ is the objective function. A point $\mathbf{x}^\star$ is a local minimizer if $f(\mathbf{x}^\star) \le f(\mathbf{x})$ for all $\mathbf{x}$ in a neighborhood of $\mathbf{x}^\star$.

Necessary condition (first-order): $\nabla f(\mathbf{x}^\star) = \mathbf{0}$.

Sufficient condition (second-order): $\nabla f(\mathbf{x}^\star) = \mathbf{0}$ and $\nabla^2 f(\mathbf{x}^\star) \succ 0$ (positive definite).

The gradient of $f : \mathbb{R}^n \to \mathbb{R}$ is the vector of first partial derivatives:

$$\nabla f(\mathbf{x}) = \begin{bmatrix} \frac{\partial f}{\partial x_1} & \frac{\partial f}{\partial x_2} & \cdots & \frac{\partial f}{\partial x_n} \end{bmatrix}^T$$

The Hessian is the $n \times n$ matrix of second partial derivatives:

$$[\nabla^2 f(\mathbf{x})]_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}$$

For a twice-differentiable function, the Hessian is symmetric. The Hessian encodes the curvature of $f$: its eigenvalues determine whether the function curves up (positive), down (negative), or is flat in each direction.

from scipy.optimize import minimize

result = minimize(
    fun,          # callable: f(x) -> float
    x0,           # initial guess (1D array)
    method=...,   # 'Nelder-Mead', 'BFGS', 'L-BFGS-B', etc.
    jac=...,      # gradient (callable or True for auto)
    hess=...,     # Hessian (callable, or HessianUpdateStrategy)
    tol=...,      # convergence tolerance
    options=...,  # dict of solver-specific options
)

The returned OptimizeResult object contains:

• result.x: the optimal point $\mathbf{x}^\star$
• result.fun: the optimal value $f(\mathbf{x}^\star)$
• result.jac: gradient at the solution
• result.nit: number of iterations
• result.success: whether the optimizer converged

Nelder-Mead is a derivative-free method that maintains a simplex of $n+1$ vertices in $\mathbb{R}^n$. At each iteration, it reflects, expands, contracts, or shrinks the simplex based on function values at the vertices.

result = minimize(f, x0, method='Nelder-Mead')

Pros: No gradient needed; robust for noisy or non-smooth objectives.

Cons: Slow convergence ($O(1/\sqrt{k})$); no convergence guarantee in dimension $> 2$; does not scale to high dimensions ($n > 20$).

BFGS (Broyden-Fletcher-Goldfarb-Shanno) is a quasi-Newton method that builds an approximate inverse Hessian $\mathbf{B}_k^{-1}$ from gradient differences:

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \mathbf{B}_k^{-1} \nabla f(\mathbf{x}_k)$$

where $\alpha_k$ is chosen by a line search. The update uses rank-2 corrections to maintain positive definiteness.

L-BFGS-B (Limited-memory BFGS with Bounds) stores only the last $m$ gradient differences (typically $m = 10$), reducing memory from $O(n^2)$ to $O(mn)$. It also supports simple box constraints $l_i \le x_i \le u_i$.

# BFGS (no bounds)
result = minimize(f, x0, method='BFGS', jac=grad_f)

# L-BFGS-B (with bounds)
bounds = [(0, None)] * n  # x_i >= 0
result = minimize(f, x0, method='L-BFGS-B', jac=grad_f, bounds=bounds)

Newton's method uses the exact Hessian for quadratic convergence:

$$\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1} \nabla f(\mathbf{x}_k)$$

Newton-CG avoids forming the full Hessian inverse by solving the Newton system $\nabla^2 f \cdot \mathbf{d} = -\nabla f$ approximately using the Conjugate Gradient method. This requires only Hessian-vector products, not the full Hessian matrix.

result = minimize(f, x0, method='Newton-CG',
                  jac=grad_f, hess=hess_f)

# Or with Hessian-vector product only
result = minimize(f, x0, method='Newton-CG',
                  jac=grad_f, hessp=hess_vec_product)

CG (Conjugate Gradient): A separate method='CG' uses the nonlinear conjugate gradient method (Fletcher-Reeves / Polak-Ribiere). It requires only gradients, not Hessians.