Die Druckversion wird nicht mehr unterstützt und kann Darstellungsfehler aufweisen. Bitte aktualisiere deine Browser-Lesezeichen und verwende stattdessen die Standard-Druckfunktion des Browsers.

Optimisation

Introduction

Optimisation is the systematic search for the best feasible decision according to a stated objective. In mathematical optimisation, you choose decision variables, define an objective function to minimise or maximise, and specify the constraints that acceptable solutions must satisfy. This framework appears in Mathematics, Operations research, Computer science, Engineering, Economics, Statistics, and Machine learning.

At university level, optimisation is not only about obtaining a numerical answer. You need to understand how a model represents a real decision, when a solution is globally or locally optimal, which algorithms are appropriate, how computational choices affect results, and how to evaluate trade-offs and uncertainty.

By the end of this aiMOOC, you should be able to formulate optimisation problems, classify important problem types, apply optimality conditions, explain major algorithmic ideas, interpret dual variables and sensitivity, evaluate computational evidence, and transfer optimisation methods to new applications.

Formulating an Optimisation Problem

A standard constrained minimisation problem can be written as

$min_{x} f (x)$

subject to

$g_{i} (x) \leq 0, i = 1, \dots, m$

and

$h_{j} (x) = 0, j = 1, \dots, p .$

Here, $x$ is the vector of decision variables, $f$ is the objective function, and the functions $g_{i}$ and $h_{j}$ define inequality and equality constraints. The set of all points satisfying the constraints is the feasible set. A feasible point that achieves the best objective value is an optimal solution.

A maximisation problem can be converted to minimisation by negating the objective. The formulation matters: a mathematically correct solver cannot repair a model that represents the wrong objective, omits an essential constraint, or uses unsuitable units.

From Real Decisions to Mathematical Models

Suppose a university must schedule rooms, lecturers, and courses. Decision variables could indicate which course uses which room and time slot. Constraints can enforce room capacities, prevent timetable clashes, and respect lecturer availability. The objective might minimise unused capacity, student travel between buildings, or an explicitly weighted combination of several goals.

A strong model separates four questions. What can be chosen? determines the variables. What counts as success? determines the objective. What is physically, legally, or logically required? determines the constraints. Which data are uncertain or estimated? determines whether deterministic, stochastic, or robust methods are appropriate.

Major Problem Classes

Optimisation methods are specialised because mathematical structure determines what can be guaranteed and what can be computed efficiently.

Continuous optimisation uses variables that can vary over intervals of real numbers. Discrete optimisation uses choices such as integers, binary variables, permutations, or graph structures. Unconstrained optimisation has no explicit feasibility restrictions beyond the domain, whereas constrained optimisation restricts admissible solutions.

A linear programme has a linear objective and linear constraints. A quadratic programme has a quadratic objective with linear constraints in its common form. A nonlinear programme contains nonlinear objectives or constraints. An integer programme requires some or all variables to be integers. A stochastic optimisation problem explicitly models randomness, while robust optimisation seeks decisions that remain acceptable under specified uncertainty sets.

Convex and Non-Convex Structure

Convexity is central because it changes the meaning of local optimality. A set is convex when the line segment between any two of its points remains in the set. A function $f$ is convex when, for any $x$ , $y$ , and $0 \leq θ \leq 1$ ,

$f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y) .$

For a convex minimisation problem with a convex feasible set, every local minimum is a global minimum. Strict convexity can additionally give uniqueness of the minimiser when one exists. Non-convex problems may contain many local minima, saddle points, disconnected feasible regions, or other structures that make global optimisation much harder.

Optimality Conditions

For a differentiable unconstrained function, a local optimum in the interior usually satisfies the first-order stationarity condition $\nabla f (x^{*}) = 0$ . The Hessian matrix $\nabla^{2} f (x)$ describes local curvature. At a stationary point, a positive definite Hessian is a sufficient condition for a strict local minimum, while an indefinite Hessian identifies a saddle point.

For an equality-constrained problem, the Lagrange multiplier method forms a Lagrangian such as

$L (x, λ) = f (x) + λ^{𝖳} h (x) .$

At a regular constrained optimum, the gradient of the objective is balanced by a linear combination of the constraint gradients. Geometrically, objective contours become tangent to active constraint surfaces.

Karush-Kuhn-Tucker Conditions

For differentiable inequality-constrained problems, the Karush-Kuhn-Tucker conditions extend the Lagrange multiplier idea. In a common minimisation convention with constraints $g_{i} (x) \leq 0$ , the conditions include primal feasibility, dual feasibility of the multipliers, stationarity of the Lagrangian, and complementary slackness.

Complementary slackness links an inequality and its multiplier: an inactive inequality has zero multiplier, while a positive multiplier can occur only when the corresponding constraint is active. Under suitable constraint qualifications, KKT conditions are necessary for local optimality. For convex problems, they can also be sufficient under standard assumptions.

Algorithms for Continuous Optimisation

No single algorithm is best for every optimisation problem. The choice depends on derivatives, dimensionality, convexity, noise, constraint structure, sparsity, and the required accuracy.

Gradient Descent and First-Order Methods

For a differentiable objective, gradient descent updates

$x_{k + 1} = x_{k} - α_{k} \nabla f (x_{k}),$

where $α_{k}$ is the step size or learning rate. The negative gradient is the direction of steepest local decrease under the Euclidean norm. A step size that is too large can cause oscillation or divergence, while a step size that is too small can make progress unnecessarily slow.

First-order methods scale well to high-dimensional problems because they avoid forming or factorising a Hessian. Variants include stochastic gradient descent, momentum methods, projected gradient methods for constraints, and proximal methods for objectives with structured non-smooth terms.

Newton, Quasi-Newton, and Derivative-Free Methods

Newton's method uses both gradient and Hessian information to construct a local quadratic model. Near a well-behaved solution it can converge very rapidly, but Hessian computation and factorisation can be expensive. Quasi-Newton methods such as BFGS approximate curvature using successive gradients, often providing a useful compromise between speed and cost.

When derivatives are unavailable, unreliable, or very expensive, derivative-free methods can be useful. The Nelder-Mead method, for example, moves and reshapes a simplex using reflection, expansion, contraction, and shrink operations. It can work well on some low-dimensional smooth problems, but it does not provide the same general guarantees as convex first-order methods.

Linear and Discrete Optimisation

Linear Programming and the Simplex Method

A linear programme can be written in a standard form such as maximising $c^{𝖳} x$ subject to $A x \leq b$ and $x \geq 0$ . Its feasible set is a convex polyhedron. The simplex method traverses a sequence of basic feasible solutions along this polyhedron, using pivot rules and reduced-cost information to seek an optimum. Degeneracy can produce pivots without objective improvement, so practical implementations use additional safeguards and numerical techniques.

The simplex method is historically important and often effective in practice. Interior-point methods provide another major approach to linear and convex optimisation and can be especially attractive for large structured problems.

Integer and Combinatorial Optimisation

Discrete decisions arise when you must select projects, assign people, route vehicles, design networks, or schedule tasks. Integer programming combines algebraic models with integrality restrictions. Exact approaches include branch-and-bound, branch-and-cut, and dynamic programming for problems with suitable structure.

Combinatorial problems can be computationally difficult. The Travelling salesperson problem asks for a shortest tour that visits each location once and returns to the start. For large difficult instances, heuristics and metaheuristics can produce strong solutions without proving global optimality. Ant-colony optimisation is one example of a population-based metaheuristic inspired by collective trail-following behaviour.

Duality and Sensitivity

Duality associates an optimisation problem with another problem whose values can bound the original objective. For a minimisation problem, a Lagrangian dual function provides lower bounds on the primal optimum. Weak duality holds very broadly. Strong duality, where primal and dual optimal values coincide, requires additional conditions and is especially powerful in convex optimisation.

Dual variables are also useful for interpretation. In linear programming, a dual variable can represent the marginal value of relaxing a constraint, often called a shadow price. Sensitivity analysis asks how the optimal solution or objective changes when coefficients, right-hand sides, or other data are perturbed.

Worked Examples

Resource Allocation Example

Consider two activities with non-negative levels $x$ and $y$ . Maximise $3 x + 2 y$ subject to $x + y \leq 4$ , $x \leq 2$ , and $y \leq 3$ . The feasible vertices are obtained from intersections of the boundary lines. Evaluating the objective at those vertices shows that $(x, y) = (2, 2)$ is optimal with objective value $10$ .

The important lesson is not merely the answer. The linear structure makes the feasible region convex and the objective linear, so vertex-based reasoning is justified. If you changed an upper bound or objective coefficient, sensitivity analysis could show whether the same basis remains optimal.

One-Dimensional Gradient Descent Example

Let $f (x) = (x - 3)^{2}$ . Then $f^{'} (x) = 2 (x - 3)$ . With $x_{0} = 0$ and a constant step size $α = 0.2$ , gradient descent gives $x_{1} = 1.2$ , $x_{2} = 1.92$ , and $x_{3} = 2.352$ . The iterates approach the unique minimiser $x^{*} = 3$ .

This example also illustrates why the learning rate matters. For a quadratic objective, convergence can be analysed mathematically; in more complex problems, line search, adaptive schedules, or problem-specific tuning may be needed.

Equality-Constrained Example

Suppose you want to maximise $x y$ subject to $x + y = 10$ with positive variables. The Lagrangian is $L (x, y, λ) = x y + λ (10 - x - y)$ . Stationarity gives $y - λ = 0$ and $x - λ = 0$ , so $x = y$ . Combining this with the constraint gives $x = y = 5$ , which yields the maximum product.

Computational Practice

A solver result should be treated as evidence, not magic. Check feasibility residuals, optimality residuals, termination status, iteration limits, and whether the solver claims a local or global guarantee. Scale variables and constraints when magnitudes differ greatly, because poor scaling can harm numerical stability.

Initialisation matters for many non-convex algorithms. Random restarts can reveal sensitivity to starting points. Reproducible experiments should record the objective, constraints, data version, random seed where relevant, solver and version, tolerances, stopping criteria, hardware-sensitive settings when important, and final diagnostics.

Modern optimisation workflows often use modelling systems such as CVX, CVXPY, JuMP, or algebraic modelling languages to separate model specification from numerical solvers. This separation makes models easier to inspect, test, and reuse.

Choosing an Algorithm

Begin with structure rather than popularity. If a problem is convex, exploit convexity. If it is a large smooth unconstrained problem, first-order or quasi-Newton methods may be appropriate. If it contains integer decisions, use mixed-integer optimisation methods. If derivatives are unavailable, consider derivative-free methods. If uncertainty is central, use stochastic or robust formulations rather than pretending uncertain inputs are exact.

You should also distinguish solution quality from solution speed. An algorithm that quickly returns a feasible point may be valuable in real-time systems even without a global proof, while safety-critical planning may require rigorous bounds or certificates.

Applications, Trade-Offs, and Responsible Modelling

Optimisation supports energy dispatch, supply chains, portfolio design, medical resource allocation, communications, control systems, machine learning, manufacturing, transport, and scientific inference. In each field, the objective function encodes a definition of what is valuable.

This creates a responsibility: an optimum is only optimal relative to the model. If an objective ignores fairness, resilience, environmental cost, uncertainty, or rare but severe failures, the computed solution may be mathematically correct yet practically harmful. Multi-objective optimisation, explicit constraints, robust formulations, and stakeholder review can make trade-offs visible instead of hiding them inside a single score.

For university work, always ask what is measured, what is omitted, who is affected, which assumptions support the model, and how sensitive the recommendation is to those assumptions.

Interactive Tasks

Quiz: Test Your Knowledge

What is the feasible set of an optimisation problem? (All points that satisfy every constraint) (!All points with zero gradient) (!All points with integer coordinates) (!All points with the same objective value)

What is the main role of the objective function? (To quantify what is minimised or maximised) (!To specify every numerical algorithm) (!To guarantee that the feasible set is convex) (!To remove the need for constraints)

Which statement is true for convex minimisation with a convex feasible set? (Every local minimum is a global minimum) (!Every stationary point is a maximum) (!Every feasible point has the same value) (!Every problem has exactly one solution)

Which direction does standard gradient descent use for a local update? (The negative gradient direction) (!The positive gradient direction) (!A random direction only) (!The largest coordinate direction)

What do Lagrange multipliers help analyse? (Optimisation with constraints) (!Only sorting algorithms) (!Only integer arithmetic) (!Unrelated probability samples)

What does complementary slackness connect? (An inequality constraint and its multiplier) (!Two unrelated objective functions) (!A random seed and a tolerance) (!A Hessian and a data file)

For which problem class is the simplex method designed? (Linear programming) (!Unconstrained image compression) (!Symbolic integration) (!Database encryption)

What can a dual variable represent in linear programming? (The marginal value of relaxing a constraint) (!The number of solver iterations) (!The size of the source code) (!The order of matrix rows)

Which feature makes a mixed-integer problem discrete? (Some variables must take integer values) (!Every coefficient must be negative) (!The objective must be constant) (!Every constraint must be an equality)

Which practice best supports reproducible computational optimisation? (Recording solver settings and model data) (!Reporting only the final objective value) (!Changing tolerances without documentation) (!Ignoring termination status)

Memory Game

Objective	Quantity to be minimised or maximised
Feasibility	Satisfaction of all required constraints
Convexity	Structure that can turn local minima into global minima
Gradient	Vector of first partial derivatives
Duality	Relationship between a primal problem and a bounding problem
Integrality	Requirement that selected variables take whole-number values

Drag and Drop

Match the correct terms.	Topic
Linear objective and linear constraints	Linear programming
Use of first derivative information	Gradient method
Whole-number decision restrictions	Integer optimisation
Primal bounds from an associated problem	Duality theory
Protection against specified uncertainty	Robust optimisation

...

Crossword Puzzle

Convexity	What property makes every local minimum global in a convex minimisation problem?
Gradient	What vector collects the first partial derivatives of a scalar objective?
Simplex	Which linear programming method moves among basic feasible solutions?
Duality	What theory relates a primal optimisation problem to an associated bounding problem?
Feasible	What word describes a point that satisfies every constraint?
Integer	What type of variable is restricted to whole-number values?

LearningApps

Cloze Text

An optimisation model uses decision variables to represent the choices you can

. The function that measures what should be improved is the

. A point that satisfies every constraint is called

. In a convex minimisation problem, a local minimum is also a

minimum. Gradient descent updates variables using first-order

. Lagrange multipliers help express first-order conditions for

problems. In linear programming, dual variables can be interpreted as marginal values or

prices. Reliable computational work records solver settings, tolerances, and termination

.

Open-Ended Tasks

Easy

Objective Function Audit: Choose a familiar university decision, identify the decision variables, propose one objective, and explain one important factor that the objective leaves out.
Feasible Region Sketch: Create a labelled image of a two-variable constrained problem, shade its feasible region, and mark at least one feasible and one infeasible point.
Gradient Descent Experiment: Use a spreadsheet or short program to run gradient descent on a simple quadratic, vary the step size, and describe how the convergence behaviour changes.
Optimisation Interview: Interview a student, lecturer, engineer, analyst, or manager about a real decision they try to optimise and summarise the objective, constraints, and uncertainty they face.

Standard

Linear Programming Project: Formulate and solve a small resource-allocation problem, justify every coefficient and constraint, and interpret the optimal solution in the original context.
Solver Comparison: Solve the same smooth optimisation problem with two different algorithms, record iterations and final residuals, and explain why their behaviour differs.
Optimisation Video Explainer: Produce a three-to-five-minute video that teaches convexity, gradient descent, or duality using your own numerical example and visualisation.
Campus Optimisation Walk: Visit a campus location connected to timetabling, energy, transport, catering, or logistics and document where optimisation could improve a real process.

Advanced

KKT Analysis: Derive the KKT conditions for a constrained nonlinear problem, identify the active constraints at your candidate solution, and test whether the conditions certify optimality.
Robust Optimisation Study: Build a deterministic model and a robust variant for the same uncertain decision, compare their solutions, and explain the price paid for additional protection.
Combinatorial Optimisation Benchmark: Implement or use an exact method and a heuristic for a discrete problem, compare solution quality and runtime across increasing instance sizes, and discuss scalability.
Ethical Optimisation Project: Design a model for a socially consequential allocation problem, interview or consult at least two stakeholder perspectives, and revise the objective or constraints to make important trade-offs explicit.

Learning Assessment

Model Critique: Given a proposed optimisation model for allocating scarce resources, identify at least three modelling assumptions, explain their consequences, and propose justified revisions.
Algorithm Selection: Compare two candidate algorithms for a large constrained problem and defend your choice using convexity, derivative availability, dimensionality, accuracy, and computational cost.
Sensitivity Reasoning: Explain how a change in one binding constraint could affect the optimum, then connect your explanation to dual variables or shadow prices.
Convergence Diagnosis: Analyse a run in which an iterative method oscillates or stalls, identify plausible mathematical and numerical causes, and design a sequence of diagnostic tests.
Transfer Challenge: Translate a problem from another discipline into decision variables, objective, constraints, and uncertainty, then justify the resulting problem class and solution approach.
Evidence-Based Solver Report: Evaluate whether a reported solution is trustworthy using feasibility, optimality conditions, solver status, tolerance information, and independent checks.

Evidence of Learning

Knowledge: You can explain objective functions, feasible sets, local and global optima, convexity, first- and second-order conditions, Lagrange multipliers, KKT conditions, linear and integer programming, duality, and sensitivity.

Skills: You can translate a real decision into a mathematical model, derive or check optimality conditions, select an algorithm from problem structure, run computational experiments, inspect solver diagnostics, and communicate limitations.

Products: Strong evidence includes a transparent optimisation model, reproducible code or solver file, a visualisation of feasible or search geometry, a reasoned comparison of algorithms, and a concise technical report that connects the mathematics to the application.

Transfer achievements: You can recognise optimisation structure in an unfamiliar field, reformulate a problem when assumptions change, distinguish numerical success from mathematical guarantees, and evaluate whether an objective and its constraints reflect responsible real-world priorities.

OERs on the Topic

For deeper university study, the freely accessible online materials for Convex Optimization by Stephen Boyd and Lieven Vandenberghe provide a rigorous treatment of convex sets, convex functions, duality, optimality conditions, and numerical methods. The Stanford and MIT lecture videos embedded above can be used for guided review before attempting the advanced tasks.