10.4 Algorithms

For unconstrained problems, gradient descent moves along \(-\nabla f\) and converges linearly; Newton’s method solves \(\nabla ^2f\,d = -\nabla f\) and converges quadratically near a minimum with positive definite Hessian; quasi-Newton methods (BFGS) build up curvature information from gradients. Constraints are handled by

penalty methods, which add \(\rho \sum \max (0, g_i)^2\) to the objective and let \(\rho \to \infty \);
barrier methods, which add \(-t\sum \log (-g_i)\), keeping iterates strictly feasible, and let \(t \to 0\); for a convex problem the barrier minimiser \(x(t)\) is within \(mt\) of optimal, and \(\lambda _i(t) = -t/g_i(x(t))\) estimates the multipliers. This is the idea behind the interior-point methods for LP mentioned in the section on the revised simplex method;
sequential quadratic programming (SQP), which solves at each step a QP built from a quadratic model of the Lagrangian and linearised constraints, and is the method of SciPy’s SLSQP.

For non-convex problems these methods find local optima only, and global optimisation needs branch and bound over the variables’ ranges or many starting points.

[next] [prev] [prev-tail] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.