The segment between two feasible points is feasible — one line of argument per inequality — and a linear objective is affine along that segment, which means its first differences are constant. Put the two together and a feasible point with no improving feasible direction cannot be beaten anywhere at all. That is a global conclusion from a local check, and it is the licence an algorithm needs in order to stop.
Core ideas
Two short arguments and one conclusion. The conclusion is what “The Simplex Method” spends its time cashing in.
If a·x ≤ b and a·y ≤ b, then along the segment the left-hand side is a weighted average of two numbers that are both at most b, so it is at most b. Every row survives independently, so the whole set does — and the sign restrictions are rows, so they survive too.
c·(x + t(y − x)) is c·x + t(c·y − c·x), which is a straight line in t. Sample it at equal steps and the first differences are equal: there is no bump in the middle of a segment for a better point to hide in.
Suppose x is feasible and no feasible direction from x improves the objective. For any feasible y, the whole segment from x to y is feasible, and the objective along it changes at a constant rate; if y were better, the rate would be an improvement and the segment an improving feasible direction. So no such y exists.
The material
The two arguments, the sampled first differences that show the second one, and what goes wrong on a set that is not convex.
A set S is convex when for every x and y in S and every t with 0 ≤ t ≤ 1, the point x + t(y − x) is also in S. That point traces the segment from x at t = 0 to y at t = 1.
The definition is about every pair of points in the set, so it says nothing at all until both ends are in it — which is why the lab refuses to answer the question while one of the two chosen points lies outside.
Let S be the set of points satisfying finitely many linear inequalities aᵏ·x ≤ bᵏ, including the sign restrictions. Then S is convex.
Take x and y in S and t with 0 ≤ t ≤ 1, and write z = x + t(y − x). For any one row, aᵏ·z = aᵏ·x + t(aᵏ·y − aᵏ·x) = (1 − t)(aᵏ·x) + t(aᵏ·y).
Both 1 − t and t are at or above zero, and both aᵏ·x and aᵏ·y are at most bᵏ, so aᵏ·z ≤ (1 − t)bᵏ + t bᵏ = bᵏ. The row holds at z.
The argument used nothing about the other rows, so it applies to each of them separately, and z satisfies all of them at once. An equality row is the same argument run twice, and a sign restriction is a row like any other.
□
Take the region x + y ≤ 8, x ≤ 5, y ≤ 6 with both variables at or above zero, the objective 3x + 2y, and the two points (1, 1) and (5, 3). Sampling the objective at eight equal steps along the segment gives 5, 7, 9, 11, 13, 15, 17, 19, 21: a first difference of exactly 2, eight times over. That constant is what affine means, and it is computed over exact fractions of the way along rather than measured off a graph.
Let S be convex, let c·x be linear, and let p be a point of S such that for every q in S no movement from p towards q improves the objective. Then c·p is at least as good as c·q for every q in S: p is optimal, globally.
The proof is one line given the two facts above. For any q, the segment from p to q lies in S and the objective is affine along it, so if c·q were better than c·p the objective would improve immediately on leaving p in that direction — a direction that was assumed not to improve.
This is the result an algorithm needs, and it is worth being precise about what it replaces. The corner point theorem says an optimum can be found at a corner. That is a statement about where to look. It says nothing whatever about the corner you happen to be standing on, and an algorithm that stops needs to know about that one. Convexity plus a linear objective is what licenses stopping, and the distinction becomes urgent the moment there are too many corners to visit.
Replace the polyhedron with two blocks and a gap: one with x between 0 and 3, one with x between 5 and 8, both with y between 0 and 6. Every point of each block is feasible and the union is not convex, because a segment can leave it.
From (1, 1) in the western block to (5, 3) on the edge of the eastern one, the segment lies inside the western block for t from 0 to 1/2 and then leaves the set entirely, touching the eastern block again only at t = 1. Three of the nine sampled points are outside. Meanwhile the best corner of the western block is (3, 6), worth 21, and no step inside that block improves on it — while (8, 6) in the eastern block is worth 36. A purely local check at (3, 6) proves nothing at all.
Notice what did and did not survive. The objective is still linear, and along any segment it is still affine: the first differences are constant whether or not the segment stays in the set. What failed is the first fact, and losing it is enough to make a local optimum a local optimum and nothing more.
Whether a segment stays inside is decided rather than sampled. For one block, a·(p + t(q − p)) ≤ c is a single linear inequality in t, so the whole family of rows collapses to one interval of t; the segment lies in that block exactly on that interval. Two blocks give two intervals, and whether they cover all of t from 0 to 1 is a question with an exact answer — here they do not, and the gap opens at t = 1/2.
That is the end of the modelling course, and the hand-over is precise. A corner is an algebraic object; there are at most C(n + m, m) of them; and a corner with no improving feasible direction is optimal everywhere. An algorithm that walks from corner to adjacent corner, improving each time, may therefore stop when no improving direction remains — and that algorithm is “The Simplex Method”.
Interactive
No improving direction proves global optimality only when the set is convex
Method
Two arguments and one conclusion, in an order that makes the conclusion one line.
aᵏ·z = (1 − t)(aᵏ·x) + t(aᵏ·y) with both weights at or above zero. A weighted average of two numbers at most bᵏ is at most bᵏ. That is the whole argument for one row.
Nothing in the step used any other row, so it holds for each of them separately and therefore for all of them at once. Sign restrictions included: they are rows.
Evaluate c·(x + t(y − x)) at equal fractions and take first differences. They are equal, exactly, and a difference that is nearly equal would be a bug in the arithmetic rather than a fact about the geometry.
No improving feasible direction implies optimal everywhere. It is not the corner point theorem, which says only that some optimum sits at a corner and nothing about the one you are standing on.
The same two points and the same objective in both settings. The objective behaves identically; the set does not.
The first differences are +2 in both settings, because affineness is a fact about the objective and not about the set. What changes is whether the segment is available as evidence: in the convex set it connects any two feasible points, so a local check at one of them speaks about the other, and in the union it does not.
For a faded rehearsal, keep the union and move the second point to (2, 4), inside the western block. The supplied first move is which block each end lies in: both are in the west, so the segment never has to cross the gap. Predict whether the whole segment stays inside, what the first differences are, and whether (3, 6) can still be beaten — and then say which of the two facts of this lesson your prediction used.
You should be able to show a polyhedron is convex, show a linear objective is affine along a segment by its constant first differences, state the stopping principle that follows, and say which of the two facts fails on a set that is not convex.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.