Optimisation

every linear program you have ever written down was a lie: the coefficients came from measurements, forecasts and vendor spreadsheets, and the optimal vertex — sitting, by design, on the boundary of the feasible region — shatters the moment any of them wobbles. 𐃏 robust optimisation is the pessimist’s response: declare a set \(\mathcal{U}\) of realisations you refuse to be hurt by, and demand feasibility for every member of it. no distributions, no expectations, no scenarios — just a set and a worst case. the surprise, and the reason the field exists, is that this worst case can usually be folded back into a deterministic problem of the same (or nearly the same) complexity class.¹

a linear program assumes you know the data. stochastic programming admits that you do not — some coefficients are random — but insists you know their distribution, and asks for the decision that is best on average. 𐃏 the structural insight that makes this a paradigm rather than a hack: split the decision in two. commit to \(x\) now, before the coin is flipped; after uncertainty resolves, take a corrective recourse action \(y\) that adapts to whatever happened. the objective charges you for both, weighting the second stage by expectation.¹

take a linear program and add one word — integer — and the complexity class jumps from polynomial to NP-hard. that word buys expressive power nothing continuous can match: yes/no decisions, either/or logic, fixed costs, sequencing, assignment. integer programming is the lingua franca of operations research precisely because “decide” is not a convex verb. 𐃏

promote the objective of a linear program from a plane to a bowl and you get quadratic programming: minimise a quadratic function over a polyhedron. it is the smallest step beyond LP, yet it captures a startling share of applied mathematics — support vector machines, portfolio selection, ridge regression, model-predictive control — because “squared penalty subject to linear rules” is how half the world states its preferences. 𐃏

“programming” here means planning, not coding — the word predates the software sense. 𐃏 a linear program optimises a linear objective over a region carved out by linear inequalities. it is the base camp of mathematical programming: quadratic, integer and non-linear programming all generalise it in one direction or another, and all of them lean on LP machinery (relaxations, duals, warm starts) to get anything done. clrs devotes chapter 29 to it (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009).

averaged over all possible problems, every learning algorithm is exactly as good as random guessing — and every optimiser is exactly as good as blind enumeration. 𐃏 this sounds like nihilism but is actually the sharpest possible argument for inductive bias: an algorithm can only beat chance on some problems by losing to chance on others, so the whole game of machine learning is choosing whose lunch to eat.