FOLLOW AN IDEA
Optimization and Operations Research
Explore objectives and convexity; algorithms and constraints; discrete decisions and multiple objectives. Concepts and connections are available independently of video coverage.
Prerequisites and connections
Gradient
In Euclidean coordinates, partial derivatives form a vector describing directional change.
Video explanations to be added
Objectives and convexity
Optimization
Derivatives help identify candidate extrema; endpoints, domain restrictions and the distinction between local and global extrema must also be checked.
1 reviewed resourcesConvex sets
Every segment joining two points of a convex set stays inside the set.
Video explanations to be addedConvex functions
A convex function lies below chords connecting points on its graph.
Video explanations to be addedConvex optimization
Minimizing a convex function on a convex feasible set makes local minima global.
Video explanations to be added
Algorithms and constraints
Gradient descent
Iterates move opposite the gradient; step-size and smoothness conditions control convergence.
Video explanations to be addedNewton optimization
Gradient and Hessian information form a local quadratic step, often with globalization safeguards.
Video explanations to be addedLinear programming model
Maximise or minimise a linear objective subject to linear inequalities, the workhorse of allocation problems.
5 reviewed resourcesSimplex method
Move vertex to vertex along the feasible polytope, each step improving the objective until no improving edge remains.
1 reviewed resourcesNonlinear programming and KKT conditions
For smooth nonlinear models, optimality requires stationarity, primal and dual feasibility and complementary slackness.
1 reviewed resourcesDuality and shadow price
Every linear program has a dual; the dual value of a binding constraint is the marginal worth of relaxing it.
1 reviewed resources
Discrete decisions and multiple objectives
Integer programming
Force some variables to be whole numbers or binary, which models choosing, counting and sequencing decisions.
1 reviewed resourcesBranch and bound
Solve relaxed linear problems, branch on fractional integers and prune nodes whose bound cannot beat the incumbent.
1 reviewed resourcesDynamic programming recursions
Split a sequential decision into stages and store subproblem values so each is computed once.
Video explanations to be addedNetwork flow models
Maximise flow through capacities; the min-cut theorem turns a bottleneck argument into a computable bound.
1 reviewed resourcesMulti-objective optimization and Pareto front
Trade off competing objectives; the Pareto front collects solutions that no longer can be improved on one goal without hurting another.
3 reviewed resources