Back to the on-screen lesson ·
Closure under mixtures, why intersections are safe and unions are not, and where an or costs you convexity.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state the definition of a convex set, prove convexity for a set defined by linear inequalities, disprove it with a single counterexample, and recognise the standard convex and non-convex sets on sight. You will also be able to say why an intersection of convex sets is convex however many there are, why a union need not be, and why every or in a specification is a place convexity is about to be lost.
From lesson 3: a linear optimum sits at a corner, and the argument for that leaned on being able to take a small step in any direction from an interior point. From lesson 5: integrality breaks it. Both were leaning on one property, unnamed until now. This lesson names it and makes it the organising idea of the rest of the course.
Convex combination: $(1-\lambda)x + \lambda y$ with $0 \le \lambda \le 1$ — a point of the segment joining $x$ and $y$.
Convex set: one containing every convex combination of every pair of its points.
Half-space: $\{x : a^\top x \le b\}$, the points on one side of a hyperplane. Convex, and the building block of every linear model.
Polyhedron: an intersection of finitely many half-spaces — the feasible region of a linear program.
Extreme point: a point of the set that is not a mixture of two others. The corners.
Intersection: the points in both sets. Convexity survives it.
Union: the points in either set. Convexity does not survive it, which is why or is the expensive word in a specification.
A set $C$ is convex when, for any two of its points $a$ and $b$ and any $\lambda$ with $0 \le \lambda \le 1$,
$$\lambda a + (1 - \lambda) b \in C.$$
In words: the whole segment between any two points of the set stays inside it. The expression $\lambda a + (1 - \lambda) b$ is a convex combination — a mixture of $a$ and $b$ — and it is worth reading as a mixture rather than as algebra, because that is what it means in every application: half of one plan and half of another.
The sets that turn up.
| Set | Convex? | Why |
|---|---|---|
| Half-space $\{x : a^\top x \le b\}$ | yes | the left side is linear, so it is at most $b$ on a mixture |
| Polyhedron $\{x : Ax \le b\}$ | yes | an intersection of half-spaces |
| Ball $\{x : \|x\| \le r\}$ | yes | the norm of a mixture is at most the mixture of norms |
| Integer points | no | the midpoint of two lattice points need not be one |
| A sphere (surface only) | no | the segment passes through the inside |
| A union of two discs | no | a segment from one to the other leaves both |
Intersections are safe, unions are not. If every $C_i$ is convex then $\bigcap_i C_i$ is convex: a mixture that stays in each stays in all. This is why adding constraints never breaks convexity, and why a model with ten thousand linear constraints is as convex as one with two.
Unions are the opposite, and this is the practical heart of it: every or in a specification — either this depot or that one — makes the feasible set a union, breaks convexity, and turns a tractable model into a search.
Another way: picture
Two shapes. In the first, a disc, every segment you can draw between two points stays inside. In the second, a crescent, a segment between the two horns passes through the empty bite. That bite is the whole of non-convexity, and it is what every hard problem in this course has in some form.
Another way: steps
To decide whether a set is convex:
Let $a^\top x_1 \le b$ and $a^\top x_2 \le b$, and let $0 \le \lambda \le 1$. Then
$$a^\top(\lambda x_1 + (1-\lambda)x_2) = \lambda\, a^\top x_1 + (1-\lambda)\, a^\top x_2 \le \lambda b + (1-\lambda) b = b.$$
Two facts did all the work: the left-hand side is linear, so it distributes over the mixture, and the weights are non-negative, so multiplying the inequalities by them preserves their direction. Both conditions matter — with a negative weight the last step reverses, which is exactly why $\lambda$ is confined to $[0,1]$ and why a point outside the segment proves nothing.
That is the entire reason linear programming is easy. Everything in unit 3 that promises a global answer is ultimately claiming this line.
Testing one pair of points. Convexity is a statement about all pairs. Finding one segment that stays inside proves nothing; finding one that leaves proves non-convexity outright. The asymmetry is worth remembering — disproving is cheap, proving needs an argument about arbitrary points.
Confusing a set with its boundary. A disc is convex; the circle around it is not. Models constrained by an equality $g(x) = 0$ live on a surface, and surfaces are almost never convex, which is why equality constraints are treated separately from inequalities in lesson 12.
Thinking more constraints means less convex. Intersection preserves convexity exactly. More linear constraints make the region smaller, never dented.
*Missing the or. It hides in words: either, unless, at most one of, if... then*. Each is a union, and each is a binary variable in disguise.
The word suggests a bulge, and half the convex sets in this course have corners: a triangle is convex, a half-space is convex, and the whole of $\mathbb{R}^n$ is convex. Nor does it mean bounded — an unbounded polyhedron is convex, which is exactly why an unbounded linear program is possible. The only content of the word is the segment test, and it is worth checking your intuition against the two cases that catch people: a set with a dent is not convex even if it is smooth everywhere, and a set with sharp corners is convex as long as it has no dent.
Is $S = \{x \in \mathbb{Z} : 0 \le x \le 4\}$ convex? Take $a = 0$ and $b = 1$, both in $S$.
Two points of the set.
Take $\lambda = \tfrac12$: the mixture is $\tfrac12$, which is not an integer.
One mixture outside.
So $S$ is not convex, and that is a complete proof. No general argument was needed — and note that this is exactly the reason lesson 5's integer programs are hard.
A counterexample is a whole answer.
Let $C_1, \ldots, C_m$ be convex and let $x, y \in \bigcap_i C_i$. Then $x, y \in C_i$ for every $i$.
Unpack what membership of the intersection means.
Fix $\lambda \in [0,1]$. Since each $C_i$ is convex, $\lambda x + (1-\lambda)y \in C_i$ — for every $i$ separately.
Apply convexity once per set.
Being in every $C_i$ is being in the intersection, so the mixture is in $\bigcap_i C_i$. Note that $m$ never appeared: the argument holds for infinitely many sets too, which is how the convexity of some quite exotic sets gets established.
The count never entered the argument.
Try two points: $(1, 1)$ and $(4, 1)$. Wait — is $(4,1)$ in the set? $4 \times 1 = 4 \ge 1$, yes. And $(1,1)$: $1 \ge 1$, yes.
Check membership before testing the segment.
The midpoint is $(2.5, 1)$, and $2.5 \ge 1$, so that mixture stays in. One segment proves nothing, so try harder: $(0.5, 2)$ and $(2, 0.5)$ are both in the set.
Their midpoint is $(1.25, 1.25)$, and $1.25 \times 1.25 = 1.5625 \ge 1$. Still inside — and in fact this set is convex, being the region above a convex curve in the positive quadrant. The moral is the asymmetry: two successful segments were not a proof, and the proof needs lesson 8's machinery.
Match each set construction to its convexity result.
| Always convex | May be non-convex | Convex | |
|---|---|---|---|
| Intersection of convex sets | |||
| Union of two separated convex sets | |||
| A linear half-space $a^T x \le b$ |
Build the proof that the intersection of two convex sets is convex.
This task has no paper form; do it on a device.
In one variable a convex set is an interval. Which $x$ satisfy both $|x - 5| \le 3$ and $x \ge 2$?
This task has no paper form; do it on a device.
Is the half-space $\{x : a^\top x \le b\}$ convex?
A rule says: *either use fewer than $9$ vans, or open the second depot.* Why does this rule make the model hard?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A rule says: *either use fewer than $8$ vans, or open the second depot.* Why does this rule make the model hard?
You can test a set for convexity, prove it for a polyhedron, and name where convexity is lost — unions, integrality, and surfaces. Next: the same idea for functions.
10. Your turn: is $\{(x,y) : xy \ge 1,\ x > 0\}$ convex?, step 3