Mathematics Prelims

June 9, 2009

An Quick Aside on Convexity

Filed under: General,Linear Programming — cjohnson @ 9:19 pm

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.Convex Sets

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 x_0 and x_1 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 x_0 and x_1, we mean the point \lambda x_0 + (1 - \lambda) x_1 where \lambda \in [0, 1].  (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 X is convex, then for any finite collection of points x_1, x_2, ..., x_n \in X we have that

\displaystyle \sum_{i=1}^n \lambda_i x_i \in X

where

\displaystyle \sum_{i=1}^n \lambda_i = 1

\displaystyle \lambda_1, ..., \lambda_n \in [0, 1]

We will show this inductively where our base case, n = 2, follows immediately from our definition of convexity.  Now assume for the result holds for n.  We will show the result holds for n+1:  Let x_1, ..., x_{n+1} \in X and \lambda_1, ..., \lambda_{n+1} \in [0, 1] with \sum_{i=1}^{n+1} \lambda_i = 1.  We begin by rewriting our sum:

\displaystyle \sum_{i=1}^{n+1} \lambda_i x_i = \lambda_1 x_1 + ... + \lambda_n x_n + \lambda_{n+1} x_{n+1}

\displaystyle = \frac{1 - \lambda_{n+1}}{1 - \lambda_{n+1}} \left( \lambda_1 x_1 + ... \lambda_n x_n \right) + \lambda_{n+1} x_{n+1}

\displaystyle = (1 - \lambda_{n+1}) \left( \frac{\lambda_1}{1 - \lambda_{n+1}} x_1 + ... + \frac{\lambda_n}{1 - \lambda_{n+1}} x_n \right) + \lambda_{n+1} x_{n+1}

Notice that \sum_{i=1}^{n+1} \lambda_i = 1 implies \sum_{i=1}^n \lambda_i = 1 - \lambda_{n+1}, so the sum of the coefficients in the expression inside parenthesis is one.  Since each of these x_i points is in our convex set X, we have a convex combination and thus the sum is in the set — call this point \bar{x}.  Now we have (1 - \lambda_{n+1}) \bar{x} + \lambda_{n+1} x_{n+1} is a convex combination of points inside X, and so we have our result.

Advertisements

1 Comment »

  1. […] 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 | Reply


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

Blog at WordPress.com.

%d bloggers like this: