Vertex optimality
Vertex Optimality
In linear programming, when an optimal solution exists, we can usually find one at a vertex of the feasible region.
This is the key geometric reason the graphical method works.
Vertex
A vertex is a corner point of the feasible region.
In two dimensions, it is usually formed by the intersection of two active boundary lines.
Example:
\[x_1+2x_2=10\] \[2x_1+x_2=16\]Solving gives:
\[\left(\frac{22}{3},\frac{4}{3}\right)\]If this point satisfies all constraints, it is a vertex of the feasible region.
Active Constraints
A constraint is active at a point if it holds with equality.
For example, at:
\[x^*=\left(\frac{22}{3},\frac{4}{3}\right)\]we have:
\[x_1+2x_2=10\]and:
\[2x_1+x_2=16\]So these two constraints are active.
Why Vertices Matter
A linear objective has straight contour lines:
\[c^Tx=k\]As we slide the contour line, the last point of contact with a polygon is usually a vertex.
If the last contact is not a single vertex, it is an edge whose endpoints are vertices.
So at least one vertex is still optimal.
Practical Rule
For a two-variable LP with a bounded feasible polygon:
- find all vertices
- compute the objective value at each vertex
- choose the best value
This always works when the feasible region is nonempty and bounded.
Example
Suppose the vertices of a feasible region are:
\[(0,0),\quad (0,3),\quad (2,4),\quad (5,1),\quad (6,0)\]and the objective is:
\[\max 3x_1+x_2\]Compute:
| Vertex | Objective value |
|---|---|
| $(0,0)$ | $0$ |
| $(0,3)$ | $3$ |
| $(2,4)$ | $10$ |
| $(5,1)$ | $16$ |
| $(6,0)$ | $18$ |
The best vertex is:
\[(6,0)\]with value:
\[18\]Edge Optimum
Sometimes the objective line is parallel to an edge.
Then every point on that edge has the same objective value.
The optimum is not unique.
But the endpoints of that edge are vertices, so optimal vertices still exist.
Connection to Basic Feasible Solutions
In standard form, vertices correspond to basic feasible solutions.
This is why simplex can solve LP problems by moving from one basic feasible solution to another.
Graphically:
\[\text{vertex}\quad \leftrightarrow \quad \text{basic feasible solution}\]Local and Global Optimality
For linear programming, local optimality implies global optimality.
The feasible region is convex and the objective function is linear.
So there are no hidden curved valleys or isolated local optima.
Limitations
Vertex optimality does not mean every vertex is optimal.
It means that if an optimum exists, we only need to search among vertices or edges.
Also, if the feasible region is unbounded, the problem may or may not have a finite optimum.
Checklist
You understand vertex optimality if you can:
- identify vertices graphically
- find vertices by solving pairs of boundary equations
- test whether an intersection is feasible
- compute objective values at vertices
- explain why at least one optimum is found at a vertex
- connect vertices to basic feasible solutions
See Also
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.