Carview!

CARVIEW

MOTORHOMES

Select Language

HTTP/2 301 server: nginx date: Tue, 30 Dec 2025 18:22:01 GMT content-type: text/html; charset=UTF-8 location: https://mathprelims.wordpress.com/category/general/ x-hacker: Want root? Visit join.a8c.com/hacker and mention this header. host-header: WordPress.com vary: accept, content-type, cookie x-redirect-by: WordPress x-ac: 3.bom _dca MISS alt-svc: h3=":443"; ma=86400 strict-transport-security: max-age=31536000 server-timing: a8c-cdn, dc;desc=bom, cache;desc=MISS;dur=321.0 HTTP/2 200 server: nginx date: Tue, 30 Dec 2025 18:22:01 GMT content-type: text/html; charset=UTF-8 vary: Accept-Encoding x-hacker: Want root? Visit join.a8c.com/hacker and mention this header. host-header: WordPress.com vary: accept, content-type, cookie content-encoding: gzip x-ac: 1.bom _dca MISS alt-svc: h3=":443"; ma=86400 strict-transport-security: max-age=31536000 server-timing: a8c-cdn, dc;desc=bom, cache;desc=MISS;dur=366.0 General | 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.

Mathematics Prelims

June 9, 2009

An Quick Aside on Convexity

Recent Posts

Categories