Ferkans — Interactive Telecom Tutor

Why Convexity Is the Dividing Line

In wireless system design we constantly solve optimization problems — allocating power, designing beamformers, scheduling users. The fundamental question is: can we find the global optimum efficiently?

The answer hinges on convexity. If an optimization problem is convex, every local minimum is a global minimum, and efficient polynomial-time algorithms exist. If not, we generally face NP-hard problems and must settle for heuristics.

This section develops the vocabulary: convex sets, convex functions, and the key tests for verifying convexity.

Definition:
Convex Set

A set $\mathcal{C} \subseteq \mathbb{R}^n$ is convex if for every $\mathbf{x}, \mathbf{y} \in \mathcal{C}$ and every $\theta \in [0, 1]$ ,

$\theta \mathbf{x} + (1 - \theta) \mathbf{y} \in \mathcal{C}.$

In words: the line segment connecting any two points in $\mathcal{C}$ lies entirely within $\mathcal{C}$ .

The empty set $\emptyset$ and singletons $\{\mathbf{x}_0\}$ are convex by convention (the line-segment condition is vacuously satisfied).

Example: Standard Examples of Convex Sets

Verify that each of the following sets is convex:

Hyperplane: $\{\mathbf{x} \in \mathbb{R}^n : \mathbf{a}^T \mathbf{x} = b\}$
Halfspace: $\{\mathbf{x} \in \mathbb{R}^n : \mathbf{a}^T \mathbf{x} \leq b\}$
Euclidean ball: $\mathcal{B}(\mathbf{x}_0, r) = \{\mathbf{x} : \|\mathbf{x} - \mathbf{x}_0\| \leq r\}$
Ellipsoid: $\mathcal{E} = \{\mathbf{x} : (\mathbf{x} - \mathbf{x}_c)^T \mathbf{P}^{-1} (\mathbf{x} - \mathbf{x}_c) \leq 1\}$ where $\mathbf{P} \succ 0$ .

Solution

Hyperplane

Let $\mathbf{x}, \mathbf{y}$ satisfy $\mathbf{a}^T \mathbf{x} = b$ and $\mathbf{a}^T \mathbf{y} = b$ . Then $\mathbf{a}^T (\theta \mathbf{x} + (1-\theta)\mathbf{y}) = \theta b + (1-\theta) b = b$ .

Halfspace

$\mathbf{a}^T (\theta \mathbf{x} + (1-\theta)\mathbf{y}) = \theta \mathbf{a}^T \mathbf{x} + (1-\theta) \mathbf{a}^T \mathbf{y} \leq \theta b + (1-\theta) b = b$ .

Euclidean ball

By the triangle inequality and convexity of the norm: $\|\theta \mathbf{x} + (1-\theta) \mathbf{y} - \mathbf{x}_0\| = \|\theta(\mathbf{x} - \mathbf{x}_0) + (1-\theta)(\mathbf{y} - \mathbf{x}_0)\| \leq \theta \|\mathbf{x} - \mathbf{x}_0\| + (1-\theta) \|\mathbf{y} - \mathbf{x}_0\| \leq \theta r + (1-\theta) r = r$ .

Ellipsoid

The substitution $\mathbf{z} = \mathbf{P}^{-1/2}(\mathbf{x} - \mathbf{x}_c)$ maps the ellipsoid to the unit ball, which is convex. Since an affine pre-image of a convex set is convex, the ellipsoid is convex. $\blacksquare$

Definition:
Convex Cone

A set $\mathcal{K} \subseteq \mathbb{R}^n$ is a cone if $\mathbf{x} \in \mathcal{K} \implies \alpha \mathbf{x} \in \mathcal{K}$ for all $\alpha \geq 0$ .

A convex cone is a set that is both convex and a cone: for any $\mathbf{x}, \mathbf{y} \in \mathcal{K}$ and $\alpha, \beta \geq 0$ ,

$\alpha \mathbf{x} + \beta \mathbf{y} \in \mathcal{K}.$

The positive semidefinite cone $\mathbb{S}^n_+ = \{\mathbf{X} \in \mathbb{S}^n : \mathbf{X} \succeq 0\}$ is a fundamental convex cone in optimization.

The PSD cone $\mathbb{S}^n_+$ is self-dual: its dual cone is itself. This property underlies the elegance of SDP duality.

Theorem: Intersection of Convex Sets Is Convex

If $\{\mathcal{C}_i\}_{i \in I}$ is any (possibly infinite) collection of convex sets, then $\bigcap_{i \in I} \mathcal{C}_i$ is convex.

Each set independently "passes" the line-segment test. The intersection inherits this property because a line segment in the intersection lies in every $\mathcal{C}_i$ .

Proof

Direct verification

Let $\mathbf{x}, \mathbf{y} \in \bigcap_i \mathcal{C}_i$ and $\theta \in [0,1]$ . For each $i$ , both $\mathbf{x}$ and $\mathbf{y}$ belong to $\mathcal{C}_i$ , so by convexity of $\mathcal{C}_i$ the combination $\theta \mathbf{x} + (1-\theta)\mathbf{y} \in \mathcal{C}_i$ . Since this holds for every $i$ , the combination is in $\bigcap_i \mathcal{C}_i$ . $\blacksquare$

Definition:
Polyhedron

A polyhedron is the intersection of finitely many halfspaces and hyperplanes:

$\mathcal{P} = \{\mathbf{x} : \mathbf{A}\mathbf{x} \preceq \mathbf{b},\; \mathbf{C}\mathbf{x} = \mathbf{d}\}$

where $\preceq$ denotes componentwise inequality. A bounded polyhedron is called a polytope.

Every feasible region of a linear program is a polyhedron. In wireless scheduling, the rate region of a broadcast channel is a polyhedron (or its convex hull).

Convex Set Visualization

Explore the intersection of halfplanes in $\mathbb{R}^2$ and verify that the resulting polyhedron is convex. Drag the halfplane parameters to reshape the feasible region.

Parameters

a_1

(constraint 1 slope)1

b_1

(constraint 1 bound)2

a_2

(constraint 2 slope)-1

b_2

(constraint 2 bound)1

Show epigraph of

x_1^2 + x_2^2

Convex vs. Non-Convex Sets — The Line Segment Test

Visualise the defining property of convexity: for a convex set, the line segment between any two points stays inside the set. For a non-convex set, the segment can exit.

Left: an ellipse (convex) — the line segment stays inside. Right: an L-shaped region (non-convex) — the midpoint escapes.

Key Takeaway

A polyhedron $\{\mathbf{x} : \mathbf{A}\mathbf{x} \preceq \mathbf{b}\}$ is always convex because it is the intersection of halfspaces, each of which is convex. This is why linear and quadratic programs have well-structured feasible regions.

Definition:
Convex Function

A function $f : \mathbb{R}^n \to \mathbb{R}$ is convex if its domain $\text{dom}(f)$ is a convex set and for all $\mathbf{x}, \mathbf{y} \in \text{dom}(f)$ and $\theta \in [0, 1]$ ,

$f(\theta \mathbf{x} + (1-\theta)\mathbf{y}) \leq \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}).$

The function is strictly convex if the inequality is strict whenever $\mathbf{x} \neq \mathbf{y}$ and $\theta \in (0,1)$ .

It is concave if $-f$ is convex.

Equivalently, $f$ is convex iff its epigraph $\text{epi}(f) = \{(\mathbf{x}, t) : f(\mathbf{x}) \leq t\}$ is a convex set. This is the "epigraph characterization."

Definition:
Epigraph

The epigraph of $f : \mathbb{R}^n \to \mathbb{R}$ is

$\text{epi}(f) = \{(\mathbf{x}, t) \in \mathbb{R}^{n+1} : \mathbf{x} \in \text{dom}(f),\; f(\mathbf{x}) \leq t\}.$

$f$ is convex if and only if $\text{epi}(f)$ is a convex set. The epigraph is the "region above the graph" of $f$ .

Theorem: First-Order Condition for Convexity

Let $f : \mathbb{R}^n \to \mathbb{R}$ be differentiable. Then $f$ is convex if and only if $\text{dom}(f)$ is convex and

$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y} - \mathbf{x})$

for all $\mathbf{x}, \mathbf{y} \in \text{dom}(f)$ .

The first-order Taylor approximation (the tangent hyperplane) is a global under-estimator of a convex function. This is the key geometric property that makes gradient-based algorithms work: the gradient always points toward the minimizer.

Show Hint

For the forward direction, use the definition with $\theta \to 0$ .

For the converse, apply the inequality twice with roles swapped and combine.

Proof

Forward direction ($\Rightarrow$)

Assume $f$ is convex. Fix $\mathbf{x}, \mathbf{y} \in \text{dom}(f)$ . By convexity: $f(\mathbf{x} + \theta(\mathbf{y} - \mathbf{x})) \leq f(\mathbf{x}) + \theta(f(\mathbf{y}) - f(\mathbf{x}))$ . Rearranging: $\frac{f(\mathbf{x} + \theta(\mathbf{y}-\mathbf{x})) - f(\mathbf{x})}{\theta} \leq f(\mathbf{y}) - f(\mathbf{x})$ . Taking $\theta \to 0^+$ : $\nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x}) \leq f(\mathbf{y}) - f(\mathbf{x})$ .

Converse ($\Leftarrow$)

Assume the first-order condition holds. Let $\mathbf{z} = \theta \mathbf{x} + (1-\theta)\mathbf{y}$ . Applying the condition at $\mathbf{z}$ : $f(\mathbf{x}) \geq f(\mathbf{z}) + \nabla f(\mathbf{z})^T(\mathbf{x}-\mathbf{z})$ and $f(\mathbf{y}) \geq f(\mathbf{z}) + \nabla f(\mathbf{z})^T(\mathbf{y}-\mathbf{z})$ . Multiply by $\theta$ and $(1-\theta)$ respectively and add: $\theta f(\mathbf{x}) + (1-\theta)f(\mathbf{y}) \geq f(\mathbf{z}) + \nabla f(\mathbf{z})^T [\theta(\mathbf{x}-\mathbf{z}) + (1-\theta)(\mathbf{y}-\mathbf{z})]$ . The bracketed term equals $\mathbf{0}$ , proving convexity. $\blacksquare$

Theorem: Second-Order Condition for Convexity

Let $f : \mathbb{R}^n \to \mathbb{R}$ be twice differentiable. Then $f$ is convex if and only if $\text{dom}(f)$ is convex and the Hessian is positive semidefinite everywhere:

$\nabla^2 f(\mathbf{x}) \succeq 0 \quad \forall\, \mathbf{x} \in \text{dom}(f).$

$f$ is strictly convex if $\nabla^2 f(\mathbf{x}) \succ 0$ for all $\mathbf{x}$ (this is sufficient but not necessary for strict convexity).

The Hessian being PSD means the function curves upward in every direction — like a bowl, never a saddle.

Proof

Reduce to one dimension

For any $\mathbf{x} \in \text{dom}(f)$ and direction $\mathbf{v} \in \mathbb{R}^n$ , define $g(t) = f(\mathbf{x} + t\mathbf{v})$ . Then $g''(t) = \mathbf{v}^T \nabla^2 f(\mathbf{x} + t\mathbf{v}) \mathbf{v}$ .

Apply one-dimensional condition

$f$ is convex iff $g$ is convex for every such restriction. A scalar function $g$ is convex iff $g''(t) \geq 0$ for all $t$ . This holds for all $\mathbf{v}$ iff $\nabla^2 f(\mathbf{x}) \succeq 0$ . $\blacksquare$

Example: Verifying Convexity via the Hessian

Show that the following functions are convex:

$f(\mathbf{x}) = \mathbf{x}^T \mathbf{A} \mathbf{x}$ where $\mathbf{A} \succeq 0$
$f(x) = e^{ax}$ for any $a \in \mathbb{R}$
$f(\mathbf{x}) = \log(1 + e^{\mathbf{a}^T \mathbf{x} + b})$ (log-sum-exp building block)

Solution

Quadratic form

$\nabla f = 2\mathbf{A}\mathbf{x}$ and $\nabla^2 f = 2\mathbf{A} \succeq 0$ . Hence $f$ is convex (and strictly convex iff $\mathbf{A} \succ 0$ ).

Exponential

$f'(x) = ae^{ax}$ , $f''(x) = a^2 e^{ax} \geq 0$ for all $x$ .

Softplus / log-logistic

Let $u = \mathbf{a}^T \mathbf{x} + b$ . Then $f(u) = \log(1 + e^u)$ has $f''(u) = \frac{e^u}{(1+e^u)^2} > 0$ . Since $f$ is a convex function of a linear (affine) argument, the composition is convex. $\blacksquare$

Common Mistake: Maximising a Concave Function $\neq$ Minimising a Convex One?

Mistake:

Students sometimes think that maximising a concave function is a fundamentally different problem from minimising a convex function.

Correction:

Maximising $f$ (concave) is identical to minimising $-f$ (convex). The distinction is purely notational. In wireless communications, capacity-maximisation problems (concave objective) are exactly as "easy" as their minimisation reformulations.

Theorem: Operations That Preserve Convexity

The following operations preserve convexity of functions:

Non-negative weighted sum: If $f_1, \ldots, f_k$ are convex and $w_i \geq 0$ , then $\sum_i w_i f_i$ is convex.
Pointwise supremum: If $f_\alpha$ is convex for each $\alpha \in \mathcal{A}$ , then $g(\mathbf{x}) = \sup_\alpha f_\alpha(\mathbf{x})$ is convex.
Composition with affine map: If $f$ is convex, then $g(\mathbf{x}) = f(\mathbf{A}\mathbf{x} + \mathbf{b})$ is convex.
Partial minimisation: If $f(\mathbf{x}, \mathbf{y})$ is convex in $(\mathbf{x}, \mathbf{y})$ , then $g(\mathbf{x}) = \inf_{\mathbf{y}} f(\mathbf{x}, \mathbf{y})$ is convex (provided $g > -\infty$ ).

Rule 2 is especially powerful: a maximum of convex functions is convex. For example, $\|\mathbf{x}\|_\infty = \max_i |x_i|$ is convex as the pointwise max of the convex functions $|x_i|$ .

Proof

Proof of rule 2 (pointwise supremum)

$\text{epi}(g) = \{(\mathbf{x}, t) : f_\alpha(\mathbf{x}) \leq t \;\forall \alpha\} = \bigcap_\alpha \text{epi}(f_\alpha)$ . Each $\text{epi}(f_\alpha)$ is convex (since $f_\alpha$ is convex), and the intersection of convex sets is convex. Hence $\text{epi}(g)$ is convex, so $g$ is convex. $\blacksquare$

Why This Matters: Convexity in Rate Regions

The capacity region of a multiple-access channel (MAC) is a convex polytope. The sum-rate boundary is a concave function of the individual rates. Understanding convexity lets us move freely between "maximise sum rate" and "find the Pareto-optimal rate tuple" — both are convex optimisation problems.

See full treatment in Turbo Codes

Historical Note: A Brief History of Convexity

1896–2004

The study of convex sets goes back to Hermann Minkowski (1896), who used convex bodies in his geometry of numbers. Werner Fenchel developed convex conjugates in the 1940s. The systematic treatment of convex optimisation was pioneered by Rockafellar's Convex Analysis (1970). The field was transformed by Boyd and Vandenberghe's 2004 textbook, which showed that many engineering problems — including wireless resource allocation — are secretly convex.

Quick Check

Which of the following sets is not convex?

$\{(x_1, x_2) : x_1^2 + x_2^2 \leq 1\}$ (unit disk)

$\{(x_1, x_2) : x_1^2 + x_2^2 \geq 1\}$ (exterior of unit disk)

$\{(x_1, x_2) : |x_1| + |x_2| \leq 1\}$ ( $\ell_1$ ball)

$\{\mathbf{X} \in \mathbb{S}^n : \mathbf{X} \succeq 0\}$ (PSD cone)

Correction:

\{(x_1, x_2) : x_1^2 + x_2^2 \geq 1\}

(exterior of unit disk)

Correct. The exterior of a ball is not convex: take two points on opposite sides and their midpoint is the origin, which has $\|\mathbf{x}\| = 0 < 1$ and lies outside the set.

Quick Check

Which function is convex on $\mathbb{R}$ ?

$f(x) = x^3$

$f(x) = -\log x$ on $x > 0$

$f(x) = \sin x$

$f(x) = -x^2$

Correction:

f(x) = -\log x

on

x > 0

$f''(x) = 1/x^2 > 0$ for all $x > 0$ . So $-\log x$ is strictly convex on its domain.

Convex Set

A set $\mathcal{C}$ where the line segment between any two points in $\mathcal{C}$ remains in $\mathcal{C}$ : $\theta \mathbf{x} + (1-\theta)\mathbf{y} \in \mathcal{C}$ for $\theta \in [0,1]$ .

Convex Function

A function $f$ whose epigraph is a convex set, equivalently, $f(\theta \mathbf{x} + (1-\theta)\mathbf{y}) \leq \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y})$ for $\theta \in [0,1]$ .

Related: Convex Set, Epigraph, Hessian

Epigraph

The set of points lying on or above the graph of a function: $\text{epi}(f) = \{(\mathbf{x}, t) : f(\mathbf{x}) \leq t\}$ . $f$ is convex iff its epigraph is a convex set.

Related: Convex Function

Convex Cone

A set that is closed under non-negative linear combinations: $\alpha \mathbf{x} + \beta \mathbf{y} \in \mathcal{K}$ for $\alpha, \beta \geq 0$ . The PSD cone $\mathbb{S}^n_+$ is the most important example in optimisation.

Related: Convex Set, Psd Cone

Convex Sets and Convex Functions

Why Convexity Is the Dividing Line

Definition: Convex Set

Example: Standard Examples of Convex Sets

Hyperplane

Halfspace

Euclidean ball

Ellipsoid

Definition: Convex Cone

Theorem: Intersection of Convex Sets Is Convex

Direct verification

Definition: Polyhedron

Convex Set Visualization

Parameters

Convex vs. Non-Convex Sets — The Line Segment Test

Key Takeaway

Definition: Convex Function

Definition: Epigraph

Theorem: First-Order Condition for Convexity

Forward direction ($\Rightarrow$)

Converse ($\Leftarrow$)

Theorem: Second-Order Condition for Convexity

Reduce to one dimension

Apply one-dimensional condition

Example: Verifying Convexity via the Hessian

Quadratic form

Exponential

Softplus / log-logistic

Common Mistake: Maximising a Concave Function ≠\neq= Minimising a Convex One?

Theorem: Operations That Preserve Convexity

Proof of rule 2 (pointwise supremum)

Why This Matters: Convexity in Rate Regions

Historical Note: A Brief History of Convexity

Quick Check

Quick Check

Convex Set

Convex Function

Epigraph

Convex Cone

Definition:
Convex Set

Definition:
Convex Cone

Definition:
Polyhedron

Definition:
Convex Function

Definition:
Epigraph

Common Mistake: Maximising a Concave Function $\neq$ Minimising a Convex One?