Mathematics Prelims

June 10, 2009

Extreme Points, Part 1 — Geometric Intuition

Filed under: Linear Programming — cjohnson @ 4:51 pm

Recall from earlier that in a linear program we have a set of constraints, Ax \leq b, each of which defines a half-space.  The intersection of all these half-spaces, along with our standing assumption x \geq 0 defines our feasible region: the region in space where satisfying all of our constraints.  In general, the intersection of a finite number of half-spaces is called a polyhedral set, and if the set is bounded set call it a polytope.

One thing to notice about polyhedral sets is that they’re convex.  To see this, suppose that our polyhedral set is defined by Ax \leq b.  Now let x_0 and x_1 be two points satisfying these constraints (in each of the corresponding half-spaces).  Let \lambda \in [0, 1].  We have the following.

\displaystyle A(\lambda x_0 + (1 - \lambda) x_1) = A (\lambda x_0) + A((1 - \lambda) x_1)

\displaystyle \, \, \, = \lambda A x_0 + (1 - \lambda) A x_1

\displaystyle \, \, \, \leq \lambda b + (1 - \lambda) b

\displaystyle \, \, \, = (\lambda + 1 - \lambda) b

\displaystyle \, \, \, = b

So A(\lambda x_0 + (1 - \lambda) x_1) \leq b and the set is convex.

Now, if we had only a few (two or three) variables, then we could explicitly graph the polyhedral set and we’d notice that it has some sharp “corners” when two lines (or planes) that form the boundary of a half-space intersect.  These points are of interest to us because if an optimal solution exists it must occur at one of these corner points.

As an example, consider the following linear program:

Maximize \displaystyle \frac{1}{2} x_1 + x_2

Subject to the following:

\displaystyle x_2 \leq 3

\displaystyle x_1 + x_2 \leq 5

\displaystyle x_1, x_2 \geq 0

Graphing these we have

Extreme Points

The extreme points for our feasible region are the five corners above, each of which is the intersection of two of the lines determined by our constraints.  Now let’s consider all of the points where our objective function would be equal to 2.  These are the points satisfying the equation \frac{1}{2} x_1 + x_2 = 2 — all such points lie on a line, and in particular are the points on the red line below.

z=2Note that if we were to consider the points where our objective function is 3 (the points lying on the line \frac{1}{2} x_1 + x_2 = 3), we’d have a similar picture, but with our line simply shifted up one unit:

z=3Remember that our goal is to maximize our objective function while satisfying all of the constraints / staying within the feasible region.  Geometrically, then, what we should do is move this line up as far as we can — as our objective increases when we shift the line up — and stay in the feasible region.  Each of these lines is called an objective contour.  Looking at the set of all possible values the objective function could take on we have something similar to the following (I say “something similar” because the picture would just be solid red if we looked at all the contours).

contoursFrom this picture we see that the optimal solution occurs at the top-right extreme point.  Since an extreme point is the intersection of two lines, we can simply calculate the intersection point of those two lines to see to find the precise point where optimality is obtained (these are called binding constraints since they’re satisfied by equality).

Those lines are x_2 = 3 and x_1 + x_2 = 5, so optimality occurs at (x_1, x_2) = (2, 3) and our objective function takes on the value 4.

This geometric argument is nice and intuitive, but falls apart if we have more than three variables (since we’re in at least four dimensional space where such pictures can’t be drawn).  In the next post we’ll see how to characterize the extreme points of the feasible region algebraically.  Later we’ll see how to traverse the extreme points of the feasible region, using that algebraic description, in such a way that we always move to a “closer to optimal” extreme point, until we finally get there (or determine no such optimal point exists).

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: