Corner Point Theorem

Optimization · Axiom Academy

Understanding the fundamental theorem that makes linear programming tractable The feasible region of a linear program is bounded by linear constraints, forming a convex polytope. The vertices (or corner points ) are where constraint boundaries intersect. These special points are defined as locations where multiple constraints are satisfied with equality. In 2D, a vertex occurs where two constraint lines meet. In higher dimensions, a vertex requires as many linearly independent constraints as there are variables. Linear objective functions have a crucial property: they achieve their extreme values (maximum or minimum) at the boundary of the feasible region, never in the interior. Even more specifically, among all boundary points, the extreme values occur at vertices. This is because the level curves (isocost/isoprofit lines) of a linear function are parallel straight lines. As we move these lines in the direction of optimization, the last point they touch in the feasible region is always a corner. 3. The Fundamental Theorem of Linear Programming The Corner Point Theorem states: If a linear programming problem has an optimal solution, then at least one optimal solution occurs at a vertex of the feasible region.

This is the written version of the interactive lesson above. See the full Optimization course.