Open methods - Executable Engineering: Interactive Numerical Methods in Python

In bracketed minimization, we relied on knowing a 1D interval $[a, b]$ containing an optimum. In multiple dimensions ( $N \ge 2$ ), however, bounding an optimum a priori is rarely possible: there is no simple multidimensional analogue of a 1D bracket.

Instead, we turn to open methods for unconstrained optimization. Open methods start from an initial guess $\mathbf{x}_0$ and iteratively explore the landscape by generating search directions and step lengths.

Landscape of open optimization methods¶

Open optimization algorithms divide broadly into four main categories based on the information they require and how they ensure stability:

Gradient-Free Optimizers:
- Evaluate: Only function values $f(\mathbf{x})$ .
- Methods: Powell’s method (conjugate line searches) and Nelder-Mead (downhill simplex / amoeba).
- Best for: Noisy, non-differentiable, or black-box objective functions where analytical or automatic gradients are unavailable.
Gradient-Based Optimizers:
- Evaluate: Function values $f(\mathbf{x})$ , gradients $\nabla f(\mathbf{x})$ , and second derivatives (Hessian $\mathbf{H}$ ).
- Methods: Newton’s optimization method, Gradient Descent, and Conjugate Gradient.
- Best for: Smooth, differentiable problems where local slopes and curvatures can accelerate convergence to quadratic rates ( $k=2$ ).
Indefinite Systems and Saddle Points:
- Challenge: In multiple dimensions, stationary points (where $\nabla f = \mathbf{0}$ ) are not always minima. If the Hessian $\mathbf{H}$ has both positive and negative eigenvalues, the stationary point is a saddle point.
- Implication: Unconstrained Newton steps can jump straight into saddle points or even local maxima!
Trust Region Methods:
- Strategy: Restrict each step to an adaptive radius $\|\mathbf{s}\| \le \Delta$ where the quadratic model is trusted to accurately approximate the real surface.
- Best for: Robust global convergence on non-convex, ill-conditioned, or indefinite landscapes where standard line searches fail.

Overview of algorithms in this section¶

Method	Derivative Order	Convergence Rate	Key Strengths & Use Cases
Powell’s Method	0 (Gradient-free)	Superlinear / quadratic near minima	Exploits conjugate directions without derivatives; efficient for smooth, low-dimensional problems.
Nelder-Mead	0 (Gradient-free)	Heuristic	Extremely robust to noise and non-differentiable cusps; crawls downhill like an amoeba.
Gradient Descent	1 (First order)	Linear ( $k=1$ )	Simple and scalable; widely used in machine learning (SGD) with momentum.
Newton’s Method	2 (Second order)	Quadratic ( $k=2$ ) near minima	Extremely fast convergence on convex surfaces; requires assembling and solving with $\mathbf{H}$ .
Trust Region	1 or 2	Superlinear to quadratic	Robust global convergence; safely avoids saddle points and handles indefinite Hessians.