How to Identify Convex Sets 

To determine whether a given set is convex or non-convex, we use several practical identification methods. In practice, you rarely rely on just one method—you combine geometry, algebra, and known results.

---

1. Line Segment Test (Definition Test)

Rule

A set $C$ is convex if for any two points
$x_1, x_2 \in C$ and any $\lambda \in [0,1]$,

$$\lambda x_1 + (1-\lambda)x_2 \in C$$

How to Apply

1. Choose two arbitrary points in the set.

2. Form their convex combination.

3. Check whether the resulting point satisfies the defining condition of the set.

Example (Convex)

$$C = \{x \in \mathbb{R}^2 : x_1 + x_2 \le 1\}$$

Take $x^{(1)}, x^{(2)} \in C$. Then:

$$\lambda x^{(1)} + (1-\lambda)x^{(2)} \Rightarrow x_1 + x_2 \le 1$$

✔ Convex

Example (Non-Convex)

$$C = \{(x,y) : x^2 + y^2 = 1\}$$

Points lie on a circle boundary only.
The line segment between two points lies inside the circle, not on it.
✘ Not convex

---

2. Shape-Based (Geometric) Identification

Rule

• Solid shapes without dents or holes → convex

• Shapes with holes or indentations → non-convex

Examples

Shape	Convex?
Solid disk	✔
Square	✔
Triangle	✔
Donut (ring)	✘
Crescent shape	✘

📌 Quick classroom intuition:
“If you can stretch a rubber band between any two points and it stays inside, the set is convex.”

---

3. Constraint-Based Identification

Rule

A set defined by linear equalities or inequalities is convex.

$$C = \{x : Ax \le b, \; Cx = d\}$$

Examples

Convex

$$\{x : 2x_1 - x_2 \le 3\}$$
$$\{x : x_1 \ge 0,\; x_2 \ge 0\}$$

Non-Convex

$$\{x : x_1 x_2 \ge 1\}$$

(product of variables → usually non-convex)

---

4. Intersection Rule

Rule

If

$$C = C_1 \cap C_2 \cap \cdots \cap C_k$$

and each $C_i$ is convex, then $C$ is convex.

Example

$$C = \{x : x_1 \ge 0\} \cap \{x : x_2 \ge 0\}$$

This is the first quadrant — convex ✔

---

5. Norm-Based Identification

Rule

Sets defined using norms are convex.

$$\{x : \|x\| \le r\}$$

Examples

• $\ell_2$ ball (circle/sphere)

• $\ell_1$ ball (diamond shape)

• $\ell_\infty$ ball (square)

✔ All are convex

---

6. Sublevel Set Test

Rule

If $f(x)$ is a convex function, then the set

$$\{x : f(x) \le \alpha\}$$

is convex.

Example

$$f(x) = x_1^2 + x_2^2 \Rightarrow \{x : x_1^2 + x_2^2 \le 1\}$$

✔ Convex

---

7. Affine Transformation Rule

Rule

If $C$ is convex and

$$T(x) = Ax + b$$

then $T(C)$ is convex.

Example

A rotated or shifted circle remains convex.

---

8. Common Non-Convex Warning Signs

A set is likely non-convex if it involves:

• Products of variables ($xy$)

• Ratios of variables ($x/y$)

• Discrete choices

• Equality constraints on curved boundaries only

Example

$$\{x : x^2 + y^2 = 1\}$$

✘ Non-convex

---

Summary Table

Method	When to Use	Result
Line segment test	Formal proof	Exact
Shape intuition	2D/3D geometry	Fast
Linear constraints	Optimization problems	Convex
Norm sets	Regularization	Convex
Sublevel sets	Function-based	Convex
Product constraints	Warning sign	Usually non-convex

---

Key Message for Students

Always identify convexity before solving an optimization problem.

Convex sets make problems solvable, stable, and predictable.

 Example

Question

Prove that the set

$$C = \{(x_1, x_2) \in \mathbb{R}^2 : 2x_1 + 3x_2 = 7\}$$

is a convex set.

---

Solution

To prove that $C$ is convex, we use the definition of a convex set.

A set $C \subseteq \mathbb{R}^2$ is convex if for any two points
$(x_1^{(1)}, x_2^{(1)}) \in C$ and $(x_1^{(2)}, x_2^{(2)}) \in C$, and for any
$\lambda \in [0,1],$

$$\lambda (x_1^{(1)}, x_2^{(1)}) + (1 - \lambda)(x_1^{(2)}, x_2^{(2)}) \in C.$$

---

Let

$$(x_1^{(1)}, x_2^{(1)}),\ (x_1^{(2)}, x_2^{(2)}) \in C.$$

Then, by definition of $C$,

$$2x_1^{(1)} + 3x_2^{(1)} = 7 \quad \text{and} \quad 2x_1^{(2)} + 3x_2^{(2)} = 7.$$

Consider the convex combination

$$(x_1, x_2) = \lambda (x_1^{(1)}, x_2^{(1)}) + (1 - \lambda)(x_1^{(2)}, x_2^{(2)}), \quad \lambda \in [0,1].$$

That is,

$$x_1 = \lambda x_1^{(1)} + (1 - \lambda)x_1^{(2)}, \quad x_2 = \lambda x_2^{(1)} + (1 - \lambda)x_2^{(2)}.$$

Now,

$$\begin{aligned} 2x_1 + 3x_2 &= 2[\lambda x_1^{(1)} + (1 - \lambda)x_1^{(2)}] + 3[\lambda x_2^{(1)} + (1 - \lambda)x_2^{(2)}] \\ &= \lambda (2x_1^{(1)} + 3x_2^{(1)}) + (1 - \lambda)(2x_1^{(2)} + 3x_2^{(2)}) \\ &= \lambda(7) + (1 - \lambda)(7) \\ &= 7. \end{aligned}$$

Thus, $(x_1,x_2)\in \mathrm{C.}$

---

Conclusion

Since every convex combination of points in $C$ also belongs to $C$,

$$\boxed{C \text{ is a convex set.}}$$