Problem-solving recipes
A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.
What are you being asked to do?
Start with what you're actually holding.
Given a word problem, no equations written yet — the modeling recipe turns the paragraph into decision variables, an objective, and a constraint list, ready to classify and solve.
Minimizing a function you can't (or don't want to) differentiate — one variable with a bracket already trapping the minimum, golden-section search; the same setup but with a fixed number of iterations decided in advance, Fibonacci search; three known bracket points and a function that looks parabola-shaped near its minimum, quadratic-fit search; several variables, no bracket, only function values to compare, Nelder-Mead.
Already have a descent direction, need a step size — backtracking line search.
An equality-constrained problem, solved by hand with a Lagrange multiplier — the equality-constrained recipe for one constraint; a second constraint active at the same time extends it.
A constrained nonlinear problem, need a candidate point verified (or found) by hand — the KKT recipe.
Solving a linear program by hand — the simplex pivot recipe if an all-slack starting basic feasible solution is available; when a \ge or = constraint rules that starting basis out, the Big-M recipe if that's the only method taught so far, or the artificial-variables recipe once two-phase simplex is also available and either route will do.
Need the dual of an LP you already have in \min\ c^\top x form — the dual-construction recipe.
Given a finite point set, need to know which points are the convex hull's real corners — the convex-hull recipe; asking instead whether one specific point is reachable as a nonnegative combination of some generating vectors is the separate conic-hull-membership recipe.
A trust-region method, but the problem has a constraint too — the constrained trust-region step recipe, for deciding whether the ball or the linearized constraint caps the step and computing it either way.
Need a directional derivative, or want to confirm the gradient really is the steepest direction at a point — the directional-derivative recipe.
Know an LP's optimal vertex, need the range one number can move through before it stops being optimal — the cost-coefficient recipe for a cost, or its extension for a resource (right-hand-side) value too.
An LP relaxation's optimum is fractional and rounding can't be trusted — branch and bound.
A constrained nonlinear problem, want to reuse an unconstrained solver instead of building a constrained one from scratch — penalty as the simplest version; the method of multipliers once penalty's growing \rho makes subproblems too stiff; a log barrier when every iterate must stay strictly feasible along the way, with the primal-dual Newton step as one advance along that barrier's central path.
Running gradient descent with per-parameter adaptive step sizes — the Adam update step. Searching with no gradient at all, trying to escape local minima — simulated annealing (one point), a genetic algorithm (a population), or particle swarm (a swarm pulled toward personal and global bests) — pick by what you're already tracking.
Comparing feasible designs on more than one objective, or sizing a decision against a probabilistic guarantee — Pareto dominance or chance-constrained capacity, both in the multiobjective/robust chapter.
Need to know whether a multivariable function is convex, not just classify one critical point — the Hessian-convexity recipe: compute H, check it's positive semidefinite everywhere, and conclude.
Have the gradient and the true Hessian at the current point — Newton's method's own step. Have the gradient but no true Hessian, only an inverse-Hessian approximation built from past gradients — a BFGS update step instead.
Want directions better than plain steepest descent without ever forming a Hessian — conjugate gradient (uses the gradient/residual), coordinate descent (updates one variable at a time, no derivative at all), or Powell's method (builds conjugate-style directions from function values alone, no derivative either).
Have one side of an LP's optimal solution and need the other, without solving a second LP — the complementary-slackness recovery recipe.
Working with gradients and directional derivatives
Running a second-order unconstrained-optimization step
Run one step of Newton's method for optimization
Use when: you have a differentiable f with its gradient and Hessian available at the current iterate x^{(k)}
Goal: the next iterate x^{(k+1)}, and eventually a stationary point once the stopping check passes
Newton's method for optimization
Needs the true Hessian at the current point.
Run one BFGS update step
Use when: you're minimizing f with a current point x^{(k)}, its gradient g_k, and an inverse-Hessian approximation B_k — no true Hessian computed
Goal: the next point x^{(k+1)} and an updated approximation B_{k+1} that matches the curvature just observed
Quasi-Newton methods: DFP and BFGS
Approximates the inverse Hessian from gradients alone — no true Hessian needed.
Finding a minimum without a derivative
Run golden-section search on a bracket
Use when: you have a unimodal f and a valid bracket [a,b], and want its minimum to a stated tolerance without ever differentiating f
Goal: a bracket narrower than the required tolerance, guaranteed to trap the minimum
Golden-section search
One variable — needs a bracket that already traps the minimum.
Run Fibonacci search on a bracket
Use when: you have a unimodal f, a valid bracket [a,b], and a FIXED number of iterations n decided in advance, rather than an open-ended tolerance
Goal: the narrowest possible bracket achievable in exactly n function evaluations — the best any comparison-only method can guarantee for that budget
Fibonacci search
Same bracket, but the number of iterations is fixed in advance — a schedule tuned to that exact budget beats golden-section's fixed ratio.
Run quadratic-fit search on three bracket points
Use when: you have three points x_1<x_2<x_3 with known values f_1,f_2,f_3 from a bracket that traps the minimum, and want to exploit HOW MUCH lower one point is instead of only comparing which is smaller
Goal: a new candidate minimizer at the fitted parabola's vertex, replacing one of the three points for the next fit
Quadratic-fit search
Trades comparison-only safety for speed by fitting a parabola through three points — pair with golden-section as a fallback when the fit lands outside the bracket.
Run one Nelder-Mead iteration
Use when: you have three (or, in general, n+1) trial points and only function VALUES to compare, no derivative available at all
Goal: a new simplex, no worse than the old one, that has crept toward the minimum
Pattern search and Nelder-Mead
Several variables — compares function values across a simplex, no bracket needed.
Running an alternative descent method without a full Hessian
Run conjugate gradient descent
Use when: you're minimizing a quadratic f(x)=\tfrac12x^\top Ax-b^\top x (or applying the same update rules to a general nonlinear f) and want directions that never undo an earlier step's progress
Goal: a sequence of iterates that reaches the exact minimizer in at most n steps on a quadratic, using only gradient (residual) evaluations
Conjugate gradient descent
Uses the gradient (residual) to build directions that never undo an earlier step's progress.
Run one cycle of coordinate descent
Use when: you're minimizing a multivariable function by updating one variable at a time, holding the others fixed
Goal: an updated point after every coordinate has been minimized once, plus a check for whether that's already the exact minimizer
Coordinate descent
No derivative at all — minimizes one variable at a time, cycling through them.
Run one cycle of Powell's method
Use when: you're minimizing a function using only function values, no gradient, and already have a set of n search directions to cycle through (initially the coordinate axes)
Goal: an updated point plus an updated, more effective direction set to start the next cycle from
Powell's method
Also no derivative — builds conjugate-style directions from function values alone.
Choosing a step size along a descent direction
Solving an equality-constrained problem with Lagrange multipliers
Solve a Lagrange multiplier problem with two constraints active at once
Use when: two equality constraints, or two inequality constraints both active at the candidate point, must hold at the same time, so one multiplier can't account for \nabla f alone
Goal: a candidate point solving the full stationarity system for both multipliers, checked against both constraints and (for an inequality constraint) checked for a nonnegative multiplier
Two constraints at once, revisited
Extends the recipe above to two constraints active at once.
Working with convex and conic hulls
Find the convex hull of a finite point set
Use when: you have finitely many points in \mathbb R^n and need to know which ones are genuine vertices of the hull versus which are redundant
Goal: the subset of points that are actual vertices of \operatorname{conv}(S), with every other point identified as a convex combination of them
The convex hull and conic hull
Which of a finite set of points are genuine hull vertices.
Check whether a point lies in a conic hull
Use when: you have finitely many generating vectors and a target point, and want to know whether the target is some nonnegative combination of the generators
Goal: explicit weights \lambda_i\ge0 exhibiting the target as \sum\lambda_ix_i, or confirmation that none exist
The convex hull and conic hull
A related but different question — is one target point a nonnegative combination of given generators.
Checking whether a function is convex
Verify convexity of a multivariable function via its Hessian
Use when: you have a twice continuously differentiable f on a convex domain S and need to know whether f is convex on S, not just classify one critical point
Goal: a convex / not-convex / convex-only-on-a-sub-region verdict for the whole domain, from one Hessian computation
The second-order (Hessian) characterization of convexity
Compute the Hessian, confirm it's positive semidefinite at every point of the domain, and conclude.
Solving a linear program by hand
Run the simplex method to completion
Use when: you have a maximize-form LP already in canonical form (every constraint reduced to an equation with a slack variable) and an all-slack starting basic feasible solution
Goal: the optimal basic feasible solution and objective value, reached by walking from vertex to adjacent vertex
The simplex method: the ratio test and pivoting · extended later in this course
Needs an all-slack starting basic feasible solution.
Solve an LP with the Big-M method
Use when: a standard-form LP has at least one \ge or = constraint with no natural starting slack, and you want to solve it directly in one penalized simplex run
Goal: the optimal solution of the original LP, or a certificate (a positive artificial) that none exists
The Big-M method
A \ge or = constraint rules out that starting basis — Big-M only, the first method this course teaches for it.
Solve an LP that needs artificial variables
Use when: a standard-form LP has at least one \ge or = constraint, so the all-slack starting basis isn't available
Goal: the optimal solution of the original LP, or a certificate that none exists
Two-phase simplex
Once two-phase simplex is also available, covers both Big-M and two-phase as alternate routes for the same \ge/= situation.
Recovering one LP solution from the other
Finding how far one LP coefficient can move
Find the allowable range for one LP coefficient, cost or resource
Use when: you know an LP's optimal vertex and need the exact interval ONE cost coefficient, or ONE resource (right-hand-side) value, can move through before today's optimal vertex changes
Goal: the exact interval that coefficient or resource level can move through while today's optimal vertex -- and its shadow price -- stays valid
Sensitivity to resource changes
Extends the recipe above to cover a resource (right-hand-side) value too.
Solving an integer program exactly
Handling constraints by solving a sequence of unconstrained problems
Run the method of multipliers
Use when: plain penalty's growing ρ is making subproblems too stiff to solve reliably, and the constraint is (or can be turned into) an equality
Goal: a multiplier estimate that converges to the true one, at a fixed, modest ρ
The augmented Lagrangian method
Use once penalty's growing ρ makes subproblems too stiff to solve reliably.
Solve a constrained problem with a log barrier
Use when: you have inequality constraints, a strictly feasible starting point is available, and you want every iterate to stay feasible along the way
Goal: a central path of strictly feasible points converging to the constrained optimum as μ shrinks
Barrier methods and the central path
Use when every iterate must stay strictly feasible along the way.
Take one primal-dual interior-point step
Use when: you already have a strictly feasible point and want to advance the central path without fully re-solving a barrier subproblem from scratch
Goal: an updated (x, λ) pair, closer to the KKT solution, at a lower cost than Section 4's full resolve
Interior-point methods
One step along the central path, once the barrier method above is already running.
Adaptive gradient-based optimization
Searching without a gradient (metaheuristics)
Run one simulated annealing iteration
Use when: you have a current point x, its value f(x), a temperature T, and a candidate neighbor x' to consider
Goal: the next current point and the cooled temperature to carry into the next iteration
Simulated annealing
One point at a time, accepting occasional uphill moves.
Run one genetic algorithm generation
Use when: you have a population of candidate points, each with a known f-value, and are minimizing f
Goal: the next generation's population, with its best-found value no worse than this generation's
Genetic algorithms
A population evolved by selection, crossover, and mutation.
Update one particle's velocity and position
Use when: you know a particle's current position x, velocity v, its own personal best p, and the swarm's global best g
Goal: the particle's new velocity and position for the next iteration
Particle swarm optimization
A swarm of particles pulled toward personal and global bests.
Comparing designs and sizing under uncertainty
Score designs by weighted sum and confirm the winner
Use when: you have several feasible designs' objective values and a stated preference between the objectives
Goal: the weighted-sum winner, confirmed to be genuinely Pareto-optimal
The weighted-sum method and its blind spot
A stated preference between the objectives, expressed as weights.
Rank designs by goal programming
Use when: you have a stated target for each objective, instead of a preference between the objectives themselves
Goal: every design's total weighted deviation from its stated goals, ranked smallest to largest
Goal programming
A stated target for each objective, instead of a preference between them.
Compute VaR and CVaR from a loss table
Use when: you have a discrete loss table (outcomes and their probabilities) and a risk level \alpha
Goal: the value-at-risk threshold and the conditional value-at-risk that follows it
Value-at-risk and conditional value-at-risk
Extends the chance-constrained capacity idea to a discrete loss table and its worst-tail severity.
Compute the price of robustness
Use when: you have a nominal design and either an uncertainty radius or a cost budget, and need what protection actually costs
Goal: the robust cost at a given radius, or the radius a given cost budget affords
How much does robustness cost?
What the robust or chance-constrained capacity above actually costs, at a radius or a budget.