Optimisation Methods — Exam Cheat Sheet

3 Chapters
1Conjugate Gradient Method
Building Q and b from f(x)
xᵢ²coefficient × 2 → diagonal Q[i][i]
xᵢxⱼcoefficient stays → Q[i][j] AND Q[j][i]
−cxᵢflip sign → b[i]
Always verify Q is SPD: Q=Qᵀ and all eigenvalues > 0
Algorithm (7 steps)
  1. Set k=0, choose x⁽⁰⁾
  2. g⁽⁰⁾ = Qx⁽⁰⁾ − b. If g=0 stop. Set d⁽⁰⁾ = −g⁽⁰⁾
  3. αₖ = −(g⁽ᵏ⁾ᵀd⁽ᵏ⁾) / (d⁽ᵏ⁾ᵀQd⁽ᵏ⁾)
  4. x⁽ᵏ⁺¹⁾ = x⁽ᵏ⁾ + αₖd⁽ᵏ⁾
  5. g⁽ᵏ⁺¹⁾ = Qx⁽ᵏ⁺¹⁾ − b. If g=0 stop.
  6. βₖ = (g⁽ᵏ⁺¹⁾ᵀQd⁽ᵏ⁾) / (d⁽ᵏ⁾ᵀQd⁽ᵏ⁾)
  7. d⁽ᵏ⁺¹⁾ = −g⁽ᵏ⁺¹⁾ + βₖd⁽ᵏ⁾ → go to step 3
Calculator hack (Casio 991ES Plus)
MatAQ — never overwrite!
MatBx⁽ᵏ⁾ — update each iteration
MatCb — never overwrite!
g: MatA×MatB−MatC = (write down!) Qd: load d into MatB → MatA×MatB = dot products: type manually (a×c)+(b×d)
Key facts
✓n variables → solves in exactly n steps
✓Compute Qd⁽ᵏ⁾ ONCE — reuse for both α and β (same denominator!)
✗Never round α early — keep 4 decimal places minimum
✗Don't forget the − sign in the α formula
2Linear Programming
Two standard forms
CanonicalStandard
GoalMaximizeMinimize
ConstraintsAll ≤All =
Variables≥ 0≥ 0, RHS ≥ 0
Conversion rules
Min→Maxmultiply objective by −1
≥ → ≤multiply constraint by −1
= → ≤split into two: ≤ b AND −≤ −b
≤ → =add slack variable +s
≥ → =subtract surplus variable −s
neg RHSmultiply whole constraint by −1 (watch: flips inequality!)
Graphical solution (2 variables only)
  1. Identify x₁, x₂ (decision variables)
  2. Build table: rows=resources, cols=variables
  3. Write LP: objective + constraints
  4. Find x-intercepts: set x₂=0 then x₁=0 for each constraint
  5. Find intersection: solve constraint pair simultaneously
  6. Test ALL corners against ALL constraints (feasibility check)
  7. Evaluate z at every feasible corner
  8. Pick max/min → optimal solution
Never just check the intersection point! Always test ALL feasible corners — optimal can be anywhere.
Word problem → table template
x₁x₂...Limit
Resource 1a₁₁a₁₂≤/≥ b₁
Resource 2a₂₁a₂₂≤/≥ b₂
Objectivec₁c₂Max/Min
tipRows = constraints (limits). Columns = decisions (what you control). Last row = objective coefficients.
3The Simplex Method
Table structure (what goes where)
SectionContent
Top c rowObjective coefficients (slacks = 0)
Basis colCurrent basic variables
c colObj coeff of current basis vars
z colRHS values (b values)
BodyConstraint coefficients
θ colz÷entering col (only if col > 0)
zⱼ−cⱼ rowOptimality check (all ≤ 0 = optimal)
At start with slack basis: zⱼ−cⱼ = just flip sign of top c row!
Each iteration (4 decisions)
ENTERcolumn with max zⱼ−cⱼ > 0
LEAVErow with min θ (skip if col ≤ 0)
PIVOTelement at their intersection
STOPwhen ALL zⱼ−cⱼ ≤ 0
Row operations
Rule 1 (pivot row): new = old ÷ pivot element Rule 2 (other rows): new = old − (col value × new pivot row) Rule 3 (zⱼ−cⱼ row): same as Rule 2
Setup checklist
Min?Already correct for Simplex
Max?Multiply objective by −1 first
≤ constraintsadd slack +s (cost=0)
≥ constraintssubtract surplus −s, add artificial variable for basis
= constraintsadd artificial variable only
Reading the optimal solution
in basisxⱼ = z column value of its row
not in basisxⱼ = 0
z valuez column of zⱼ−cⱼ row (flip sign if was Max problem!)
Artificial variables (Big-M / Phase I): must equal 0 at optimum. If any artificial > 0 in final basis → problem is infeasible.
! Common exam mistakes to avoid
CGForgetting − sign in αₖ formula
CGRounding too early — keep 4+ decimal places
CGRecomputing Qd⁽ᵏ⁾ separately for α and β — compute once, reuse!
LPFlipping sign of b when multiplying ≥ by −1 — b flips too!
LPOnly checking intersection corner for optimum — check ALL feasible corners
LPForgetting = constraints stay as = in Standard Form (no slack/surplus needed)
SXComputing θ for negative or zero column values — skip those rows!
SXDeclaring optimal before checking EVERY zⱼ−cⱼ value
SXForgetting to flip z sign when reading answer for a Max problem
SXSlack variables always have cost 0 in objective — never forget this!