Corner-Point Method

Proof of the Corner Point Theorem.

Let $R$ be the feasible region, a convex polygon (possibly unbounded) formed by the intersection of finitely many half-planes. Let $Z = ax + by$ be the objective function. Assume that $Z$ attains an optimal value (say a maximum) at some point $P$ in $R$. We must show that there exists a corner point of $R$ where $Z$ takes the same optimal value.

Case 1: $P$ is already a corner point. Then the conclusion is immediate — the optimal value occurs at a corner point.

Case 2: $P$ lies on an edge (boundary line segment) of $R$ but is not a corner. Let the edge be the line segment joining two corner points $A$ and $B$ of $R$. Since $P$ lies on this edge, we can write $P$ as a convex combination of $A$ and $B$:

$P = \lambda A + (1-\lambda)B \quad \text{for some } \lambda \in [0,1].$

Because $Z$ is linear, we have:

$Z(P) = Z(\lambda A + (1-\lambda)B) = \lambda Z(A) + (1-\lambda)Z(B).$

This is a weighted average of $Z(A)$ and $Z(B)$. Since $Z(P)$ is the maximum value, it must be at least as large as both $Z(A)$ and $Z(B)$. But a weighted average of two numbers can equal the maximum only if both numbers equal that maximum. Therefore:

$Z(A) = Z(B) = Z(P).$

Hence both corner points $A$ and $B$ also give the same optimal value.

Case 3: $P$ lies in the interior of $R$ (not on any edge). Since $R$ is a convex polygon, any interior point can be expressed as a convex combination of the corner points. Let the corner points of $R$ be $C_1, C_2, \dots, C_k$. Then there exist nonnegative weights $\lambda_1, \lambda_2, \dots, \lambda_k$ with $\sum_{i=1}^k \lambda_i = 1$ such that:

$P = \sum_{i=1}^k \lambda_i C_i.$

By linearity of $Z$:

$Z(P) = \sum_{i=1}^k \lambda_i Z(C_i).$

This is a convex combination (weighted average) of the values $Z(C_1), Z(C_2), \dots, Z(C_k)$. Since $Z(P)$ is the maximum, it must be at least as large as each $Z(C_i)$. A convex combination of numbers can equal the maximum only if every term in the combination equals that maximum. Therefore:

$Z(C_1) = Z(C_2) = \dots = Z(C_k) = Z(P).$

Thus every corner point attains the same optimal value.

…

We prove part (i) first. Let $R$ be a bounded convex polygon in the plane — the feasible region of a linear programming problem. Since $R$ is bounded, it can be enclosed in some sufficiently large circle. The objective function $Z = ax + by$ is a linear function of two variables.

Step 1: Existence of extreme values. Because $R$ is closed (it includes its boundary) and bounded, it is a compact set in $\mathbb{R}^2$. A linear function is continuous on $\mathbb{R}^2$, and a continuous function on a compact set always attains both a maximum and a minimum value. So $Z$ definitely has a maximum $M$ and a minimum $m$ on $R$.

Step 2: The level lines of $Z$. For any constant $c$, the equation $ax + by = c$ represents a straight line — a level line of $Z$. All level lines are parallel to each other (they have the same slope $-\frac{a}{b}$, provided $b \neq 0$). As $c$ increases, the line shifts in the direction of the gradient vector $(a, b)$; as $c$ decreases, it shifts opposite to the gradient.

Step 3: Locating the optimum. Suppose the maximum value $M$ is attained at some point $P$ inside $R$ (not on the boundary). Draw the level line through $P$: $ax + by = M$. Since $P$ is interior, there is a small neighbourhood around $P$ that lies entirely inside $R$. Move the level line slightly in the direction of the gradient — this gives a line $ax + by = M + \epsilon$ for some small $\epsilon > 0$. Because $P$ is interior, part of this new line still lies inside $R$, meaning there are points in $R$ where $Z$ takes the value $M + \epsilon > M$. This contradicts the assumption that $M$ is the maximum. Therefore, the maximum cannot occur at an interior point — it must occur on the boundary of $R$.

Step 4: The boundary is a polygon. The feasible region $R$ is defined by linear inequalities, so its boundary consists of straight line segments (edges) that meet at corner points (vertices). The boundary is a convex polygon.

Step 5: On an edge, $Z$ is linear. Consider any edge of $R$ lying on the line $px + qy = r$ (one of the constraint boundaries). On this edge, the objective function $Z = ax + by$ is a linear function of one variable (say $x$, since $y$ is determined by $x$ through the edge equation). A linear function on a closed interval attains its maximum and minimum at the endpoints of that interval — the endpoints of the edge are precisely the corner points of $R$.

Step 6: Conclusion for bounded $R$. Since the maximum of $Z$ on $R$ must occur on the boundary, and on each edge the maximum occurs at an endpoint (a corner point), the overall maximum on $R$ must occur at some corner point. The same argument applies to the minimum. This proves part (i).

Step 7: Unbounded $R$. If $R$ is unbounded, the region extends infinitely in at least one direction. Consider the level lines of $Z$. If moving the level line in the direction of increasing $Z$ always keeps part of the line inside $R$ (because $R$ extends infinitely in that direction), then $Z$ can be made arbitrarily large — no maximum exists. Similarly, if moving opposite to the gradient always keeps part of the line inside $R$, no minimum exists.

…