Optimisation Algorithms

A map of the field: continuous versus discrete, constrained versus unconstrained, convex versus non-convex, and why each split changes the algorithm.

Decision variables, objective, constraints and feasibility; translating a word problem into standard form without changing what it means.

Assumes: The Optimisation Landscape

Standard and canonical form, the feasible polytope, and why an optimum always sits at a vertex.

Assumes: Formulating an Optimisation Problem · Systems of Linear Equations

Tableau construction, pivoting rules, degeneracy and cycling, with a full numeric run from initial to optimal tableau.

Assumes: Linear Programming · Gaussian Elimination

Constructing the dual, weak and strong duality, complementary slackness, and reading shadow prices off the solution.

Assumes: The Simplex Method

How far a coefficient can move before the optimum changes, ranging on costs and right-hand sides, and what that buys a decision maker.

Assumes: Linear Programming Duality

Why rounding an LP solution fails, LP relaxation bounds, branch and bound traced on a small problem, and cutting planes.

Assumes: Linear Programming Duality

Max-flow/min-cut, transportation and assignment problems, and the Hungarian algorithm.

Assumes: Linear Programming · Graph Representations

Knapsack, TSP and set cover; NP-hardness, approximation ratios and when a greedy bound is provably good.

Assumes: Integer and Mixed-Integer Programming · Dynamic Programming

Exact versus backtracking line search, the Armijo and Wolfe conditions, and what linear, superlinear and quadratic convergence mean in iterations.

Assumes: Gradient Descent · Convex Sets and Convex Functions

Conjugate directions, why it solves an n-dimensional quadratic in n steps, and its use on large sparse systems.

Assumes: Line Search and Convergence Rates · Quadratic Forms and Definiteness

Secant conditions, the BFGS update derived, limited-memory L-BFGS, and why the Hessian is approximated rather than formed.

Assumes: The Conjugate Gradient Method · Newton and Quasi-Newton Methods

Modelling the objective locally and bounding the step, the Cauchy point, and comparison with line search.

Assumes: Quasi-Newton Methods

Optimising one variable at a time, when it converges, and why it is the method of choice for lasso and large sparse problems.

Assumes: Line Search and Convergence Rates

The subdifferential, optimality conditions without differentiability, and the slow but reliable subgradient method.

Assumes: Coordinate Descent

The proximal operator, soft thresholding derived in closed form, ISTA and FISTA acceleration.

Assumes: Subgradients and Non-Smooth Optimisation

Splitting a hard problem into easy pieces, the augmented Lagrangian, and consensus formulations for distributed fitting.

Assumes: Proximal Gradient Methods

Log-barrier functions, the central path, primal-dual formulations, and why they beat simplex on very large problems.

Assumes: Linear Programming Duality · KKT Conditions

Staying feasible by projecting each step, projections onto simple sets, and Frank–Wolfe as an alternative.

Assumes: Proximal Gradient Methods

Optimising an expectation from samples, Robbins–Monro conditions, convergence of SGD, and variance reduction with SVRG and SAGA.

Assumes: Line Search and Convergence Rates · Laws of Large Numbers

Black-box and derivative-free optimisation, exploration versus exploitation, and the no-free-lunch consequence for search.

Assumes: The Optimisation Landscape

Accepting worse solutions with decaying probability, the Metropolis criterion, cooling schedules and convergence guarantees.

Assumes: Metaheuristics: When Gradients Are Unavailable · Uniform and Exponential Distributions

Encoding, selection, crossover and mutation; CMA-ES, and where evolutionary search genuinely beats gradients.

Assumes: Simulated Annealing

Population methods driven by social behaviour, velocity updates, pheromone trails, and their typical failure modes.

Assumes: Genetic Algorithms and Evolution Strategies

Surrogate models over expensive objectives, Gaussian process posteriors, and the EI, UCB and Thompson acquisition functions.

Assumes: Metaheuristics: When Gradients Are Unavailable · The Multivariate Normal Distribution · Bayesian Estimation and Conjugate Priors

Pareto dominance and the Pareto front, scalarisation, epsilon-constraint methods and NSGA-II.

Assumes: Genetic Algorithms and Evolution Strategies

Scaling and conditioning, diagnosing non-convergence, choosing a solver, and reading the output of a commercial optimiser.

Assumes: Stochastic Optimisation · Interior-Point Methods