Optimisation is the mathematical science of making the best possible choice from a set of available alternatives. Whether minimising cost, maximising profit, or achieving some other objective subject to constraints, optimisation problems arise across engineering, economics, operations research, and the sciences. This course develops both the theoretical foundations and practical methods for solving optimisation problems, from small-scale applications to large systems of industrial importance. We begin by establishing the conceptual and mathematical preliminaries needed to formulate and analyse optimisation problems rigorously, then progress through increasingly sophisticated techniques for finding optimal solutions.

The course centres on several interconnected themes. First is the role of constraints: most real-world optimisation involves restrictions on feasible solutions, and understanding how constraints affect optimality is crucial. Second is the distinction between continuous and discrete optimisation, illustrated through polynomial-time algorithms for linear programs versus the combinatorial complexity of network routing. Third is the interplay between single-agent optimisation and game-theoretic settings, where multiple decision-makers compete or cooperate. Throughout, we emphasise both necessary conditions for optimality (such as the Lagrange multiplier conditions) and algorithmic methods for computing optimal solutions.

The chapters build a natural progression. We establish foundations in Chapter 1, then introduce Lagrange multipliers in Chapter 2 — the cornerstone technique for handling equality and inequality constraints. Chapter 3 treats linear programming, where constraints are affine and objectives linear, revealing the geometric structure of feasible regions and the simplex method. Chapter 4 shifts perspective to game theory, where optimisation becomes strategic: each player optimises their own objective given others' choices, leading to equilibrium concepts rather than global optima. Finally, Chapter 5 applies these ideas to network problems — routing, flow, matching — where graph structure combines with optimisation to solve canonical operational problems.

# Introduction and Preliminaries

This opening chapter lays the algebraic and analytic groundwork for the entire course. The central subject of Operations Research is optimisation under constraints: given an objective function and a set of feasibility conditions, find the decision variables that achieve the best objective value. Before developing algorithmic machinery, the course establishes what the most general form of such a problem looks like, introduces the special but fundamental case of linear programming, and recalls the classical theory of unconstrained optimisation — in particular, the role of convexity — that motivates everything that follows.

## Constrained Optimisation and Its General Form

Every optimisation problem in this course can be written in a single canonical form. To see why this is worth doing, consider a factory that wants to minimise production cost. Minimising over all of $\mathbb{R}^n$ with no restrictions is meaningless — producing nothing would minimise cost without any practical meaning. Practical problems always come with constraints, and the art of the subject is to handle those constraints systematically.

[definition: Constrained Optimisation Problem] The **general constrained optimisation problem** is: \begin{align*} \text{minimise} \quad & f(x) \\ \text{subject to} \quad & h(x) = b, \quad x \in X, \end{align*} where $x \in \mathbb{R}^n$ is the **vector of decision variables**, $f: \mathbb{R}^n \to \mathbb{R}$ is the **objective function**, $h: \mathbb{R}^n \to \mathbb{R}^m$ and $b \in \mathbb{R}^m$ define the **functional constraints**, and $X \subseteq \mathbb{R}^n$ is the **regional constraint**. [/definition]

This formulation is genuinely the most general one. Several apparent variants reduce to it:

- **Maximisation.** To maximise $f$, minimise $-f$. - **Inequality functional constraints.** To handle $h(x) \geq b$, introduce a **slack variable** $z \geq 0$ and rewrite the constraint as $h(x) - z = b$, with $z \geq 0$ appended to the regional constraint. - **Unconstrained variables.** If a variable $x_j$ may take any sign, write $x_j = x_j^+ - x_j^-$ with $x_j^+, x_j^- \geq 0$. Both parts are then governed by the standard regional constraint.

Note: throughout this course almost every object is a vector, so vectors are not bolded — context always makes the distinction clear.

## Linear Programming

What special structure can we exploit when the objective and all constraints are linear? This question is not merely academic: linearity turns out to be the key to both theoretical tractability and practical solvability.

**Linear programming** is the special case of constrained optimisation in which both the objective function and all constraints are linear. Linearity buys two decisive advantages. First, the feasible region — the intersection of finitely many half-spaces — is a convex polytope with only finitely many vertices. Second, it is a classical fact that if a finite optimum exists, it is always attained at one of these vertices. This means the search for an optimum over an infinite feasible set reduces, in principle, to checking finitely many candidate points. In practice the simplex method (Chapter 3) exploits this geometry to move efficiently from vertex to vertex, and interior-point methods (Chapter 4) achieve polynomial worst-case complexity. Neither guarantee is available for general nonlinear programs.

A general linear program can involve constraints of mixed types ($\geq$, $\leq$, $=$) and variables with mixed sign restrictions. One can reduce all of these, via the slack variable technique above, to two canonical forms.

[definition: General and Standard Forms of a Linear Program] The **general form** of a linear program is: \begin{align*} \text{minimise} \quad & c^\top x \\ \text{subject to} \quad & Ax \geq b, \quad x \geq 0. \end{align*} The **standard form** is: \begin{align*} \text{minimise} \quad & c^\top x \\ \text{subject to} \quad & Ax = b, \quad x \geq 0. \end{align*} [/definition]

The two forms are equivalent: introduce slack variables $z \geq 0$ with $Ax - z = b$ to pass from general to standard form. The standard form is preferred when developing theoretical results, because equality constraints are easier to work with algebraically. In practice, the conversion can increase the number of variables, which is a computational trade-off rather than a theoretical one.

[example: A Two-Dimensional Linear Program] Minimise $-(x_1 + x_2)$ subject to \begin{align*} x_1 + 2x_2 &\leq 6, \\ x_1 - x_2 &\leq 3, \\ x_1, x_2 &\geq 0. \end{align*} Because this is a two-dimensional problem, the feasible region — the set of $(x_1, x_2)$ satisfying all constraints — is a convex polygon. Its corners are found by solving pairs of binding constraints. The origin $(0,0)$ is the intersection of $x_1 = 0$ and $x_2 = 0$. The point $(3,0)$ is the intersection of $x_1 - x_2 = 3$ and $x_2 = 0$: substituting $x_2 = 0$ gives $x_1 = 3$. The point $(0,3)$ is the intersection of $x_1 + 2x_2 = 6$ and $x_1 = 0$: substituting $x_1 = 0$ gives $x_2 = 3$. The point $(4,1)$ is the intersection of the two non-trivial constraints $x_1 + 2x_2 = 6$ and $x_1 - x_2 = 3$: subtracting the second from the first gives $3x_2 = 3$, so $x_2 = 1$ and $x_1 = 4$. Thus the four corners are $(0,0)$, $(3,0)$, $(4,1)$, and $(0,3)$. The objective function $-(x_1 + x_2)$ defines level curves $x_1 + x_2 = k$ (lines with slope $-1$), and its gradient (the cost vector $c = (-1,-1)^\top$) points in the direction of steepest decrease of the objective. To minimise $-(x_1 + x_2)$, we push the level curve $x_1 + x_2 = k$ as far as possible in the direction of $c$, i.e.\ we want the largest value of $x_1 + x_2$. The objective values at the corners are: $(0,0) \mapsto 0$, $(3,0) \mapsto -3$, $(4,1) \mapsto -5$, $(0,3) \mapsto -3$. The minimum value $-5$ is attained at $x^* = (4,1)$. [/example]

[illustration:lp-feasible-region-level-curves]

The example already suggests the key structural fact about linear programs: the optimum is always achieved at a corner of the feasible region. This observation drives the entire algorithmic development in subsequent chapters.