In the previous section we saw how the feasible region of a linear program is constructed as the intersection of a number of halfplanes, one for each constraint. Using this insight we developed a graphical approach for solving 2D LPs. Together with Fourier-Motzkin elimination as a means for reducing the dimensionality of an LP, this gave us a general method for solving linear programs.
Unfortunately Fourier-Motzkin produces a rather large number of constraints, so it is unsuited for solving problems with many variables.
In this section I will talk more about the properties of the feasible region. With more knowledge about the feasible region, we’ll eventually be able to understand a very popular method for solving linear programs, the Simplex Method.
Let us start by introducing some notation and some terms.
Already in the last part we started writing the variables as a column vector and the constants as a row vector . We did the same with the cost function, writing the weights for each variable as a row vector . This way we could use the dot product instead of writing sums explicitly.
The constraints can be written using a matrix vector product. We write the in a matrix like so
Note that the rows of are simply the vectors .
Now we can write the constraints simply as , where is a column vector of the . Summarizing we get the general form of a linear program:
Note that it really doesn’t matter whether we use or . Just multiplying by switches a constraint around without changing it.
Def A polyhedron is a set in whose members obey a set of linear inequalities If the region is bounded (i.e. it has a finite volume) it can also be called polytope. We say is the dimensionality of the polyhedron.
I already used the word halfspace without giving a formal definition. Let us remedy this.
Def Let , .
With this definition we can say that a polyhedron is an intersection of a bunch of halfspaces.
A corner of a -dimensional polyhedron is, intuitively, a point where edges meet. I will give a bunch of different definitions and them prove them to be equal.
The simplest definition uses a line. A corner of a polyhedron is a point in the polyhedron where we can find a line that touches the polyhedron only at .
Def Let be a polyhedron. A vector is a vertex of P if s.t. for all ; that is, is the minimal point for some cost vector (the unique optimal solution for some LP with the feasible set P). See figure [Fig:vertex]
Corners are interesting for optimization because the converse is also kind of true, at least for bounded polyhedra. For any cost vector , we can find a vertex of the (bounded) polyhedron such that for all points in the polyhedron. There is no strict inequality here because the line defined by might be parallel to one of the edges of the polyhedron. If the polyhedron is not bounded, there are some such that for any point there is a point such that , that is, the optimal value for this cost vector is unbounded. These are of course the cost vectors that define a line that doesn’t leave the polyhedron.
However, we need some more definitions and theorems before we can prove the above statement.
Def An extreme point of a polyhedron P is a vector s.t. is not a convex combination of any two distinct vectors different from .
Convex combinations of two points are all points for which the equation has a solution for in . Geometrically, the points lie on a line between and . You can also take the convex combinations of more than two points. The principle is the same though, you add all the points, scaling each one with a non-negative scaling factor . The combination is convex if the sum to 1.
Example: In 2D we can always select the two adjacent corners of a point on the edge of if and only if is not a corner. Then will be on the line between the two corners.
Def Let be a polyhedron that is defined by some linear inequalities : . We’ll say that the -th constraint is active at a point if we have equality:
The constraints define the edges of polyhedron. If a point is on an edge that constraint is active. Intuitively the point must be a corner if it lies on the intersection of edges.
Def Let be a polyhedron in standard form and let . The vector is a basic solution if at all equality constraints are active and there are active constraints that are linearly independent. See solution in figure [Fig:bsfVSbs] for an example of a basic solution. If a basic solution is also feasible, we call it a basic feasible solution (b.f.s.). See the point in figure [Fig:bsfVSbs] for an example of a basic feasible solution.
A polyhedron with fever than constraints never has a basic solution.
Now we want to prove that the three definitions are all equivalent to each other.
Theorem Let be a polyhedron and . The following statements are equivalent
We show 1.) 2.) 3.) 1.).
is a vertex is an extreme point: Proof by contraposition.
Assume the existence of both different from such that is a linear combination of and , i.e. . Since is a linear combination of two vectors, it’s not an extreme point. We show that it is also not a vertex.
From the definition of vertex we know that some cost vector should exist such that , for all , that is is optimal w.r.t. . Together with the assumption this leads to a contradiction.
extreme point bsf. Proof by contraposition.
Suppose is not a basic feasible solution. Then is either not feasible, or not a basic solution. If it’s not feasible, then it can’t be an extreme point. Hence we can assume and it’s not a basic solution.
Let be a matrix of active constraints at and the matrix of the inactive constraints such that , . Since is not a bfs the matrix doesn’t have full rank and hence its kernel is nonempty. So we can find some vector in the kernel:
With we define two vectors:
Note that . That means that is not an extreme point if , because is a convex combination of the two. Consider
Since the active constraints are still active. For the inactive constraints we have some slack before we leave the polyhedron. If we choose small enough we’re still within. It suffices to choose such that
That is, we make epsilon small enough such that we don’t violate the tightest of the constraints in .
Hence (and analogous ) are still in the polyhedron and is not an extreme point.
bfs vertex: Suppose is a bfs. We construct a cost vector for which is the unique optimal solution.
Let be the matrix of active constraints s.t. . Let be the sum of the rows of . We know the objective value for w.r.t. . It’s .
Because has rank , is the unique solution to . For all that are different from , , hence is the optimal point for the cost vector . Therefore is a vertex.