Convex sets

Convexity can be introduced as a fairly intuitive concept that applies to n-dimensional subsets of . Spaces with multiple dimensions will be the subject of next chapter, but we can visualize things on a plane, which is just the set  of points with two coordinates. We use boldface characters when referring to a point , with coordinates (x₁, x₂). Subscripts refer to coordinates; for instance, point y has coordinates (y₁, y₂). Generally speaking, in the next chapter we consider tuples x = (x₁, x₂, … x_n) in , but two-dimensional visualization is what we need to grasp the concepts. Intuitively, a set S is convex if all of the points on the line segment joining two points x and y in it belong to S itself, for any choice of x and y. Figure 2.24 illustrates the idea:

1. Set S₁ is a polyhedron, and is convex.
2. Set S₂ is a standard example of a nonconvex set.
3. The last set S₃ is a bit different, but nonconvex nevertheless. It is a discrete set obtained by considering only points with integer coordinates.²⁴

Here is a formal definition of convexity that applies to subsets of .

DEFINITION 2.16 (Convex sets) A set  is convex if, given any pair of points x and y in S, for any real number λ in the interval [0, 1] we have

For an arbitrary value λ, λx + (1 − λ)y is just a way to describe the line passing through that pair of points (we know from elementary geometry in the plane that there is exactly one such line; this also applies to lines in spaces with multiple dimensions). If we restrict λ to the interval [0, 1], we are just considering the line segment between them. Indeed, if we set λ = 0, we get y; if we set λ = 1, we get x.

Fig. 2.24 Convex and nonconvex sets.

Fig. 2.25 Convex and nonconvex functions.