Fletcher Practical Methods Of Optimization

Working Through Fletcher's Optimization Methods in Real Code

Fletcher's Practical Methods Of Optimization isn't a cookbook you follow end to end. It's a reference you pull apart, take the pieces that apply, and patch together with whatever else your problem demands. I've spent years using it as the backbone for engineering design loops, and the gap between the clean derivations on the page and what actually runs in production is wider than most people expect. The book covers the full spectrum from basic line search unconstrained methods all the way through sequential quadratic programming for constrained problems. If you're just starting out, Chapter 1 through Chapter 4 will give you enough to implement a decent BFGS routine. The real value shows up later when you're wrestling with constraints and need to understand why your SQP solver is stalling.

Getting Started With Fletcher Practical Methods Of Optimization

Start by implementing a simple gradient descent with backtracking line search. It's the easiest way to see what Fletcher means by "sufficient decrease" versus "curvature condition." Most people skip this and go straight to BFGS, but understanding where the Armijo and Wolfe conditions actually come from matters when your optimizer starts behaving strangely on a production problem. Here's a stripped-down BFGS update in practice. You maintain an approximation to the inverse Hessian, B, and update it each iteration using the gradient difference s and step difference y. The Sherman-Morrison-Woodbury structure keeps it at O(n^2) per iteration instead of O(n^3). For problems up to a few thousand variables this is fine. Beyond that you'll want a limited-memory variant. The key formula for the BFGS inverse Hessian update is straightforward to code but easy to get wrong. If you're not careful about the curvature condition s^T y > 0, your Hessian approximation can go indefinite and your search direction becomes meaningless. Fletcher discusses this in detail around Section 1.9, and the short version is: check the condition before applying the update, and if it fails, skip the iteration or fall back to a gradient step.

I ran into this exact issue on a structural optimization project where the design space included some nearly singular configurations. The BFGS updates started accumulating numerical noise because s^T y was positive but extremely small. My workaround was to add a simple regularization term: if s^T y fell below a threshold relative to ||s|| * ||y||, I reset the Hessian approximation to the identity and started fresh. This happened maybe once every few dozen iterations, and it completely stabilized the convergence.

Constrained Optimization Is Where Things Get Real

Unconstrained methods are nice. Constrained methods are where you learn whether you actually understand optimization or just know how to call scipy.optimize. Fletcher covers penalty methods, augmented Lagrangian techniques, and SQP. The augmented Lagrangian approach, often called the method of multipliers, tends to be the most robust in practice for medium-scale problems. The basic idea is you take your Lagrangian L(x, lambda) = f(x) + lambda^T h(x) and add a quadratic penalty term mu/2 * ||h(x)||^2. Unlike a pure penalty method, you update the multipliers lambda between subproblems instead of just cranking up mu until convergence. This avoids the ill-conditioning that pure penalty methods suffer from. The trick is the multiplier update. The standard rule is lambda_new = lambda_old + mu * h(x*). If your constraint violation isn't dropping, either mu is too small or your subproblem solver isn't accurate enough. Fletcher walks through this in Chapter 9, and the practical takeaway is that you generally want to solve each subproblem to moderate accuracy rather than high accuracy. A fresh start on the multiplier gives you more information than squeezing one more decimal out of a poorly conditioned subproblem.

Sequential quadratic programming works differently. At each iteration you linearize the constraints and approximate the Lagrangian Hessian, then solve a quadratic subproblem to get your step. The QP subproblem itself needs to be solved accurately, and that's where things can fall apart. If your QP solver hits a numerical boundary or returns an infeasible solution, your whole algorithm stalls. I found that a robust implementation needs a fallback strategy for when the QP is infeasible. The standard approach is a least-squares feasibility subproblem: minimize ||c(x) + Jac_c(x)^T d||^2 to find a direction that reduces constraint violation even if you can't satisfy everything. Fletcher covers this in the context of merit function methods, and it's worth reading that section carefully because the theory behind why it works isn't obvious from a single pass.

Trust Region Methods: Often Overlooked But Useful

Fletcher devotes significant attention to trust region methods, and honestly they deserve more use than they get. The intuition is simple: instead of picking a step size along a search direction, you define a region around your current point where your quadratic model is trusted, then solve a constrained subproblem within that region. The ratio of actual reduction to predicted reduction determines whether you accept the step and whether you expand or contract the trust region. This single mechanism handles both step length and direction selection without needing a separate line search. For problems where the objective has significant local curvature variations, trust region methods can be more stable than line search approaches. The main downside is computational cost. Each iteration requires solving a trust region subproblem, which itself is an optimization problem. The dogleg method works well for moderate sizes, but for large-scale problems you need a conjugate gradient based inner solver, and that adds complexity. I've seen production code where the trust region overhead made the algorithm slower than a comparable BFGS implementation with a good line search, despite better per-step robustness. The tradeoff is real.

Numerical Issues That Nobody Talks About

Floating point arithmetic ruins more optimization code than poor algorithmic choices. When you're computing finite difference gradients, the step size is a constant source of bugs. Too large and you're approximating the wrong derivative. Too small and rounding error dominates. A common rule of thumb is to use a step around machine epsilon raised to one-third power, which for double precision is roughly 1e-5. Fletcher mentions this briefly, but the practical implication is that your gradient check should never pass with a step smaller than 1e-7 without investigation. Another issue is scaling. If your objective function has variables on different orders of magnitude, the Hessian approximation becomes ill-conditioned and the optimizer spends most of its time correcting for poor geometry. I once spent three days debugging an optimization that turned out to be entirely a scaling issue. The fix was simply to normalize all design variables to have unit order of magnitude before running the solver. Convergence went from hundreds of iterations to fewer than twenty. Memory management matters too. BFGS stores a full n-by-n matrix, which for a 10,000 variable problem is about 800 MB. That's manageable on most modern machines but becomes a constraint quickly. Limited-memory BFGS stores only the last m gradient differences, typically m = 5 to 20, which brings the memory footprint down to roughly O(mn). The convergence rate degrades somewhat, but for most engineering applications the difference is negligible and the speedup is substantial.

When Fletcher's Methods Break Down

None of this works well if your problem is discontinuous or non-differentiable. Fletcher's methods assume smooth objectives and constraints. If you're working with simulation black boxes that have discontinuities, no amount of tweaking the Hessian approximation will help. You'd be better off with derivative-free methods or evolutionary approaches, though those come with their own costs. Highly constrained problems with many active constraints can also be problematic. The KKT system that arises in SQP can become singular or near-singular when constraints are redundant or nearly dependent. Regularization techniques exist, but they add complexity and parameters to tune. If you're facing this scenario regularly, looking into interior point methods or a full barrier approach might save you more time than trying to make SQP work. The book itself is dense. It's not written as a tutorial, and the notation can shift between chapters. I find it useful to have a second reference alongside it, like Nocedal and Wright's Numerical Optimization, which covers similar material with slightly different emphasis and more modern algorithmic details. Using both texts together fills in gaps that either one leaves open.

If you want the actual book, it's widely available through academic publishers and most university libraries carry it. The second edition is the one to get. The first edition has some notation differences and misses later developments in trust region and quasi-Newton theory that Fletcher himself contributed to.