Optimisation Methods

A huge share of practical problems reduce to the same shape: find the choice that's best, subject to constraints. The cheapest delivery route, the staff roster that covers every shift, the portfolio with the most return for a given risk, the model weights that minimise error — all are optimisation problems. It's one of the most unifying ideas in all of applied maths, quietly powering machine learning, logistics, economics, and engineering alike.

This page is the broader landscape beyond the gradient descent you've already met — deepening the operations-research foundation. The throughline is a single, powerful insight: whether an optimisation problem is easy or brutally hard depends almost entirely on the shape of its landscape, and recognising that shape is the first thing a good optimiser does.

Optimisation as a unifying frame

Every optimisation problem has the same three parts: an objective (the thing to minimise or maximise — cost, error, time), variables (the decisions you control), and constraints (the rules the solution must satisfy — budgets, capacities, physical limits). Phrase a problem in those terms and you've made it an optimisation problem, ready for a whole toolbox of methods.

Recognising this frame is itself valuable: "minimise total cost such that every demand is met and no truck is over capacity" is the same kind of problem as "minimise prediction error such that the weights aren't too large." The methods differ by the landscape, which is where we go next.

Convex vs non-convex: the great divide

The single most important property of an optimisation problem is whether it's convex. A convex problem has a landscape shaped like a single smooth bowl: there's one lowest point, and any local minimum is the global minimum. That guarantee is everything — it means a simple downhill method (like gradient descent) is certain to find the true best answer. Convex problems are, in a real sense, "solved."

The great divide. A convex landscape is a single bowl — roll downhill and you always reach the one true minimum. A non-convex landscape has many valleys; a downhill method gets stuck in whichever local minimum it happens to land near, with no guarantee it's the best.

A non-convex problem has a landscape full of hills and valleys — many local minima. A downhill method gets trapped in whichever valley it starts near, with no guarantee it's the deepest. Most genuinely hard optimisation (including training deep networks) is non-convex, which is why so much effort goes into either making problems convex or accepting "good enough" answers. Convexity is the line between "solvable" and "hard."

Linear programming & the simplex method

The classic, beautifully solvable case is linear programming (LP): a linear objective subject to linear constraints. The constraints carve out a feasible region — a multi-dimensional polygon — and a key theorem says the optimum always sits at one of its corners (vertices). That turns an infinite search into checking corner points.

The famous simplex method (Dantzig, 1947) exploits this: start at a corner of the feasible region and walk along edges to adjacent corners that improve the objective, until no neighbour is better — that corner is optimal. It's the workhorse behind classic operations research — resource allocation, diet problems, transportation, blending — and LP is convex, so the answer it finds is genuinely the best.

Integer programming: the leap in difficulty

Add one innocent-looking requirement — that some decisions must be whole numbers — and the difficulty explodes. Integer programming covers the many problems where you can't have 2.7 trucks or assign half a person to a shift. The trouble is that "integer" makes the feasible region a scatter of discrete points rather than a smooth region, which is non-convex and, in general, NP-hard — there's no known efficient algorithm that always solves it fast.

The practical workhorse is branch-and-bound — cleverly partition the problem into subproblems, solve the easy (relaxed, continuous) version of each, and prune branches that can't possibly beat the best solution so far. It works remarkably well in practice despite the worst-case hardness. The lesson is worth internalising: requiring whole-number answers is a genuine jump in difficulty, not a detail — many real scheduling and assignment problems are hard for exactly this reason.

Handling the constraints

Constraints are what make optimisation realistic — and tricky. For smooth constrained problems, the classic tool is Lagrange multipliers (generalised to the KKT conditions): a method that folds the constraints into the objective, turning "minimise subject to" into a single system to solve, and revealing how hard each constraint is "pushing" at the optimum (its shadow price — how much the objective would improve if you relaxed that constraint a little). That sensitivity information is often as valuable as the solution itself, because it tells you which constraint to loosen first.

Metaheuristics: when the landscape is ugly

For non-convex, discrete, or black-box problems where exact methods are hopeless, you turn to metaheuristics — general-purpose search strategies that look for a good-enough solution without any guarantee of the best. Most are inspired by nature:

Genetic algorithms — evolve a population of candidate solutions: keep the fittest, "breed" them by combining parts, and "mutate" randomly. Natural selection as a search method.
Simulated annealing — borrow from metallurgy: explore widely at first (accepting some worse moves to escape local minima), then gradually "cool" to settle into a good valley.

Where it shows up in my work

Best decisions under constraints

"Find the best decision subject to constraints" is a shape that recurs constantly in government work — allocating limited resources, scheduling staff or assets, planning under budget and capacity limits. The most valuable habit optimisation gives me is recognising when a problem is one of these, then identifying its structure before reaching for a method: a linear problem yields to LP/simplex and a guaranteed-best answer, while an integer-constrained one (whole people, whole vehicles) is genuinely harder and needs branch-and-bound or a good-enough heuristic.

The convex-vs-non-convex distinction is the key judgement — it's the difference between "solvable exactly" and "settle for good enough," and knowing which you're facing prevents both over-engineering and false confidence. It connects straight to gradient descent (the convex workhorse), model training (non-convex), and OR (the classic applications) — a unifying lens across much of the toolkit.

Refresh in 60 seconds

Optimisation = objective + variables + constraints — minimise/maximise the best decision. The unifying frame under ML, OR, allocation.
The great divide: convex (one bowl — any local min is global, "solvable") vs non-convex (many valleys — downhill methods get stuck).
Linear programming (linear objective + constraints) → the optimum is at a corner; the simplex method walks corner to corner. Convex, exact.
Integer programming (whole-number decisions) is a real jump — non-convex, NP-hard; solved with branch-and-bound.
Constraints via Lagrange multipliers / KKT — and the shadow price tells you which constraint to relax.
Metaheuristics (genetic algorithms, simulated annealing) find good-enough answers for ugly problems — no optimality guarantee (no free lunch). Match the method to the structure; don't over-engineer.

The convex/non-convex divide, LP/simplex and integer-programming/branch-and-bound, and the metaheuristics + no-free-lunch framing reflect current optimisation references alongside OR coursework.