Extreme Points, Part 1 — Geometric Intuition

Recall from earlier that in a linear program we have a set of constraints, , each of which defines a half-space.  The intersection of all these half-spaces, along with our standing assumption 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 .  Now let and be two points satisfying these constraints (in each of the corresponding half-spaces).  Let .  We have the following.

So 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

Subject to the following:

Graphing these we have

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 — all such points lie on a line, and in particular are the points on the red line below.

Note that if we were to consider the points where our objective function is 3 (the points lying on the line ), we’d have a similar picture, but with our line simply shifted up one unit:

Remember 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).

From 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 and , so optimality occurs at 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).

An Quick Aside on Convexity

I’ve been meaning to write a post on the extreme points of a feasible set for the last few days, and in that post I need to talk about convexity.  Originally I was going to just define convex set and convex combination inside of that post, but decided it might be better for those to be defined in their own post.  It’s been busy at school the last couple of days, but I’m still hoping to get a couple more LP posts written this week.

Intuitively a convex set is one which doesn’t have any “inward bumps.”  In the image below, the region on the left is convex while the region on the right is not.

To say the set doesn’t have any “inward bumps” is rather vague, though.  A more precise notion is to say that for any two points in the set, the line segment connecting those points lies entirely in the set.  We see the region on the left has this property, while the region on the right does not: pick two points in opposite “legs,” and the line segment joining them will not lie completely within the region.  Of course, when we start talking about higher dimensional spaces simply drawing the line segment doesn’t really work.  What we’ll do instead is pick tow points, say and and take a convex combination of these points.  If all such convex combinations lie in the set, the set is convex.

By a convex combination of the points and , we mean the point where .  (Recall that we’re dealing with points inside of a vector space, so by adding two points we’re adding the associated vectors.)  One important thing to note about convex sets is that if is convex, then for any finite collection of points we have that

where

We will show this inductively where our base case, , follows immediately from our definition of convexity.  Now assume for the result holds for .  We will show the result holds for :  Let and with .  We begin by rewriting our sum:

Notice that implies , so the sum of the coefficients in the expression inside parenthesis is one.  Since each of these points is in our convex set , we have a convex combination and thus the sum is in the set — call this point .  Now we have is a convex combination of points inside , and so we have our result.

LP Part 3: The Feasible Region

Suppose we want to consider all of the points in the plane that satisfy the inequality .  What does such a set look like? Well, one way to visualize it is to draw the line and then take everything under or on the line.  This is an example of a half-space: a “line” that cuts the space in two, and then we take everything on one side of that “line.”  I write “line” because in higher dimensions this isn’t actually a line.  In three dimensions, for instance, it’s a plane.  In four dimensions it’s a hyperplane.  We’ll use the word hyperplane to just mean a linear equality regardless of dimension.  Recall that a linear equality is simply an equation of the form ; no exponents, no logs or square roots, just constant multiples added up.  And so a half-space is everything on one side of a hyperplane.

In a linear program we tend to have a few of these linear inequalities  in the form of our constraints.  When we actually write out , we see that each row in corresponds to a particular inequality and so each constraint defines a half-space.  We’re only concerned with points that satisfy all of the constraints, however, and thus want our optimal solution to occur within the intersection of these half-spaces.  This intersection of all the half-spaces defined by our constraints is called the feasible region of the program.

As far as the feasible region is concerned, there are four cases we need to be aware of when it comes time to actually solve a linear program: the feasible region is empty; the feasible region is not empty, but is bounded; the region is not bounded, but the objective function is;  neither the feasible region nor the objection function are bounded.

The first case occurs when our constraints “cancel each other out.”  For instance if we had the constraints and .  The first constraint puts us on one half of a hyperplane, and then the second tries to get us back on the other side.  Since both of these inequalities can’t hold at the same time, there are no points inside our feasible region.  That’s a simple example of an infeasible LP.  Another, slightly more complicated example occurs if our constraints are

Multiplying this out, we have the following.

An Infeasible Region

In the above picture, areas that satisfy an inequality are shaded in blue, and areas satisfying two equalities are in a dark blue (the shading is additive).  Notice that no area is in a blue any darker than the areas satisfying two inequalities; no area satisfies all three inequalities.  Since no point satisfies all three inequalities, our feasible region is empty.

We’ll say the feasible region is bounded if we can place a circle of finite radius around it, encompassing the entire feasible region.  If the feasible region is bounded, then our objective must be bounded.  As we will see later, our objective is minimized or maximized only at “corners” of the feasible region.  Such a corner occurs only when some number of our constraints are satisfied by equality (the particular number depending on the dimension of the problem).  In two dimensions, for instance, corners occur when two lines cross, and we’re only on a line if we satisfy a constraint with equality.  In three dimensions we’d need three planes to intersect.  Since we only concern ourselves with problems which have a finite number of constraints, we only have a finite number of these corners (this number may be huge, though, so just enumerating all possible corners isn’t a reasonable strategy).

If our feasible region is unbounded, however, our objective function may or may not be bounded.  It could be that we can make the objective arbitrarily large by picking numbers that are farther and farther out, but it could also be that picking huge numbers isn’t particularly helpful.  For example, suppose our only restrictions were , so we can pick any pair of points in the first quadrant.  If our goal is to maximize , then we can make this value as big as we want by picking big enough numbers.  If our goal is to minimize , however, then the best we can do is to pick .

For a slightly less trivial example, suppose we want to maximize subject to the constraints , , .  Now our feasible region is an infinite strip, a portion of which is given below.

Despite being able to pick very large numbers, our maximum occurs at the point , .  If we were to increase any our value would drop since we’re subtracting , and we’ve already made as large as we can.  So we have a bounded objective function, even though our feasible region is unbounded.  We will generally refer to a linear program as being bounded if it’s objective function is bounded, and unbounded if it’s objective function is unbounded.  Note that for the LP to be unbounded, the feasible region must be unbounded.  If the LP is bounded, however, the feasible region may be either bounded or unbounded.

In the next post we’ll look at the extreme points of the feasible region, which are the “corners” alluded to earlier, and give an argument for why the maximum/minimum must occur at an extreme point.

Linear Programming, Part II – Slack and Surplus

Recall from last time that a linear program is an optimization problem of the form

Maximize

Subject to and

Where the system of constraints is just a convenient way to write something of the form

Notice that our use of maximization, instead of minimization, is immaterial as any maximization problem can be turned into an equivalent minimization problem and vice versa.  The problem of maximizing is equivalent (has precisely the same solutions) as the problem of minimizing .

Likewise, our use of inequalities instead of is more a matter of taste and convenience than necessity: is the same thing as .  What we would like to do, though, is get rid of those inequalities altogheter.  If we can turn these constraints into a system of equations of the form , then we’ll be able to apply techniques from linear algebra to help us manipulate the LP (linear program).  Later we’ll see how to cleverly use elementary row operations to traverse the set of potential optimal solutions.  But first we have to lose those nasty little inequalities.

So here’s the idea: say we have .  We can turn this into an equation by inserting a non-negative variable, , which equals .  That is, takes up the slack left by , and becomes .  Algebraically, if we set , we have and that’s why we have equality.

If our inequality goes the other way, say , we’ll just subtract off the surplus: set (note that this means ) and so becomes .  So in the system of inequalities above we can get a system of equations by tacking on a slack, or taking out the surplus, for each inequality.  The earlier system then becomes

Where is the slack (surplus) we add (subtract) for the -th constraint.  Now our matrices will of course have to change a little bit to take these new variables into account.  Originally, was an matrix, was a -vector, and was a -vector.  For our system of equations we’ll let and where is the identity matrix; note that doesn’t change.  Note too that we append the identity because we have only slack variables; if some of those had been surplus variables, the corresponding entries we append would be negative.

So by throwing in an extra variable for each inequality constraint we have a system of equations which is amenable to the techniques of linear algebra.  If it were to happen that the resultant matrix was invertible (which requires it to be square — an equal number of equations and unknowns) then we could just multiply by the inverse and find the solution.  This doesn’t work for our general problem though since there will normally be infinitely many possible solutions.  Our goal will be to weed out the best solution from those possibilities.  In the next post we’ll look at this space of possible solutions.

An Introduction to Linear Programming, Part I

In a first semester calculus class you learn how to optimize a differentiable function by looking at what happens where the derivative is zero (and the endpoints if you’re concerned with a closed interval).  The idea being what comes up must come down: if the function goes up and then goes down, a maximum must occur somewhere between (and similarly for a minimization problem), so you look for the precise point that “up” turns to “down.”  What I want to talk about in the next few posts is how to maximize (or minimize) a linear function in the presence of linear constraints.  (Note that as it’s taught in calculus, such optimization problems have no additional constraints.)

That is, we’ll look at functions of the form where and are vectors in .  The is the dot product of these two vectors, and is just a convenient way of writing .  So the are our variables and the are constants normally referred to as cost coefficients.

An example of such a function is the cost of, say, building a house.  Let’s suppose is the amount of lumber used which costs $2 per pound (I have no idea how much lumber costs, so you’ll have to excuse me if that’s a completely ridiculous value); is the amount of brick which we’ll assume is $3 per pound; and let’s say is the amount of roofing we use and it costs $5 per pound.  Here our cost for building the house would be , and so we could just say and .  This function, , we will refer to as our objective function, and our goal will be to make this as small (or large) as possible given certain restrictions (linear constraints).

Now, by a linear constraint we mean that there are limits on the resources we use, and we can express these limits in the same way we expressed the cost.  In our house building example, for instance, we may not be able to use any more than 2000lb of brick, so we’d have a constraint .  Similarly let’s assume we must use less than 1500lb of lumber and 300lb of roofing materials: , and .  If we further assume that our house must weigh at least 2100lb (for whatever reason) then we’d have the constraint .  Just to make things more complicated, let’s assume we have to use at least 50lb of roofing materials: .  (I know this is a goofy example with silly constraints, but it still serves the purpose of showing us what a linear programming problem is.  The last two constraints are there only so we don’t have a trivial solution.)

Now our linear program is simply the following:

Minimize

Subject to the following:

This last constraint simply says that we can’t have a negative amount of brick, lumber, or roof.

So, our problem is that we want to minimize the cost of building a house when we’re faced with certain restrictions on amounts of material we can use.  (Now you should see why the last two constraints are needed to prevent a trivial solution: if you want to minimize the cost and there’s nothing telling you can’t, just use zero brick, zero lumber, and zero roofing!)

It is generally convenient to rewrite this set of constraints as a matrix.  In our particular problem we could set up the matrix

Then if we let , our constraints could be expressed simply as

Where we will adopt the convention that if and are vectors of the same size, means that each component of is less than or equal to the corresponding component of ; for all .  (Notice that in order to write our problem like this we had to multiply the last two inequalities by -1 so that we’d have instead of the we started with.)

This is all linear programming means: maximize (or minimize) the function under the condition that and .  The term linear programming, by the way, is due to George Dantzig who studied such problems while trying to optimize schedules for the US Air Force in the 1940s.  The Air Force referred to their schedules as “programs,” and so such problems came to be known as linear programs.

In the next post we’ll discuss slack and surplus variables which allow us to turn the inequalities above into equalities, which will be necessary for us to solve linear programs algorithmically.