Math317Fa26 Lec06 Duality
Watch on YouTube →
Overview
Steven Miller introduces linear programming duality, defining the dual of a canonical minimization problem and proving that any feasible dual value is a lower bound on any feasible primal value. He connects the idea of transforming a hard problem into a useful related one to prime factorization, derives why unitary matrices have eigenvalues of absolute value 1, and illustrates duality's practical value through Fourier transforms, approximation bounds, and a queens-and-pawns chess problem.
Key takeaways
- For a minimization LP with Ax = b and x ≥ 0, the dual maximizes yᵀb subject to yᵀA ≤ cᵀ, with y unrestricted; every dual-feasible value is a lower bound on every primal-feasible value.
- A primal-feasible solution and a dual-feasible solution whose objective values match certify primal optimality, while their difference gives an explicit optimality gap.
- A unitary matrix preserves the complex inner-product norm; applying this to an eigenvector proves every eigenvalue has absolute value 1.
- Duality can make a search smaller: the 5×5 queens-and-pawns formulation reduces a placement count from 25 choose 5 to 25 choose 3 by exchanging which pieces are placed and protected.
- Poisson summation can turn a slowly converging Gaussian sum into a rapidly decaying transformed sum, reducing the number of terms needed for a useful estimate.
- Optimization accuracy should be judged against the scale and purpose of the decision, and rigid, public thresholds can encourage people to evade detection just below the cutoff.
Chapters
- Miller reviews the canonical form: minimize cᵀx subject to Ax = b and x ≥ 0.
- An unrestricted variable can be represented as uⱼ − vⱼ with both parts nonnegative, though this may increase problem size.
- Inequalities become equalities by adding slack or excess variables, and maximization can be converted to minimization by negating c.
- For the canonical minimization problem, the dual maximizes yᵀb subject to yᵀA ≤ cᵀ.
- The dual variables y are unrestricted real numbers; Miller emphasizes that nonnegativity is not assumed.
- The shared A, b, and c connect the two problems, while the dual introduces a new set of variables.
- Miller contrasts a public product n = pq of two secret, roughly 200-digit primes with a secret random 5,000-digit password.
- A gatekeeper can verify a proposed factor by division without storing p or q, whereas checking the random password requires storing the password itself.
- The example illustrates how factoring is believed to be hard while multiplication and division are easy, motivating transformations to related problems that are easier to analyze.
- Miller defines an eigenpair by Av = λv and a unitary matrix U by UᴴU = UUᴴ = I, where ᴴ denotes conjugate transpose.
- For an eigenvector v, the quantity (Uv)ᴴ(Uv) equals vᴴv because U preserves length.
- Substituting Uv = λv gives |λ|²‖v‖² = ‖v‖²; since v is nonzero, every eigenvalue satisfies |λ| = 1.
- A feasible solution satisfies the constraints but need not be optimal; for an airline, a schedule with no flights is feasible but earns no revenue.
- Movie-theater schedules must respect capacity and operational constraints, while staggered start and end times can reduce staffing pressures.
- Warehouse leasing can reserve capacity, such as keeping 15% uncommitted for urgent clients while maintaining a target such as 60% committed.
- For primal-feasible x̂ and dual-feasible ŷ, Miller proves ŷᵀb ≤ cᵀx̂ by comparing ŷᵀAx̂ with cᵀx̂ and using Ax̂ = b.
- A dual-feasible value is a lower bound on the minimum primal value; a primal-feasible value is an upper bound.
- If feasible solutions have equal objective values, the primal solution is optimal, and a small gap between the two values quantifies how close a candidate is to optimal.
- Miller introduces the Fourier transform, defined by integrating f(x) against the oscillatory factor e^(−2πixy).
- Under sufficiently rapid decay of a function and its derivatives, Poisson summation equates the sum of f over integers with the sum of its Fourier transform over integers.
- For a Gaussian, the transform is another Gaussian with its scale parameter shifted; the transformed sum can decay rapidly enough that a few terms replace evaluating on the order of √n terms.
- Miller argues that acceptable error depends on scale: a $10,000 discrepancy can be negligible in a multimillion-dollar budget.
- A bank may not find it worthwhile to investigate a $12 disputed charge, while a $16,000 charge may justify an investigator.
- A publicly known hard cutoff, such as investigating only charges of $5,000 or more, can invite fraud just below the threshold.
- On small boards, rotations and reflections let the analysis assume a queen occupies a representative square, as in the 2×2 and 3×3 examples.
- On a 3×3 board, three queens cannot all occupy the center, so cases beginning at the center need not be analyzed separately.
- Eliminating redundant or impossible cases reduces the search while preserving coverage of all valid arrangements.
- Miller reframes the 5×5 puzzle of placing five queens so three pawns are safe as a related problem with three queens and five safe pawns.
- Without using symmetry, choosing five squares among 25 requires checking 25 choose 5 placements, while choosing three requires only 25 choose 3.
- Miller mentions a paper on how many pawns can be safely placed with n queens and recommends the Online Encyclopedia of Integer Sequences for investigating unfamiliar integer sequences.
Transcript excerpt
0:01 Welcome to math 317, operations research. Today is lecture six. We're going to be talking about dual problems, the chess problem, etc. Uh the t-shirt or shirt I'm wearing today has a quote, "Absolutely nothing happened in sector 83 by 9 by 12 today. Cultural extra credit to find out what this is from. You are not allowed to do any web searching or have anybody do any web searching for you. You are welcome to talk to people." And the hint from conversations before class began is that it's probably related to something science fiction. I will be sharing eventually the story behind this. It's a great example of operations research solving the right problem as efficiently as possible. Too many times people are concerned with I have to do something in
0:49 a certain way. No, you have to solve a problem. Frequently there is yes a natural approach to solve it but sometimes there is a better way and so we will talk about stuff like that throughout the semester depending on how comfortable I am with you. I may give you some examples from the real world where you can use stuff like this. All right so let's just review where we were. So definition 4.3.1 the canonical linear programming problem. It's very useful to be able to take anything that I'm given and put it into a standard form and then I know that it's going to be formulated correctly for the crank I'm going to put it through to solve. This is not saying that this is necessarily the best way to do it. But this is at least a way that's going to work. I can assume that my variables are non- negative. That was really easy. If
1:38 they're not non- negative, I can just
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Steven Miller.