Convexity/What is a convex set?

From Wikibooks, open books for an open world
Jump to navigation Jump to search
A convex set; no line can be drawn connecting two points that does not remain completely inside the set

A convex set is a set of points such that, given any two points A, B in that set, the line AB joining them lies entirely within that set.

Intuitively, this means that the set is connected (so that you can pass between any two points without leaving the set) and has no dents in its perimeter. Sections of the perimeter may be straight lines.

Notes[edit | edit source]

  1. It is assumed that the concept of a line joining two points is defined. In a vector space over the reals, it is the set {λA+(1-λ)B}, 0 < λ < 1}. It will be assumed that we are dealing with vector spaces over the reals unless the contrary is stated explicitly.
  2. By convention, the empty set and all sets consisting of a single point are regarded as convex. Since we cannot find two distinct points in such sets, we cannot say that the line joining two such points isn't contained in the set.

Theorem[edit | edit source]

If X is a convex set and x1 ... xk are any points in it, then

where all and

is also in X.

Proof: If , the theorem is true by the definition of a convex set.

Now we proceed by induction. Assume the theorem is true for . If , we can formulate the definition of as a linear combination of two points, one of which is itself a linear combination of the first points and the other is the th point:

where .

By the induction hypothesis, the first point must be in ; therefore, from the definition, .