Skip to content

Reading CMU 07-380 Lecture 5: Linear Programming, and Why the Optimum Sits at a Vertex of the Feasible Region

Sep 29, 20261 min
Home›learning
TL;DR07-380 Lec5 turns the Diet Problem from words into min cᵀx s.t. Ax ⪯ b, then draws it: each constraint is a half-plane, the cost is a direction, and cost contours are perpendicular to c. Push a contour in the −c direction until it last touches the feasible region and you always hit a vertex, so solvers only need the intersections of constraint boundaries. Vertex enumeration checks them all; simplex walks greedily from one vertex to a better neighbor.
#cmu#07-380#ai-course#course-guide#linear-programming#optimization
Series: Reading CMU 07-380 (7 / 15)
Reading CMU 07-380 HW2: Classical and Motion Planning, from Robot-Cook PDDL to RRT* to Graphing LPsReading CMU 07-380 Lecture 6: Integer Programming, Relax to an LP and Branch and Bound

🌏 中文版

This is Lecture 5 of CMU 07-380 AI & ML II, Fall 2026: Continuous Optimization: LP (9/9). The previous post on HW2 closed out the planning module. This lecture opens a new module, "Optimization."

In 07-280 Lecture 8 we learned gradient descent: a smooth objective, no constraints, follow the slope downhill. LP is the opposite case. The objective is linear, so its gradient is the same everywhere and never reaches zero. What decides the answer is a set of linear constraints. Walking downhill just takes you to the edge of the feasible region, and the question becomes: which point on that edge?

The short answer: if an LP has a finite optimum, the set of optimal points always includes at least one vertex. A solver only has to check the intersections of constraint boundaries, not the whole plane.

Everything here reflects the course site as of 2026-09-29. The site notes that the schedule is subject to change.

Official materials and what I read

Access level: all of the above downloads freely from outside CMU, so this lecture's materials reach A3 (defined in the global AI/CS course map). The site has no lecture recordings, and the Canvas checkpoint and Quiz 1 are CMU-only.

The starting question: from a word problem to solver input

The whole lecture runs on one Diet Problem. A restaurant sells two items, and the doctor sets three goals:

FoodCostCaloriesSugarCalcium
Stir-fry (per oz)1100320
Boba (per fl oz)0.550470

The goals are 2000 ≤ calories ≤ 2500, sugar ≤ 100 g, and calcium ≥ 700 mg. What is the cheapest way to eat?

The slides sum up the key idea as a pipeline: Problem description → LP formulation → LP Solver. The PR3 notes add that you should be able to move between three views of the same problem: words, the optimization form, and a picture when there are two variables.

Let x₁ be ounces of stir-fry and x₂ fluid ounces of boba. Calories have both a lower and an upper bound, so they give two inequalities. The two ≥ constraints get multiplied by −1 to become ≤. The result is inequality form:

min  cᵀx          c = [1, 0.5]ᵀ
s.t. Ax ⪯ b

A = [ -100  -50 ]    b = [ -2000 ]   calorie min
    [  100   50 ]        [  2500 ]   calorie max
    [    3    4 ]        [   100 ]   sugar
    [  -20  -70 ]        [  -700 ]   calcium

The notes point out that after flipping, the minus signs live inside the numbers in A and b; the formulation itself has none. Slide Polls 1 and 2 test exactly this. Add a nutrition constraint and the height of A and the length of b grow. Add a menu item and the lengths of x and c and the width of A grow.

The slides also list two other forms: general form (adds equality constraints and a constant d) and standard form (Ax = b, x ⪰ 0). The course convention is inequality form unless noted otherwise, and the forms are interchangeable.

The picture: constraints are half-planes, cost is a direction

The second half of PR3 builds one idea: the sign of a dot product tells you whether two vectors point roughly the same way or opposite ways. Two rules follow.

  1. Cost contours are perpendicular to c. cᵀx = 0 is the line through the origin perpendicular to c. cᵀx = 1, 2, … are parallel lines shifted in the direction of c. The slides ask how the spacing changes as c gets longer. It shrinks, because each step now changes the cost faster.
  2. a points into the infeasible side. aᵀx ≤ b is a half-plane. Stepping from the boundary in the direction of a increases aᵀx and breaks the constraint. b only shifts the boundary; a alone decides which side is infeasible.

Stack the four half-planes and their intersection is the feasible region, all points that satisfy every constraint. Minimizing cᵀx means sliding a line perpendicular to c in the −c direction. The last point (or edge) it touches before leaving the region is the answer.

The same picture explains the vertex result. When that line leaves the region, it touches either a corner or a whole edge, and the ends of an edge are corners too. The Desmos demo Cost with one constraint goes with slide Poll 5: does a minimizing LP with exactly one constraint always go to −∞? Drag it and you will see that when c points exactly opposite to a, the minimum sits on the boundary. Any other direction is unbounded.

Algorithms: only look at intersections

The key slide line is "Solutions are at feasible intersections of constraint boundaries!!" Two algorithms follow.

Vertex enumeration

  1. List every pairwise intersection of constraint boundaries. In 2-D, pick two rows of A and solve a 2×2 system; in N dimensions, pick N rows
  2. Keep only the intersections that satisfy every inequality
  3. Return the one with the lowest objective

Simplex (intuition only)

  • Start at a feasible intersection (if none is obvious, you can solve another LP to find one)
  • A "neighbor" swaps one row of the current subset for a row outside it; then check feasibility
  • Move to any neighbor with a lower objective; stop when there is none

The slides call this greedy local hill-climbing that nonetheless always finds the optimum for an LP. Interior point methods are marked out of scope, with only Figure 11.2 from Boyd shown.

flowchart LR
  A[Word problem] --> B["Inequality form<br/>min cᵀx s.t. Ax ⪯ b"]
  B --> C{Solve}
  C --> D["Vertex enumeration<br/>all intersections → keep feasible → take min"]
  C --> E["Simplex<br/>greedy walk to a better neighboring vertex"]
  C -.-> F["Interior point<br/>(out of scope)"]

A worked example you can redo: vertex enumeration on the Diet Problem

I computed this from the slide's A and b; it is not an official solution. Four constraints give six pairs:

PairIntersection (x₁, x₂)Feasible?Cost with c=[1,0.5]
calorie min × calorie maxparallel, none——
calorie min × sugar(12, 16)yes20
calorie min × calcium(17.5, 5)yes20
calorie max × sugar(20, 10)yes25
calorie max × calcium(23.33, 3.33)yes25
sugar × calcium(32.31, 0.77)no (too many calories)—

Two vertices tie. That is because c = [1, 0.5] is exactly 1/100 of the calorie row [100, 50]. The cost contours run parallel to the calorie-min boundary, so the whole edge from (12, 16) to (17.5, 5) is optimal. This matches Recitation Problem 2, part 4: an LP can have infinitely many optimal solutions when the cost vector is perpendicular to a constraint boundary. Vertex enumeration still returns the correct optimal value; it just reports one of the vertices.

The branch and bound example in the next lecture uses c = [1, 0.6]. With that cost, the unique optimal vertex is (17.5, 5), with cost 20.5.

Recitation and homework

  • Recitation Problem 1: given a picture of a feasible region, describe the two algorithms using vertices, intersections, and neighbors, then run simplex from point B and from point C. The solutions end at E and D, which are equally good. The lesson: where simplex stops depends on where it starts, but the optimal value does not
  • Cargo Plane: 4 cargoes × 3 compartments, 12 variables and 10 constraints, so A is a sparse 10×12 matrix. The solutions spell out the modeling assumptions, such as cargo being splittable and compartments being fillable. The orange-and-pineapple follow-up asks for a graph with cost contours; the answer is 9 boxes of oranges and 5 of pineapples for 105 gold pieces
  • HW2 written Q2 Bayes the Bat (8 pts), Q3 Graphing LPs (6 pts), and Q4 Feasible Regions (9 pts) all drill this lecture's modeling and graphing. See the HW2 guide
  • HW3 programming, Linear and Integer Programming, Q1–Q3 has you write the three steps of vertex enumeration: find intersections, filter feasible ones, pick the best. HW3 is due 10/1, and this series does not post solutions

Connections

  • LP fits naturally after 07-280 CSPs. The slides write a CSP as "any x that satisfies the constraints"; an LP picks the cheapest such x
  • The slides ask, next to the LP form, whether linear regression or neural-net training is an LP. Squared error is not a linear objective, and neural nets are further still. That is the line between LP and general optimization (fᵢ(x) ≤ 0)
  • The site also links the 15-281 Fall 2025 LP course notes as a second explanation

Things to do tonight

  1. Open LP: Constraint, drag b negative, and confirm that a still points into the shaded (infeasible) side.
  2. Compute the six intersections in the table with numpy, then change c to [1, 0.6] and see which vertex wins.
  3. Without the solutions, write out Cargo Plane's 12 variables and 10 constraints and check that A is 10×12.

Series navigation

References

Related

Reading CMU 07-380 Lecture 6: Integer Programming, Relax to an LP and Branch and Bound1 minCMU 07-380 Stage Recap: From Reasoning Under Certainty and Optimization to Uncertainty1 minReading CMU 07-380 HW2: Classical and Motion Planning, from Robot-Cook PDDL to RRT* to Graphing LPs1 min