Skip to content

Mathematics · Ch 7 — Linear Programming

Convex Sets

7.1.1

Convex Sets

Definition (Convex set). A set of points in a plane is said to be a convex set if the line segment joining any two

points of the set lies entirely within the set. In other words, pick any two points AA and BB from the set — if the set

is convex, every point on the straight segment ABAB must also belong to the set; if even one pair of points has a

connecting segment that leaves the set at some point, the set is NOT convex.

Simple shapes like a full disc, a solid triangle, a rectangle, or a half-plane are all convex sets: no matter which two

points inside them you pick, the straight segment between them never pokes outside the shape's own boundary. A shape with

a "dent," a crescent, or a hole (an annulus) is NOT convex, because it is always possible to find two points inside the

shape whose connecting segment cuts across the missing region and temporarily leaves the set.

Figure 1fig 7.1(a) — a convex set (ellipse): the segment joining interior points A and B lies entirely inside the set.
Fig. 1 — fig 7.1(a) — a convex set (ellipse): the segment joining interior points A and B lies entirely inside the set.

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.1(a) — a convex set (ellipse): the segment joining interior points A and B lies entirel …

Figure 2fig 7.1(b) — a convex set (pentagon): segment AB joining two interior points stays within the polygon.
Fig. 2 — fig 7.1(b) — a convex set (pentagon): segment AB joining two interior points stays within the polygon.

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.1(b) — a convex set (pentagon): segment AB joining two interior points stays wit …

Figure 3fig 7.1(c) — a non-convex set (dart): segment AB leaves the set through the concave notch.
Fig. 3 — fig 7.1(c) — a non-convex set (dart): segment AB leaves the set through the concave notch.

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.1(c) — a non-convex set (dart): segment AB leaves the set through the …

Figure 4fig 7.1(d) — a non-convex set (annulus / ring): segment AB crosses the central hole, leaving the set.
Fig. 4 — fig 7.1(d) — a non-convex set (annulus / ring): segment AB crosses the central hole, leaving the set.

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.1(d) — a non-convex set (annulus / ring): segment AB crosses the central hole, …

Note (i) — convex sets may be bounded. A convex set can be a closed, finite shape that fits entirely inside some large

enough circle — every polygon, disc, or bounded region enclosed by straight or curved boundaries falls in this category,

as long as it also passes the segment test above.

Figure 5fig 7.2(a) — a bounded convex set (trapezium) fitting within a finite region.
Fig. 5 — fig 7.2(a) — a bounded convex set (trapezium) fitting within a finite region.

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.2(a) — a bounded convex set (trapezium) fitting within a fi …

Figure 6fig 7.2(b) — a bounded convex set (hexagon).
Fig. 6 — fig 7.2(b) — a bounded convex set (hexagon).

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.2(b) — a bounded convex set (he …

Note (ii) — convex sets may be unbounded. A convex set need not be finite in extent. A single half-plane (e.g. the

solution of one linear inequation ax+by≤cax+by\le c) is convex and unbounded — it stretches out indefinitely in the directions

parallel to its boundary line, yet the segment joining any two of its points still lies entirely within it, since a

half-plane has no "dent" to escape through. This distinction between bounded and unbounded convex regions becomes

important later in the chapter (section 7.2.3), because a feasible region built only from ≥\ge constraints (with no

matching upper bound) is typically unbounded, and an unbounded feasible region can fail to have a finite maximum even

though it is still perfectly convex.

Figure 7fig 7.3(a) — an unbounded convex set: the half-plane above the line y = x, extending indefinitely.
Fig. 7 — fig 7.3(a) — an unbounded convex set: the half-plane above the line y = x, extending indefinitely.

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.3(a) — an unbounded convex set: the half-plane above the line y = x, extendin …

Figure 8fig 7.3(b) — an unbounded convex set: the region inside the parabola y = x².
Fig. 8 — fig 7.3(b) — an unbounded convex set: the region inside the parabola y = x².

Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.

fig 7.3(b) — an unbounded convex set: the region inside the para …

These convexity ideas are exactly what justifies the Corner-Point Method used throughout the rest of the chapter: because …

Start your 14-day free trial to unlock the full solution →
← Previous · 7.1Q21 — Solve graphically : 2x + y ≥ 5 and x - y ≤ 1Next · 7.1.2 →Graphical representation of linear inequations in two variables