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.

### Like this:

Like Loading...

*Related*

[…] 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 […]

Pingback by Extreme Points, Part 1 — Geometric Intuition « Mathematics Prelims — June 10, 2009 @ 4:51 pm |