What is the formal definition of a convex set?
answer
- think about straight lines
- pick any two points of the set
- the whole segment must stay inside
- t*x + (1-t)*y for t in [0,1]
basics
~20 sA set is convex if the straight segment joining any two of its points lies entirely inside it: for every x and y in the set C and every t in [0, 1], the point t*x + (1-t)*y is also in C.
solid answer
~40 sA set `C` is convex when, for all `x, y` in `C` and all `t` in `[0, 1]`, the convex combination `t*x + (1-t)*y` belongs to `C`. Geometrically: pick any two points of the set, draw the segment between them, and the segment never leaves the set. Half-planes such as `{(x, y) : x + y <= 3}`, balls, boxes and the L1 ball `{x : sum |x_i| <= 1}` are convex; a crescent, an annulus like `1 <= x^2 + y^2 <= 4`, and the union of two disjoint disks are not, because you can pick two points whose connecting segment leaves the region. Convexity survives intersection, translation, scaling and affine maps, which is why feasible regions built from linear constraints are automatically convex.
go deeper
Be ready to state the segment condition precisely and to classify simple shapes on sight: disk yes, half-plane yes, annulus no, union of two disks no.
Explain why the condition is stated with a parameter t in [0,1], and show that intersections preserve convexity while unions do not, with the one-line segment argument.
Demonstrate that you build convexity rather than check it: recognise a feasible region as an intersection of half-spaces or norm balls, and know which operations you may apply without re-proving anything.
Own the modelling call — whether to express a constraint set so that it is convex at all, since the choice between a convex relaxation and an exact non-convex description determines what solver guarantees you can promise.
## The definition A set `C` in `R^n` is **convex** if for every pair of points `x, y` in `C` and every scalar `t` in `[0, 1]`, ``` t*x + (1 - t)*y is in C ``` The expression `t*x + (1 - t)*y` is called a **convex combination** of `x` and `y`. As `t` sweeps from `0` to `1`, the point traces the straight segment from `y` to `x`. So the definition says exactly: *the segment between any two points of the set stays inside the set*. Nothing about smoothness, symmetry or roundness is required. The definition extends to more than two points: `C` is convex if and only if every convex combination `t_1*x_1 + ... + t_k*x_k` (with `t_i >= 0` and `sum t_i = 1`) of points of `C` is again in `C`. The two-point version already implies the general one by induction. ## Examples that are convex - A **half-space**: `{x : a . x <= b}` for a fixed vector `a` and scalar `b`. If two points each satisfy the inequality, so does every point between them, because `a . x` is linear in `x`. - Any **ball** in any norm, including the Euclidean ball `{x : ||x||_2 <= 1}` and the **L1 ball** `{x : sum |x_i| <= 1}` (the diamond). Norm balls are convex because norms satisfy the triangle inequality and positive homogeneity. - A **box** `{x : l_i <= x_i <= u_i}`, which is an intersection of half-spaces. - The whole space, a single point, and the empty set (vacuously). ## Examples that are not convex - An **annulus** such as `1 <= x^2 + y^2 <= 4`. Take the points `(-1.5, 0)` and `(1.5, 0)`: both are in the ring, but their midpoint `(0, 0)` is in the hole, so the segment escapes. - A **crescent** or any shape with a dent: the segment across the dent leaves the region. - The **union of two disjoint disks**: a segment from one disk to the other passes through empty space. - A **curve** such as the circle `x^2 + y^2 = 1` on its own (as opposed to the filled disk): the chord between two points of the circle is inside the disk, not on the circle. ## Operations that preserve convexity This is the practical part, because most convex sets you meet are built rather than checked from scratch: - **Intersection** of any number of convex sets is convex. If a segment lies in each set, it lies in all of them at once. This is why a feasible region defined by many linear inequalities is convex. - **Translation** `C + v`, **scaling** `a*C`, and more generally **affine images** `{A*x + b : x in C}` are convex. - **Minkowski sum** `{x + y : x in C, y in D}` of two convex sets is convex. - **Union** is the notable failure: the union of two convex sets is generally not convex. ## The bridge to convex functions Convex sets and convex functions are two views of the same idea. A function `f` is convex exactly when its **epigraph** — the set of points lying on or above its graph, `{(x, t) : t >= f(x)}` — is a convex set in one higher dimension. In the other direction, every **sublevel set** `{x : f(x) <= c}` of a convex function is a convex set. The converse of that last statement is false: `f(x) = sqrt(|x|)` has sublevel sets `[-c^2, c^2]`, which are intervals and therefore convex, yet the function itself is not convex. Functions whose sublevel sets are all convex are called quasiconvex, a strictly weaker property. ## Why interviewers ask Convexity of the feasible region is half of what makes an optimisation problem tractable — the other half is convexity of the objective. Being able to say *why* a region qualifies (it is an intersection of half-spaces, it is a norm ball) rather than pointing at a picture is the difference between recognition and understanding.
- Is the intersection of two convex sets always convex, and what about their union?The intersection always is: if a segment lies inside each set, it lies inside both, hence inside the intersection. The union generally is not — two disjoint disks are each convex, but a segment from one to the other passes through empty space. This asymmetry is why feasible regions built from many constraints (an intersection) stay convex.
- How does the epigraph connect convex sets to convex functions?The epigraph of `f` is the set of points on or above its graph: `{(x, t) : t >= f(x)}`. A function is convex if and only if its epigraph is a convex set in one higher dimension. That equivalence lets you transfer every fact about convex sets to convex functions and back, and it is the standard way the two definitions are unified.
- Are the sublevel sets of a convex function convex, and does the converse hold?Yes for the forward direction: `{x : f(x) <= c}` is convex whenever `f` is convex, since the chord bound keeps intermediate points below `c`. The converse fails. `f(x) = sqrt(|x|)` has sublevel sets `[-c^2, c^2]`, which are convex intervals, yet the function is not convex. Such functions are called quasiconvex.
Think of the set as a room. It is convex if, standing anywhere inside, you can see every other point of the room without a wall blocking the line of sight.
saying these in an interview costs you the question
- Confuses a convex set with a convex function
- Claims the union of convex sets is always convex
- Says an annulus is convex because it is round
- Requires the boundary to be smooth or curved outward
- Checks only endpoints instead of the whole segment