Convex and Non Convex Sets

Convex Sets

Intuitive Idea

A convex set is a collection of points such that the straight line segment connecting any two points in the set lies entirely within the set.

• Think of a solid ball or a solid square: no matter which two points you choose, the line between them never goes outside.

• A non-convex set has dents, holes, or gaps, so a line between two points may pass outside the set.

Visual Intuition

• Convex → no dents or holes

• Non-convex → has indentations or holes

Pic Curtesy: wikipedia

---

Definition (Simple Terms)

The Rule

1. Pick any two points in the set.

2. Draw the straight line segment between them.

3. If the entire line stays inside the set, the set is convex.

If this fails even once, the set is non-convex.

---

Mathematical Definition

A set $C \subseteq \mathbb{R}^n$  is convex if for any two points
$x_1, x_2 \in C$ and for any number $\theta \in [0,1]$,

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

Interpretation

• $\theta \in [0,1]$ controls where the point lies on the line segment:

  • $\theta = 0$ → point $x_2$

  • $\theta = 1$→ point $x_1$

  • $0 < \theta < 1$ → point between $x_1$ and $x_2$

• This expression is called a convex combination.

---

Examples of Convex Sets

1. Simple Geometric Shapes

• Solid circles (disks)

• Squares and rectangles

• Triangles

• Ellipses

• Solid cubes and spheres

2. Lines and Planes

• A single line

• A line segment

• A plane or hyperplane

• A half-space, such as:

  $$\{x : Ax \le b\}$$
  

3. Vector and Norm-Based Sets

• Unit ball:

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

• Any closed ball centered at the origin

📌 Key idea: No holes, no inward dents.

---

Examples of Non-Convex Sets (Concave Sets)

• A crescent-moon (C-shaped) region

• A star-shaped figure

• A donut or ring shape (torus)

• Any shape with:

  • holes

  • indentations

  • disconnected parts

📌 In these cases, you can find two points whose connecting line leaves the set.

---

Convex vs Non-Convex (Summary)

Feature	Convex Set	Non-Convex Set
Line segment stays inside	✔ Always	✘ Sometimes
Has dents or holes	✘ No	✔ Yes
Optimization friendly	✔ Yes	✘ Difficult
Local minimum = global	✔ Yes	✘ No

Important Properties of Convex Sets

Let $C, C_1, C_2 \subseteq \mathbb{R}^n$ be convex sets unless stated otherwise.

---

1. Line Segment Property (Closure under Convex Combinations)

If $x_1, x_2 \in C$, then for any $\theta \in [0,1]$,

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

📌 This is the defining property of convex sets.

---

2. Closure under Finite Convex Combinations

If $x_1, x_2, \dots, x_k \in C$ and
$\theta_i \ge 0$, $\sum_{i=1}^k \theta_i = 1$, then

$$\sum_{i=1}^k \theta_i x_i \in C$$

📌 Any weighted average of points in a convex set remains in the set.

---

3. Intersection of Convex Sets is Convex

If $C_1$ and $C_2$ are convex, then:

$$C_1 \cap C_2 \text{ is convex}$$

📌 Used extensively in constrained optimization where multiple conditions are imposed.

⚠️ Note: The union of convex sets is not necessarily convex.

---

4. Affine Transformation Preserves Convexity

If $C$ is convex and $f(x) = Ax + b$, then:

$$f(C) = \{Ax + b : x \in C\} \text{ is convex}$$

📌 Important in:

• Feature transformations

• Linear mappings in ML

• Coordinate changes

---

5. Translation and Scaling Preserve Convexity

If $C$ is convex and $\alpha \in \mathbb{R}$:

• Translation:

  $$C + a = \{x + a : x \in C\}$$
  

• Scaling:

  $$\alpha C = \{\alpha x : x \in C\}$$
  

Both result in convex sets.

---

6. Convex Hull is the Smallest Convex Set

The convex hull of a set $S$, denoted $\text{conv}(S):$

• Is convex

• Contains $S$
  

• Is the smallest convex set containing $S$
  

📌 Every convex set can be expressed as the convex hull of its points.

---

7. Half-Spaces and Hyperplanes are Convex

• Hyperplane:

  $$\{x : a^T x = b\}$$
  

• Half-space:

  $$\{x : a^T x \le b\}$$
  

Both are convex.

📌 Fundamental building blocks of feasible regions.

---

8. Subsets Defined by Linear Constraints are Convex

Any set of the form:

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

is convex.

📌 These sets define polyhedra, which occur frequently in:

• Linear programming

• SVM constraints

• Feasible regions in ML models

---

9. Sublevel Sets of Convex Functions are Convex

If $f$ is a convex function, then for any $\alpha$:

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

is convex.

📌 This links convex sets and convex functions directly.

---

10. Convex Sets Have No “Holes”

Convex sets are:

• Connected

• Simply shaped (no cavities or indentations)

📌 This geometric simplicity enables efficient optimization algorithms.

---

11. Every Local Minimum in a Convex Set is Global (Optimization Insight)

While this is a property of convex optimization, it relies critically on convex sets:

If a convex function is minimized over a convex set, any local minimum is a global minimum.

---

12. Extreme Points and Boundary Structure

• Extreme points cannot be written as convex combinations of other points.

• Convex sets are completely characterized by their extreme points (especially polytopes).

📌 Important in:

• Linear programming

• Sparse solutions

• LASSO

---

13. Supporting Hyperplane Property

For every boundary point of a closed convex set, there exists a supporting hyperplane that touches the set at that point and lies entirely on one side.

📌 Foundation for:

• Duality theory

• KKT conditions

• SVM theory

---

Summary Table

Property	Key Idea	ML Relevance
Convex combinations	Weighted averages stay inside	Stability
Intersection	Constraints combine safely	Feasible region
Affine invariance	Geometry preserved	Feature maps
Convex hull	Minimal convex enclosure	Classification
Sublevel sets	Loss defines region	Optimization
Supporting hyperplanes	Separation possible	SVM, duality